Back to Search
Start Over
An extremal problem motivated by triangle-free strongly regular graphs.
- Source :
-
Journal of Combinatorial Theory - Series B . Jul2022, Vol. 155, p52-82. 31p. - Publication Year :
- 2022
-
Abstract
- We introduce the following combinatorial problem. Let G be a triangle-free regular graph with edge density ρ. (In this paper all densities are normalized by n , n 2 2 etc. rather than by n − 1 , ( n 2 ) , ...) What is the minimum value a (ρ) for which there always exist two non-adjacent vertices such that the density of their common neighbourhood is ≤ a (ρ) ? We prove a variety of upper bounds on the function a (ρ) that are tight for the values ρ = 2 / 5 , 5 / 16 , 3 / 10 , 11 / 50 , with C 5 , Clebsch, Petersen and Higman-Sims being respective extremal configurations. Our proofs are entirely combinatorial and are largely based on counting densities in the style of flag algebras. For small values of ρ , our bound attaches a combinatorial meaning to so-called Krein conditions that might be interesting in its own right. We also prove that for any ϵ > 0 there are only finitely many values of ρ with a (ρ) ≥ ϵ but this finiteness result is somewhat purely existential (the bound is double exponential in 1 / ϵ). [ABSTRACT FROM AUTHOR]
- Subjects :
- *REGULAR graphs
*MOTIVATION (Psychology)
*GRAPH theory
*FINITE, The
*ALGEBRA
Subjects
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 155
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 156472336
- Full Text :
- https://doi.org/10.1016/j.jctb.2022.02.001