Exponential decay conjecture for the Hamming-cube theta number

Let H(n,s)H(n,s) denote the Hamming hypergraph on Hn\mathbb{H}^n whose edges are ss-triangles, and for fixed c>1c>1 let s(n,c)s(n,c) be the even integer closest to n/cn/c. The quantity mathvartheta(H(n,s(n,c)))/2nmathvartheta(H(n,s(n,c))) / 2^n is the normalized theta number for this hypergraph.

Hamming-cube decay conjecture. For every fixed c>2c>2, the quantity

ϑ(H(n,s(n,c)))/2n\vartheta(H(n,s(n,c))) / 2^n

decays exponentially fast with nn, whereas

ϑ(H(n,s(n,2)))/2n\vartheta(H(n,s(n,2))) / 2^n

decays linearly fast with nn.

This conjecture concerns the asymptotic density bound produced by the theta number for subsets of the Hamming cube that avoid ss-triangles. The exponential-versus-linear transition is supported by numerical evidence, but no proof or resolution is supplied here.

Sources & referencesView supporting material

Primary source

Davi Castro-Silva, Fernando Mário de Oliveira Filho, Lucas Slot and Frank Vallentin, “A recursive theta body for hypergraphs”, arXiv:2206.03929 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.