Nerovnosti pro stopy hypergrafů a souborů permutací
| Thesis title in Czech: | Nerovnosti pro stopy hypergrafů a souborů permutací |
|---|---|
| Thesis title in English: | Trace inequalities for hypergraphs and families of permutations |
| English key words: | shatter function|trace inequality|hypergraphs|permutations |
| Academic year of topic announcement: | 2024/2025 |
| Thesis type: | diploma thesis |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | prof. RNDr. Martin Tancer, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 22.05.2025 |
| Date of assignment: | 23.05.2025 |
| Confirmed by Study dept. on: | 23.05.2025 |
| Advisors: | prof. Xavier Goaoc |
| Guidelines |
| 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. |
| References |
| 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. |