<p>The generalized <i>q</i>-Kneser graph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_q(n,k,t)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mi>q</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for integers <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">\(k&gt;t&gt;0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>&gt;</mo> <mi>t</mi> <mo>&gt;</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq3.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">\(n&gt;2k-t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>&gt;</mo> <mn>2</mn> <mi>k</mi> <mo>-</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation> is the graph whose vertices are the <i>k</i>-dimensional subspaces of an <i>n</i>-dimensional <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(F_q\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mi>q</mi> </msub> </math></EquationSource> </InlineEquation>-vector space with two vertices <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(U_1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>U</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(U_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>U</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> adjacent if and only if <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="126" /> </InlineMediaObject> <EquationSource Format="TEX">\(\dim (U_1\cap U_2)&lt;t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>dim</mo> <mo stretchy="false">(</mo> <msub> <mi>U</mi> <mn>1</mn> </msub> <mo>∩</mo> <msub> <mi>U</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> <mo>&lt;</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation>. We determine the treewidth of the generalized <i>q</i>-Kneser graphs <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_q(n,k,t)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mi>q</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> when <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq9.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(t\ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and <i>n</i> is sufficiently large compared to <i>k</i>. The imposed bound on <i>n</i> is a significant improvement of the previously known bound. One consequence of our results is that the treewidth of each <i>q</i>-Kneser graph <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq1.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_q(n,k,t)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mi>q</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">\(k&gt;t&gt;0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>&gt;</mo> <mi>t</mi> <mo>&gt;</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq12.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="107" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\ge 3k-t+9\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>3</mn> <mi>k</mi> <mo>-</mo> <mi>t</mi> <mo>+</mo> <mn>9</mn> </mrow> </math></EquationSource> </InlineEquation> is equal to <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1674_Article_IEq13.gif" Format="GIF" Height="27" Rendition="HTML" Resolution="72" Type="Linedraw" Width="125" /> </InlineMediaObject> <EquationSource Format="TEX">\({n\brack k}_q-{n-t\brack k-t}_q-1.\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mfenced close="]" open="["> <mfrac linethickness="0pt"> <mi>n</mi> <mi>k</mi> </mfrac> </mfenced> <mi>q</mi> </msub> <mo>-</mo> <msub> <mfenced close="]" open="["> <mfrac linethickness="0pt"> <mrow> <mi>n</mi> <mo>-</mo> <mi>t</mi> </mrow> <mrow> <mi>k</mi> <mo>-</mo> <mi>t</mi> </mrow> </mfrac> </mfenced> <mi>q</mi> </msub> <mo>-</mo> <mn>1</mn> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation></p>

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

On the treewidth of generalized q-Kneser graphs

  • Klaus Metsch

摘要

The generalized q-Kneser graph \(K_q(n,k,t)\) K q ( n , k , t ) for integers \(k>t>0\) k > t > 0 and \(n>2k-t\) n > 2 k - t is the graph whose vertices are the k-dimensional subspaces of an n-dimensional \(F_q\) F q -vector space with two vertices \(U_1\) U 1 and \(U_2\) U 2 adjacent if and only if \(\dim (U_1\cap U_2)<t\) dim ( U 1 U 2 ) < t . We determine the treewidth of the generalized q-Kneser graphs \(K_q(n,k,t)\) K q ( n , k , t ) when \(t\ge 2\) t 2 and n is sufficiently large compared to k. The imposed bound on n is a significant improvement of the previously known bound. One consequence of our results is that the treewidth of each q-Kneser graph \(K_q(n,k,t)\) K q ( n , k , t ) with \(k>t>0\) k > t > 0 and \(n\ge 3k-t+9\) n 3 k - t + 9 is equal to \({n\brack k}_q-{n-t\brack k-t}_q-1.\) n k q - n - t k - t q - 1 .