CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Matroids and ordered sets
Président: Jorn van der Pol (University of Waterloo)

JOHN GOLDWASSER, West Virginia University
Polychromatic colorings in the integers and the integers mod n  [PDF]

Given a finite subset S of the integers, we say a coloring of the integers with r colors is S-polychromatic if every translate of S gets all r colors. The polychromatic number of S is the largest r for which there is an S-polychromatic coloring. We show that the polychromatic number of any set of size 4 is at least 3. A corollary is that the codensity of S in the integers is at most 1/3, confirming a conjecture of Newman. We also consider polychromatic colorings of the integers mod n, where the problem has a different flavor. We solve it for all sets of size 3 and some of size 4.

RICHARD LANG, University of Waterloo
Upper density of monochromatic infinite paths  [PDF]

We prove that in every $2$-colouring of the edges of $K_\mathbb{N}$ there exists a monochromatic infinite path $P$ such that $V(P)$ has upper density at least $(12+\sqrt{8})/17 \approx 0.87226$ and further show that this is best possible. This settles a problem of Erdős and Galvin.

Joint work with Jan Corsten, Louis DeBiasio and Ander Lamaison.

SEAN MCGUINNESS, Thompson Rivers University
Serial Exchanges of Elements in a Matroid  [PDF]

In this talk, we examine a conjecture of Kotlar and Ziv who conjectured that if $B_1$ and $B_2$ are disjoint bases in a matroid $M$, then for any subset $X\subseteq B_1$ there is a subset $Y \subseteq B_2$ and orderings $x_1 \prec x_2 \prec \cdots \prec x_k$ and $y_1 \prec y_2 \prec \cdots \prec y_k$ of $X$ and $Y$ respectively such that $(B_1\backslash \{ x_1, \dots ,x_i \}) \cup \{ y_1, \dots ,y_i \}$ and $(B_2\backslash \{ y_1, \dots ,y_i \}) \cup \{ x_1, \dots ,x_i \}$ are bases for $i = 1, \dots ,k.$ We shall discuss old and new results relating to this problem.

TAMÁS MÉSZÁROS, Freie Universität Berlin
Boolean dimension and tree-width  [PDF]

The dimension is a key measure of complexity of partially ordered sets. Small dimension allows succinct encoding. Indeed if $P$ has dimension $d$, then to know whether $x \leq y$ in $P$ it is enough to check whether $x \leq y$ in each of the $d$ linear extensions of a witnessing realizer. Focusing on the encoding aspect Nešetřil and Pudlák defined a more expressive version of dimension. A poset $P$ has Boolean dimension at most $d$ if it is possible to decide whether $x \leq y$ in $P$ by looking at the relative position of $x$ and $y$ in only $d$ permutations of the elements of $P$. We prove that posets with cover graphs of bounded tree-width have bounded Boolean dimension. This stays in contrast with the fact that there are posets with cover graphs of tree-width three and arbitrarily large dimension.