Nerovnosti pro stopy hypergrafů a souborů permutací
| Název práce v češtině: | Nerovnosti pro stopy hypergrafů a souborů permutací |
|---|---|
| Název v anglickém jazyce: | Trace inequalities for hypergraphs and families of permutations |
| Klíčová slova anglicky: | shatter function|trace inequality|hypergraphs|permutations |
| Akademický rok vypsání: | 2024/2025 |
| Typ práce: | diplomová práce |
| Jazyk práce: | |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | prof. RNDr. Martin Tancer, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 22.05.2025 |
| Datum zadání: | 23.05.2025 |
| Datum potvrzení stud. oddělením: | 23.05.2025 |
| Konzultanti: | prof. Xavier Goaoc |
| Zásady pro vypracování |
| A standard tool in combinatorial and computational geometry is the shatter function f of a (geometric) set system F. Roughly speaking f(m) is defined as the maximum number of possible intersections of a subset of the ground set (of the set system) of size m with sets in F. The asymptotic growth rate of a shatter function is often its most important feature.
The diploma thesis will investigate how the growth rate of a shatter function can be controlled by fixing one of its values. For example, a classical lemma of Sauer, Vapnik and Chervonenkis, and Shelah asserts that for any fixed integer m, if f(m) is at most 2^m − 1 then f(n) = O(n^(m−1)). Shatter functions can also be defined for other combinatorial structures, for instance for permutations, lattices, sumsets, ... The investigation will start with a litterature review with two goals in mind: - Understand the various proofs of Sauer’s lemma, for instance via linear algebra or via compression. - Clarify the smallest parameters m and k for which the known trace inequalities for hypergraphs are not tight, updating a table in (Cheong et al. 2013). The work can then continue in the direction of sharpening some of the open cases or extending some of the proof techniques to other combinatorial structures. |
| Seznam odborné literatury |
| Noga Alon, Guy Moshkovitz, and Noam Solomon. Traces of hypergraphs. Journal of the London Mathematical Society, 100(2):498–517, 2019.
Otfried Cheong, Xavier Goaoc, and Cyril Nicaud. Set systems and families of permutations with small traces. European Journal of Combinatorics, 34(2):229–239, 2013. Z. Füredi and J Pach. Traces of finite sets: Extremal problems and geometric applications. Extremal problems for finite sets (Visegrád, 1991), 251–282. Bolyai Soc. Math. Stud, 3. |