Loading Events

« All Events

  • This event has passed.

Kevin Hendrey, Covering radius in the Hamming permutation space

Tuesday, March 24, 2020 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)


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.


Tuesday, March 24, 2020
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B232
IBS (기초과학연구원)


Sang-il Oum (엄상일)
View Organizer Website
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: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.