A new series of dense graphs of high girth 论文

摘要

Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k greater-than-or-equal-to 1"> <mml:semantics> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo> ≥ </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">k \geq 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be an odd integer, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="t equals left floor StartFraction k plus 2 Over 4 EndFraction right floor"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>t</mml:mi> <mml:mo>=</mml:mo> <mml:mrow> <mml:mo>⌊</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mstyle displaystyle="false" scriptlevel="0"> <mml:mfrac> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:mn>4</mml:mn> </mml:mfrac> </mml:mstyle> </mml:mrow> <mml:mo>⌋</mml:mo> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{t = \left \lfloor {\tfrac {{k + 2}}{4}} \right \rfloor }</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and <italic>q</italic> be a prime power. We construct a bipartite, <italic>q</italic> -regular, edge-transitive graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C upper D left-parenthesis k comma q right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>C</mml:mi> <mml:mi>D</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>q</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">CD(k,q)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upsilon less-than-or-equal-to 2 q Superscript k minus t plus 1"> <mml:semantics> <mml:mrow> <mml:mi> υ </mml:mi> <mml:mo> ≤ </mml:mo> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>q</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo> − </mml:mo> <mml:mi>t</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\upsilon \leq 2{q^{k - t + 1}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and girth <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="g greater-than-or-equal-to k plus 5"> <mml:semantics> <mml:mrow> <mml:mi>g</mml:mi> <mml:mo> ≥ </mml:mo> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>5</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">g \geq k + 5</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . If <italic>e</italic> is the the number of edges of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C upper D left-parenthesis k comma q right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>C</mml:mi> <mml:mi>D</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>q</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">CD(k,q)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , then <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="e equals normal upper Omega left-parenthesis upsilon Superscript 1 plus StartFraction 1 Over k minus t plus 1 EndFraction Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>e</mml:mi> <mml:mo>=</mml:mo> <mml:mi mathvariant="normal"> Ω </mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi> υ </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo> − </mml:mo> <mml:mi>t</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">e = \Omega ({{\upsilon ^{1 + \frac {1}{{k - t + 1}}}}})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . These graphs provide the best known asymptotic lower bound for the greatest number of edges in graphs of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upsilon"> <mml:semantics> <mml:mi> υ </mml:mi> <mml:annotation