Jung Attila: Shadow of hypergraphs with bounded degree

Description of video

Date: 3/4/21
Speaker :Jung Attila

Keywords

    The shadow of a k-uniform hypergraph H is defined as the (k-1)-uniform hypergraph \sigma(H) whose hyperedges are those (k-1)-element sets which are contained in at least one hyperedge of H. The famous Kruskal-Katona Theorem answers the question of the minimum possible size |\sigma(H)| of the shadow of a k-uniform hypergraph with given size |H|. What can we say about the size of the shadow with the additional constraint that the maximum degree of H is bounded from above with some number d? We study the shadow ratio |\sigma(H)| / |H| among k-uniform hypergraphs with degree bound d. We show that cliques \binom{[n]}{k} are extremal even among hypergraphs with degree bound d = \binom{n-1}{k-1} + \Theta(n^{k-2}) and give a general (but not sharp) lower bound on the shadow ratio for every k and d.

    Downloads