Pith. sign in

REVIEW 5 minor 16 references

Paths of even length with equal-degree endpoints

T0 review · 0 major / 5 minor · reviewed 2026-07-11 · grok-4.5

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

Pith's one-line read For even-length paths of fixed length, the half graph is the unique densest 2n-vertex graph with no equal-degree endpoints.

desk verdict Solid resolution of the even-length uniqueness problem for half-graphs; long but complete proof with only the usual asymptotic caveat. read the letter →

arxiv 2607.04368 v1 pith:KT2RTOLL submitted 2026-07-05 math.CO

Kaizhe Chen , Zhen Liu , Qinghou Zeng This is my paper · ORCID
classification math.CO MSC 05C3505C38
keywords halfgraphequal-degreeendpointspathsofevenlengthextremaltheorydegreesequencesErdős–Hajnalproblem
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

The paper settles a natural even-length counterpart of a classical question of Erdős and Hajnal: how many edges can an n-vertex graph have without two equal-degree vertices joined by a path of prescribed length. Earlier work had completely resolved the odd-length case, with the complete bipartite graph K_{n,n+1} as the unique extremal example. Here the authors prove that for every fixed even length 2ℓ with ℓ ≥ 2 and all sufficiently large n, the unique 2n-vertex graph with at least (n² + n)/2 edges that avoids equal-degree endpoints on a 2ℓ-path is the half graph H_n. The half graph is the bipartite graph on parts of size n in which the i-th vertex of one side is joined to the first i vertices of the other side; it already meets the edge bound and contains no forbidden configuration. The result answers an open problem of Chen and Ma and confirms an asymptotic density conjecture of Attwa et al. for even lengths.

What carries the argument

A controlled decomposition of neighborhoods of equal-degree pairs (the sets A_s, A_t, B_st, Y_st and the 2ℓ+4-core of induced subgraphs) together with multiset-sum bounds that force the maximum equal degree β to equal n and the graph to be exactly H_n.

What would settle it

Exhibit, for some fixed ℓ ≥ 2 and arbitrarily large n, a 2n-vertex graph with at least (n² + n)/2 edges that is not isomorphic to H_n yet still has no equal-degree pair joined by a 2ℓ-path.

Watch

Extended reading notes

Core claim

For every fixed integer ℓ ≥ 2 and all sufficiently large n, the half graph H_n is the unique graph on 2n vertices with at least (n² + n)/2 edges that contains no two vertices of equal degree joined by a path of length 2ℓ.

Load-bearing premise

The uniqueness statement holds only for all n larger than some (unspecified) constant depending on ℓ, because the proof relies on asymptotic error terms that dominate only when n is large enough.

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.

Referee Report

0 major / 5 minor

Summary. The paper proves that for every fixed integer ℓ ≥ 2 and all sufficiently large n, the half-graph H_n is the unique graph on 2n vertices with at least (n^{2} + n)/2 edges that contains no two equal-degree vertices joined by a path of length 2ℓ (Theorem 1.5). This determines the extremal function p_{2ℓ}(2n) exactly for large n, answers Problem 1.3 of Chen–Ma, and settles the asymptotic question of Attwa et al. (Problem 1.4). The argument proceeds by controlling the set R of vertices of degree ≥ n + ℓ + 1 (Lemmas 3.1–3.6), analysing equal-degree pairs via a four-layer core decomposition of exclusive neighbourhoods (Lemma 3.7), a multiset degree-sum bound (Lemma 2.3), and a sequence of degree-sequence contradictions that force the maximum equal degree eta to equal n and the graph to be isomorphic to H_n (Lemmas 3.9–3.18).

Significance. The result completes the even-length half of the Erdős–Hajnal-type programme initiated by Chen–Ma and continued by Liu–Zeng, Zhao–Wang–Lu and Attwa et al. It supplies a new extremal characterisation of the half-graph, an object of independent interest in model theory and structural graph theory. The proof is fully self-contained, relies only on classical tools (Erdős–Gallai, Naor–Verstraëte), and contains no free parameters or circular reductions. The uniqueness statement is asymptotic, which is the natural level of precision for this series of problems.

minor comments (5)
  1. [Notation / Lemma 3.7] The constant 2ℓ + 4 that defines core(H) is never justified beyond the greedy path-construction needs of Lemma 3.7(a). A short remark that any larger constant works and that 2ℓ + 4 is chosen only for convenience would improve readability.
  2. [Lemma 2.3] Lemma 2.3 is stated for a multiset of 2n integers each at most n; the three cases on α are carefully checked, but the final O(n) terms are absorbed without an explicit lower bound on n. Adding a parenthetical “for n ≥ N(ℓ)” would make the dependence transparent.
  3. [Notation paragraph after D_st] In the definition of the four-layer sets A_{s,i} the intersection with the ambient exclusive neighbourhood is written twice; a single sentence clarifying that the core is taken first and then intersected would remove a minor notational redundancy.
  4. [Throughout §3] Several places write “O_ℓ(n^{3/2})” while others write “O(ℓ n^{3/2})”. Uniformising the subscript notation would avoid any momentary confusion.
  5. [Introduction and Lemma 3.18] The half-graph is introduced with the classical bipartition {u_i} imes {v_j}, i ≥ j; later the proof reconstructs an isomorphic labelling with parts of size n. A one-line remark that the two presentations differ only by a relabelling would help the reader match the final construction with the definition.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained combinatorial proof of uniqueness for even-length paths

full rationale

The derivation of Theorem 1.5 proceeds entirely by direct arguments: high-degree vertex control (Lemmas 3.1–3.6), core decompositions and path-avoidance for equal-degree pairs (Lemma 3.7), multiset degree-sum bounds (Lemma 2.3), and successive contradictions forcing β = n and the half-graph adjacency rule (Lemmas 3.9–3.18). All thresholds (e.g., 300ℓ√n, 2ℓ+4) are chosen for convenience inside the estimates and do not feed back into the statement. Self-citations ([4], [11], [12]) refer to odd-length or related cases treated by overlapping authors; none is invoked as a black-box uniqueness theorem that forces the even-length conclusion. The half-graph lower bound is elementary and independent. No definitional loop, fitted parameter, or load-bearing self-citation reduces the claim to its inputs.

Assumptions & free parameters 0 free parameters · 3 assumptions · 2 invented entities

The paper is a pure existence/uniqueness theorem in extremal graph theory. It relies only on two classical external theorems and on standard graph-theoretic definitions; no free parameters are fitted and no new physical or combinatorial entities are postulated beyond technical auxiliary sets used inside the proof.

assumptions (3)
  • standard math Erdős–Gallai theorem: a graph with no path of length k has at most ((k-1)/2)|V| edges (Theorem 2.1).
    Invoked repeatedly to bound edges inside B_st, H_Bst and other induced subgraphs that would otherwise create a forbidden 2ℓ-path.
  • standard math Naor–Verstraëte bound on the extremal number ex(m,n,C_{2k}) (Theorem 2.2).
    Used in the greedy construction of S in Lemma 3.10 to obtain a C_{2ℓ}-free bipartite graph and derive a contradiction.
  • standard math Every finite graph on ≥2 vertices has two vertices of equal degree (classical hand-shaking fact).
    Background motivation; the whole problem is a density refinement of this fact.
invented entities (2)
  • core(H) — the unique maximal induced subgraph of minimum degree ≥2ℓ+4
    purpose: Technical device that isolates a high-minimum-degree piece inside which short paths can be built greedily (Lemma 3.7(a)).
    Defined ad hoc for the proof; no independent existence claim outside the paper.
  • Four-layer partition A_{s,i} (i=1..4) of the exclusive neighborhoods of an equal-degree pair
    purpose: Organizes vertices according to the cores of successive bipartite graphs so that path-extension lemmas apply only on the high-degree layers.
    Purely definitional scaffolding; disappears once the uniqueness is proved.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Paths of even length with equal-degree endpoints." pith.science (2026). https://pith.science/paper/KT2RTOLL

@misc{pith2026260704368,
  author       = {Pith},
  title        = {Pith review of: Paths of even length with equal-degree endpoints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KT2RTOLL}},
  note         = {Machine review of arXiv:2607.04368}
}
abstract

Addressing a question posed by Erd\H{o}s and Hajnal, Chen and Ma proved that, for all $n \ge 600$, the complete bipartite graph $K_{n,n+1}$ is the unique graph on $2n+1$ vertices with at least $n^2+n$ edges that contains no two vertices of equal degree joined by a path of length three. In this paper, we extend this result and prove that for every fixed integer \(\ell\ge 2\) and sufficiently large \(n\), the unique \(2n\)-vertex graph with at least \((n^2+n)/2\) edges that contains no two vertices of equal degree joined by a path of length \(2\ell\) is the half graph \(H_n\). This resolves the problem posed by Chen and Ma, as well as a related question of Attwa, Az\'ocar Carvajal, Boyadzhiyska, Pierron, and Taraz concerning paths of even length with equal-degree endpoints.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 4 linked inside Pith

  1. [1]

    N. Alon, J. Fox and Y . Zhao, Efficient arithmetic regularity and removal lemmas for induced bipartite patterns,Discrete Anal.(2019), Paper No. 3, 14 pp

    2019

  2. [2]

    Attwa, M

    Y . Attwa, M. Az ´ocar Carvajal, S. Boyadzhiyska, T. Pierron and A. Taraz, The density of graphs with noℓ-path connecting equal-degree vertices: A short proof,arXiv preprint arXiv:2605.09798(2026)

    arXiv 2026

  3. [3]

    T. F. Bloom, Erd˝os Problem #816,https://www.erdosproblems.com/816, accessed May 28, 2026. 21

    2026

  4. [4]

    Chen and J

    K. Chen and J. Ma, A problem of Erd ˝os and Hajnal on paths with equal-degree endpoints,J. Combin. Theory Ser . B179 (2026), 1–18

    2026

  5. [5]

    Chudnovsky, R

    M. Chudnovsky, R. Kim, S.-I. Oum and P. Seymour, Unavoidable induced subgraphs in large graphs with no homogeneous sets,J. Combin. Theory Ser . B118 (2016), 1–12

    2016

  6. [6]

    Dreier, I

    J. Dreier, I. Eleftheriadis, N. M ¨ahlmann, R. McCarty, M. Pilipczuk and S. Toru´nczyk, First- order model checking on monadically stable graph classes, inProceedings of the 2024 IEEE 65th Annual Symposium on F oundations of Computer Science (FOCS), IEEE, 2024, 21–30

    2024

  7. [7]

    Erd ˝os and T

    P. Erd ˝os and T. Gallai, On maximal paths and circuits of graphs,Acta Math. Acad. Sci. Hungar .10 (1959), 337–356

    1959

  8. [8]

    Erd ˝os, Some combinatorial, geometric and set theoretic problems in measure theory, in D

    P. Erd ˝os, Some combinatorial, geometric and set theoretic problems in measure theory, in D. K¨olzow and D. Maharam-Stone (eds.),Measure Theory, Oberwolfach 1983, Lecture Notes in Mathematics, vol. 1089, Springer, Berlin, 1984, pp. 321–327

    1983

Show all 16 references
  1. [9]

    Erd ˝os and A

    P. Erd ˝os and A. Hajnal, Chromatic number of finite and infinite graphs and hypergraphs, Discrete Math.53 (1985), 281–285

    1985

  2. [10]

    Erd ˝os, Problems and results in combinatorial analysis and combinatorial number theory, in Graph Theory, Combinatorics, and Applications, V ol

    P. Erd ˝os, Problems and results in combinatorial analysis and combinatorial number theory, in Graph Theory, Combinatorics, and Applications, V ol. 1 (Kalamazoo, MI, 1988), Wiley, New York, 1991, pp. 397–406

    1988

  3. [11]

    Liu and Q

    Z. Liu and Q. Zeng, A complement of the Erd ˝os-Hajnal problem on paths with equal-degree endpoints,arXiv preprint arXiv:2505.00523(2025)

    2025 arXiv

  4. [12]

    Liu and Q

    Z. Liu and Q. Zeng, Paths of length five with equal-degree endpoints,arXiv preprint arXiv:2604.11664(2026)

    2026 arXiv

  5. [13]

    Malliaris and S

    M. Malliaris and S. Shelah, Regularity lemmas for stable graphs,Trans. Amer . Math. Soc. 366 (2014), 1551–1585

    2014

  6. [14]

    Naor and J

    A. Naor and J. Verstra ¨ete, A Note on Bipartite Graphs Without 2k-Cycles,Combin. Probab. Comput.14 (2005), 845–849

    2005

  7. [15]

    Ne ˇsetˇril, P

    J. Ne ˇsetˇril, P. Ossona de Mendez, M. Pilipczuk, R. Rabinovich and S. Siebertz, Rankwidth meets stability, inProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2021, pp. 2014–2033

    2021

  8. [16]

    X. Zhao, Y . Wang and M. Lu, A generalization of the Erd ˝os-Hajnal problem on paths with equal-degree endpoints,arXiv preprint arXiv:2605.03825(2026). 22

    2026 arXiv

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.