Erdős–Ko–Rado conjecture for k-intersecting invertible matrices

About 13 years old · traced to

Let qq be a prime power, let k∈Nk\in\mathbb{N}, and let Γ=GL⁡(n,Fq)\Gamma=\operatorname{GL}(n,\mathbb{F}_q). Define

Xq,n,k={A∈GL⁡(n,Fq):rank⁡(A−I)>n−k},Gq,n,k=Cay⁡(Γ,Xq,n,k).X_{q,n,k}=\{A\in\operatorname{GL}(n,\mathbb{F}_q):\operatorname{rank}(A-I)>n-k\},\qquad G_{q,n,k}=\operatorname{Cay}(\Gamma,X_{q,n,k}).

The graph's independent sets are the kk-intersecting families of invertible matrices, and α(G)\alpha(G) and ϑ(G)\vartheta(G) denote its independence number and Lovász theta-number. Erdős–Ko–Rado conjecture. For each q,k∈Nq,k\in\mathbb{N}, there exists n0=n0(q,k)∈Nn_0=n_0(q,k)\in\mathbb{N} such that for all n≥n0n\geq n_0,

ϑ(Gq,n,k)=α(Gq,n,k)=∏i=kn−1(qn−qi).\vartheta(G_{q,n,k})=\alpha(G_{q,n,k})=\prod_{i=k}^{n-1}(q^n-q^i).

The product is achieved by matrices fixing pointwise a chosen kk-dimensional subspace. Computational evidence supports the assertion for small values of nn and qq, but the stated asymptotic result remains open.

References

Primary source

Evan DeCorte, David de Laat and Frank Vallentin, “Fourier analysis on finite groups and the Lovász theta-number of Cayley graphs”, arXiv:1307.5703 (2013).

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.