Réunion d'hiver SMC 2018

Vancouver, 7 - 10 décembre 2018

Session en l'honneur de Robert Woodrow à l'occasion de son 70e anniversaire. Sujets : théorie des modèles de structures relationnelles; structures homogènes; ensembles ordonnés; graphiques
Org: Gena Hahn (University of Montreal) et Imed Zaguia (Royal Military College)
[PDF]

ANDRÉS ARANDA, Technische Universität Dresden
Morphism extension classes of graphs  [PDF]

The concept of homomorphism-homogeneity was introduced by Cameron and Ne\v{s}et\v{r}il in 2006 as a variation on ultrahomogeneity: instead of requiring isomorphisms between finite substructures to extend to automorphisms of the ambient structure, they require homomorphisms between finite substructures to extend to endomorphisms. By adjusting the type of initial homomorphism and final endomorphism, one obtains 18 morphism-classes (for example, one can require monomorphisms to extend to bijective endomorphisms).

In this talk, I will present the partial order of morphism-extension classes for graphs and connected graphs, and a surprising result for countably infinite connected HH-homogeneous graphs: if they embed an infinite independent set, then the Rado graph is a spanning subgraph. As a corollary, almost all MB-homogeneous graphs are bimorphism-equivalent to the Rado graph.

Joint work with Thomas Coleman and David Hartman.

ANTHONY BONATO, Ryerson university
The new world of infinite random geometric graphs  [PDF]

The infinite random or Rado graph $R$ has been of interest to graph theorists, probabilists, and logicians for the last half-century. The graph $R$ has many peculiar properties, such as its categoricity: $R$ is the unique countable graph satisfying certain adjacency properties. Erdos and Renyi proved in 1963 that a countably infinite binomial random graph is isomorphic to $R$.

Random graph processes giving unique limits are, however, rare. Recent joint work with Jeannette Janssen proved the existence of a family of random geometric graphs with unique limits. These graphs arise in the normed space $\ell _{\infty }^{n}$, which consists of $\mathbb{R}^{n}$ equipped with the $L_{\infty }$-norm. Balister, Bollobas, Gunderson, Leader, and Walters used tools from functional analysis to show that these unique limit graphs are deeply tied to the $L_{\infty }$-norm. Precisely, a random geometric graph on any normed, finite-dimensional space not isometric $\ell _{\infty}^{n}$ gives non-isomorphic limits with probability $1$.

With Janssen and Anthony Quas, we have discovered unique limits in infinite dimensional settings including sequences spaces and spaces of continuous functions. We survey these newly discovered infinite random geometric graphs and their properties.

PETER CAMERON, University of St Andrews
Synchronization update  [PDF]

Synchronization and separation are permutation group properties lying between primitivity and 2-transitivity; the first comes from the theory of synchronizing automata and the second is closely related. Rather few examples are known of permutation groups which are synchronizing but not separating. Recently, it has been shown that such a group must be almost simple (in the O'Nan--Scott classification). I also report on recent results on some classes of groups, such as symmetric or alternating groups acting on $k$-subsets of the original domain.

PETER GIBSON, York University
The profile of a relation  [PDF]

Local-global results in the theory of relational structures have been a recurring theme in Robert Woodrow’s work. We discuss one such result, analyzing the consequences of the hypothesis that a relational structure has only finitely many isomorphism types of size $\kappa$, for some infinite cardinal $\kappa$.

Hereditarily Semi-Rigid Families of Linear Orders  [PDF]

Let $X$ be a non-empty set and ${\rho}$ be a relation on $X$. A partial map $f: {\rm dom}(f) \to X$ (where ${\rm dom}(f) \subseteq X$) is called a partial endomorphism of $\rho$ if for every $a_1,\dots,a_t \in {\rm dom}(f)$, $(a_1,\dots,a_t) \in \rho \Rightarrow (f(a_1),\dots,f(a_t)) \in \rho.$ A partial endomorphism $f$ of ${\rho}$ is trivial if $f$ is a subfunction of the identity map or a subfunction of a constant map on $X$. A relational structure ${\mathcal R}:=(X,\rho_1,\dots,\rho_m)$ is called hereditarily semi-rigid if its partial endomorphisms are all trivial, i.e., if for every partial function $f$ on $X$, if $f$ is a partial endomorphism of each of $\rho_1$, $\rho_2, \dots,\rho_m$, then $f$ is trivial. In this talk, we present some of our latest results concerning hereditarily semi-rigid families of linear orders on a set $X$. This is joint work with Maurice Pouzet and Imed Zaguia.

JAN HUBIČKA, Charles University
Metrically homogeneous graphs as homogenizations of $(1,\delta)$-structures  [PDF]

We discuss conjectured classification of metrically homogeneous graphs of finite diameter $\delta$ as given by Gregory Cherlin. We focus on properties that can be derived by considering these structures as homogenizations of their reducts containing edges in distance of 1 and $\delta$ only. We show how that all such reducts are originating from metrically homogeneous graphs with primitive automorphism group are described by means of finitely many $(1,\delta)$-cycles and cliques.

JULIA KNIGHT, University of Notre Dame
Coding one structure in another  [PDF]

There are familiar examples in which a structure $\mathcal{A}$ is coded in a structure $\mathcal{B}$. In some of these examples the decoding is effective. Harrison-Trainor, Melnikov, R. Miller, and Montalban defined a notion of effective interpretation. In their definition, the tuples from $\mathcal{B}$ that represent elements of $\mathcal{A}$ do not have a fixed arity, and the formulas that define the interpretation are computable infinitary $\Sigma_1$. Harrison-Trainor et al. showed that there is an effective interpretation of $\mathcal{A}$ in $\mathcal{B}$ iff there are Turing operators $\Phi$ taking copies of $\mathcal{B}$ to copies of $\mathcal{A}$ and $\Psi$ taking isomorphisms between copies of $\mathcal{B}$ to isomorphisms between the corresponding copies of $\mathcal{A}$. We consider several examples, with the goal of testing whether the notion of effective interpretation captures the idea of effective decoding.

THOMAS KUCERA, University of Manitoba
Saturated Free Algebras and Almost Indiscernible Theories  [PDF]

[With Anand Pillay, University of Notre Dame.]

We extend to uncountable languages the studies of the model theory of saturated free algebras in countable languages by [Baldwin, Shelah (1983)], and generalizations by [Pillay, Sklinos (2015)].

A theory $T$ of cardinality $\tau$ is $(\mu,\kappa)$-almost indiscernible ($1\le\mu\le\tau<\kappa$) if $T$ has a saturated model of power $\kappa$ which is the algebraic closure of an indiscernible set of $\mu$-tuples. $T$ is $(\mu,\kappa)$-almost indiscernible iff $T$ is $(\mu,\tau^{+})$-almost indiscernible.

Any such theory $T$ is superstable, stable in all cardinalities $\lambda\ge\tau$, and non-multidimensional. There is a pairwise orthogonal family $\mathcal{R}$ of regular types over $M_{\tau}$, the $\tau$-saturated model of cardinality $\tau$, and a corresponding family $\mathcal{W}$ of types of maximal weight one sets over $M_{\tau}$, such that any $N\succeq M_{\tau}$ is prime over $M_{\tau}$ and an independent family of realizations of types in $\mathcal{R}$, and is the algebraic closure of $M_{\tau}$ and an independent family of realizations of types in $\mathcal{W}$.

In a saturated free algebra in an uncountable language, the type of a basis element is well-defined. We conjecture that for an arbitrary such theory: it is totally transcendental, one-based, with quantifer elimination down to primitive formulas, and with finite Morley rank.

We have sharper results for theories of modules.

BENOIT LAROSE, Champlain College and LACIM, UQAM
Some questions on finite groups motivated by the complexity of QCSP  [PDF]

Let $G$ be a finite group, and consider the following decision problem: given a quantified system of equations such as $$\exists x \forall y \exists z \, x^2y^3=z^4xz \wedge y^2z^5 = x \wedge \cdots,$$ is it valid ? Recent developments in the algebraic theory of the computational complexity of quantified constraint satisfaction problems (QCSP) lead us to study the nature of the surjective operations compatible with the group operation, i.e. the group epimomorphisms of the form $f: {G}^n \rightarrow G$. We show, amongst other results, that if $G$ is a quasi-simple group, then all these operations are essentially unary, whence the associated QCSP is PSPACE-complete.\

(Work in progress with Barnaby Martin, University of Durham, UK)

BOJAN MOHAR, Simon Fraser University
50 years of the Ringel and Youngs Map Colour Theorem  [PDF]

What is the smallest genus of a surface in which the complete graph $K_n$ can be embedded? This question, known as the Heawood problem, was resolved in 1968 by Ringel and Youngs and is henceforth known as the Map Colour Theorem. The methods used in the solution gave birth to topological graph theory.

In the 1990s, Archdeacon and Grable and Rodl and Thomas proved that the genus of random graphs behaves very much like the genus of complete graphs.

The talk will outline recent results (joint work with Yifan Jing) about genus embeddings of dense graphs building on the above-mentioned work. These results, which were originally motivated by algorithmic questions, use contemporary notions of quasi-randomness and graph limits, and lead to interesting new problems in topological graph theory.

MICHAEL PAWLIUK, University of Calgary
Some homogeneous directed graphs are strange  [PDF]

The project of finding Ramsey expansions for all homogeneous directed graphs (completed by Jasinski-Laflamme-Nguyen Van The-Woodrow in 2014) was a key development in making my PhD thesis possible. I will explain recent developments in the understanding of these homogeneous directed graphs.

MAURICE POUZET, Claude-Bernard University and University of Calgary
A topological interpretation of de Jongh -Parikh theorem and applications  [PDF]

An ordered set $P$ is partially well-ordered (pwo) if it contains no infinite descending chain and if all its antichains are finite. A famous result of de Jongh and Parikh (1977) asserts that among the linear extensions of $P$, one has a largest order type, say $\ell(P)= \omega^{\beta_0}\cdot m_0+\cdots +\omega^{\beta_{k-1}} \cdot m_{k-1}$. We give a topological interpretation of the coefficients of $\ell(P)$ in terms of Cantor-Bendixson rank. The set ${\bf Id}(P)$ of ideals (non-empty up-directed initial segments) of $P$, once equipped with the topology induced by topology on the power set $\mathcal P (P)$, being a compact scattered topological space, we define a partition of $P$ into $k$ blocks $P_i$ so that $\beta_i$ is the rank of ${\bf Id}(P_i)$ and $m_i$ the number of elements having that rank. We illustrate our result with the poset $P$ made of words over a finite alphabet $A$.

We compute the ordinal length of the set $\mathbf {I}_{<\omega}(P)$ of finitely generated ideals of a wqo $P$ that is embeddable into $[\omega]^{<\omega}$, the poset of finite subsets of $\omega$. Building on this result, we compute the ordinal length of the set of monomial ideals in $n$ variables. This answers a question of Aschenbrenner and Pong, 2004.

This is a joint work with C.Delhomm\'e (Universit\'e de la R\'eunion) and M.Sobrani (University of Fes, Morocco).

BILL SANDS, University of Calgary
Two open problems from joint work with Robert Woodrow  [PDF]

From papers in finite partially ordered sets, written with Robert Woodrow (and others), we highlight two problems of a numerical nature which are still open after all these years.

NORBERT SAUER, University of Calgary
Partitions of homogenous graphs and other structures  [PDF]

There are several different notions of vertex divisibility of structures. In particular in the case of homogeneous graphs and their ages. Or at least structures with a large automorphism group. Which of those notions imply which of the others? The three most prominent ones are the following:

(1) A structure is indivisible if for every partition of it into two parts there exists an embedding of the structure into one of the parts.

The age of a structure is the class of its finite induced substructures up to isomorphism.

(2) A structure is weakly indivisible if for every partition into two parts, for which the age of one of the parts is not equal to the age of the structure, is embeddable into the other part.

(3) A structure is age indivisible if for every partition into two parts the age of one of the parts is equal to the age of the structure.

PIERRE SIMON, UC Berkeley
Geometric homogeneous structures  [PDF]

Call a homogeneous structure geometric if the number of types over a finite set grows polynomially with the size of the set. By a theorem of Macpherson, this is equivalent to having few orbits on finite unordered sets (more precisely, not bounded below by an exponential of a degree two polynomial). As observed by Cameron and Macpherson, such structures all appear to be tree-like or order-like. Using results on the model theory of NIP structures, one can hope to classify geometric homogeneous structures. In this talk I will present some results initiating such a classification and a conjectural picture of the whole class.

DAVID WEHLAU, Royal Military College
Finite planes, ZZ-topes and Fibonacci Numbers.  [PDF]


It turns out that we may describe these polynomials uniformly in terms of $p$. This description allows us to generalize to any integer value of $p$. Taking $p=1$ we recover a classical family of orthogonal polynomials the Morgan-Voyce polynomials which originally arose in a study of electrical resistance in 1959. The Morgan-Voyce polynomials are known to have many connections with the Fibonacci sequence. Our approach yields a new description of the Morgan-Voyce polynomials in terms of an infinite sequence of binary vectors.

Using certain initial segments of this sequence as the vertices of a polytope, we recover the zigzag order polytopes. These polytopes were considered by Stanley and shown to have strong connections with certain elements of the permutation group and with zigzag (or fence) posets. If time permits we will also illustrate a number of other surprising properties of this sequence of binary vectors.

This is joint work with H.E.A. Campbell (UNB).

GRAHAM WRIGHT AND GEŇA HAHN, CMS / Université de Montréal