Bisection width, max-cut and internal partitions of 5-regular graphs

Endre Cs\'oka; Levente Szemer\'edi; Panna T\'imea Fekete; Zolt\'an L\'or\'ant Nagy

REVIEW 4 major objections 5 minor 39 references

Bisection width, max-cut and internal partitions of 5-regular graphs

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read Random 5-regular graphs can be bisected with fewer than 0.496488n crossing edges almost surely, which also gives them an internal partition.

desk verdict Genuinely new algorithmic idea and a clean internal-partition application, but the headline numerical bound is not rigorously established because Table 1 is uncertified floating-point output. read the letter →

arxiv 2509.08531 v1 pith:FEKNWIHG submitted 2025-09-10 math.CO

Endre Csóka , Panna Tímea Fekete , Zoltán Lóránt Nagy , Levente Szemerédi This is my paper · ORCID

classification math.CO MSC 05C8005C70

keywords bisectionwidthmax-cutrandomregulargraphsinternalpartitionslocalalgorithmsfactorofIIDrecoloringinfinitetree

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

Random 5-regular graphs can be split into two nearly equal halves with fewer than 0.496488n crossing edges, asymptotically almost surely. The paper obtains this with a new factor of IID process — a local random rule applied identically at every vertex — that runs the earlier greedy bisection algorithm in bulk rounds and then recolors a set of 'miscolored' vertices to repair bad local decisions. The cut density is computed numerically on the infinite 5-regular tree and then transferred to finite random graphs through their locally tree-like structure. Because the improved value lies strictly below n/2, the same construction proves that asymptotically almost every 5-regular graph has an internal partition, and it also yields a max cut larger than 2.003n.

What carries the argument

The carrying object is a Markov chain for the color distribution on the rooted two-neighborhood of the infinite 5-regular tree. At each of about 1/ε steps the algorithm selects a dominant vertex type, the highest-priority type whose uncolored measure is at least ε, and uses threshold probabilities to color vertices of that type; the transition table for the second neighborhood gives the exact law after each step. The recoloring phase then builds a balanced bipartite graph from vertices whose final color disagrees with their terminal neighborhood, and a known theorem guarantees a large bihole — an independent set with equally many vertices on both sides — whose color swap lowers the cut by a positive constant per vertex. The numerical recursion on this tree object yields the claimed 0.496488 cut density.

What would settle it

Compute the tree Markov recursion with exact rational or interval arithmetic at 1/ε = 5·$10^{4}$: if the improved cut density is not strictly below 0.496488, the strict inequality in Theorem 1.2 fails. Alternatively, simulate the algorithm on large random 5-regular graphs and check whether the empirical average cut size stays below 0.496488n by an o(n) margin.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a local factor-of-IID bisection algorithm whose expected cut density on a random 5-regular graph is asymptotically at most 0.496488 edges per vertex, strictly below the earlier numerical upper bound of about 0.5028 and below one half. The algorithm runs the earlier greedy coloring in a constant number of bulk rounds, independent of n, and then flips a set of miscolored vertices whose existence is guaranteed by a bounded-degree bipartite independence theorem. The performance is computed numerically on the infinite 5-regular tree through a Markov process on the rooted two-neighborhood, and the paper argues that the transfer to random n-vertex graphs carries only an o(n) error with high probability. The strict inequality below n/2 is then used to prove that asymptotically almost every 5-regular graph has an internal partition.

Load-bearing premise

The proof assumes that the cut density computed numerically on the infinite 5-regular tree transfers to random n-vertex graphs up to an o(n) error, and that the strict inequality below 0.496488n is real rather than an artifact of four-decimal rounding.

Editorial extensions

If this is right

The bisection width of a random 5-regular graph is asymptotically almost surely below 0.496488n, improving the earlier upper bound of roughly 0.5028n.
The maximum cut of a random 5-regular graph is asymptotically almost surely larger than 2.003n.
Asymptotically almost every 5-regular graph admits an internal partition, meaning every vertex has at least as many neighbors in its own class as in the other.
The same two-phase local algorithm gives improved upper bounds on bisection width and lower bounds on max-cut for random d-regular graphs for every constant d greater than 4.
The bulk-coloring variant of the greedy algorithm terminates in a constant number of rounds independent of n, and its tree-based analysis avoids the differential equation method.

Reading between the lines

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

The tree computation at 1/ε = 2.5·10^6 suggests the improved cut density may be as low as 0.496392n; the paper stops at 0.496488 because it only certifies the coarser step, so a tighter bound may be within reach without new ideas.
A direct simulation on large random 5-regular graphs comparing the empirical bisection size with the predicted tree value would test the assumed o(n) transfer error.
The recoloring phase currently uses only about a third of the available miscolored vertices; tracking second neighborhoods could enlarge the gain, as the paper itself notes in its conclusion.
For d at least 7 the same route is blocked because the paper does not expect bisection width below n/2; internal partitions for larger odd degrees would need a different mechanism.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

Dear colleague,

Here is my honest take. The paper has a genuinely new algorithmic idea—adding a terminal recoloring phase to the Díaz–Serna–Wormald greedy bisection and analyzing it via a density recursion on the infinite 5-regular tree—and it uses that to settle the open internal-partition case for 5-regular graphs, conditional on the numerical bound. The finite-round local algorithm in Section 2.3 is a nice contribution in itself, and the tree recursion in Section 2.5 is coherent; I checked the q_t definition and the transition structure and it hangs together. The application to internal partitions via the Bárnkopf–Nagy–Paulovics theorem is clean and not circular.

The soft spot is exactly where the stress-test points. The number 0.496488 is not established by the computation in Table 1. It is floating-point output with no interval bounds, and the strict inequality in Theorem 1.2 requires the true tree value to be below 0.496488 by a positive margin. If the true value is 0.4964884, the theorem as stated fails. Remark 2.8 concedes that the starred rows use simplified formulas, and even the unstarred row accumulates rounding and discretization error over 50,000 steps with nothing controlling it. This is fixable: run the same recursion with interval arithmetic, or state the theorem with a safely rounded constant such as 0.49649 and prove that value. But as it stands, Theorem 1.2 (and therefore Theorems 1.3 and 1.4) is not rigorously proved.

The transfer from the infinite tree to random graphs in Section 2.7 is also a sketch. The cycle-counting argument gives p_l→0, and it is plausible that this bounds the discrepancy of the empirical distribution, but the sentence 'p_l also gives an upper bound on the L∞-distance' is doing work that needs a real argument. I would call this a moderate gap, not a fatal one; for a local algorithm with bounded dependence radius, the standard local-weak-convergence argument should work, but it needs to be written out.

Minor but real: the abstract says d>4 while only d=5 is quantified. That should be corrected.

Overall: the algorithmic idea is good, the internal-partition application is the kind of result people in this area will care about, and the flaws are numerical rigor and a sketched transfer, not a conceptual dead end. I would send it to a serious referee with a request for the authors to either certify the computation or soften the theorem. It deserves referee time, but it is not ready as is.

Referee Report

4 major / 5 minor

Summary. The paper introduces a new factor-of-IID local algorithm for random d-regular graphs, based on the greedy algorithm of Díaz, Serna, and Wormald, augmented by a recoloring phase. The algorithm is analyzed on the infinite d-regular tree via a recursion for the law of the colored two-neighborhood, with the sequence of dominant types and thresholds treated as precomputed parameters. For d=5, numerical evaluation of the recursion yields an improved cut density of 0.496488, from which the paper derives Theorem 1.2 (bisection width of a random 5-regular graph is a.a.s. smaller than 0.496488n), Theorem 1.3 (max-cut is a.a.s. larger than 2.003n), and Theorem 1.4 (almost every 5-regular graph has an internal partition). Section 2.7 sketches a transfer argument from the infinite tree to random graphs, and Section 3 derives the max-cut and internal-partition consequences.

Significance. If made rigorous, the main result would improve the known upper bound for the bisection width of random 5-regular graphs from about 0.5028n to below 0.5n, and would settle the existence of internal partitions for random 5-regular graphs, the first odd degree d>3 for which this is known. The algorithmic idea of appending a recoloring phase and analyzing the process through marginals on the infinite d-regular tree is natural and potentially useful for other parameter regimes. The authors also provide source code for the recursion, and the transition formulas in Section 2.5 are internally consistent. The significance is conditional, however, because the central numerical constant is not certified and the tree-to-graph transfer is only sketched.

major comments (4)

[Section 2.6 / Table 1] The proof of Theorem 1.2 rests on the value 0.496488 obtained from a floating-point recursion over 5·10^4 steps. No rounding or discretization error bounds are provided, and Remark 2.8 explicitly concedes that the last two rows of Table 1 were computed with simplified formulas in which higher-order terms are omitted. The table therefore supplies numerical evidence, not a proven upper bound. To make the theorem rigorous, the computation must be repeated with certified interval arithmetic or an a priori bound on the accumulated error, and the final constant must be a proven upper bound rather than a printed floating-point value.
[Theorem 1.2 / Section 2.6] Even if the computation were exact, the displayed value supports only 'at most 0.496488', not 'a.a.s. smaller than 0.496488n'. The cut size is integer-valued, so for values of n with 0.496488n an integer, an upper bound of 0.496488n does not imply a strict inequality unless a positive margin is established. The applications only require a bound below n/2, so the authors could state the theorem with a slightly larger certified constant or with a non-strict inequality; as written, the strict inequality is not justified.
[Section 2.7] The transfer argument from the infinite tree to random graphs is asserted rather than proved. After bounding the probability p_l that a random vertex has a cycle in its R-neighborhood, the text says that p_l 'also gives an upper bound on the L∞-distance of the empirical and the calculated distribution'. A proof requires two ingredients: (i) for every vertex whose R-neighborhood is acyclic, the joint law of its colored two-neighborhood after N steps under the precomputed sequence (D_t, q_t) equals the tree marginal, and (ii) the empirical average over the n vertices is concentrated around the tree expectation up to an O(p_l) error. The current text only counts vertices near short cycles and does not establish either ingredient.
[Section 2.3] The algorithm is not shown to produce a bisection. In the original DSW procedure, vertices are colored in asymmetric pairs to maintain exact balance between the color classes; here vertices are colored independently in parallel, and the final random coloring of uncolored vertices makes the expected class sizes equal but not the actual ones. The difference between the numbers of red and blue vertices is of order sqrt(n), and the recoloring phase swaps equal numbers of red and blue vertices, so it cannot repair this imbalance. The paper should either specify a balancing step that changes the cut by o(n) edges or prove that the imbalance is o(1); as written, the constructed partition need not satisfy the definition of a bisection.

minor comments (5)

[Section 2.3] The sentence 'The number of steps is denoted by by N' contains a duplicated word 'by'.
[Table 1] The first row appears internally inconsistent: the improvement is 0.501778−0.501257=0.000521, whereas μ(3)·0.0199445≈0.00680, which is not consistent with the other rows if the improvement is μ(3) times the miscolored-vertex density. Please check the reported values.
[Section 2.7] The sentence 'Probability p_l also gives an upper bound on the L∞-distance of the empirical and the calculated distribution' conflates the probability of a bad event with a distance bound on distributions; a formal lemma with the precise coupling would clarify the argument.
[Section 2.5] The formula for q̂_t is load-bearing for the recursion but is justified only by 'One can check'; a short derivation would improve the paper's rigor and readability.
[Lemma 2.6] The induction in the proof of Lemma 2.6 is terse, especially the notation B_t and the handling of the conditioning events; expanding the argument would make the independence claim easier to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the numerical bound is a computed output of the tree recursion, not fitted to the theorem; self-cited [5] is an independent external theorem.

full rationale

The paper's main numerical claim (Theorem 1.2, 0.496488n) is produced by an explicit transition-probability recursion on the infinite 5-regular tree in Sections 2.5-2.6. The dominant types and thresholds q_t, q̂_t are defined from the evolving measure µ_{t-1}, not from the target bound, and the cut density is then evaluated as µ({v0 red, v1 blue}) minus a recolor improvement. Table 1 even reproduces the prior DSW value (0.5028) as a check, showing the calculation is not calibrated to the final constant. The transfer to random graphs in Section 2.7 rests on the independent Bollobás/Wormald Poisson cycle-count result, so no 'prediction' is equivalent to an input by construction. Theorem 1.4 uses the self-cited theorem [5] (Bärnkopf, Nagy, Paulovics) only as an external lemma: if bisection width ≤ n/2 + 5 then an internal partition exists; that theorem's statement does not presuppose Theorem 1.2 or any value computed here. Concerns about missing floating-point error bounds and the sketchiness of the R-neighborhood coupling are correctness/rigor issues, not circularity. No step in the derivation appears to reduce to its own input or to a fitted parameter renamed as a prediction.

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

The central claim rests on a self-contained density-evolution computation on the infinite 5-regular tree plus several external theorems from random graph theory and combinatorics. The only numerical free parameter is the step size ε. No new entities are introduced.

free parameters (1)

step size ε = 1/50000 = 2e-5
Algorithmic parameter controlling the number of rounds (N = 1/ε). The reported bound 0.496488 is the value computed for this particular ε; smaller ε would give better bounds (as the last row of Table 1 shows) but require more computation.

assumptions (5)

standard math Number of cycles of length k in a random d-regular graph converges to Poisson with mean (d-1)^k/(2k).
Used in Section 2.7 for the error bound; standard result due to Bollobás and Wormald.
domain assumption Every balanced bipartite graph on 2k vertices with maximum degree Δ contains a bihole of size μ(Δ)k per side for k ≥ k0(Δ) (Axenovich et al.).
External theorem used in Section 2.2-2.3 to bound the recoloring gain; independent of the present paper.
domain assumption A 5-regular graph with a bisection of size at most n/2+5 has an internal partition.
Theorem from Bárnkopf-Nagy-Paulovics [5] used to derive Theorem 1.4; note it is authored by one of the current paper's co-authors but is an independent published result.
domain assumption For a vertex whose R-neighborhood is a tree, the local algorithm with the fixed parameter sequence (D_t, q_t) has the same output distribution on the finite graph as on the infinite tree.
Standard coupling assumption for factor-of-IID local algorithms; implicit in Section 2.7.
domain assumption The algorithm is symmetric under swapping colors, so the probability a vertex is miscolored red equals that for blue.
Used to treat the miscolored bipartite graph as balanced; follows from the measure-preserving involution in Section 3.1 but not stated in Section 2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Bisection width, max-cut and internal partitions of 5-regular graphs." pith.science (2026). https://pith.science/paper/FEKNWIHG

@misc{pith2026250908531,
  author       = {Pith},
  title        = {Pith review of: Bisection width, max-cut and internal partitions of 5-regular graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FEKNWIHG}},
  note         = {Machine review of arXiv:2509.08531}
}

read the original abstract

In this paper, we present a new factor of IID process based on the local algorithm introduced by D\'iaz, Serna, and Wormald (2007). This new approach allows us to improve the previously known upper bounds on the minimum and maximum bisection width and the maximum cut of random d-regular graphs for d > 4 by introducing a new recoloring phase after the termination of the original algorithm. As an application, we show that random 5-regular graphs asymptotically almost surely admit an internal partition, i.e., a partition of the vertex set into two nonempty classes so that every vertex has at least half of its neighbors in its own class.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 37 canonical work pages

[1]

N. Alon, B. Bollob´ as, M. Krivelevich, and B. Sudakov. Maximum cuts and judicious partitions in graphs without short cycles.Journal of Combinatorial Theory, Series B, 88(2):329–346, 2003

work page 2003
[2]

Axenovich, J.-S

M. Axenovich, J.-S. Sereni, R. Snyder, and L. Weber. Bipartite independence number in graphs with bounded maximum degree.SIAM Journal on Discrete Mathematics, 35(2):1136–1148, 2021

work page 2021
[3]

Balla, O

I. Balla, O. Janzer, and B. Sudakov. On maxcut and the lov´ asz theta function.Proceedings of the American Mathematical Society, 152(05):1871–1879, 2024

work page 2024
[4]

Ban and N

A. Ban and N. Linial. Internal partitions of regular graphs.Journal of Graph Theory, 83(1):5–18, 2016

work page 2016
[5]

B¨ arnkopf, Z

P. B¨ arnkopf, Z. L. Nagy, and Z. Paulovics. A note on internal partitions: the 5-regular case and beyond.Graphs and Combinatorics, 40(2):36, 2024

work page 2024
[6]

Basso, E

J. Basso, E. Farhi, K. Marwaha, B. Villalonga, and L. Zhou. The quantum approximate opti- mization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington- kirkpatrick model.Bulletin of the American Physical Society, 67, 2022

work page 2022
[7]

Bayati, D

M. Bayati, D. Gamarnik, and P. Tetali. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. InProceedings of the forty-second ACM symposium on Theory of computing, pages 105–114, 2010

work page 2010
[8]

Bazgan, Z

C. Bazgan, Z. Tuza, and D. Vanderpooten. Satisfactory graph partition, variants, and general- izations.European Journal of Operational Research, 206(2):271–280, 2010

work page 2010

Show all 39 references

[9]

Bollob´ as

B. Bollob´ as. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.European Journal of Combinatorics, 1(4):311–316, 1980. 12

1980
[10]

Bollob´ as

B. Bollob´ as. The isoperimetric number of random regular graphs.European Journal of combina- torics, 9(3):241–244, 1988

1988
[11]

P. Buser. Cubic graphs and the first eigenvalue of a riemann surface.Mathematische Zeitschrift, 162:87–99, 1978

1978
[12]

W.-K. Chen, D. Gamarnik, D. Panchenko, and M. Rahman. Suboptimality of local algorithms for a class of max-cut problems.The Annals of Probability, 47(3):1587–1618, 2019

2019
[13]

Coja-Oghlan, P

A. Coja-Oghlan, P. Loick, B. F. Mezei, and G. B. Sorkin. The ising antiferromagnet and max cut on random regular graphs.SIAM Journal on Discrete Mathematics, 36(2):1306–1342, 2022

2022
[14]

Dembo, A

A. Dembo, A. Montanari, and S. Sen. Extremal cuts of sparse random graphs.The Annals of Probability, pages 1190–1217, 2017

2017
[15]

D´ ıaz,¨O

J. D´ ıaz,¨O. Y. Diner, M. Serna, and O. Serra. On minimum vertex bisection of random d-regular graphs.Journal of Computer and System Sciences, 144:103550, 2024

2024
[16]

J. Dıaz, N. Do, M. J. Serna, and N. C. Wormald. Bounds on the max and min bisection of random cubic and random 4-regular graphs.Theoretical computer science, 307(3):531–547, 2003

2003
[17]

D´ ıaz, M

J. D´ ıaz, M. J. Serna, and N. C. Wormald. Bounds on the bisection width for randomd-regular graphs.Theoretical Computer Science, 382(2):120–130, 2007

2007
[18]

El Alaoui, A

A. El Alaoui, A. Montanari, and M. Sellke. Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree.Random Structures & Algorithms, 63(3):689–715, 2023

2023
[19]

Ferber, M

A. Ferber, M. Kwan, B. Narayanan, A. Sah, and M. Sawhney. Friendly bisections of random graphs.Communications of the American Mathematical Society, 2(10):380–416, 2022

2022
[20]

M. U. Gerber and D. Kobler. Classes of graphs that can be partitioned to satisfy all their vertices. Australasian Journal of Combinatorics, 29:201–214, 2004

2004
[21]

Hatami, L

H. Hatami, L. Lov´ asz, and B. Szegedy. Limits of locally–globally convergent graph sequences. Geometric and Functional Analysis, 24(1):269–296, 2014

2014
[22]

Hoppen and N

C. Hoppen and N. Wormald. Local algorithms, regular graphs of large girth, and random regular graphs.Combinatorica, 38(3):619–664, 2018

2018
[23]

Z. Jin, A. Milojevi´ c, and I. Tomon. Beyond the maxcut problem inh-free graphs.arXiv preprint arXiv:2507.13298, 2025

2025 arXiv
[24]

D. S. Johnson and M. R. Garey.Computers and intractability: A guide to the theory of NP- completeness. WH Freeman, 1979

1979
[25]

Klamt and E

S. Klamt and E. D. Gilles. Minimal cut sets in biochemical reaction networks.Bioinformatics, 20(2):226–234, 2004

2004
[26]

Kristiansen, S

P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi. Introduction to alliances in graphs. In 17th International Symposium of Computer Information Science, volume 17, pages 308–312, 2002

2002
[27]

Lichev and D

L. Lichev and D. Mitsche. On the minimum bisection of random 3-regular graphs.The Electronic Journal of Combinatorics, pages P2–40, 2023

2023
[28]

Linial and S

N. Linial and S. Louis. Asymptotically almost every 2r-regular graph has an internal partition. Graphs and Combinatorics, 36(1):41–50, 2020

2020
[29]

R. Lyons. Factors of IID on trees.Combinatorics, Probability and Computing, 26(2):285–300, 2017

2017
[30]

Minzer, A

D. Minzer, A. Sah, and M. Sawhney. On perfectly friendly bisections of random graphs.The Annals of Probability, 52(6):2281–2341, 2024. 13

2024
[31]

Montanari, G

A. Montanari, G. Parisi, and F. Ricci-Tersenghi. Instability of one-step replica-symmetry-broken phase in satisfiability problems.Journal of Physics A: Mathematical and General, 37(6):2073, 2004

2004
[32]

Poljak and Z

S. Poljak and Z. Tuza. Maximum cuts and large bipartite subgraphs.Combinatorial optimiza- tion.(DIMACS series in discrete mathematics and theoretical computer science 20.), pages 181– 244, 1995

1995
[33]

R¨ aty, B

E. R¨ aty, B. Sudakov, and I. Tomon. Positive discrepancy, maxcut, and eigenvalues of graphs. arXiv preprint arXiv:2311.02070, 2023

2023 arXiv
[34]

K. H. Shafique and R. D. Dutton. On satisfactory partitioning of graphs.Congressus Numeran- tium, pages 183–194, 2002

2002
[35]

Sharan, A

R. Sharan, A. Maron-Katz, and R. Shamir. Click and expander: a system for clustering and visualizing gene expression data.Bioinformatics, 19(14):1787–1799, 2003

2003
[36]

Stiebitz

M. Stiebitz. Decomposing graphs under degree constraints.Journal of Graph Theory, 23(3):321– 324, 1996

1996
[37]

Thomassen

C. Thomassen. Graph decomposition with constraints on the connectivity and minimum degree. Journal of Graph Theory, 7(2):165–167, 1983

1983
[38]

N. C. Wormald. Models of random regular graphs.London mathematical society lecture note series, pages 239–298, 1999

1999
[39]

Zdeborov´ a and S

L. Zdeborov´ a and S. Boettcher. A conjecture on the maximum cut and bisection width in random regular graphs.Journal of Statistical Mechanics: Theory and Experiment, 2010(02):P02020, 2010. 14

2010

Pith tools

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

[1] [1]

N. Alon, B. Bollob´ as, M. Krivelevich, and B. Sudakov. Maximum cuts and judicious partitions in graphs without short cycles.Journal of Combinatorial Theory, Series B, 88(2):329–346, 2003

work page 2003

[2] [2]

Axenovich, J.-S

M. Axenovich, J.-S. Sereni, R. Snyder, and L. Weber. Bipartite independence number in graphs with bounded maximum degree.SIAM Journal on Discrete Mathematics, 35(2):1136–1148, 2021

work page 2021

[3] [3]

Balla, O

I. Balla, O. Janzer, and B. Sudakov. On maxcut and the lov´ asz theta function.Proceedings of the American Mathematical Society, 152(05):1871–1879, 2024

work page 2024

[4] [4]

Ban and N

A. Ban and N. Linial. Internal partitions of regular graphs.Journal of Graph Theory, 83(1):5–18, 2016

work page 2016

[5] [5]

B¨ arnkopf, Z

P. B¨ arnkopf, Z. L. Nagy, and Z. Paulovics. A note on internal partitions: the 5-regular case and beyond.Graphs and Combinatorics, 40(2):36, 2024

work page 2024

[6] [6]

Basso, E

J. Basso, E. Farhi, K. Marwaha, B. Villalonga, and L. Zhou. The quantum approximate opti- mization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington- kirkpatrick model.Bulletin of the American Physical Society, 67, 2022

work page 2022

[7] [7]

Bayati, D

M. Bayati, D. Gamarnik, and P. Tetali. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. InProceedings of the forty-second ACM symposium on Theory of computing, pages 105–114, 2010

work page 2010

[8] [8]

Bazgan, Z

C. Bazgan, Z. Tuza, and D. Vanderpooten. Satisfactory graph partition, variants, and general- izations.European Journal of Operational Research, 206(2):271–280, 2010

work page 2010