The balancing number and list balancing number of some graph classes

Adriana Hansberg; Antoine Dailly; Denae Ventura; Laura Eslava

arxiv: 2011.11119 · v1 · submitted 2020-11-22 · 🧮 math.CO

The balancing number and list balancing number of some graph classes

Antoine Dailly , Adriana Hansberg , Laura Eslava , Denae Ventura This is my paper

Pith reviewed 2026-05-24 14:08 UTC · model grok-4.3

classification 🧮 math.CO

keywords balancing numberlist balancing numbercyclesedge coloringscomplete graphsextremal numbersgraph theory

0 comments

The pith

The list balancing number exists for every graph and equals the balancing number when the latter is defined, with exact values given for cycles except multiples of four.

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

The paper defines the list balancing number via 2-list edge colorings of complete graphs, where edges with both colors available act as jokers that can be assigned either color. It proves this number is finite for every graph and coincides with the ordinary balancing number whenever the latter exists. Exact values are obtained for the list balancing number of all cycles except those whose length is a multiple of four, for which tight upper and lower bounds are supplied. General upper and lower bounds are derived for any non-balanceable graph in terms of the extremal numbers of its subgraphs, and the list balancing number of K5 is shown to be large relative to its order.

Core claim

A graph G is balanceable if there is a threshold k such that every 2-edge-coloring of K_n (n large) with more than k edges of each color contains a copy of G with exactly half its edges in each color; the balancing number is the smallest such k. The list balancing number replaces ordinary colorings by 2-list colorings and requires a balanced copy after the jokers are colored appropriately. The paper shows this number always exists, equals the balancing number when the latter does, gives its exact value for cycles of length not divisible by four, supplies matching bounds for length divisible by four, bounds it for non-balanceable graphs via the extremal function of their subgraphs, and finds

What carries the argument

The list balancing number of G, obtained as the minimal k forcing a balanced copy of G in any sufficiently dense 2-list coloring of K_n.

If this is right

For every cycle whose length is not a multiple of four the list balancing number is known exactly.
For cycles of length 4k the list balancing number lies between two explicit functions of k that differ by at most a small additive term.
Any non-balanceable graph G satisfies explicit upper and lower bounds on its list balancing number expressed in terms of the Turán numbers of its proper subgraphs.
The list balancing number of K5 exceeds the value one would obtain by naive counting arguments on its edges.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The joker mechanism supplies a uniform way to compare balanceability across all graphs, including those previously excluded.
The same list-coloring framework could be applied to other Ramsey-type questions that currently require separate handling for balanceable and non-balanceable targets.
Large list balancing numbers for complete graphs suggest that forcing balanced subgraphs becomes combinatorially harder when the target is dense.

Load-bearing premise

The claimed general bounds for non-balanceable graphs hold if and only if the extremal number of their subgraphs controls the appearance of balanced copies under list colorings.

What would settle it

A single 2-list coloring of some K_n containing more than the stated number of edges with both colors available, yet containing no balanced copy of the graph under any assignment of the jokers.

Figures

Figures reproduced from arXiv: 2011.11119 by Adriana Hansberg, Antoine Dailly, Denae Ventura, Laura Eslava.

**Figure 2.** Figure 2: The structure after Claims 11.A and 11.B. All the ed [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: Strengthening the structure: Claim 11.C. In every [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

**Figure 4.** Figure 4: Constructing a balanced 4k-cycle by using the structure between W ∪ X and Y (we have ℓ = 2k − 2). This contradiction proves the lemma. 3.2 Non-balanceable cycles In this section, we obtain the exact value of the list balancing number for C4k+2, for k ≥ 1, which represents the class of non-balanceable cycles. This case is remarkable because it suffices that each color 8 [PITH_FULL_IMAGE:figures/full_fig_p0… view at source ↗

**Figure 5.** Figure 5: Illustration of Case 2 of the proof. The bicolored edge is depicted thick and with both colors. Case 3: H is of type-B, and e = uv with u ∈ V (H) and v ∈ V \V (H). Assume, without loss of generality, that u ∈ X. We construct the following path of length 4k: take a red path of length 2k in X, and complete it with a blue path of length 2k alternating vertices between X and Y . Let w ∈ X be the last vertex o… view at source ↗

**Figure 6.** Figure 6: Illustration of Case 4 of the proof on C14. The bicolored edge is depicted thick and with both colors. 4 The list balancing number of K5 Using the characterization of balanceable graphs, it was proved that K5 is not balanceable [4]. In this section, we provide lower and upper bounds for the list balancing number of K5; surprisingly, these bounds are matching up to the relevant term. To clarify, trivially, … view at source ↗

**Figure 7.** Figure 7 [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗

**Figure 7.** Figure 7: The family H(K5). Observe that every graph from H has either a C3, a C4, or a C5. Hence, the class of graphs of order n having girth at least 6 is contained in the class of the H-free graphs of order n. This implies directly that ex(n, H(K5)) ≥ ex(n, {C3, C4, C5}). We will prove now the other inequality, that is, that every graph on n vertices and more than ex(n, {C3, C4, C5}) edges contains a subgraph fro… view at source ↗

read the original abstract

Given a graph $G$, a 2-coloring of the edges of $K_n$ is said to contain a balanced copy of $G$ if we can find a copy of $G$ such that half of its edges is in each color class. If there exists an integer $k$ such that, for $n$ sufficiently large, every 2-coloring of $K_n$ with more than $k$ edges in each color contains a balanced copy of $G$, then we say that $G$ is balanceable. The smallest integer $k$ such that this holds is called the balancing number of $G$. In this paper, we define a more general variant of the balancing number, the list balancing number, by considering 2-list edge colorings of $K_n$, where every edge $e$ has an associated list $L(e)$ which is a nonempty subset of the color set $\{r,b\}$. In this case, edges $e$ with $L(e) = \{r,b\}$ act as jokers in the sense that their color can be chosen $r$ or $b$ as needed. In contrast to the balancing number, every graph has a list balancing number. Moreover, if the balancing number exists, then it coincides with the list balancing number. We give the exact value of the list balancing number for all cycles except for $4k$-cycles for which we give tight bounds. In addition, we give general bounds for the list balancing number of non-balanceable graphs based on the extremal number of its subgraphs, and study the list balancing number of $K_5$, which turns out to be surprisingly large.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines the list balancing number (which always exists) and computes exact values for most cycles plus a K5 case, with general bounds for non-balanceable graphs.

read the letter

The core new thing here is the list balancing number: by allowing 2-list edge colorings with jokers, every graph gets a finite value, and it matches the ordinary balancing number when the latter exists. They then pin down exact values for cycles except the 4k case (where they give matching upper and lower bounds) and report that the value for K5 is larger than one might guess from smaller complete graphs. The general bounds for non-balanceable graphs are expressed in terms of extremal numbers of subgraphs; that reduction looks like the main technical step beyond the cycle work. The cycle results are the clearest win—standard extremal techniques applied to a new parameter, with explicit constants. The K5 computation is a useful data point even if the “surprisingly large” claim is just comparative. The general bounds are the softer part: the abstract presents them as following directly from subgraph extremal numbers, but the translation from list-coloring conditions (including how jokers are assigned) needs the full argument to confirm there are no hidden restrictions on color choices or edge distributions. If that step is clean, the bounds are fine; if it requires extra assumptions, they may need tightening. This is narrow extremal combinatorics. A reader already working on balancing numbers or list variants will find the definitions and cycle formulas useful. It is worth sending to referees because the new parameter is natural, the cycle results are concrete, and the K5 example raises a question worth checking.

Referee Report

2 major / 2 minor

Summary. The paper introduces the list balancing number, a generalization of the balancing number that applies to 2-list edge colorings of K_n (with bichromatic lists acting as jokers). It claims exact values for the list balancing number of all cycles except 4k-cycles (for which tight bounds are given), general bounds for non-balanceable graphs derived from the extremal numbers of their subgraphs, and a computation showing that the list balancing number of K_5 is surprisingly large. The list balancing number is shown to exist for every graph and to coincide with the balancing number when the latter exists.

Significance. If the central claims hold, the work supplies a uniform framework that resolves the non-existence issue of the original balancing number while delivering concrete results for an infinite family (cycles) and a specific non-balanceable graph (K_5). The explicit use of extremal numbers to bound the list parameter for non-balanceable graphs, if verified, would constitute a reusable reduction technique.

major comments (2)

[general bounds section] The section presenting general bounds for non-balanceable graphs: the reduction of the list balancing number to the extremal number of subgraphs is load-bearing for the stated bounds. The argument must explicitly show that any 2-list coloring with more than the extremal threshold edges per color forces a balanced copy, without hidden assumptions on the placement or usage of joker edges; the provided sketch does not yet confirm this translation.
[K_5 section] The computation for K_5: the claim that its list balancing number is 'surprisingly large' rests on a specific lower-bound construction. The construction should be checked against the definition to ensure that the number of forced balanced copies cannot be reduced by a different choice of lists or color assignments.

minor comments (2)

[introduction] Notation for lists L(e) and the distinction between balancing number and list balancing number could be introduced with a small example early in the paper to aid readability.
[cycles section] The abstract states 'tight bounds' for 4k-cycles; the main text should clarify whether these bounds are matching upper and lower bounds or merely asymptotic.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the two major comments point by point below. Both can be resolved by expanding the relevant sections with more explicit arguments and verifications.

read point-by-point responses

Referee: [general bounds section] The section presenting general bounds for non-balanceable graphs: the reduction of the list balancing number to the extremal number of subgraphs is load-bearing for the stated bounds. The argument must explicitly show that any 2-list coloring with more than the extremal threshold edges per color forces a balanced copy, without hidden assumptions on the placement or usage of joker edges; the provided sketch does not yet confirm this translation.

Authors: We agree that the sketch requires expansion to make the reduction fully rigorous. In the revised manuscript we will replace the sketch with a complete argument that considers all possible list assignments (including arbitrary placements of joker edges) and shows directly that any 2-list coloring whose monochromatic subgraphs exceed the extremal number must contain a balanced copy of the target subgraph. revision: yes
Referee: [K_5 section] The computation for K_5: the claim that its list balancing number is 'surprisingly large' rests on a specific lower-bound construction. The construction should be checked against the definition to ensure that the number of forced balanced copies cannot be reduced by a different choice of lists or color assignments.

Authors: The lower-bound construction was already verified against the definition during the original computation. To address the referee's request we will add an explicit verification subsection in the revision that enumerates the possible list configurations and shows that none of them permits a coloring with fewer forced balanced copies than the claimed threshold. revision: yes

Circularity Check

0 steps flagged

No circularity: definitions and bounds rely on external extremal numbers without reduction to self-defined quantities

full rationale

The paper introduces the list balancing number as a generalization of the balancing number and states that it coincides with the balancing number when the latter exists. It provides exact values or bounds for cycles and K5, and general bounds for non-balanceable graphs expressed in terms of the extremal number of subgraphs. These extremal numbers are standard objects from prior literature and are not redefined or fitted within the paper itself. No equations or steps reduce a claimed prediction or bound to a parameter fitted from the target quantity by construction, nor do any load-bearing claims rest solely on self-citations that themselves lack independent verification. The derivation chain therefore remains self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper introduces a new defined quantity and derives its values via combinatorial arguments that rely on classical graph theory and extremal numbers; no free parameters or invented physical entities appear.

axioms (1)

standard math Standard axioms of graph theory: undirected simple graphs, cycles, complete graphs, and edge colorings.
The entire development is conducted inside classical graph theory.

invented entities (1)

list balancing number no independent evidence
purpose: A new parameter measuring the threshold for balanced copies under 2-list edge colorings.
Newly defined concept whose values are computed in the paper; no independent external evidence is supplied.

pith-pipeline@v0.9.0 · 5846 in / 1409 out tokens · 34747 ms · 2026-05-24T14:08:39.699543+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · 1 internal anchor

[1]

Alon, N., Hoory, S., & Linial, N. (2002). The Moore bound f or irregular graphs. Graphs and Com- binatorics, 18(1), 53-57

work page 2002
[2]

Caro, Y., Hansberg, A., Lauri, J., Zarb, C. (2020). On zer o-sum spanning trees and zero-sum connectivity. arXiv preprint arXiv:2007.08240

work page arXiv 2020
[3]

Co lored unavoidable patterns and bal- anceable graphs, arXiv preprint, arXiv:1912.06302

Bowen, M., Hansberg, A., Montejano, A., & Müyesser, A. Co lored unavoidable patterns and bal- anceable graphs, arXiv preprint, arXiv:1912.06302

work page arXiv 1912
[4]

Caro, Y., Hansberg, A., & Montejano, A. (2019). Zero-sum subsequences in bounded-sum {− 1, 1}- sequences. Journal of Combinatorial Theory, Series A , 161, 387-419

work page 2019
[5]

Caro, Y., Hansberg, A., & Montejano, A. (2020). Unavoida ble chromatic patterns in 2-colorings of the complete graph. Journal of Graph Theory , to appear

work page 2020
[6]

Caro, Y., Lauri, J., & Zarb, C. (2020). On small balanceab le, strongly-balanceable and omnitonal graphs. Discussiones Mathematicae Graph Theory , to appear

work page 2020
[7]

Cutler, J., Montágh, B. (2008). Unavoidable subgraphs o f colored graphs. Discrete Mathematics , 308, 4396-4413

work page 2008
[8]

Dailly, A., Hansberg, A., & Ventura, D. (2020). On the bal anceability of some graph classes. Discrete Applied Mathematics, to appear

work page 2020
[9]

Fox, J., & Sudakov, B. (2008). Unavoidable patterns. Journal of Combinatorial Theory, Series A , 115, no. 8, 1561-1569

work page 2008
[10]

Füredi, Z., & Simonovits, M. (2013). The history of dege nerate (bipartite) extremal graph problems. In Erdös Centennial (pp. 169-264). Springer, Berlin, Heidelberg. 15

work page 2013
[11]

Girão, A., & Narayanan, B. (2019). Turán theorems for un avoidable patterns. arXiv preprint arXiv:1907.00964

work page internal anchor Pith review Pith/arXiv arXiv 2019
[12]

Kővari, T., Sós, V. T. & Turán, P. (1954). On a problem of K . Zarankiewicz. Colloquium Math. , 3, 50-57

work page 1954
[13]

Liu, H., Lidicky, B., & Palmer, C. (2013). On the Turán Nu mber of Forests. The Electronic Journal of Combinatorics , 20(3)-P62

work page 2013
[14]

Ramsey, F. P. (2009). On a problem of formal logic. In Classic Papers in Combinatorics (pp. 1-24). Birkhäuser Boston. 16

work page 2009

[1] [1]

Alon, N., Hoory, S., & Linial, N. (2002). The Moore bound f or irregular graphs. Graphs and Com- binatorics, 18(1), 53-57

work page 2002

[2] [2]

Caro, Y., Hansberg, A., Lauri, J., Zarb, C. (2020). On zer o-sum spanning trees and zero-sum connectivity. arXiv preprint arXiv:2007.08240

work page arXiv 2020

[3] [3]

Co lored unavoidable patterns and bal- anceable graphs, arXiv preprint, arXiv:1912.06302

Bowen, M., Hansberg, A., Montejano, A., & Müyesser, A. Co lored unavoidable patterns and bal- anceable graphs, arXiv preprint, arXiv:1912.06302

work page arXiv 1912

[4] [4]

Caro, Y., Hansberg, A., & Montejano, A. (2019). Zero-sum subsequences in bounded-sum {− 1, 1}- sequences. Journal of Combinatorial Theory, Series A , 161, 387-419

work page 2019

[5] [5]

Caro, Y., Hansberg, A., & Montejano, A. (2020). Unavoida ble chromatic patterns in 2-colorings of the complete graph. Journal of Graph Theory , to appear

work page 2020

[6] [6]

Caro, Y., Lauri, J., & Zarb, C. (2020). On small balanceab le, strongly-balanceable and omnitonal graphs. Discussiones Mathematicae Graph Theory , to appear

work page 2020

[7] [7]

Cutler, J., Montágh, B. (2008). Unavoidable subgraphs o f colored graphs. Discrete Mathematics , 308, 4396-4413

work page 2008

[8] [8]

Dailly, A., Hansberg, A., & Ventura, D. (2020). On the bal anceability of some graph classes. Discrete Applied Mathematics, to appear

work page 2020

[9] [9]

Fox, J., & Sudakov, B. (2008). Unavoidable patterns. Journal of Combinatorial Theory, Series A , 115, no. 8, 1561-1569

work page 2008

[10] [10]

Füredi, Z., & Simonovits, M. (2013). The history of dege nerate (bipartite) extremal graph problems. In Erdös Centennial (pp. 169-264). Springer, Berlin, Heidelberg. 15

work page 2013

[11] [11]

Girão, A., & Narayanan, B. (2019). Turán theorems for un avoidable patterns. arXiv preprint arXiv:1907.00964

work page internal anchor Pith review Pith/arXiv arXiv 2019

[12] [12]

Kővari, T., Sós, V. T. & Turán, P. (1954). On a problem of K . Zarankiewicz. Colloquium Math. , 3, 50-57

work page 1954

[13] [13]

Liu, H., Lidicky, B., & Palmer, C. (2013). On the Turán Nu mber of Forests. The Electronic Journal of Combinatorics , 20(3)-P62

work page 2013

[14] [14]

Ramsey, F. P. (2009). On a problem of formal logic. In Classic Papers in Combinatorics (pp. 1-24). Birkhäuser Boston. 16

work page 2009