Arras–Joos conjecture for independent sets in Cartesian products of triangles

About 1 year old · traced to

Let GG be the Cartesian product of tt copies of the triangle K3K_3:

G=□i=1tK3.G=\mathbin{\Box}_{i=1}^t K_3.

Write i(G)i(G) for the number of independent sets of GG.

Arras–Joos conjecture. As tt tends to infinity,

i(G)=(1+o(1))3⋅2t−1⋅23t−1exp⁡((3/2)3t−1).i(G)=(1+o(1))3\cdot 2^{t-1}\cdot 2^{3^{t-1}}\exp\left((3/2)^{3^t-1}\right).

Even for this non-bipartite Cartesian product, the asymptotic number of independent sets was not known in the source's discussion; this conjecture gives the proposed asymptotic formula.

References

Primary source

Maurício Collares, Joshua Erde, Anna Geisler and Mihyun Kang, “Counting independent sets in expanding bipartite regular graphs”, arXiv:2503.22255 (2025).

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.