For an odd integer <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2024_128_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="79" /> </InlineMediaObject> <EquationSource Format="TEX">$n = 2d-1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>2</mn> <mi>d</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, let <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2024_128_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">${\mathcal {B}}_d$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">B</mi> <mi>d</mi> </msub> </math></EquationSource> </InlineEquation> be the subgraph of the hypercube <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2024_128_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">$Q_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> induced by the two largest layers. In this paper, we describe the typical structure of proper q-colorings of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2024_128_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">$V({\mathcal {B}}_d)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mo stretchy="false">(</mo> <msub> <mi mathvariant="script">B</mi> <mi>d</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and give asymptotics on the number of such colorings when q is an even number. The proofs use various tools including information theory (entropy), Sapozhenko’s graph container method and a recently developed method of Jenssen and Perkins that combines Sapozhenko’s graph container lemma with the cluster expansion for polymer models from statistical physics.

The Number of Colorings of the Middle Layers of the Hamming Cube

期刊论文
发表日期：

2025年1月2日

查看全文

Lina Li,
Gweneth McKinley,
Jinyoung Park

摘要

For an odd integer $n = 2d-1$ $n = 2 d - 1$ , let ${\mathcal {B}}_d$ $B_{d}$ be the subgraph of the hypercube $Q_n$ $Q_{n}$ induced by the two largest layers. In this paper, we describe the typical structure of proper q-colorings of $V({\mathcal {B}}_d)$ $V (B_{d})$ and give asymptotics on the number of such colorings when q is an even number. The proofs use various tools including information theory (entropy), Sapozhenko’s graph container method and a recently developed method of Jenssen and Perkins that combines Sapozhenko’s graph container lemma with the cluster expansion for polymer models from statistical physics.