We study the Turán problem for highly symmetric bipartite graphs arising from geometric shapes and periodic tilings commonly found in nature.<OrderedList> <ListItem> <ItemNumber>(1)</ItemNumber> <ItemContent> The prism <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11856_2025_2820_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="108" /> </InlineMediaObject> <EquationSource Format="TEX">$C_{2\ell}^{\square}:=C_{2\ell} \square K_{2}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msubsup> <mi>C</mi> <mrow> <mn>2</mn> <mi>ℓ</mi> </mrow> <mrow> <mi>◻</mi> </mrow> </msubsup> <mo>:=</mo> <msub> <mi>C</mi> <mrow> <mn>2</mn> <mi>ℓ</mi> </mrow> </msub> <mi>◻</mi> <msub> <mi>K</mi> <mrow> <mn>2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> is the graph consisting of two vertex disjoint 2ℓ-cycles and a matching pairing the corresponding vertices of these two cycles. We show that for every ℓ ≥ 4, <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11856_2025_2820_Article_IEq2.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="145" /> </InlineMediaObject> <EquationSource Format="TEX">$\text{ex}(n, C_{2\ell}^{\square})=\Theta(n^{3/2})$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mtext>ex</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msubsup> <mi>C</mi> <mrow> <mn>2</mn> <mi>ℓ</mi> </mrow> <mrow> <mi>◻</mi> </mrow> </msubsup> <mo stretchy="false">)</mo> <mo>=</mo> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>3</mn> <mrow> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation>. This resolves a conjecture of He, Li and Feng. </ItemContent> </ListItem> <ListItem> <ItemNumber>(2)</ItemNumber> <ItemContent> The hexagonal tiling in honeycomb is one of the most natural structures in the real world. We show that the extremal number of honeycomb graphs has the same order of magnitude as their basic building unit 6-cycles. </ItemContent> </ListItem> <ListItem> <ItemNumber>(3)</ItemNumber> <ItemContent> We also consider bipartite graphs from quadrangulations of the cylinder and the torus. We prove near optimal bounds for both configurations. In particular, our method gives a very short proof of a tight upper bound for the extremal number of the 2-dimensional grid, improving a recent result of Bradač, Janzer, Sudakov and Tomon. </ItemContent> </ListItem> </OrderedList>Our proofs mix several ideas, including shifting embedding schemes, weighted homomorphism and subgraph counts and asymmetric dependent random choice.

Extremal number of graphs from geometric shapes

期刊论文
发表日期：

2025年9月29日

查看全文

Jun Gao,
Oliver Janzer,
Hong Liu,
Zixiang Xu

摘要

We study the Turán problem for highly symmetric bipartite graphs arising from geometric shapes and periodic tilings commonly found in nature. (1)

The prism $C_{2\ell}^{\square}:=C_{2\ell} \square K_{2}$ $C_{2 ℓ}^{◻} := C_{2 ℓ} ◻ K_{2}$ is the graph consisting of two vertex disjoint 2ℓ-cycles and a matching pairing the corresponding vertices of these two cycles. We show that for every ℓ ≥ 4, $\text{ex}(n, C_{2\ell}^{\square})=\Theta(n^{3/2})$ $ex (n, C_{2 ℓ}^{◻}) = Θ (n^{3 / 2})$ . This resolves a conjecture of He, Li and Feng.

(2)

The hexagonal tiling in honeycomb is one of the most natural structures in the real world. We show that the extremal number of honeycomb graphs has the same order of magnitude as their basic building unit 6-cycles.

(3)

We also consider bipartite graphs from quadrangulations of the cylinder and the torus. We prove near optimal bounds for both configurations. In particular, our method gives a very short proof of a tight upper bound for the extremal number of the 2-dimensional grid, improving a recent result of Bradač, Janzer, Sudakov and Tomon.

Our proofs mix several ideas, including shifting embedding schemes, weighted homomorphism and subgraph counts and asymmetric dependent random choice.