<p>A bipartite <i>r</i>-uniform hypergraph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="105" /> </InlineMediaObject> <EquationSource Format="TEX">\(H=(X,Y,E)\)</EquationSource> </InlineEquation> is said to be bi-<i>k</i>-edge-maximal if every subhypergraph <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq2.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(H'\)</EquationSource> </InlineEquation> of <i>H</i> has edge-connectivity at most <i>k</i>, but for any edge <i>e</i> in <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">\(H^{bc}\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="177" /> </InlineMediaObject> <EquationSource Format="TEX">\(H+e=(X,Y,E\cup \{e\})\)</EquationSource> </InlineEquation> contains a subhypergraph with edge-connectivity at least <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq5.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(k+1\)</EquationSource> </InlineEquation>. Here, <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">\(H^{bc}\)</EquationSource> </InlineEquation> is the bipartite <i>r</i>-uniform hypergraph with bipartition (<i>X</i>,&#xa0;<i>Y</i>) and edge set <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq7.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="53" /> </InlineMediaObject> <EquationSource Format="TEX">\(E(H^{bc})\)</EquationSource> </InlineEquation><InlineEquation ID="IEq7101"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq7101.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="87" /> </InlineMediaObject> <EquationSource Format="TEX">\(=\{e\subseteq X\cup\)</EquationSource> </InlineEquation><InlineEquation ID="IEq7020"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq7020.gif" Format="GIF" Height="18" Rendition="HTML" Resolution="72" Type="Linedraw" Width="112" /> </InlineMediaObject> <EquationSource Format="TEX">\(Y:~e\cap X\ne \emptyset ,\)</EquationSource> </InlineEquation><InlineEquation ID="IEq7000"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq7000.gif" Format="GIF" Height="18" Rendition="HTML" Resolution="72" Type="Linedraw" Width="78" /> </InlineMediaObject> <EquationSource Format="TEX">\(~e\cap Y\ne \emptyset ,\)</EquationSource> </InlineEquation><InlineEquation ID="IEq70001"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq70001.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="72" /> </InlineMediaObject> <EquationSource Format="TEX">\(~e\notin E(H)\)</EquationSource> </InlineEquation><InlineEquation ID="IEq70002"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2961_Article_IEq70002.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="176" /> </InlineMediaObject> <EquationSource Format="TEX">\(~\text {and}~ e~\text {has cardinality}~ r\}\)</EquationSource> </InlineEquation>. In this paper, we investigate the upper and lower bounds on the sizes of bi-<i>k</i>-edge-maximal <i>r</i>-uniform hypergraphs. Furthermore, some extremal hypergraphs achieving these bounds are characterized. This complements previous results on bi-<i>k</i>-edge-maximal graphs.</p>

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

On the Sizes of Bi-k-Edge-Maximal r-Uniform Hypergraphs

  • Qinglin Wang,
  • Yingzhi Tian

摘要

A bipartite r-uniform hypergraph \(H=(X,Y,E)\) is said to be bi-k-edge-maximal if every subhypergraph \(H'\) of H has edge-connectivity at most k, but for any edge e in \(H^{bc}\) , \(H+e=(X,Y,E\cup \{e\})\) contains a subhypergraph with edge-connectivity at least \(k+1\) . Here, \(H^{bc}\) is the bipartite r-uniform hypergraph with bipartition (XY) and edge set \(E(H^{bc})\) \(=\{e\subseteq X\cup\) \(Y:~e\cap X\ne \emptyset ,\) \(~e\cap Y\ne \emptyset ,\) \(~e\notin E(H)\) \(~\text {and}~ e~\text {has cardinality}~ r\}\) . In this paper, we investigate the upper and lower bounds on the sizes of bi-k-edge-maximal r-uniform hypergraphs. Furthermore, some extremal hypergraphs achieving these bounds are characterized. This complements previous results on bi-k-edge-maximal graphs.