Large Cuts in Hypergraphs via Energy
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913897165881344 |
|---|---|
| author | Räty, Eero Tomon, István |
| author_facet | Räty, Eero Tomon, István |
| contents | A simple probabilistic argument shows that every $r$-uniform hypergraph with $m$ edges contains an $r$-partite subhypergraph with at least $\frac{r!}{r^r}m$ edges. The celebrated result of Edwards states that in the case of graphs, that is $r=2$, the resulting bound $m/2$ can be improved to $m/2+Ω(m^{1/2})$, and this is sharp. We prove that if $r\geq 3$, then there is an $r$-partite subhypergraph with at least $\frac{r!}{r^r} m+m^{3/5-o(1)}$ edges. Moreover, if the hypergraph is linear, this can be improved to $\frac{r!}{r^r} m+m^{3/4-o(1)},$ which is tight up to the $o(1)$ term. These improve results of Conlon, Fox, Kwan, and Sudakov. Our proof is based on a combination of probabilistic, combinatorial, and linear algebraic techniques, and semidefinite programming.
A key part of our argument is relating the energy $\mathcal{E}(G)$ of a graph $G$ (i.e. the sum of absolute values of eigenvalues of the adjacency matrix) to its maximum cut. We prove that every $m$ edge multigraph $G$ has a cut of size at least $m/2+Ω(\frac{\mathcal{E}(G)}{\log m})$, which might be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_01682 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Large Cuts in Hypergraphs via Energy Räty, Eero Tomon, István Combinatorics A simple probabilistic argument shows that every $r$-uniform hypergraph with $m$ edges contains an $r$-partite subhypergraph with at least $\frac{r!}{r^r}m$ edges. The celebrated result of Edwards states that in the case of graphs, that is $r=2$, the resulting bound $m/2$ can be improved to $m/2+Ω(m^{1/2})$, and this is sharp. We prove that if $r\geq 3$, then there is an $r$-partite subhypergraph with at least $\frac{r!}{r^r} m+m^{3/5-o(1)}$ edges. Moreover, if the hypergraph is linear, this can be improved to $\frac{r!}{r^r} m+m^{3/4-o(1)},$ which is tight up to the $o(1)$ term. These improve results of Conlon, Fox, Kwan, and Sudakov. Our proof is based on a combination of probabilistic, combinatorial, and linear algebraic techniques, and semidefinite programming. A key part of our argument is relating the energy $\mathcal{E}(G)$ of a graph $G$ (i.e. the sum of absolute values of eigenvalues of the adjacency matrix) to its maximum cut. We prove that every $m$ edge multigraph $G$ has a cut of size at least $m/2+Ω(\frac{\mathcal{E}(G)}{\log m})$, which might be of independent interest. |
| title | Large Cuts in Hypergraphs via Energy |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.01682 |