On small balanceable, strongly-balanceable and omnitonal graphs

Christina Zarb; Josef Lauri; Yair Caro

REVIEW 5 major objections 5 minor 19 references

On small balanceable, strongly-balanceable and omnitonal graphs

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

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

Pith's one-line read The paper proves that equal-edge bipartite graph pairs always form a balanceable disjoint union, and completes all balance, strong-balance, and omnitonal values for graphs with at most four edges.

desk verdict The union theorem is new and correct; the catalogue is not fully verified and needs repair before it can be trusted. read the letter →

arxiv 1908.08237 v3 pith:F3AUALM3 submitted 2019-08-22 math.CO

Yair Caro , Josef Lauri , Christina Zarb This is my paper · ORCID

classification math.CO MSC 05C5505C3505D10

keywords balanceablegraphsstrongbalancenumberomnitonalamoebasedgecolouringsTuránnumbersRamseymatching

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 works inside Ramsey theory: instead of asking when every red/blue edge-colouring of a large complete graph forces a monochromatic copy of a graph G, it asks when the colouring forces a copy of G whose colours are split evenly (or differ by one, when |E(G)| is odd). The main new result is that if G and H are any two bipartite graphs with the same number of edges, their disjoint union G∪H is balanceable, with bal(n,G∪H) ≤ max{ex(n,G),ex(n,H)} once n is at least |V(G)|+|V(H)|+R(G,H). This matters because individual bipartite graphs can fail to be balanceable—for instance C_{4t+2} is not—so the theorem produces balanceable unions out of non-balanceable parts. The paper also introduces a 'triple property' linking strong balance of (2t−1)K2 with balance of 2tK2 and (2t+1)K2, derives the exact common value $\binom{t-1}{2} + (t-1)(n-t+1)$, and completes tables of bal, sbal, and ot for all graphs on at most four edges.

What carries the argument

The argument turns on comparing colour-class sizes with extremal numbers. Theorem 3.1 uses the fact that for bipartite G and H, ex(n,G) and ex(n,H) are sub-quadratic, so a colour class with more than max{ex(n,G),ex(n,H)} edges must contain G (and the other must contain H); the Ramsey number R(G,H) then guarantees that the unclaimed vertex set can supply a monochromatic copy that makes the two copies vertex-disjoint. The 'triple property' is a second device: for G=(2t−1)K2, H=2tK2, F=(2t+1)K2, adding or deleting a single edge preserves the balance number, and the chain of inequalities reduces all three parameters to ex(n,tK2) via a classical extremal formula for matchings. The catalogue also leans on the amoeba concept—a graph that can be moved through a complete graph by single edge replacements—because Theorem C states that bipartite amoebas are omnitonal with ot(n,G)=ex(n,G).

What would settle it

A red/blue colouring of K_n in which each colour has more than max{ex(n,G),ex(n,H)} edges but no balanced copy of G∪H exists would refute Theorem 3.1. For the catalogue, computing the actual threshold n0 for a four-edge amoeba such as 4K2 and exhibiting a colouring with min{|R|,|B|} > ex(n,4K2) that lacks some required colour distribution would refute the corresponding table row.

Watch

Extended reading notes

Core claim

The central claim, Theorem 3.1, is that the disjoint union of two bipartite graphs with equal edge counts is balanceable. Concretely, if e(G)=e(H) and n ≥ |V(G)|+|V(H)|+R(G,H), then any 2-edge-colouring of K_n with more than max{ex(n,G),ex(n,H)} edges in each colour contains a balanced copy of G∪H. Because bipartite Turán numbers are sub-quadratic, the colour class with the larger count contains a copy of G and the other contains a copy of H; when the two copies overlap, the unused vertices still number at least R(G,H), so a monochromatic copy of one of the graphs can replace the overlapping part and separate the two copies. A second result, the triple property, shows that for G=(2t−1)K2, H=2tK2, F=(2t+1)K2 one has sbal(n,G)=bal(n,H)=bal(n,F) for all sufficiently large n, and Theorem 3.4 evaluates this common value as ex(n,tK2). These results, together with ad hoc arguments for specific four-edge graphs, yield the complete catalogue of bal, sbal, and ot for every graph with at most four edges.

Load-bearing premise

The omnitonal rows of the catalogue depend on Theorem C's promise that ot(n,G)=ex(n,G) beyond some threshold n0(G), but the paper never computes or bounds any n0 for the listed four-edge amoebas, so the advertised 'n ≥ n0' validity ranges are unverified.

Editorial extensions

If this is right

Two copies of a non-balanceable bipartite graph, such as C_{4t+2}, form a balanceable union; the example in the paper gives bal(n, 2C_{4t+2}) ≤ (4t+1)n^{1+1/(4t+2)} + 16(4t+1)n for n ≥ 14t+6.
For matchings, the exact values for n ≥ 7t−1 are sbal(n,(2t−1)K2) = bal(n,2tK2) = bal(n,(2t+1)K2) = $\binom{t-1}{2} + (t-1)(n-t+1)$.
Every graph on at most four edges now has a known balance number (when balanceable), with new values such as bal(n,4K2)=n−1 for n≥10 and bal(n,K1,3∪K2)=n−1 for n≥9.
The union theorem is a general construction: equal-edge bipartite pairs are balanceable without either component being balanceable, extending the class of graphs known to be balanceable.

Reading between the lines

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

Beyond the paper, the triple property suggests a general stability phenomenon: for many graphs G, adding one edge to a balanced graph family may leave bal unchanged, offering a route to exact balance numbers for larger graphs without fresh extremal analysis.
Beyond the paper, the union theorem opens a characterisation problem: given a family of bipartite graphs with equal edge counts, when is their disjoint union balanceable, and can bal(n, ∪G_i) be expressed in terms of the individual extremal numbers?
Beyond the paper, the unquantified n0 in Theorem C for four-edge amoebas invites a computational check: determining the first n where each listed graph becomes omnitonal would turn the table's asymptotic statements into explicit, machine-verifiable ranges.

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

Colleague,

The one result worth knowing here is Theorem 3.1: if G and H are bipartite with equal edge counts, then G∪H is balanceable. The proof is a short Ramsey-plus-Turán argument and it is correct. That is genuinely new and gives a large class of balanceable graphs that were not covered by earlier criteria. The matching closed forms via the triple property (Theorem 3.4) are also a solid addition.

The rest of the paper is a catalogue of bal/sbal/ot for graphs with at most four edges. This is where the soft spots are. Several table entries are not actually verified in the paper. The omnitonal rows in Table 1 all say 'valid n ≥ n0' with n0 taken from Theorem C of [6]; the paper never bounds n0 for any of those graphs, so the reader is left with an existential threshold. For a catalogue, that is a genuine incompleteness. In addition, the amoeba property is asserted for most of those graphs with no proof or reference to a public source (the paper cites [5], 'in preparation'). Some case analyses are also sloppy: Theorem 2.2's lower bound claims a red 2-factor avoids a red K1,3∪K2, but that only rules out copies with three or four red edges; a (2,2) copy can still appear. The same theorem's Case 3 ignores blue edges from the center to Y. Theorem 2.3 has a counting error in Case 2 ('four such deleted edges incident to u' should be three). These gaps are almost certainly repairable, but as written the catalogue is not a complete, verified computation. The 'left to the reader' entries in Table 2 are a further sign of that.

I want to be clear that the central new theorem holds up; the issues are in the tables and the supporting cases, not in the main idea. The citation pattern is fine—reliance on [6] is appropriate, though leaning on an 'in preparation' paper for the amoeba facts is a weakness.

Who is this for? Someone working in zero-sum Ramsey or unavoidable patterns will want the union theorem and the matching closed forms. The catalogue is useful as a reference if the gaps are fixed, but it is not yet a trustworthy table.

My recommendation: send it to peer review, but the referee should require the authors to either supply the missing n0 bounds (or explicitly state that no bound is known), justify the amoeba assertions, and repair the case analyses in 2.2 and 2.3 before publication. The paper has merit but needs a serious revision.

Referee Report

5 major / 5 minor

Summary. The paper studies three Ramsey-type parameters for 2-edge-coloured complete graphs: the balance number bal(n,G), the strong balance number sbal(n,G), and the omnitonal number ot(n,G). Its two stated goals are to catalogue these parameters for all graphs with at most four edges (Tables 1–3) and to prove new general results. The main new theorem (Theorem 3.1) states that if G and H are bipartite graphs with e(G)=e(H), then the disjoint union G∪H is balanceable for n sufficiently large, with bal(n,G∪H) ≤ max{ex(n,G), ex(n,H)}. The paper also introduces a 'triple property' and uses it, together with Turán and Ramsey bounds, to prove that for n ≥ 7t−1, sbal(n,(2t−1)K2) = bal(n,2tK2) = bal(n,(2t+1)K2) = ex(n,tK2). Several ad-hoc theorems supply values for individual small graphs, and the paper closes with tables summarizing the computed values.

Significance. If fully supported, the catalogue of bal, sbal, and ot for all graphs on at most four edges would be a useful reference, and Theorem 3.1 is a genuine extension of earlier balanceability results: previous union theorems required one component to be balanceable or omnitonal, whereas Theorem 3.1 only requires bipartiteness and equal edge counts. The proof of Theorem 3.1 is short, elementary, and correct, and the matching formulas in Theorem 3.4 are a nice application. The paper is purely combinatorial, uses no fitted parameters, and, where it proves results directly, the arguments are mostly transparent. However, the advertised catalogue is not fully verified: several table entries rely on an existential n0 that is never quantified, on amoeba assertions that are not proved in the manuscript, and on case analyses that are left to the reader. These gaps affect the central claim that the paper provides a complete catalogue.

major comments (5)

[Section 4, Table 1; Section 2.1, Theorem C] Table 1 lists ten omnitonal entries with 'Valid n: n ≥ n0' and cites Theorem C, but Theorem C only asserts the existence of n0 = n0(G) for bipartite amoebas; the paper never computes or bounds n0 for any of 4K2, 2K2∪K1,2, 2K1,2, K2∪P4, P5, K1,3 with extended leaf, P4, 3K2, P3∪K2, or 2K2. Since the stated goal is a catalogue with explicit validity ranges, a reader cannot determine for which n the equality ot(n,G)=ex(n,G) is claimed, and the advertised ranges are not established.
[Section 4, Table 1; Section 2.1, Lemma G and ref. [5]] The 'Amoeba' column in Table 1 marks 'Y' for the same ten graphs, but the amoeba property is not proved for them in the manuscript. The text explicitly mentions only tK2 and Pk as amoebas; Lemma G gives a necessary condition, not sufficiency, and the only reference for the amoeba status of the other graphs is [5], which is cited as 'in preparation'. Because Theorem C applies only to bipartite amoebas, the omnitonal entries remain unverified unless the amoeba property is supplied or a published reference is given.
[Theorem 2.2, Case 3] In Theorem 2.2, Case 3, after constructing a K1,3 with red edges va, vb and blue edge vc, the proof says that 'all blue edges are incident with c with at most one more possible blue edge ab, making the total number of blue edges at most n'. This overlooks blue edges from v to Y = V(Kn)\ {v,a,b,c}. Such edges do not immediately give the required vertex-disjoint blue K2, and they break the counting bound |B|≤n. The case analysis therefore does not establish ot(n,K1,3∪K2)=n as written.
[Theorem 2.3, Case 2] In Theorem 2.3, Case 2, the condition for two independent red edges in the remaining graph is stated as (n−6 choose 2) − (n−5) ≥ n−6 and then simplified to n^2 −15n+52 ≥ 0. The correct equivalent inequality is n^2 −17n+64 ≥ 0, which fails for n=10 and n=11. Consequently the proof of bal(n,4K2)=n−1 does not justify the claimed range n≥10.
[Section 4, Table 2, footnote 1] Footnote 1 to Table 2 states that the proofs for bal(n,2K1,2)=1, bal(n,K2∪P4)=1, bal(n,P5)=1, bal(n,K1,3 with extended leaf)=1, and bal(n,K3+e)=1 are 'very similar to the proof of Theorem 2.4' and are left to the reader. For a paper whose stated contribution is a complete catalogue, these entries are part of the central claim; deferring their proofs makes the catalogue incomplete. They should either be proved in the manuscript or the table should be presented as conjectural.

minor comments (5)

[Theorem 2.2, Case 2(ii)] The expression '|X| = n5 ≥ 5' appears to be a typo for 'n−5'.
[Section 3, triple-property definition] The definition of the triple property uses 'bal(F,n)' and 'bal( F, n )' inconsistently; the function bal is defined with the graph as the second argument.
[Theorem 2.4] The K1,2 constructions such as 'K1,2 on the vertices {c; d, e}' use the semicolon notation for the center, but in several places the subsequent colour arguments appear to require the other vertex as the center; please check and clarify the intended stars.
[Theorem 2.7] The word 'atrting' in the last sentence of the proof is a typo for 'starting'.
[Observation 3.3] In the proof of the triple property for matchings, the statement that the graph L on at least 3t+4 vertices is all-red is true only after the preceding exclusion of blue edges incident with the e_i; the text should make that dependence explicit.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation found; the catalogue's omnitonal rows inherit an unspecified n0 from prior work by the same group, which is a completeness gap rather than a circular reduction.

full rationale

The paper's new results are derived from standard external tools and are not equivalent to their inputs by construction. Theorems 2.2-2.7 and 3.1-3.4 are proved directly from Turan's theorem, Ramsey numbers, Erdos-Gallai, and elementary case analysis, with no fitted parameters and no target quantity defined in terms of the output. The union theorem (Theorem 3.1) is a genuine derivation: if both colour classes exceed max{ex(n,G), ex(n,H)}, a red G and a blue H exist, and the Ramsey condition on the leftover vertices forces disjoint copies, yielding a balanced G union H. The triple property (Observation 3.3 and Theorem 3.4) is established by explicit inequalities, not by assuming the conclusion. Table 1's omnitonal values for bipartite amoebas are direct applications of Theorem C from [6], a theorem by overlapping authors, and the amoeba classification for several listed graphs is asserted with reference to [5], which is in preparation; these are self-citations, and the unquantified n0 in Theorem C makes the advertised validity ranges incomplete. However, this is a missing bound and an omitted proof, not equivalence by construction: Theorem C is a general parameter-free statement whose assumptions do not include the specific target equality ot(n,G)=ex(n,G), and no parameter is fitted to force the table entries. The circularity score is therefore low, with the n0 gap and unproved amoeba assertions treated as completeness and correctness concerns rather than circular reasoning.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted; the paper is purely combinatorial. Axioms are standard extremal/Ramsey results plus one lemma from an unpublished companion paper. The main unquantified input is the threshold n0 in Theorem C used throughout Table 1.

assumptions (6)

standard math Turan's theorem: if |R| > ex(n,G) then R contains a copy of G
Invoked at the start of Theorem 3.1 to guarantee red G and blue H when min{|R|,|B|} exceeds max{ex(n,G), ex(n,H)}.
standard math Ramsey's theorem: for n large enough, any 2-colouring of E(K_n) contains a red G or a blue H
Used in Theorem 3.1 to find a copy of G or H in the leftover vertex set X, requiring |X| >= R(G,H).
domain assumption Sub-quadratic extremal bound for bipartite graphs: ex(n,G) = o(n^2)
Needed in Theorem 3.1 to ensure that min{|R|,|B|} > max{ex(n,G), ex(n,H)} is achievable for large n. Cited to [13], not proved in the paper.
standard math Erdos-Gallai matching theorem: ex(n,tK2) = max{C(2t-1,2), C(t-1,2)+(t-1)(n-t+1)}
Used in Theorem 3.4 to evaluate the closed form for the matching numbers.
domain assumption Faudree-Schelp cycle Ramsey number: R(C_{4t+2}, C_{4t+2}) = 6t+2
Used in Example 3.2 to derive the stated bound for bal(n, 2C_{4t+2}).
ad hoc to paper Amoeba degree lemma (Lemma G from [5])
Quoted from the unpublished companion paper [5] and proved in the text; used to fill Table 1 entries for amoeba classification.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On small balanceable, strongly-balanceable and omnitonal graphs." pith.science (2026). https://pith.science/paper/F3AUALM3

@misc{pith2026190808237,
  author       = {Pith},
  title        = {Pith review of: On small balanceable, strongly-balanceable and omnitonal graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F3AUALM3}},
  note         = {Machine review of arXiv:1908.08237}
}

abstract

In Ramsey theory for graphs we are given a graph $G$ and we are required to find the least $n_0$ such that, for any $n\geq n_0$, any red/blue colouring of the edges of $K_n$ gives a subgraph $G$ all of whose edges are blue or all are red. Here we shall be requiring that, for any red/blue colouring of the edges of $K_n$, there must be a copy of $G$ such that its edges are partitioned equally as red or blue (or the sizes of the colour classes differs by one in the case when $G$ has an odd number of edges). This introduces the notion of balanceable graphs and the balance number of $G$ which, if it exists, is the minimum integer bal$(n, G)$ such that, for any red/blue colouring of $E(K_n)$ with more than bal$(n, G)$ edges of either colour, $K_n$ will contain a balanced coloured copy of $G$ as described above. This parameter was introduced by Caro, Hansberg and Montejano in \cite{2018arXivCHM}. There, the authors also introduce the strong balance number sbal$(n,G)$ and the more general omnitonal number ot$(n, G)$ which requires copies of $G$ containing a complete distribution of the number of red and blue edges over $E(G)$. In this paper we shall catalogue bal$(n, G)$, sbal$(n, G)$ and ot$(n,G)$ for all graphs $G$ on at most four edges. We shall be using some of the key results of Caro et al, which we here reproduce in full, as well as some new results which we prove here. For example, we shall prove that the union of two bipartite graphs with the same number of edges is always balanceable.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 17 canonical work pages

[6]

Y. Caro, A. Hansberg, and A. Montejano. Unavoidable chromat ic patterns in 2-colorings of the complete graph. arXiv e-prints , page arXiv:1810.12375, 2019

work page Pith review arXiv 2019
[5]

Y. Caro, A. Hansberg, and A. Montejano. Amoebas. in preparation, 2019

work page 2019
[1]

Avoiding zero-sum subsequences of prescribed length over the integers

C. Augspurger, M. Minter, K. Shoukry, P. Sissokho, and K. Vos s. Avoiding zero-sum subsequences of prescribed length over the integers. arXiv preprint arXiv:1603.03978, 2016

work page Pith review arXiv 2016
[2]

A. Berger. An analogue of the Erd˝ os–Ginzburg–Ziv theorem over Z. Discrete Mathematics, 342(3):815–820, 2019

work page 2019
[3]

Bollob´ as

B. Bollob´ as. Extremal graph theory . Courier Corporation, 2004

work page 2004
[4]

Bowen, A

M. Bowen, A. Hansberg, A. Montejano, and A. M¨ uyesser. Colo red unavoid- able patterns and balanceable graphs. arXiv preprint arXiv:1912.06302 , 2019

arXiv 1912
[7]

Y. Caro, A. Hansberg, and A. Montejano. Zero-sum Km over Z and the story of K4. Graphs and Combinatorics , 35(4):855–865, 2019

work page 2019
[8]

Y. Caro, A. Hansberg, and A. Montejano. Zero-sum subseque nces in bounded-sum {−1, 1}-sequences. Journal of Combinatorial Theory, Series A, 161:387–419, 2019

work page 2019

Show all 19 references

[9]

Caro and R

Y. Caro and R. Yuster. On zero-sum and almost zero-sum subgr aphs over Z. Graphs and Combinatorics , 32(1):49–63, 2016

2016
[10]

Cockayne and P.J

E.J. Cockayne and P.J. Lorimer. The ramsey number for stripes . Journal of the Australian Mathematical Society , 19(2):252–256, 1975

1975
[11]

Erd˝ os and T

P. Erd˝ os and T. Gallai. On maximal paths and circuits of graphs. Acta Mathematica Hungarica, 10(3-4):337–356, 1959

1959
[12]

Faudree and R.H

R.J. Faudree and R.H. Schelp. All ramsey numbers for cycles in gr aphs. Discrete Mathematics , 8(4):313–329, 1974

1974
[13]

F¨ uredi and M

Z. F¨ uredi and M. Simonovits. The history of degenerate (bipa rtite) extremal graph problems. In Erd˝ os Centennial, pages 169–264. Springer, 2013. 17

2013
[14]

Gir˜ ao and B

A. Gir˜ ao and B. Narayanan. Tur´ an theorems for unavoidablepatterns. arXiv preprint arXiv:1907.00964 , 2019

1907 arXiv
[15]

Pikhurko

O. Pikhurko. A note on the Tur´ an function of even cycles. Proceedings of the American Mathematical Society , 140(11):3687–3692, 2012

2012
[16]

Robertson

A. Robertson. Zero-sum analogues of van der waerden’s theo rem on arith- metic progressions. arXiv preprint arXiv:1802.03387 , 2018

2018 arXiv
[17]

Robertson

A. Robertson. Zero-sum generalized schur numbers. arXiv preprint arXiv:1802.03382, 2018

2018 arXiv
[18]

A. Sun. Zero-sum subsequences in bounded-sum {−r, s }-sequences. arXiv preprint arXiv:1907.06623 , 2019

1907 arXiv
[19]

D.B. West. Introduction to Graph Theory . Math Classics. Pearson, 2017. 18

2017

Pith tools

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

[1] [6]

Y. Caro, A. Hansberg, and A. Montejano. Unavoidable chromat ic patterns in 2-colorings of the complete graph. arXiv e-prints , page arXiv:1810.12375, 2019

work page Pith review arXiv 2019

[2] [5]

Y. Caro, A. Hansberg, and A. Montejano. Amoebas. in preparation, 2019

work page 2019

[3] [1]

Avoiding zero-sum subsequences of prescribed length over the integers

C. Augspurger, M. Minter, K. Shoukry, P. Sissokho, and K. Vos s. Avoiding zero-sum subsequences of prescribed length over the integers. arXiv preprint arXiv:1603.03978, 2016

work page Pith review arXiv 2016

[4] [2]

A. Berger. An analogue of the Erd˝ os–Ginzburg–Ziv theorem over Z. Discrete Mathematics, 342(3):815–820, 2019

work page 2019

[5] [3]

Bollob´ as

B. Bollob´ as. Extremal graph theory . Courier Corporation, 2004

work page 2004

[6] [4]

Bowen, A

M. Bowen, A. Hansberg, A. Montejano, and A. M¨ uyesser. Colo red unavoid- able patterns and balanceable graphs. arXiv preprint arXiv:1912.06302 , 2019

arXiv 1912

[7] [7]

Y. Caro, A. Hansberg, and A. Montejano. Zero-sum Km over Z and the story of K4. Graphs and Combinatorics , 35(4):855–865, 2019

work page 2019

[8] [8]

Y. Caro, A. Hansberg, and A. Montejano. Zero-sum subseque nces in bounded-sum {−1, 1}-sequences. Journal of Combinatorial Theory, Series A, 161:387–419, 2019

work page 2019