On extremal problems concerning the traces of sets.

Abstract: Given two non-negative integers n and s, define m(n,s) to be the maximal number such that in every hypergraph H on n vertices and with at most m(n,s) edges there is a vertex x such that |Hx|>|E(H)|-s, where Hx is the link graph of x.

This problem has been posed by Füredi and Pach and by Frankl and Tokushige. While the first results were only for specific small values of s, Frankl determined m(n,2^{d-1}-1) for all d with d|n. Subsequently, the goal became to determine m(n,2^{d-1}-c) for larger c. Frankl and Watanabe determined m(n,2^{d-1}-c) for c=0,1,2. Other general results were not known so far.
Our main result sheds light on what happens further away from powers of two: We prove that m(n,2^{d-1}-c)=n/d(2^d-c) for d>4c and d|n and give an example showing that this equality does not hold for c=d.

Posted on Sep 29, 2020 in Seminario de Grafos, Seminars