Kevin Hendrey, Covering radius in the Hamming permutation space

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)\geqslant 3n/4$. This talk is based on joint work with Ian M. Wanless.

Kevin Hendrey, The minimum connectivity forcing forest minors in large graphs

Given a graph $G$, we define $\textrm{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 $\textrm{ex}_c(G)$ is known to be tied to the vertex cover number $\tau(G)$, and in fact $\tau(G)\leq \textrm{ex}_c(G)\leq \frac{31}{2}(\tau(G)+1)$. We give the precise value of $\textrm{ex}_c(G)$ when $G$ is a forest. In particular we find that $\textrm{ex}_c(G)\leq \tau(G)+2$ in this setting, which is tight for infinitely many forests.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail:, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.