Hostname: page-component-6bb9c88b65-xjl2h Total loading time: 0 Render date: 2025-07-24T13:27:03.391Z Has data issue: false hasContentIssue false
  • English
  • Français

Large cuts in hypergraphs via energy

Part of: Graph theory

Published online by Cambridge University Press:  13 May 2025

EERO RÄTY  and
ISTVÁN TOMON
EERO RÄTY
Affiliation:
Umeå University, Linneaus väg 49, 901 87 Umeå, Sweden. e-mails: eero.raty@umu.se, istvan.tomon@umu.se
ISTVÁN TOMON
Affiliation:
Umeå University, Linneaus väg 49, 901 87 Umeå, Sweden. e-mails: eero.raty@umu.se, istvan.tomon@umu.se
Get access Rights & Permissions [Opens in a new window]

Abstract

A simple probabilistic argument shows that every r-uniform hypergraph with m edges contains an r-partite subhypergraph with at least $({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+\Omega(m^{1/2})$, and this is sharp. We prove that if $r\geq 3$, then there is an r-partite subhypergraph with at least $({r!}/{r^r}) m+m^{3/5-o(1)}$ edges. Moreover, if the hypergraph is linear, this can be improved to $({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+\Omega({\mathcal{E}(G)}/{\log m})$, which might be of independent interest.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05C65: Hypergraphs 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

Information

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 179 , Issue 1 , July 2025 , pp. 45 - 61
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of Cambridge Philosophical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

Footnotes

†

ER is supported by a postdoctoral grant from the Osk. Huttunen Foundation.

‡

IT is supported in part by the Swedish Research Council grant VR 2023-03375.

References

Alon, N.. Bipartite subgraphs. Combinatorica 16 (1996), 301–311.CrossRefGoogle Scholar
Alon, N., Krivelevich, M. and Sudakov, B.. MaxCut in H-free graphs. Combin. Probab. Comput. 14 (2005), 629–647.CrossRefGoogle Scholar
Alon, N., Makarychev, K., Makarychev, Y. and Naor, A.. Quadratic forms on graphs. Invent. Math. 163 (3) (2006), 499–522.CrossRefGoogle Scholar
Balla, I., Janzer, O. and Sudakov, B.. On MaxCut and the Lovász theta function. Proc. Amer. Math. Soc. 152 (2024), 1871–1879.Google Scholar
Charikar, M. and Wirth, A.. Maximizing quadratic programs: extending Grothendieck’s Inequality. FOCS (2004), 54–60.Google Scholar
Conlon, D., Fox, J., Kwan, M. and Sudakov, B.. Hypergraph cuts above the average. Israel J. Math. 233 (2019), 67–111.CrossRefGoogle Scholar
Edwards, C. S.. Some extremal properties of bipartite subgraphs. Canad. J. Math. 25 (1973), 475–485.CrossRefGoogle Scholar
Edwards, C. S.. An improved lower bound for the number of edges in a largest bipartite subgraph. Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), (1975), 167–181.Google Scholar
Erdős, P.. Problems and results in graph theory and combinatorial analysis. Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, 1977) (Academic Press, 1979), 153–163.Google Scholar
Erdős, P. and Kleitman, D. J.. On coloring graphs to maximize the proportion of multicoloured k-edges. J. Combin. Theory 5 (1968), 164–169.CrossRefGoogle Scholar
Glock, S., Janzer, O. and Sudakov, B.. New results for MaxCut in H-free graphs. J. London Math. Soc. 108 (2023), 441–481.CrossRefGoogle Scholar
Goemans, M. X. and Williamson, D. P.. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmin. Journal of the ACM 42 (6) (1995), 1115–1145.CrossRefGoogle Scholar
Grothendieck, A.. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. Sao Paulo 8 (1953), 1–79.Google Scholar
Guruswami, V.. Inapproximability results for set splitting and satisfiability problems with no mixed clauses. Algorithmica 38 (2004), 451–469.CrossRefGoogle Scholar
Håstad, J.. Some optimal inapproximability results. Journal of the Association for Computing Machinery 48 (2001), 798–859.CrossRefGoogle Scholar
Oliveira, R. I.. Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges. Preprint, ArXiv:0911.0600 (2009).Google Scholar
Räty, E., Sudakov, B. and Tomon, I.. Positive discrepancy, MaxCut and eigenvalues of graphs. Preprint, Arxiv:2311.02070.Google Scholar
Scott, A. D.. Judicious partitions and related problems. In Surveys in Combinatorics. London Math. Soc. Lecture Note Series, vol. 327, (Cambridge University Press, Cambridge, 2005) pp. 95–117.Google Scholar
Sudakov, B. and Tomon, I.. Matrix discrepancy and the log-rank conjecture. Mathematical Programming (2024), https://doi.org/10.1007/s10107-024-02117-9 CrossRefGoogle Scholar