The probabilistic universal graph conjecture for stable matrix families

At least 4 years old · documented by

Let M\mathcal M be a sequence of n×nn \times n Boolean matrices. For a sequence of matrices, let cl⁡(M)\operatorname{cl}(\mathcal M) be the set of all square submatrices of matrices in the sequence, and let cl⁡(M)n\operatorname{cl}(\mathcal M)_n denote its n×nn \times n members. Let R⁡(M)\operatorname{R}(\mathcal M) denote the randomized communication complexity of the sequence. If GTk\mathrm{GT}_k is the k×kk \times k Greater-Than matrix defined by GTk(i,j)=1\mathrm{GT}_k(i,j)=1 if and only if i≤ji \leq j, then M\mathcal M is stable when GTk∉cl⁡(M)\mathrm{GT}_k \notin \operatorname{cl}(\mathcal M) for some k∈Nk \in \mathbb N. Probabilistic Universal Graph Conjecture. One has

R⁡(M)=O(1)\operatorname{R}(\mathcal M)=O(1)

if and only if M\mathcal M is stable and

∣cl⁡(M)n∣≤2O(nlog⁡n).|\operatorname{cl}(\mathcal M)_n|\leq 2^{O(n \log n)}.

The statement is the communication-complexity formulation of the probabilistic version of the Implicit Graph Conjecture proposed by Harms, Wild, and Zamaraev. The paper's abstract states that this conjecture is refuted, so the claimed equivalence is not valid in general.

References

Primary source

Lianna Hambardzumyan, Hamed Hatami and Pooya Hatami, “A counter-example to the probabilistic universal graph conjecture via randomized communication complexity”, arXiv:2111.10436 (2021).

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.