The higher-wise independence conjecture for projective norm graphs

About 7 years old · traced to

Let qq be a prime power, let 4≤ℓ<t4\leq\ell<t be integers, and let NG⁡(q,t)\operatorname{NG}(q,t) denote the projective norm graph. A set of vertices has common neighbours if those vertices are all adjacent to each such common vertex.

Higher-wise independence conjecture. For any prime power qq and integers 4≤ℓ<t4\leq\ell<t, all but o(nℓ)o(n^\ell) sets of ℓ\ell vertices in NG⁡(q,t)\operatorname{NG}(q,t) have (1+o(1))qt−ℓ(1+o(1))q^{t-\ell} common neighbours.

The claim extends the established asymptotic description of common neighbourhoods from triples to larger sets of vertices. The paper presents it as being supported by computer calculations; its general validity remains open.

References

Primary source

Tomas Bayer, Tamás Mészáros, Lajos Rónyai and Tibor Szabó, “Exploring Projective Norm Graphs”, arXiv:1908.05190 (2019).

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.