pith. sign in

arxiv: 2604.28060 · v1 · submitted 2026-04-30 · 🧮 math.CO

Tur\'an-Type Extremal Results for Distance-k Graphs

Zhen He , Nika Salia , Casey Tompkins , Xiutao Zhu This is my paper

Pith reviewed 2026-05-07 06:27 UTC · model grok-4.3

classification 🧮 math.CO
keywords extremal graph theorydistance graphsTurán-type problemsTyomkyn-Uzzell conjecturetriangle-free graphsdistance-k graphsgraph distance
0
0 comments X

The pith

The maximum number of vertex pairs at distance three in an n-vertex graph with no triangle formed by these pairs is determined, resolving the first case of a conjecture of Tyomkyn and Uzzell.

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

This paper examines Turán-type extremal problems for distance graphs. It determines the largest possible number of pairs of vertices at exact distance three such that no three of these pairs form a triangle. This resolves the opening case of a conjecture by Tyomkyn and Uzzell. The work further settles the distance-two version by giving both the exact maximum count and a complete description of all graphs attaining it. These results supply precise bounds and structural information for distance-based extremal questions.

Core claim

We determine the maximum number of vertex pairs at distance three in an n-vertex graph with no triangle formed by these pairs, resolving the first case of a conjecture of Tyomkyn and Uzzell. We also determine the maximum number of vertex pairs at distance two in an n-vertex graph with no triangle formed by these pairs and give a complete characterization of the extremal graphs, settling another problem of Tyomkyn and Uzzell.

What carries the argument

The distance-k graph (vertices joined if at distance exactly k in the host graph) required to be triangle-free, together with the extremal function counting its edges.

Load-bearing premise

The Tyomkyn-Uzzell conjectures correctly formulate the extremal problems for distance graphs and standard graph-theoretic definitions and techniques apply without hidden restrictions on n.

What would settle it

An explicit n-vertex graph whose set of distance-three pairs exceeds the claimed maximum while forming no triangle would disprove the result.

read the original abstract

We study Tur\'an-type extremal problems for distance graphs, motivated by work of Csikv\'ari, Bollob\'as, Tyomkyn, and Uzzell. We determine the maximum number of vertex pairs at distance three in an $n$-vertex graph with no triangle formed by these pairs, resolving the first case of a conjecture of Tyomkyn and Uzzell. We also determine the maximum number of vertex pairs at distance two in an $n$-vertex graph with no triangle formed by these pairs and give a complete characterization of the extremal graphs, settling another problem of Tyomkyn and Uzzell.

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.

Referee Report

0 major / 4 minor

Summary. The paper studies Turán-type extremal problems for distance graphs. It determines the maximum number of vertex pairs at distance three in an n-vertex graph whose distance-3 graph is triangle-free, resolving the first case of a conjecture of Tyomkyn and Uzzell. It also determines the maximum number of vertex pairs at distance two under the same triangle-free condition on the distance-2 graph and gives a complete characterization of the extremal host graphs, settling another problem of the same authors.

Significance. If the proofs are correct, the results resolve two open problems in extremal graph theory by providing exact extremal functions ex(n, {C_3}, dist-k) for k=2,3 together with structural characterizations. The work extends classical Turán theory to distance graphs using stability and counting arguments, and the explicit constructions and upper bounds supply falsifiable predictions that can be checked for small n. This supplies a template for higher-distance cases and related forbidden configurations.

minor comments (4)
  1. [§1] §1, paragraph 3: the statement of the Tyomkyn–Uzzell conjecture for distance-3 graphs should be quoted verbatim (or referenced to a numbered equation) so that the precise extremal function being determined is unambiguous.
  2. [Theorem 1.2] Theorem 1.2 (distance-2 case): the characterization of extremal graphs lists several families; it is unclear whether the proof shows these are the only ones for all n or only for n sufficiently large. A short remark on the range of n would help.
  3. [§3] §3, proof of the upper bound: the stability argument invokes a lemma whose hypothesis requires n > n_0; the paper should state explicitly what n_0 is and verify the small-n cases separately or note that they follow by direct computation.
  4. [Figure 1] Figure 1: the drawing of the extremal graph for distance 3 is helpful, but the caption should indicate the value of n and the exact number of distance-3 edges achieved.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and supportive report, which recognizes that our results resolve two open problems from Tyomkyn and Uzzell by determining the extremal functions ex(n, {C_3}, dist-k) for k=2,3 along with structural characterizations. The referee recommends minor revision, but the report contains no specific major comments, criticisms, or requests for changes. We will therefore prepare a revised manuscript incorporating any minor improvements to presentation, clarity, or typographical matters.

Circularity Check

0 steps flagged

No significant circularity; resolves external conjecture with self-contained proofs

full rationale

The paper determines the extremal numbers for triangle-free distance-2 and distance-3 graphs, explicitly resolving the first case of the Tyomkyn-Uzzell conjecture and settling another problem posed by those authors. The provided abstract and context indicate that the arguments use standard stability, counting, and characterization techniques applicable directly to the imposed triangle-free condition on the distance graphs. No load-bearing steps reduce by construction to fitted parameters, self-definitions, or self-citation chains; the central claims are independent resolutions of external conjectures rather than renamings or tautological derivations. The derivation is therefore self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work is a pure combinatorial result in extremal graph theory that relies on standard definitions and theorems from graph theory with no additional free parameters, ad hoc axioms, or newly invented entities.

axioms (1)
  • standard math Standard axioms and definitions of undirected graphs, shortest-path distances, and triangles as 3-cycles.
    These foundational elements of graph theory are invoked throughout without proof, as is conventional in the field.

pith-pipeline@v0.9.0 · 5408 in / 1445 out tokens · 124720 ms · 2026-05-07T06:27:26.690461+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

6 extracted references

  1. [1]

    Bollob´ as and M

    B. Bollob´ as and M. Tyomkyn. Walks and paths in trees.Journal of Graph Theory, 70(1):54–66, 2012

    2012

  2. [2]

    Csikv´ ari

    P. Csikv´ ari. On a poset of trees.Combinatorica, 30(2):125–137, 2010

    2010

  3. [3]

    P. Erd˝ os. On a theorem of Rademacher-Tur´ an.Illinois J. Math, 6(122-127):1–3, 1962

    1962

  4. [4]

    Kang and O

    M. Kang and O. Pikhurko. MaximumK r+1-free graphs which are notr-partite.Matematychni studii, 24(1):12–20, 2005

    2005

  5. [5]

    X. Li, J. Ma, Y. Shi, and J. Yue. Note on a Tur´ an-type problem on distances.Ars Comb., 119:211– 219, 2015

    2015

  6. [6]

    Tyomkyn and A

    M. Tyomkyn and A. J. Uzzell. A Tur´ an-type problem on distances in graphs.Graphs and Combi- natorics, 29(6):1927–1942, 2013. 15

    1927