This conference focusses on several related interests of John: first order structures which are homogeneous in the sense of Fraïssé (or of more recent generalisations), and also ω-categorical structures in model theory; automorphism groups of such structures, and connections to other fields such as permutation group theory, semigroup theory, Ramsey theory and other aspects of combinatorics, topological dynamics; connections to set theory – related questions in combinatorial set theory, and permutation group methods in set theory.
The meeting is supported by the School of Mathematics at the University of Leeds and by the British Logic Colloquium.
Practical information
Registration
If you wish to attend, please submit
the registration form. Registration is now closed.
Time and Venue
The meeting will take place in the School of Mathematics, University of Leeds, and will start at , and end at .
There will be a conference dinner on Monday September 11
(£34). If you wish to attend the social dinner, please
say so in the registration form, and you will receive the
payment instructions. Unfortunately, we cannot guarantee
any new places for the social dinner. If you wish to attend,
please get in touch with Vincenzo Mantova
<V.L.Mantova@leeds.ac.uk>.
Travel & Accommodation
We have pre-booked a limited number of single rooms at
Hotel Ibis (£52/night
incl. breakfast) for the nights of 10th and 11th
September. If you wish to stay at Ibis, please say so
in the registration form, and you will receive the
payment instructions. Payment is required before 7th
August 2017. The reservation can be modified or cancelled
before 7th August. No refund shall be possible after that
date. The deadline for booking at Ibis through the
School has closed.
For information on how to reach the School of Mathematics, please read the University instructions or see our location on Google Maps.
Note. On Sunday 10th, until 18:00, the City Centre will be partially closed to traffic for the HSBC UK City Ride. Buses will not stop by the University, and the only car access will be via Mount Preston St. The closed roads are marked on this map.
Speakers
- Manfred Droste
(Leipzig) On homogeneous structures
in algebra, computer science and theoretical
physics
In algebra, we investigate particular homogeneous partial orders and the Bergman property and cofinality of their automorphism groups. In computer science, we show that a category-theoretic variant of Fraïssé's theorem can be used to construct universal Scott domains for denotational semantics of programming languages. Finally, we consider causal sets which have been proposed in theoretical physics as a fundamental model for quantum gravity.
- Mirna Dzamonja
(UEA) Some recent forcing
axioms
Recent results in set theory have made us reconsider the idea of forcing axioms, which for a while were considered as a finished subject. We shall discuss results of various authors, including some of our work joint with coworkers.
- David Evans
(Imperial) Sparse
graphs, EPPA and
Amenability
A class of finite structures has the Extension Property for Partial Automorphisms (EPPA) if every structure in the class can be embedded in a larger structure in the class having the property that every partial automorphism of the smaller structure extends to an automorphism of the larger structure. Where the class is the age of a countable homogeneous structure, this property has strong implications for the automorphism group of the structure: it is one of the main ingredients in applying the methods of Hodges, Hodkinson, Lascar and Shelah to prove the small index property and, by an observation of Kechris and Rosendal, it implies amenability.
I will describe some results about EPPA for certain classes of sparse graphs involved in the Hrushovski amalgamation constructions. There are negative results obtained from non-amenability and also positive results obtained from an extension of the Hodkinson - Otto method for proving EPPA. The latter has other applications and should be of independent interest.
This is joint work with Jan Hubička and Jaroslav Nešetřil.
- Thomas Forster
(Cambridge) Randall Holmes' Proof
of the consistency of Quine's
NF screenplay
Holmes' proof is a 40+ page doorstop and the details are (Holmes' word) diabolical. The scale of the work has significantly delayed publication. However the ideas behind the proof are very attractive, and at the apex of the proof is a delicate iterated Fraenkel-Mostowski construction, and it is this last that I would like to talk about, in honour of JKT who was my first teacher in FM methods.
- Andrew Glass
(Cambridge) Recognizing the real
line
If (Ω,≤) is a totally ordered set and Aut(Ω,≤) is transitive and satisfies the same sentences of group theory as Aut(ℝ,≤), the group of automorphisms of the real line (ℝ,≤), then (Ω, ≤) is isomorphc to (ℝ,≤).
- Bob Gray
(UEA) Universal locally finite
maximally homogeneous
semigroups slides
In 1959, P. Hall introduced the locally finite group 𝓤, today known as Hall's universal group. This group is countable, universal, simple, and any two finite isomorphic subgroups are conjugate in 𝓤. It can be explicitly described as a direct limit of finite symmetric groups. It is homogeneous in the model-theoretic sense since it is the Fraïssé limit of the class of all fini te groups. Since its introduction Hall's group has been widely studied. In this talk I will describe joint work with Igor Dolinka (Novi Sad) in which we use a generalisation of Fraïssé's theory to construct a countable, universal, locally finite semigroup 𝓣, that arises as a direct limit of finite full transformation semigroups, and has the highest possible degree of homogeneity. It is unique up to isomorphism among semigroups satisfying these properties. There are analogous results for inverse semigroups, where a maximally homogeneous universal locally finite inverse semigroup 𝓘 is constructed which is a direct limit of finite symmetric inverse semigroups. The semigroups 𝓣 and 𝓘 are the natural counterparts of Hall's universal group for semigroups and inverse semigroups, respectively. While these semigroups are not homogeneous, they still exhibit a great deal of symmetry. I will describe how several well-known homogeneous structures arise within these semigroups, such as the countable generic semilattice, the countable random bipartite graph, and Hall's group itself.
- Dietrich Kuske
(Ilmenau) Locality of counting
logics
We introduce the logic FOCN(ℙ) which extends first-order logic by counting and by numerical predicates from a set ℙ, and which can be viewed as a natural generalisation of various counting logics that have been studied in the literature.
We obtain a locality result showing that every FOCN(ℙ)-formula can be transformed into a formula in Hanf normal form that is equivalent on all finite structures of degree at most d. A formula is in Hanf normal form if it is a Boolean combination of formulas describing the neighbourhood around its tuple of free variables and arithmetic sentences with predicates from ℙ over atomic statements describing the number of realisations of a type with a single centre. The transformation into Hanf normal form can be achieved in time elementary in d and the size of the input formula. From this locality result, we infer the following applications:
- The Hanf-locality rank of first-order formulas of bounded quantifier alternation depth only grows polynomially with the formula size.
- The model checking problem for the fragment FOC(ℙ) of FOCN(ℙ) on structures of bounded degree is fixed-parameter tractable (with elementary parameter dependence).
- The query evaluation problem for fixed queries from FOC(ℙ) over fully dynamic databases of degree at most d can be solved efficiently: there is a dynamic algorithm that can enumerate the tuples in the query result with constant delay, and that allows to compute the size of the query result and to test if a given tuple belongs to the query result within constant time after every database update.
References
- Dietrich Kuske and Nicole Schweikardt. First-order logic with counting. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1–12. IEEE Computer Society, 2017.
- James Mitchell (St
Andrews) Universal sequences for
groups and
semigroups slides
Oré's Theorem from 1951 states that every element of the symmetric group S_{X} on an infinite set X is a commutator. In other words, for any permutation p on an infinite set X, the equation p = a^{-1}b^{-1}ab has a solution in the symmetric group S_{X}. If w is any word over a finite alphabet, which is not a proper power of another word, and p is any permutation of an infinite set X, then Silberger, Droste, Dougherty, Mycielski, and Lyndon showed that p = w has a solution in permutations of X.
A universal sequence for a group or semigroup G is a sequence of words w_{1}, w_{2}, … such that for any sequence g_{1}, g_{2}, … ∈ G the equations w_{i} = g_{i}, i ∈ ℕ can be solved simultaneously in G. Galvin showed that the sequence {a^{-1} (a^{i} ba^{-i}) b^{-1} (a^{i} b^{-1} a^{-i}) ba : i ∈ ℕ} is universal for the symmetric group S_{X} when X is infinite. On the other hand, if G is any countable group, then G has no universal sequences.
In this talk, I will discuss properties of universal sequences for some well-known groups and semigroups.
Joint work with J. Hyde, J. Jonušas and Y. Péresse.
- Jacob
Hilton The Cube Problem for Linear
Orders
In 1958, Sierpinski asked whether there is a linear order that is isomorphic to its cube (ordered lexicographically) but not to its square. This question was resolved in 2016 by Garrett Ervin. We will look at some of the ideas behind this result. As a warm-up exercise, we invite the reader to find a non-dense linear order that is isomorphic to its square.
- Carolyn Barker
(Leeds) Games on partial
orders
We begin with results by Mwesigye and Truss on the equivalence classes of coloured linear orders in Ehrenfeucht-Fraïssé games of length n. One would naturally wish to extend this work to partial orders. Unfortunately we do not have the same nice inductive characterisation as in the linear case, but we are nonetheless able to make some deductions about games on partial orders, including a description of the equivalence classes of partial orders up to 2-equivalence.
- Milette
Tseelon-Riis (Leeds) Automorphism
Groups of the Generalised Shift
Graph
Erdős defined the Shift Graph in 1968, and Avart, Łuczac and Rödl expanded on this definition in 2014. I will prove some new results about a selection of these graphs, and consider their automorphism groups in order to gain a deeper understanding of their properties.
Schedule
On Sunday, the lectures will be held in the MALL on Level 8 at the School of Mathematics.
On Monday and Tuesday, the lectures will be held in EC Stoner SR 9.90. To reach the room from the School of Mathematics, exit the School from Dolce Vita on Level 10, follow the corridor on the left, take staircase 4 to level 9, go right and immediately left and through a door, SR 9.90 is straight ahead at the far end of the corridor.
The coffee breaks will take place in the Reading Room on
Level 9 at the School of Mathematics, outside the Common
Room.
The reception and the social dinner will be in the Woodhouse rooms at the University House.
Sunday MALL | Monday EC Stoner SR 9.90 | Tuesday EC Stoner SR 9.90 | |
---|---|---|---|
09.30 | David Evans | James Mitchell | |
10.00 | |||
10.30 | Coffee break | Coffee break | |
11.00 | Manfred Droste | Thomas Forster | |
11.30 | |||
12.00 | Carolyn Barker | Bob Gray | |
12.30 | Lunch | ||
13.00 | |||
13.30 | Registration | ||
14.00 | Mirna Dzamonja | Jacob Hilton | |
14.30 | |||
15.00 | Coffee break | Coffee break | |
15.30 | Dietrich Kuske | Andrew Glass | |
16.00 | |||
16.30 | Milette Tseelon-Riis | ||
17.00 | |||
… | |||
18.30 | Reception | ||
19.00 | Social dinner | ||
… |