An Alon-Boppana--type bound for very dense graphs, with applications to max-cut

Shengtong Zhang

An Alon-Boppana--type bound for very dense graphs, with applications to max-cut

T0 review · 0 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that every n-vertex graph which is ε-far from a disjoint union of cliques has least eigenvalue at most −n^{1/4−ε}, and derives from the same spectral recursion new max-cut surplus bounds down to an absolute exponent…

desk verdict Proves the dense Alon–Boppana conjecture up to n^{-eps} via a clean spectral recursion; the max-cut consequences are real, and the misstatements in the write-up are cosmetic. read the letter →

arxiv 2507.10037 v1 pith:RV47YH7A submitted 2025-07-14 math.CO math.SP

Shengtong Zhang This is my paper · ORCID

classification math.COmath.SP MSC 05C5005C35

keywords spectralgraphtheoryleasteigenvaluemax-cutsurpluscompletemultipartitegraphsdisjointunionofcliquesrecursionH-freeinducedremovallemma

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves a dense analogue of the classical spectral lower bound for sparse graphs: for any ε > 0, every n-vertex graph that differs from each disjoint union of cliques by at least ε $n^{2}$ edge edits has least eigenvalue at most −$n^{{1/4−ε}}$. Restricting to regular graphs and passing to the complement yields a second eigenvalue at least $n^{{1/4−ε}}$ whenever the graph is ε-far from every balanced complete multipartite graph; the exponent 1/4 is optimal, and only a lower-order $n^{{−ε}}$ factor separates the theorem from the full conjecture. The same recursive inequality powers max-cut surplus results: surplus at least $n^{{1.01}}$ for graphs far from unions of cliques, and surplus at least c_H $m^{{0.5001}}$ for H-free graphs, an absolute exponent improvement over the long-standing √m lower bound. A sympathetic reader should care because very dense graphs, where the classical sparse bound is silent, are shown to obey an equally rigid spectral–structural dichotomy.

What carries the argument

The key machinery is the recursive inequality of Lemma 2.1: for a graph on $n$ vertices and threshold $T \ge 4(-\lambda_n)\sqrt{n}$, the cumulative positive-eigenvalue sum $S_T = \sum_{\lambda_i \ge T} \lambda_i$ satisfies $S_T^2 \le 2n S_{T^2/4n}$. It is proved from the identity $A_G = A_G \circ A_G$ (the adjacency matrix equals its entrywise square because its entries are 0 or 1), the spectral decomposition, and a Gaussian test vector on the subspace spanned by entrywise products of high eigenvectors; a flatness property of eigenvectors bounds the error terms. Iterating this recursion through Lemma 4.1 controls the total square mass of eigenvalues below any threshold, and Lemma 2.3 translates that spectral control into the structural alternative: close to a clique-union or a linear least eigenvalue. For the max-cut theorems, the same recursion runs with the SDP value $\mathrm{sp}^*(G)$ in place of $-\lambda_n$, using a clipped Gaussian vector and energy and inertia bounds, plus a logarithmic approximation factor relating $\mathrm{sp}^*(G)$ to the true surplus $\mathrm{sp}(G)$.

What would settle it

Search for an explicit infinite family of regular $n$-vertex graphs that are $\epsilon$-far from every balanced complete multipartite graph yet satisfy $\lambda_2 \le n^{1/4-\delta}$ for some fixed $\delta > 0$ and arbitrarily large $n$. One such family would directly contradict Theorem 1.3; the known equiangular-lines construction is the boundary case where $\lambda_2$ stays at order $n^{1/4}$.

Watch

Extended reading notes

Core claim

On the paper's terms, the central discovery is that the eigenvalue recursion $S_T^2 \le 2n S_{T^2/4n}$ (where $S_T$ is the sum of eigenvalues at least $T$) forces a dichotomy: a graph whose spectral mass below $\gamma n$ is small is either $\epsilon$-close to a disjoint union of cliques or has a least eigenvalue of linear size. Iterating the recursion shows that if $\lambda_n \ge -n^{1/4-\epsilon}$, the small-eigenvalue mass must be tiny, and Theorem 1.3 follows: for all $n \ge n_0(\epsilon)$, being $\epsilon$-far from a disjoint union of cliques implies $\lambda_n \le -n^{1/4-\epsilon}$. For regular graphs, the complement statement gives $\lambda_2 \ge n^{1/4-\epsilon}$ when the graph is $\epsilon$-far from every balanced complete multipartite graph. The same machinery, run with a clipped Gaussian test vector and an SDP approximation of max-cut, proves surplus bounds $\mathrm{sp}(G) \ge n^{1+c}$ with $c=1/100$, and via a density-increment step, $\mathrm{sp}(G) \ge c_H m^{0.5001}$ for $H$-free graphs.

Load-bearing premise

The load-bearing premise is that graphs with few induced cherries (a vertex with two non-adjacent neighbours) are forced to be close to a disjoint union of cliques by a removal-lemma constant that the proof does not make explicit, so every 'for all $n$ sufficiently large' threshold inherits it; for the max-cut theorems, a second premise is that the SDP relaxation stays within a logarithmic factor of the true surplus.

Editorial extensions

If this is right

For regular graphs, the only way to keep the second eigenvalue below $n^{1/4-\epsilon}$ is to be close to a balanced complete multipartite graph.
Any graph $\epsilon$-far from a disjoint union of cliques has max-cut surplus at least $n^{1.01}$, improving the classical $\sqrt{m}$-type bound by a polynomial factor in this very dense regime.
Every $H$-free graph with $m$ edges has max-cut surplus at least $c_H m^{0.5001}$, improving the exponent in the classical bound by an absolute constant.
The spectral recursion is transferable: replacing the least-eigenvalue control by an energy/SDP control yields the same structural dichotomy for surplus problems.
The density-increment result locates a large, very dense induced subgraph whenever a graph has many edges and small surplus, which is exactly the input needed for the $H$-free max-cut application.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the non-explicit constant in the cherry-removal lemma could be made polynomial, the abstract 'for all $n \gg_\epsilon 1$' thresholds would become effective, potentially converting the max-cut bounds into explicit algorithmic guarantees.
The recursion appears to be a general principle for $\{0,1\}$ matrices with controlled entrywise products of high-eigenvalue vectors, suggesting analogous eigenvalue lower bounds for higher-dimensional simplicial complexes or hypergraphs with bounded codegrees.
The surplus exponent $1.01$ is probably not optimal; optimizing the clipping parameters and the SDP bounds could push it toward $5/4$, the natural target suggested by the conjectured regular-graph bound.
The density-increment step may be iterable beyond what the paper proves; if it could be repeated polynomially many times, the $H$-free surplus exponent might climb well beyond $0.5001$ toward $3/4$.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know this is the real thing. Theorem 1.3 gives lambda_n <= -n^{1/4-eps} for any graph eps-far from a disjoint union of cliques, confirming the Raty–Sudakov–Tomon conjecture up to a lower-order factor and matching the optimal exponent. The earlier dense Alon–Boppana results only covered density at most 1/2 and gave exponent 1/3. The max-cut consequences—sp(G) >= n^{1.01} for graphs far from a disjoint union of cliques, and sp(G) >= c_H m^{0.5001} for H-free graphs—are genuine progress on two conjectures and answer questions posed by Glock–Janzer–Sudakov and Balla–Janzer–Sudakov.

What is actually new: the clipped Gaussian test-vector recursion (Lemma 2.1) that avoids the density restriction, the spectral partitioning in Lemma 2.3, and the fast density increment in Lemma 8.2. The contrapositive architecture is sound: Lemma 2.2 solves the recursion, Lemma 2.3 translates spectral mass into structural closeness, and Theorem 1.3 follows without any circular parameter fitting. I checked the key estimates; no step seems to assume the conclusion.

The soft spots are real but mostly in the presentation. Three displayed statements are wrong as written: Theorem 7.1 cites -lambda_n <= n^{1-4c} when Lemma 6.2 gives n^{(2+c)/3} (both are o(n), so the contradiction survives); the assertion in Theorem 1.7's proof that p_{i+1} >= 2p_i always holds is too quick—case 2 of Lemma 8.2 only gives p_{i+1} >= constant * sqrt(p_i), and the termination argument only needs p_i^3 n_i non-decreasing; and in Lemma 6.6 the constant 250 appears to drift after substituting the dim W bound (the stress-test note suggests ~556). All of these are repairable with constants adjusted. The more structural weakness is that the induced graph removal lemma for K_{1,2} makes delta(eps) ineffective, so all size thresholds are non-explicit and astronomical. That is a limitation, not a correctness error. The max-cut applications also inherit a log n factor from the Grothendieck constant, which is fine for the claimed polynomial exponents.

The citation pattern is responsible: the author clearly credits Balla, Raty–Sudakov–Tomon, Ihringer, and the follow-up by Jin–Milojevic–Tomon. The paper is written for spectral graph theorists and extremal combinatorists working on max-cut; it deserves a serious referee. I would send it out, asking for a cleanup of the misquoted inequalities and a careful statement of the thresholds. With that done, accept.

Referee Report

0 major / 6 minor

Summary. The paper proves an Alon--Boppana-type lower bound on the second eigenvalue of very dense regular graphs: for every ε > 0, every regular n-vertex graph that is ε-far from every Turán graph satisfies λ_2 ≥ n^{1/4−ε}. The main theorem is proved in the complementary form (Theorem 1.3): if G is ε-far from a disjoint union of cliques, then λ_n ≤ −n^{1/4−ε}, with no regularity assumption. The proof introduces a recursive inequality for sums of positive eigenvalues (Lemma 2.1), solves it by a general recursion lemma (Lemma 4.1), and converts the resulting spectral mass bound into structural closeness to a union of cliques via spectral partitioning and the induced graph removal lemma (Lemma 2.3). The same machinery is adapted to the surplus sp(G) = mc(G) − m/2, yielding Theorem 1.5 (sp(G) ≥ n^{1.01} for graphs ε-far from a disjoint union of cliques) and Theorem 1.7 (a density-increment theorem implying that K_r-free graphs with m edges have surplus at least c_r m^{0.5001}). The paper also proves that the exponent 1/4 in the spectral bound is optimal, citing de Caen's construction.

Significance. If correct, Theorem 1.3 is a substantial advance: it confirms the Ráty--Sudakov--Tomon conjecture up to the lower-order factor n^{−ε}, and it removes the previous density restriction d ≤ (1/2−ε)n from earlier independent work of Balla, Ráty--Sudakov--Tomon, and Ihringer. The max-cut consequences are also significant, giving the first absolute polynomial improvement over Edwards' bound for H-free graphs and answering questions posed by Glock--Janzer--Sudakov and Balla--Janzer--Sudakov. The proof is largely self-contained and structurally clear: the key recursion in Lemma 2.1 is derived carefully, the general recursion lemma is stated with explicit parameter conditions, and the spectral-to-structural translation is organized into verifiable claims. A notable weakness is that Lemma 5.1 relies on the induced graph removal lemma for K_{1,2}, so the constant δ(ε) is ineffective and all 'n ≫_ε 1' thresholds are non-explicit; this does not affect the validity of the results but should be acknowledged as a limitation.

minor comments (6)

[Section 6, Lemma 6.6] In the display following the substitution of dim W into the inequality, the term coming from (10) acquires an extra factor of n after multiplying through by n: it should read 8n^{5/3+52c/3}/T^2 · S_T^2, not 8n^{2/3+52c/3}/T^2 · S_T^2. With this correction the estimate 8n^{5/3+52c/3}/T^2 ≤ 8n^{64c/3−1/3} is still valid for c = 1/99, and the stated conclusion S_T^2 ≤ 250nS_{T^2/(8n)} continues to hold for sufficiently large n; the displayed computation should be fixed.
[Section 7, proof of Theorem 7.1] The sentence 'we just showed that −λ_n ≤ n^{1−4c}' is not literally what was derived from Lemma 6.2; Lemma 6.2 gives −λ_n ≤ n^{(2+c)/3}. The displayed bound n^{1−4c} is valid a fortiori because (2+c)/3 < 1−4c for c = 1/99, but the wording should be corrected to avoid the appearance of a misquoted bound.
[Section 5, Lemma 2.3, Claim 1] In Case 2 of Claim 1, the estimate 'x^T A_G x ≤ 1 − 2(1−µ) + µ ≤ −1 + 3µ ≤ 0.4' has the wrong final inequality: since µ < 0.1, one has −1 + 3µ < −0.7. The Rayleigh-quotient conclusion λ_n ≤ −min(|V_i|,|V_j|)/10 is unaffected once this sign is corrected, so this is a typographical error in a central proof, but it should be corrected.
[Section 8, proof of Theorem 1.7] The claim 'We can check that p_{i+1} ≥ 2p_i always holds' is false as stated for case 2 of Lemma 8.2 unless p_i ≤ (10^{−10}/2)^2. The intended argument uses the fact that before termination p_i < 10^{−100}, which indeed implies the inequality; the qualifier should be added. Also, 'Gi+1 be the graph G1' should read 'Gi+1 be the graph obtained by applying Lemma 8.2 with G0 = Gi'.
[Section 8, final density calculation] In the lower bound for the edge density of H, the displayed term '1 − c0 + 2·10^{−300}ε^3 n_k^2/c_0^2' should be '1 − 1/c_0 − 2·10^{−300}ε^3 n_k^2/c_0^2'. The following estimate is valid with the stated lower bound c_0 ≥ (1/3)p_k n_k, but the formula as written is incorrect.
[Throughout] There are several small typos that should be cleaned up: 'Rayley quotient' should be 'Rayleigh quotient', 'Recal' should be 'Recall', 'paritition' should be 'partition', and the phrase 'with applications to max-cut' in the title is typeset with an en-dash issue in the header. These do not affect the mathematics.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the spectral recursion and the max-cut consequences are derived from independent lemmas and external results, with no fitted input renamed as a prediction.

full rationale

The central claim, Theorem 1.3, is proved by contraposition through Lemmas 2.1, 2.2, and 2.3. Lemma 2.1 is a general recursive inequality for graphs with {0,1}-adjacency matrices, proved from the spectral decomposition and a Gaussian test vector; its only hypothesis is the threshold condition T >= 4 sqrt(n)(-lambda_n), and it does not assume the target bound. Lemma 2.2 solves this recursion with fixed constants and an explicit threshold H = (epsilon*delta)^(1/epsilon) n, and the final inequality is a direct estimate, not a fit to the conclusion. Lemma 2.3 uses the external induced graph removal lemma for H = K_{1,2} to translate spectral mass into structural closeness to a disjoint union of cliques; this is an independent result, and no step in the present paper feeds Theorem 1.3 back into it. The max-cut results use external SDP facts attributed to Alon-Makarychev-Makarychev-Naor and Raty-Tomon, together with the same recursion; the Grothendieck-constant bound K(G) = O(log n) and the energy bounds are external statements that do not include the theorem being proved. No parameter is fitted to n^{1/4-epsilon} or to n^{1+c}; the constants are hand-chosen convenience values. There are no load-bearing self-citations, since the author's own prior work is not used, and the citations to Raty-Sudakov-Tomon are for the conjectures and related context, not for the derived bounds. The manuscript itself notes non-explicit constants from the removal lemma and contains repairable arithmetic slips in the max-cut section, but these are correctness or effectiveness issues, not circularity. The derivation chain is therefore self-contained with respect to its conclusions.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central results are proved without fitting any constants to a target value. The hand-chosen exponents c=1/99, rho=1/1000, gamma=1/200 and the removal-lemma constant delta(epsilon) are convenience parameters; any sufficiently small positive constants would work in the relevant inequalities. The external theorems used, including the induced removal lemma, the Grothendieck-constant bound for the SDP relaxation, the Raty-Tomon energy bound, and Turan's theorem, are not special cases of the paper's claims.

free parameters (4)

c = 1/99
Chosen by hand in Theorem 1.5 and Lemma 6.6 to make the recursion exponents work; not fitted to data.
rho = 1/1000
Chosen by hand in Theorem 1.7 and Corollary 1.8; any sufficiently small positive constant would do.
gamma = 1/200
Chosen by hand in Lemma 8.2 and Theorem 1.7 to satisfy the density-increment inequalities; not fitted.
delta = (delta_{K1,2}(epsilon)/12)^3
Defined in Lemma 2.3 from the induced removal lemma constant; it is an implicit function of epsilon and not numerically specified.

assumptions (5)

standard math Induced graph removal lemma for H=K_{1,2}
Used in Lemma 5.1 to conclude that few cherries imply epsilon-closeness to a disjoint union of cliques; cited to Alon-Fischer-Krivelevich-Szegedy.
standard math Grothendieck-type bound K(G)=O(log n) for quadratic forms on graphs
Used in Section 6 to pass between the SDP relaxation sp*(G) and the true surplus sp(G); cited to Alon-Makarychev-Makarychev-Naor and Charikar-Wirth.
standard math Raty-Tomon energy bound sp*(G) >= E(G)/4
Lemma 6.1, credited to Raty and Tomon, is used as an input for all surplus bounds.
standard math Turan's theorem
Used in Corollary 1.8 and Theorem 1.7 to convert edge density close to 1 into the presence of a K_r.
standard math Standard spectral facts: orthonormal eigenbasis, trace identities, A_G = A_G composed entrywise with itself
Used throughout Sections 3 and 6 for the eigenvalue recursion and the entrywise product identities.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An Alon-Boppana--type bound for very dense graphs, with applications to max-cut." pith.science (2026). https://pith.science/paper/RV47YH7A

@misc{pith2026250710037,
  author       = {Pith},
  title        = {Pith review of: An Alon-Boppana--type bound for very dense graphs, with applications to max-cut},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RV47YH7A}},
  note         = {Machine review of arXiv:2507.10037}
}

abstract

For any $\epsilon > 0$, we show that if $G$ is a regular graph on $n \gg_\epsilon 1$ vertices that is $\epsilon$-far (differs by at least $\epsilon n^2$ edges) from any Tur\'{a}n graph, then its second eigenvalue $\lambda_2$ satisfies $$\lambda_2 \geq n^{1/4 - \epsilon}.$$ The exponent $1/4$ is optimal. Our result generalizes an analogous bound, independently obtained by Balla, R\"{a}ty -- Sudakov-Tomon, and Ihringer, which only applies to graphs with density at most $\frac{1}{2}$. Up to a lower-order factor, this confirms a conjecture of R\"{a}ty, Sudakov and Tomon. Our spectral approach has interesting applications to max-cut. First, we show that if a graph $G$, on $n \gg_\epsilon 1$ vertices and $m$ edges, is $\epsilon$-far from a disjoint union of cliques, then it has a max-cut of size at least $$\frac{m}{2} + n^{1.01}.$$ Our result improves upon a classical result of Edwards by a non-trivial polynomial factor, making progress towards another conjecture of R\"{a}ty, Sudakov and Tomon. As another application of our method, we show that if a graph $G$ is $H$-free and has $m$ edges, then $G$ has a max-cut of size at least $$\frac{m}{2} + c_H m^{0.5001}$$ where $c_H > 0$ is some constant depending on $H$ only. This result makes progress towards a conjecture of Alon, Bollob\'{a}s, Krivelevich and Sudakov, and answers recent questions by Glock-Janzer-Sudakov and Balla-Janzer-Sudakov.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Beyond the MaxCut problem in $H$-free graphs
math.CO 2025-07 conditional novelty 7.0 of 10

Graphs with m edges and no clique of size near sqrt(m) must have a cut exceeding m/2 by a power of m.

Reference graph

Works this paper leans on

31 extracted references · 29 canonical work pages · cited by 1 Pith paper

[1]

Beyond the classification theorem of Cameron, Goethals, Seidel, and Shult, arXiv:2404.13136, 2024

Hricha Acharya and Zilin Jiang. Beyond the classification theorem of Cameron, Goethals, Seidel, and Shult, arXiv:2404.13136, 2024

work page arXiv 2024
[2]

Maximum cuts and judicious partitions in graphs without short cycles

Noga Alon, B´ ela Bollob´ as, Michael Krivelevich, and Benny Sudakov. Maximum cuts and judicious partitions in graphs without short cycles. J. Combin. Theory Ser. B, 88(2):329–346, 2003

work page 2003
[3]

Quasi-randomness and algorithmic regularity for graphs with general degree distributions

Noga Alon, Amin Coja-Oghlan, Hiˆ ep H` an, Mihyun Kang, Vojtˇ ech R¨ odl, and Mathias Schacht. Quasi-randomness and algorithmic regularity for graphs with general degree distributions. SIAM J. Comput., 39(6):2336–2362, 2010

work page 2010
[4]

Efficient testing of large graphs

Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Efficient testing of large graphs. Combinatorica, 20(4):451–476, 2000

work page 2000
[5]

Quadratic forms on graphs

Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. Quadratic forms on graphs. Invent. Math., 163(3):499–522, 2006

work page 2006
[6]

Equiangular lines via matrix projection, arXiv:2110.15842, 2024

Igor Balla. Equiangular lines via matrix projection, arXiv:2110.15842, 2024

work page arXiv 2024
[7]

Factorization norms and an inverse theorem for maxcut, arXiv:2506.23989, 2025

Igor Balla, Lianna Hambardzumyan, and Istv´ an Tomon. Factorization norms and an inverse theorem for maxcut, arXiv:2506.23989, 2025

arXiv 2025
[8]

On MaxCut and the Lov´ asz theta function

Igor Balla, Oliver Janzer, and Benny Sudakov. On MaxCut and the Lov´ asz theta function. Proc. Amer. Math. Soc., 152(5):1871–1879, 2024

work page 2024

Show all 31 references

[9]

Note on the second eigenvalue of regular graphs,arXiv:2311.07629, 2023

Igor Balla, Eero R¨ aty, Benny Sudakov, and Istv´ an Tomon. Note on the second eigenvalue of regular graphs,arXiv:2311.07629, 2023

2023 arXiv
[10]

A. E. Brouwer, A. M. Cohen, and A. Neumaier. Distance-regular graphs, volume 18 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1989

1989
[11]

Lower bounds for max-cut in H-free graphs via semidefinite programming

Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, and Luca Trevisan. Lower bounds for max-cut in H-free graphs via semidefinite programming. SIAM J. Discrete Math., 35(3):1557–1568, 2021

2021
[12]

Maximizing quadratic programs: extending Grothendieck’s inequality

Moses Charikar and Anthony Wirth. Maximizing quadratic programs: extending Grothendieck’s inequality. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 54–60, 2004

2004
[13]

Quasirandom Cayley graphs

David Conlon and Yufei Zhao. Quasirandom Cayley graphs. Discrete Anal., pages Paper No. 6, 14, 2017

2017
[14]

Graphs with least eigenvalue−2: ten years on

Dragoˇ s Cvetkovi´ c, Peter Rowlinson, and Slobodan Simi´ c. Graphs with least eigenvalue−2: ten years on. Linear Algebra Appl., 484:504–539, 2015

2015
[15]

D. de Caen. Large equiangular sets of lines in Euclidean space. Electron. J. Combin., 7:Research Paper 55, 3, 2000

2000
[16]

C. S. Edwards. Some extremal properties of bipartite subgraphs. Canadian J. Math., 25:475–485, 1973

1973
[17]

C. S. Edwards. An improved lower bound for the number of edges in a largest bipartite subgraph. In Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), pages 167–181. Academia, Prague, 1975

1974
[18]

New results for MaxCut in H-free graphs

Stefan Glock, Oliver Janzer, and Benny Sudakov. New results for MaxCut in H-free graphs. J. Lond. Math. Soc. (2), 108(2):441–481, 2023

2023
[19]

The energy of a graph: Old and new results

Ivan Gutman. The energy of a graph: Old and new results. In Anton Betten, Axel Kohnert, Reinhard Laue, and Alfred Wassermann, editors, Algebraic Combinatorics and Applications, pages 196–211, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg

2001
[20]

Approximately strongly regular graphs

Ferdinand Ihringer. Approximately strongly regular graphs. Discrete Math., 346(3):Paper No. 113299, 16, 2023

2023
[21]

Beyond the maxcut problem in H-free graphs.Personal Communication

Zhihan Jin, Aleksa Milojevi´ c, and Istv´ an Tomon. Beyond the maxcut problem in H-free graphs.Personal Communication
[22]

Koolen, and Jae Young Yang

Hyun Kwang Kim, Jack H. Koolen, and Jae Young Yang. A structure theory for graphs with fixed smallest eigenvalue. Linear Algebra Appl., 504:1–13, 2016

2016
[23]

An improved bound for strongly regular graphs with smallest eigenvalue −m, arXiv:2506.04964, 2025

Jack Koolen, Chenhui Lv, Greg Markowsky, and Jongyook Park. An improved bound for strongly regular graphs with smallest eigenvalue −m, arXiv:2506.04964, 2025

2025
[24]

Koolen, Meng-Yue Cao, and Qianqian Yang

Jack H. Koolen, Meng-Yue Cao, and Qianqian Yang. Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey. Graphs Combin., 37(4):1139–1178, 2021

2021
[25]

Neumaier

A. Neumaier. Strongly regular graphs with smallest eigenvalue −m. Arch. Math. (Basel), 33(4):392–400, 1979/80. 28 SHENGTONG ZHANG

1979
[26]

Induced subgraph density

Tung Nguyen, Alex Scott, and Paul Seymour. Induced subgraph density. VI. bounded VC-dimension, arXiv:2312.15572, 2024

2024 arXiv
[27]

A. Nilli. On the second eigenvalue of a graph. Discrete Math., 91(2):207–210, 1991

1991
[28]

Large cuts in hypergraphs via energy.Mathematical Proceedings of the Cambridge Philosophical Society, page 1–17, May 2025

Eero R¨ aty and Istv´ an Tomon. Large cuts in hypergraphs via energy.Mathematical Proceedings of the Cambridge Philosophical Society, page 1–17, May 2025

2025
[29]

Positive discrepancy, maxcut, and eigenvalues of graphs,arXiv:2311.02070, 2023

Eero R¨ aty, Benny Sudakov, and Istv´ an Tomon. Positive discrepancy, maxcut, and eigenvalues of graphs,arXiv:2311.02070, 2023

2023 arXiv
[30]

Matrix discrepancy and the log-rank conjecture

Benny Sudakov and Istv´ an Tomon. Matrix discrepancy and the log-rank conjecture. Math. Program., 212:567–579, 2025

2025
[31]

Graph partitioning: an updated survey

Shufei Wu and Jianfeng Hou. Graph partitioning: an updated survey. AKCE Int. J. Graphs Comb., 20(1):9–19, 2023. Department of Mathematics, Stanford University, USA. Email address: stzh1555@stanford.edu

2023

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

Beyond the classification theorem of Cameron, Goethals, Seidel, and Shult, arXiv:2404.13136, 2024

Hricha Acharya and Zilin Jiang. Beyond the classification theorem of Cameron, Goethals, Seidel, and Shult, arXiv:2404.13136, 2024

work page arXiv 2024

[2] [2]

Maximum cuts and judicious partitions in graphs without short cycles

Noga Alon, B´ ela Bollob´ as, Michael Krivelevich, and Benny Sudakov. Maximum cuts and judicious partitions in graphs without short cycles. J. Combin. Theory Ser. B, 88(2):329–346, 2003

work page 2003

[3] [3]

Quasi-randomness and algorithmic regularity for graphs with general degree distributions

Noga Alon, Amin Coja-Oghlan, Hiˆ ep H` an, Mihyun Kang, Vojtˇ ech R¨ odl, and Mathias Schacht. Quasi-randomness and algorithmic regularity for graphs with general degree distributions. SIAM J. Comput., 39(6):2336–2362, 2010

work page 2010

[4] [4]

Efficient testing of large graphs

Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Efficient testing of large graphs. Combinatorica, 20(4):451–476, 2000

work page 2000

[5] [5]

Quadratic forms on graphs

Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. Quadratic forms on graphs. Invent. Math., 163(3):499–522, 2006

work page 2006

[6] [6]

Equiangular lines via matrix projection, arXiv:2110.15842, 2024

Igor Balla. Equiangular lines via matrix projection, arXiv:2110.15842, 2024

work page arXiv 2024

[7] [7]

Factorization norms and an inverse theorem for maxcut, arXiv:2506.23989, 2025

Igor Balla, Lianna Hambardzumyan, and Istv´ an Tomon. Factorization norms and an inverse theorem for maxcut, arXiv:2506.23989, 2025

arXiv 2025

[8] [8]

On MaxCut and the Lov´ asz theta function

Igor Balla, Oliver Janzer, and Benny Sudakov. On MaxCut and the Lov´ asz theta function. Proc. Amer. Math. Soc., 152(5):1871–1879, 2024

work page 2024