Questions and Conjectures

Some questions and conjectures I've worked on, or that are adjacent to things I've worked on, are below with a few comments. If you want to discuss any of them, feel free to contact me.

Let $M$ be a countable relational structure. Then the number of structures bi-embeddable with $M$ is either $1$, $\aleph_0$, or $2^{\aleph_0}$.

Conjectured by Thomassé. Partial results appear in Counting siblings in universal theories . Even making a reasonable conjecture about what the dividing lines should be seems non-trivial. One possibility is that $M$ is in the $2^{\aleph_0}$-case iff it encodes a linear order in the $2^{\aleph_0}$-case (classified in Equimorphy -- The case of chains ), or an equivalence relation with infinitely many infinite classes in some suitably loose sense.

Let $\mathcal{A}$ be the age of a structure in a finite relational language. Then the number of countable structures with age $\mathcal{A}$, up to bi-embeddability, is either $1$, $\aleph_0$, $\aleph_1$, or $2^{\aleph_0}$.

Conjectured by Pouzet-Sauer-Thomassé. They also conjectured (for a finite relational language) that it is 1 iff $\mathcal{A}$ is the age of a cellular structure. The conjecture appears with some discussion in the last section Siblings of an $\aleph_0$-categorical relational structure . The techniques of Counting siblings in universal theories , i.e. proving cellularity results via mutual algebraicity, seem promising, but more ideas are needed.

Let $\mathcal A$ be the age a countable relational structure with profile (i.e. unlabeled growth rate/speed) bounded above by a polynomial. Then the growth rate of $\mathcal A$ is realized by a cellular structure.

For hereditary graph classes, the polynomial ages are realized by cellular structures, as shown in The unlabelled speed of a hereditary graph property. This fails in general, but the growth rate may still be realized by a cellular structure.

Do we understand all primitive 3-constrained strong amalgamation classes in a finite binary symmetric language?

Do generic semigroup-valued metric spaces with Henson constraints account for all primitive 3-constrained strong amalgamation classes in a finite binary language? See Conjecture 1 of Semigroup-valued metric spaces.

Can the classification of homogeneous structures be automated?

The last section of Lachlan's 1986 ICM talk contains concrete formal conjectures, including that every amalgamation class is the intersection of a chain of finitely constrained amalgamation classes.
Also, what steps of the classification process can be computer-assisted, in a more practical sense? Matěj Konečný has written a program for the binary symmetric case.

Is the joint embedding property decidable for finitely-constrainted permutation classes?

A question of Ruškuc. The corresponding question is undecidable for graph classes and classes in a language of 3 linear orders, but the 2-dimensionality of permutation classes makes makes it difficult to encode the arguments there. In fact, since proper permutation classes are monadically NIP, they cannot definably encode an infinite grid, which blocks the argument used for 3 linear orders.