CanaDAM 2021
En ligne, 25 - 28 mai 2021

Combinatorics on Posets - Part I
Org: Tom Trotter (Georgia Institute of Technology)

BARTŁOMIEJ BOSEK, Jagellonian University
Dilworth's Theorem for Borel Posets  [PDF]

A famous theorem of Dilworth asserts that any finite poset of width $k$ can be decomposed into $k$ chains. We study the following problem: given a Borel poset $P$ of finite width $k$, is it true that it can be decomposed into $k$ Borel chains? We give a positive answer in a special case of Borel posets embeddable into the real line. We also prove a dual theorem for posets whose comparability graphs are locally countable. This is joint work with Jarosław Grytczuk and Zbigniew Lonc.

PATRICE OSSONA DE MENDEZ, CNRS, École des Hautes Études en Sciences Sociales
Small, sparse and ordered  [PDF]

An ordered graph is a simple graph with a linear order on the vertices. Ordered graphs have been particularly studied in extremal graph theory and in Ramsey theory. We show how the presence of a linear order allows to link, for a hereditary class of binary structures, the notions of "structural sparsity" (through the notion of twin-width), the notion of smallness, the model theoretic notion of dependence, and the parametrized complexity of first-order model checking.

JAROSŁAW GRYTCZUK, Technical University of Warsaw
Variations on twins in permutations  [PDF]

Let $\pi$ be a permutation of the set $[n]=\{1,2,\dots, n\}$. Two disjoint order-isomorphic subsequences of $\pi$ are called \emph{twins}. How long twins are contained in every permutation? The well-known Erd\H {o}s-Szekeres theorem implies that there is always a pair of twins of length $\Omega(\sqrt{n})$. On the other hand, by a simple probabilistic argument, Gawron proved that for every $n\geqslant 1$ there exist permutations with all twins having length $O(n^{2/3})$. He conjectured that the latter bound is the correct size of the longest twins guaranteed in every permutation. We present what is known and what is not known on this problem.

GWENAËL JORET, Université Libre de Bruxelles
The extension dimension and the linear extension polytope of a poset  [PDF]

The extension dimension of a poset P is the maximum dimension of a poset extending P. This talk focuses on posets with extension dimension 2. Our main result is a polyhedral characterization of these posets: They are exactly the posets P such that the linear extension polytope of P is equal to a natural relaxation of the polytope, consisting of the linear inequalities encoding the axioms for linear extensions. We also characterize these posets by a list of 78 forbidden induced subposets, and their comparability graphs by 2 forbidden subgraphs.

Joint work with Jean-Paul Doignon, Samuel Fiorini, and Selim Rexhep.

PIOTR MICEK, Jagellonian University
Excluding a ladder  [PDF]

A $k$-ladder is a $2 \times k$ grid graph. Which graph classes $\mathcal{C}$ exclude some ladder as a minor? We show that this is the case if and only if all graphs $G$ in $\mathcal{C}$ admit a proper vertex coloring with a bounded number of colors such that for every $2$-connected subgraph $H$ of $G$, there is a color that appears exactly once in $H$. Our structural results have applications to poset dimension: Posets whose cover graphs exclude a fixed ladder as a minor have bounded dimension.

Joint work with Tony Huynh, Gwenaël Joret, Michał Seweryn, Paul Wollan.