REVIEW 3 major objections 3 minor 11 references
Extending the Affirmative Action Problem: mixing numbers and integrated colorings of graphs
T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper counts the two-colorings in which every vertex has at least as many opposite-colored as same-colored neighbors, for complete graphs, bicliques, paths, and cycles, and bounds the count in general.
desk verdict The path and cycle mixing-number results are solid and new; Theorem 16 is false as stated and needs repair before this is publishable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central objects are integrated colorings and the mixing number. The path and cycle counts use a bijection between integrated colorings and binary strings with no three consecutive equal letters, viewed cyclically for cycles; the bivariate generating functions $F(u,z)$ and $G(u,z)$ record path length or cycle order in $z$ and mixing number in $u$. Near $u=1$, each has a unique dominant singularity $z=\zeta_1(u)$, so singularity analysis gives an asymptotic expansion of the coefficients, and a quasi-powers theorem for probability generating functions converts that expansion into a Gaussian limit law. The general bound uses a semi-random coloring of the non-pendant vertices, indicator variables for the vertices in $V''$, and the one-sided variance inequality $\Pr[X-\mathbb{E}X\ge a]\le \mathrm{Var}(X)/(\mathrm{Var}(X)+a^2)$; the quantities $\sigma^2$, $\mu$, and $V''$ are built from degree data and from the coefficients $\alpha_{i,j}(v,w)$, which count favorable color configurations for pairs of vertices.
What would settle it
Enumerate all integrated colorings of a small graph such as a triangle together with an isolated vertex, and compare the exact count with the upper bound of Theorem 16; if the bound is violated for any such graph, the theorem as stated fails.
Extended reading notes
Core claim
At the core is the observation that an integrated coloring is not the same as a maximum-cut coloring: the square circuit has integrated colorings with mixing numbers 4 and 2. The paper determines $\mathrm{IC}(G)$ and $\mathrm{ims}(G)$ exactly for four families. For $K_{2n}$, every integrated coloring has $n$ black and $n$ white vertices, giving $\mathrm{ic}(K_{2n}) = \binom{2n}{n}$ colorings, all with mixing number $n^2$; for $K_{2n-1}$ the count doubles and the mixing number is $n^2-n$. For $K_{m,n}$, the count is $2$ when one part is odd and $2 + \binom{m}{m/2}\binom{n}{n/2}$ when both are even, with mixing numbers $mn$ and $mn/2$ respectively. For paths, $\mathrm{ic}(P_n)=2F_{n-1}$ ($n\ge 2$); for cycles, $\mathrm{ic}(C_n)=L_n+2\cos(2n\pi/3)$, with $F_n$ the $n$th Fibonacci number and $L_n$ the $n$th Lucas number. Theorems 9 and 15 give a central limit theorem: the standardized mixing number of a uniformly random integrated coloring of $P_n$ or $C_n$ converges to the standard normal distribution at rate $O(n^{-1/2})$. The general bound, Theorem 16, asserts $\mathrm{ic}(G) \le \frac{\sigma^2}{\sigma^2+(|V''|-\mu)^2}\cdot 2^{|V'|}$, with Corollaries 17-19 specializing to minimum-degree, regular, and strongly regular graphs.
Load-bearing premise
The general upper bound assumes the semi-random coloring model covers every integrated coloring exactly once: pendant vertices' colors are forced by their neighbors, and all other vertices, including isolated ones, are treated as independent fair coin flips.
Editorial extensions
If this is right
- For complete graphs and bicliques, the mixing number is constant across all integrated colorings when one part is odd; only the even-even biclique case has two distinct mixing numbers, $mn/2$ and $mn$.
- For paths, the integrated mixture spectrum is exactly the integers from $\lceil(n-1)/2\rceil$ through $n-1$, so every intermediate mixing level is achievable.
- For cycles, the integrated mixture spectrum is exactly the even integers from the smallest even number at least $n/2$ through $n$.
- The number of integrated colorings of an $n$-vertex path or cycle grows like $\Theta(\varphi^n)$ with $\varphi=(1+\sqrt5)/2$, and the mixing number is concentrated about $0.7236n$ with variance about $0.6008n$.
- The second-moment bound gives a universal upper bound for $\mathrm{ic}(G)$ that is computable from the degree sequence and common-neighbor counts, with simpler forms for regular and strongly regular graphs.
Reading between the lines
- The quasi-powers route is not tied to paths and cycles: any family whose bivariate generating function for integrated colorings is rational with a unique dominant singularity should yield the same central limit theorem, so ladders, grids, or bounded-degree trees are natural next targets.
- The asymptotic mean $(\sqrt{5}/10+1/2)n \approx 0.7236n$ for both paths and cycles is close to the maximum possible mixing number $n$, so the typical integrated coloring is much nearer to fully balanced than to the minimum $(n-1)/2$; this quantifies how strongly integration constrains the mixing number.
- The second-moment bound is likely loose for sparse graphs because it discards higher-order dependencies; sharper concentration inequalities for the indicator sum could turn the bound into an exponential decay estimate for $\mathrm{ic}(G)/2^{|V'|}$.
- The exact path and cycle counts provide a null model for segregation: under a uniformly random integrated coloring, the balanced-edge count is asymptotically normal, so large deviations from this law in observed network colorings could signal non-random mixing.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies integrated colorings (unfriendly partitions) of finite graphs, in which every vertex has at least as many neighbors of the opposite color as of its own color. It gives exact characterizations and enumerations of integrated colorings for complete graphs, bicliques, paths, and cycles, together with distributions and extremal values of the mixing number (number of balanced edges). For paths and cycles it derives bivariate generating functions and proves central limit theorems for the mixing number of a uniform random integrated coloring, using singularity analysis and Hwang's quasi-powers theorem. The final section proposes a general upper bound for ic(G) via the second-moment method, with specialized bounds for regular and strongly regular graphs.
Significance. The enumerative and distributional results for paths and cycles are concrete, explicit, and follow from clearly stated generating functions and standard analytic-combinatorics tools; these are genuine strengths of the paper. The upper-bound section is ambitious and would be a useful complement to the exact results, but the main theorem in that section is not correct as stated. Since the defect is localized to Section 5 and the exact-enumeration portions appear sound, the paper is worth revising rather than rejecting.
major comments (3)
- [Section 5, Theorem 16] Theorem 16 is false as stated for simple graphs with Δ(G) ≥ 2. A concrete counterexample is G = K3 ∪ K2. For this graph, V′ consists of the three vertices of K3, V′′ = V(K3), μ = 3·(3/4) = 9/4, and σ² = 27/16, so |V′′| − μ = 3/4. The theorem's right-hand side is (27/16)/(27/16 + 9/16) · 2^3 = 6, but ic(K3 ∪ K2) = ic(K3) · ic(K2) = 6 · 2 = 12. The proof fails because the semi-random coloring assigns colors only to vertices in V′ and forces pendant vertices to the opposite color of their neighbors; in a K2 component both vertices are pendant and have no neighbor in V′, so the two colorings of that component contribute an unaccounted factor of 2. Isolated vertices, if present, similarly contribute an unaccounted factor of 2^ℓ. The theorem needs either additional hypotheses excluding K2 components and isolated vertices, or a corrected factor accounting for all components.
- [Section 5, Theorem 16] The theorem is also undefined for some graphs with Δ(G) ≥ 2. For example, take P3. Then V′ consists of the center vertex only, and since its two neighbors are pendant, λ_v = 0, so V′′ = ∅. Consequently μ = 0, σ² = 0, and |V′′| − μ = 0, making the displayed quotient 0/0. Moreover, the Chebyshev–Cantelli inequality as stated requires a > 0, whereas the proof uses a = |V′′| − μ = 0. The statement should either exclude the case V′′ = ∅ or treat it separately.
- [Section 5, proof of Theorem 16] The proof multiplies the Chebyshev–Cantelli bound by 'the total number of semi-random colorings,' implicitly 2^{|V′|}. But the probability space should be the set of all integrated colorings of the full graph. For a pendant vertex whose neighbor is also pendant, or for an isolated vertex, the described procedure does not determine a unique coloring, so the factor 2^{|V′|} is not the correct number of colorings. This is the structural reason behind the counterexample in the previous comment; the proof needs a more careful accounting of all components.
minor comments (3)
- [Section 3, first paragraph] The claim that IC(P_n) is in bijection with the set of n-bit binary strings avoiding runs of length 3 is incorrect. For P2 there are only 2 integrated colorings but 4 binary strings of length 2 avoiding runs of length 3; for P3 there are 2 integrated colorings but 6 such strings. The correct characterization is the edge-word model used in Theorem 4's proof.
- [Section 3, Theorem 4] Theorem 4 should state n ≥ 2. For n = 1 the range ⌈(n−1)/2⌉ to n−1 is 0 to 0, but the formula contains the binomial coefficient C(k−1, n−k−1) = C(−1, 0), which is not defined in the usual convention.
- [General notation] The definition of α_{i,j}(v,w) is dense; it would help readers if the boolean interpretation of i and j were stated immediately before the formula, rather than in the paragraph after it.
Circularity Check
No circularity: the derivation chain is self-contained and uses only external standard theorems and explicit combinatorial decompositions.
full rationale
The paper's enumerations are derived from explicit bijections and generating-function decompositions. The path counts are Fibonacci numbers from binary strings avoiding runs of length 3; the cycle counts are obtained from a tiling decomposition attributed to external prior work; the distributions of mixing numbers are counted by stars-and-bars arguments. No target quantity is inserted as an input to these derivations. The central limit theorems apply the external Flajolet-Odlyzko transfer theorem and Hwang's quasi-powers theorem to bivariate generating functions whose coefficients are the enumerated quantities; the assumptions of these theorems do not include the conclusion. The general upper bound in Theorem 16 is a standard probabilistic-method argument: a semi-random coloring is defined independently of ic(G), the expectation µ and variance σ² are computed from that model, and Chebyshev-Cantelli bounds the probability that a random coloring is integrated. Multiplying by the number of semi-random colorings gives an upper bound on ic(G); no fitted parameter is renamed as a prediction. All cited results are external textbooks, theorems, and OEIS entries; there is no load-bearing self-citation. Potential correctness issues with Theorem 16 for graphs with disjoint K2 components or with V'' empty would be soundness concerns, not circularity, and do not affect this audit.
Assumptions & free parameters
assumptions (3)
- standard math Flajolet-Odlyzko transfer theorem
- standard math Hwang's quasi-powers theorem
- standard math Chebyshev-Cantelli inequality
Cite this review
Pith. "Pith review of Extending the Affirmative Action Problem: mixing numbers and integrated colorings of graphs." pith.science (2026). https://pith.science/paper/DT22BU7E
@misc{pith2026250607192,
author = {Pith},
title = {Pith review of: Extending the Affirmative Action Problem: mixing numbers and integrated colorings of graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/DT22BU7E}},
note = {Machine review of arXiv:2506.07192}
}
read the original abstract
Consider a graph whose vertices are colored in one of two colors, say black or white. A white vertex is called integrated if it has at least as many black neighbors as white neighbors, and similarly for a black vertex. The coloring as a whole is integrated if every vertex is integrated. A classic exercise in graph theory, known as the Affirmative Action Problem, is to prove that every finite simple graph admits an integrated coloring. The solution can be neatly summarized with the one-liner: "maximize the number of balanced edges," that is, the edges that connect neighbors of different colors. However, not all integrated colorings advertise the maximum possible number of balanced edges. In this paper, we characterize and enumerate the integrated colorings for complete graphs, bicliques, paths, and cycles. We also derive the distributions and extremal values for the mixing numbers (the number of balanced edges) across all integrated colorings over these families of graphs. For paths and cycles in particular, we use the quasi-powers framework for probability generating functions to prove a central limit theorem for the mixing number of random integrated colorings. Lastly, we obtain an upper bound for the number of integrated colorings over any fixed graph via the second-moment method. A specialized bound for the number of integrated colorings over a regular graph is also obtained.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
Aharoni, R. and Milner, E. C. and Prikry, K. , Unfriendly partitions of a graph , J. Combin. Theory Ser. B , 50 , (1990), no. 1, 1--10
work page 1990
-
[2]
Benjamin, Arthur T. and Quinn, Jennifer J. , Proofs that really count , Mathematical Association of America, Washington, DC , (2003), ISBN 0-88385-333-7
work page 2003
-
[3]
Cowen, Robert , Mixing numbers and unfriendly colorings of graphs , Mathematica J. , 23 , (2021), Paper No. 4
work page 2021
-
[4]
Edwards, C. S. , An improved lower bound for the number of edges in a largest bipartite subgraph , P roc. S econd C zechoslovak S ympos. , P rague, (1974), 167--181
work page 1974
-
[5]
Edwards, C. S. , Some extremal properties of bipartite subgraphs , Canadian J. Math. , 25 , (1978), 475--485
work page 1978
-
[6]
Flajolet, Philippe and Odlyzko, Andrew , Singularity analysis of generating functions , SIAM J. Discrete Math. , 3 , (1990), no. 2, 216--240
work page 1990
-
[7]
Flajolet, Philippe and Sedgewick, Robert , Analytic combinatorics , Cambridge University Press, Cambridge , (2009), ISBN 978-0-521-89806-5
work page 2009
-
[8]
Hwang, Hsien-Kuei , On convergence rates in the central limit theorems for combinatorial structures , European J. Combin. , 19 , (1998), no. 3, 329--343
work page 1998
Show all 11 references
-
[9]
, Dynamics groups of asynchronous cellular automata , J
Macauley, Matthew and McCammond, Jon and Mortveit, Henning S. , Dynamics groups of asynchronous cellular automata , J. Algebraic Combin. , 33 , (2011), no. 1, 11--35
2011
-
[10]
The On-Line Encyclopedia of Integer Sequences , available electronically at oeis.org
-
[11]
Zeitz, Paul , The art and craft of problem solving , 3rd ed., John Wiley & Sons, Inc., Hoboken, NJ , (2017), ISBN 978-1-119-23990-1
2017
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.