<p>In this note, we consider a more general version of local sparsity introduced recently by Anderson, Kuchukova, and the author. In particular, we say a graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G = (V, E)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is (<i>k</i>,&#xa0;<i>r</i>)-locally sparse if, for each vertex <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(v \in V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, the subgraph induced by its neighborhood contains at most <i>k</i> cliques of size <i>r</i>. For <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(r \geqslant 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>⩾</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\varepsilon \in [0, 1]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>, we show that an <i>n</i>-vertex <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\((\Delta ^{\varepsilon r}, r)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msup> <mi mathvariant="normal">Δ</mi> <mrow> <mi>ε</mi> <mi>r</mi> </mrow> </msup> <mo>,</mo> <mi>r</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-locally sparse graph <i>G</i> of maximum degree <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\Delta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Δ</mi> </math></EquationSource> </InlineEquation> satisfies <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\alpha (G) \geqslant (1-o(1))\dfrac{n}{\eta \Delta }\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>⩾</mo> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <mi>o</mi> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mstyle displaystyle="true" scriptlevel="0"> <mfrac> <mi>n</mi> <mrow> <mi>η</mi> <mi mathvariant="normal">Δ</mi> </mrow> </mfrac> </mstyle> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\chi (G) \leqslant \Theta \left( \eta \Delta \right) \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>⩽</mo> <mi mathvariant="normal">Θ</mi> <mfenced close=")" open="("> <mi>η</mi> <mi mathvariant="normal">Δ</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\eta :==\varepsilon + \dfrac{r\log \log \Delta }{\log \Delta }\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>η</mi> <mo>:</mo> <mo>=</mo> <mo>=</mo> <mi>ε</mi> <mo>+</mo> <mstyle displaystyle="true" scriptlevel="0"> <mfrac> <mrow> <mi>r</mi> <mo>log</mo> <mo>log</mo> <mi mathvariant="normal">Δ</mi> </mrow> <mrow> <mo>log</mo> <mi mathvariant="normal">Δ</mi> </mrow> </mfrac> </mstyle> </mrow> </math></EquationSource> </InlineEquation>. For <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation> not too large, the hidden constant in the <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\Theta (\cdot )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mo>·</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> can be taken to be <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(1+o(1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>+</mo> <mi>o</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Setting <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\varepsilon = 0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, we recover classical results on <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(K_{r+1}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mi>r</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation>-free graphs due to Shearer and Johansson, which were more recently improved by Davies, Kang, Pirot, and Sereni. We prove a stronger result on the independence number in terms of the occupancy fraction in the hard-core model, and establish a local version of the coloring result in the more general setting of correspondence coloring.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Bounds for the Independence and Chromatic Numbers of Locally Sparse Graphs

  • Abhishek Dhawan

摘要

In this note, we consider a more general version of local sparsity introduced recently by Anderson, Kuchukova, and the author. In particular, we say a graph \(G = (V, E)\) G = ( V , E ) is (kr)-locally sparse if, for each vertex \(v \in V(G)\) v V ( G ) , the subgraph induced by its neighborhood contains at most k cliques of size r. For \(r \geqslant 3\) r 3 and \(\varepsilon \in [0, 1]\) ε [ 0 , 1 ] , we show that an n-vertex \((\Delta ^{\varepsilon r}, r)\) ( Δ ε r , r ) -locally sparse graph G of maximum degree \(\Delta \) Δ satisfies \(\alpha (G) \geqslant (1-o(1))\dfrac{n}{\eta \Delta }\) α ( G ) ( 1 - o ( 1 ) ) n η Δ and \(\chi (G) \leqslant \Theta \left( \eta \Delta \right) \) χ ( G ) Θ η Δ , where \(\eta :==\varepsilon + \dfrac{r\log \log \Delta }{\log \Delta }\) η : = = ε + r log log Δ log Δ . For \(\varepsilon \) ε not too large, the hidden constant in the \(\Theta (\cdot )\) Θ ( · ) can be taken to be \(1+o(1)\) 1 + o ( 1 ) . Setting \(\varepsilon = 0\) ε = 0 , we recover classical results on \(K_{r+1}\) K r + 1 -free graphs due to Shearer and Johansson, which were more recently improved by Davies, Kang, Pirot, and Sereni. We prove a stronger result on the independence number in terms of the occupancy fraction in the hard-core model, and establish a local version of the coloring result in the more general setting of correspondence coloring.