论文标题
由无三角形的强烈规则图所激发的极端问题
An Extremal Problem Motivated by Triangle-Free Strongly Regular Graphs
论文作者
论文摘要
我们介绍了以下组合问题。令$ g $为带有边缘密度$ρ$的无三角常规图。最小值$ a（ρ）$总是存在的两个非贴剂的顶点是什么，使他们的公共邻域的密度为$ \ leq a（ρ）$？我们证明了函数$ a（ρ）$的各种上限，对于值$ρ= 2/5，\ 5/16，\ 3/10，\ 11/50 $，带有$ C_5 $，CLEBSCH，PETERSEN和HIGMAN-SIMS是各自的极端配置。我们的证明完全是组合的，主要基于以国旗代数的方式计数密度。对于$ρ$的少量值，我们的界限将组合含义附加到凯林条件上，这本身可能很有趣。我们还证明，对于任何$ε> 0 $，只有$ a（ρ）\geqε$有限的$ρ$有限的值，但是这种有限的结果有些纯粹存在（绑定为$ 1/ε$的双重指数）。
We introduce the following combinatorial problem. Let $G$ be a triangle-free regular graph with edge density $ρ$. What is the minimum value $a(ρ)$ for which there always exist two non-adjacent vertices such that the density of their common neighborhood is $\leq 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 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(ρ)\geqε$ but this finiteness result is somewhat purely existential (the bound is double exponential in $1/ε$).
