Tur\'an-Type Extremal Results for Distance-k Graphs
Pith reviewed 2026-05-07 06:27 UTC · model grok-4.3
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.
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.
Referee Report
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, 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.
- [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, 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.
- [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
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
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
axioms (1)
- standard math Standard axioms and definitions of undirected graphs, shortest-path distances, and triangles as 3-cycles.
Reference graph
Works this paper leans on
-
[1]
B. Bollob´ as and M. Tyomkyn. Walks and paths in trees.Journal of Graph Theory, 70(1):54–66, 2012
work page 2012
- [2]
-
[3]
P. Erd˝ os. On a theorem of Rademacher-Tur´ an.Illinois J. Math, 6(122-127):1–3, 1962
work page 1962
-
[4]
M. Kang and O. Pikhurko. MaximumK r+1-free graphs which are notr-partite.Matematychni studii, 24(1):12–20, 2005
work page 2005
-
[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
work page 2015
-
[6]
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
work page 1927
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.