2021. 03. 04. 12:15 - 2021. 03. 04. 13:45
Online, Zoom webinar
-
-
Esemény típusa: szeminárium
Szervezés: Intézeti
-
Extremális halmazrendszerek szeminárium

Leírás

Abstract

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.

The zoom link:
https://zoom.us/j/91399666052?pwd=VCtmb0U0RVI5ckE4eXNHQkV0c1l0QT09