When Joints Meet Extremal Graph Theory: Hypergraph Joints
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909342961238016 |
|---|---|
| author | Chao, Ting-Wei Yu, Hung-Hsun Hans |
| author_facet | Chao, Ting-Wei Yu, Hung-Hsun Hans |
| contents | The Kruskal--Katona theorem determines the maximum number of $d$-cliques in an $n$-edge $(d-1)$-uniform hypergraph. A generalization of the theorem was proposed by Bollobás and Eccles, called the partial shadow problem. The problem asks to determine the maximum number of $r$-sets of vertices that contain at least $d$ edges in an $n$-edge $(d-1)$-uniform hypergraph. In our previous work, we obtained an asymptotically tight upper bound via its connection to the joints problem, a problem in incidence geometry. In a different direction, Friedgut and Kahn generalized the Kruskal--Katona theorem by determining the maximum number of copies of any fixed hypergraph in an $n$-edge hypergraph, up to a multiplicative factor.
In this paper, using the connection to the joints problem again, we generalize our previous work to show an analogous partial shadow phenomenon for any hypergraph, generalizing Friedgut and Kahn's result. The key idea is to encode the graph-theoretic problem with new kinds of joints that we call hypergraph joints. Our main theorem is a generalization of the joints theorem that upper bounds the number of hypergraph joints, which the partial shadow phenomenon immediately follows from. In addition, with an appropriate notion of multiplicities, our theorem also generalizes a generalization of Hölder's inequality considered by Finner. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06498 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | When Joints Meet Extremal Graph Theory: Hypergraph Joints Chao, Ting-Wei Yu, Hung-Hsun Hans Combinatorics Classical Analysis and ODEs 52C35, 05D40, 05D05, 05C35, 26D15 The Kruskal--Katona theorem determines the maximum number of $d$-cliques in an $n$-edge $(d-1)$-uniform hypergraph. A generalization of the theorem was proposed by Bollobás and Eccles, called the partial shadow problem. The problem asks to determine the maximum number of $r$-sets of vertices that contain at least $d$ edges in an $n$-edge $(d-1)$-uniform hypergraph. In our previous work, we obtained an asymptotically tight upper bound via its connection to the joints problem, a problem in incidence geometry. In a different direction, Friedgut and Kahn generalized the Kruskal--Katona theorem by determining the maximum number of copies of any fixed hypergraph in an $n$-edge hypergraph, up to a multiplicative factor. In this paper, using the connection to the joints problem again, we generalize our previous work to show an analogous partial shadow phenomenon for any hypergraph, generalizing Friedgut and Kahn's result. The key idea is to encode the graph-theoretic problem with new kinds of joints that we call hypergraph joints. Our main theorem is a generalization of the joints theorem that upper bounds the number of hypergraph joints, which the partial shadow phenomenon immediately follows from. In addition, with an appropriate notion of multiplicities, our theorem also generalizes a generalization of Hölder's inequality considered by Finner. |
| title | When Joints Meet Extremal Graph Theory: Hypergraph Joints |
| topic | Combinatorics Classical Analysis and ODEs 52C35, 05D40, 05D05, 05C35, 26D15 |
| url | https://arxiv.org/abs/2410.06498 |