The Balanced Bipartite Edge Count, and Three Anti-Ramsey Regimes

The Turán threshold for triangle-freeness, $ n^2/4 $, is not merely a bound: it is the edge count of a specific graph, the balanced complete bipartite graph on $n$ vertices. We prove the identity $ n/2 n/2 = n^2/4 $ by a split on parity, so that the phrase ``one edge above the Turán threshold'' names an object rather than a quantity. Above that threshold the anti-Ramsey function for odd cycles falls into three regimes as the cycle length grows: constant at $C_3$, linear at $C_5$, and quadratic from $C_7$ onward. The three are a partition of the parameter, and the linear formula falls below the quadratic one from $n = 8$, so the transition at $k = 3$ is a change of order in $n$.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-09-21
DOI
https://doi.org/10.5281/zenodo.22849350
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

The Balanced Bipartite Edge Count, and Three Anti-Ramsey Regimes

Christopher Mills
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

The Balanced Bipartite Edge Count, and Three Anti-Ramsey Regimes

Christopher Mills
preprint en

Abstract

The Turán threshold for triangle-freeness, $ n^2/4 $, is not merely a bound: it is the edge count of a specific graph, the balanced complete bipartite graph on $n$ vertices. We prove the identity $ n/2 n/2 = n^2/4 $ by a split on parity, so that the phrase ``one edge above the Turán threshold'' names an object rather than a quantity. Above that threshold the anti-Ramsey function for odd cycles falls into three regimes as the cycle length grows: constant at $C_3$, linear at $C_5$, and quadratic from $C_7$ onward. The three are a partition of the parameter, and the linear formula falls below the quadratic one from $n = 8$, so the transition at $k = 3$ is a change of order in $n$.

Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.