Traces of hypergraphs
Noga Alon, Guy Moshkovitz, Noam Solomon · Journal of the London Mathematical Society · 2019
Let Tr ( n , m , k ) denote the largest number of distinct projections onto k coordinates guaranteed in any family of m binary vectors of length n. The classical Sauer–Perles–Shelah Lemma implies that Tr ( n , n r , k ) = 2 k for k ⩽ r . Although determining Tr ( n , m , k ) precisely for general k and m seems hopeless, estimating it remains a widely open problem with connections to important questions in computer science and combinatorics. For example, an influential result of Kahn–Kalai–Linial gives non-trivial bounds on Tr ( n , m , k ) for k = Θ ( n ) and m = Θ ( 2 n ) . Here, we prove that, for r , α − 1 ⩽ n o ( 1 ) , it holds that Tr ( n , n r , α n ) = n μ ( 1 + o ( 1 ) ) with μ = r + 1 − log ( 1 + α ) 2 − log ( 1 + α ) . Thus, we (essentially) determine Tr ( n , m , k ) for k = Θ ( n ) and all m up to 2 n o ( 1 ) . For the proof, we establish a ‘sparse’ version of another classical result, the Kruskal–Katona Theorem, which gives a stronger guarantee when the hypergraph does not induce dense sub-hypergraphs. Furthermore, we prove that the parameters in our sparse Kruskal–Katona theorem are essentially best possible. Finally, we mention two simple applications which may be of independent interest.