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
- Christopher Mills (ORCID: https://orcid.org/0000-0003-0003-0552)
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