Tag: KevinHendrey

Our problem can be described in terms of a two player game, played with the set ${\mathcal{S}}_n$ of permutations on $\{1,2,\dots ,n\}$. First, Player 1 selects a subset $S$ of ${\mathcal{S}}_n$ and shows it to Player 2. Next, Player 2 selects a permutation $p$ from ${\mathcal{S}}_n$ as different as possible from the permutations in $S$, and shows it to Player 1. Finally, Player 1 selects a permutation $q$ from $S$, and they compare $p$ and $q$. The aim of Player 1 is to ensure that $p$ and $q$ differ in few positions, while keeping the size of $S$ small. The function $f(n,s)$ can be defined as the minimum size of a set $S\subseteq {\mathcal{S}}_n$ that Player 1 can select in order to gaurantee that $p$ and $q$ will differ in at most $s$ positions.

I will present some recent results on the function $f(n,s)$. We are particularly interested in determining the value $f(n,2)$, which would resolve a conjecture of Kézdy and Snevily that implies several famous conjectures for Latin squares. Here we improve the best known lower bound, showing that $f(n,2)⩾3n/4$. This talk is based on joint work with Ian M. Wanless.

Given a graph $G$, we define ${\text{ex}}_c(G)$ to be the minimum value of $t$ for which there exists a constant $N(t,G)$ such that every $t$-connected graph with at least $N(t,G)$ vertices contains $G$ as a minor. The value of ${\text{ex}}_c(G)$ is known to be tied to the vertex cover number $\tau (G)$, and in fact $\tau (G)\le {\text{ex}}_c(G)\le \frac{31}{2}(\tau (G)+1)$. We give the precise value of ${\text{ex}}_c(G)$ when $G$ is a forest. In particular we find that ${\text{ex}}_c(G)\le \tau (G)+2$ in this setting, which is tight for infinitely many forests.