William Raynaud

Quantile Technologies / Queen Mary, University of London Quantile Technologies / Queen Mary, University of London

Families of sets that are pairwise close

Combinatorics Seminar

17th November 2020, 10:00 am – 11:00 am
Virtual (online) Zoom seminar; a link will be sent to the Bristol Combinatorics Seminar mailing list, the week before the seminar.

For positive integers n and d, we say that subsets A,B \subset [n] are `d-close' if the minimum cyclic distance between some element a in A and some element b in B is at most d. We say a set system F is `d-close' if every pair of sets in F are d-close, and we a say a pair of set systems F, G are `cross-d-close' if for every pair of sets A in F and B in G, A and B are d-close. We investigate the maximum possible sizes of such set systems. In particular, for each non-negative integer k, we investigate the maximum possible size of k-uniform d-close set systems (i.e., d-close set systems that contain only k-element subsets of [n]). This is a natural extension of the well-known Erdos-Ko-Rado theorem, which corresponds to the case d=0. We prove tight, stable bounds for k at most a constant fraction of n (depending on d). To do so, we employ the junta method, introduced to extremal combinatorics by Dinur and Friedgut, and significantly extended by Keller and Lifshitz. Joint work with David Ellis (Bristol).

Comments are closed.