The Independence Number of the Orthogonality Graph — Or: The Usefulness of Literature Study

Let {X} be the orthogonality graph, that is the graph with {\{ -1, 1 \}^n} as vertices with two vertices adjacent if they are orthogonal. So {x, y \in \{ -1, 1 \}^n} are adjacent if {x \cdot y = x_1y_1 + x_2y_2 + \ldots + x_ny_n = 0}. There are many publications which investigate this problem. The aim of this post is two fold:

  1. To summarize the state of the art.
  2. To demonstrate how careful literature study is helpful to obtain results.

1. A Large Independent Set

So let us start with investigating the independence number of {X}. What is the largest independent set which we can think of? If {n} is odd, then we can simply take all the vertices as {x \cdot y \neq 0} for all vertices {x, y}. If {n \equiv 2 ~(\text{mod}~4)}, then {X} is bipartite. Particularly, we can just take half of all vertices. So the only interesting case left is when {n = 4m} for some integer {m}. Consider the sets

\displaystyle Y_1 = \{ x \in \{ -1, 1 \}^{n-1}: | \{ x_i: x_i = 1 \} | \leq m \}

and

\displaystyle Y_2 = \{ x \in \{ -1, 1 \}^{n-1}: | \{ x_i: x_i = 1 \} | > 3m \}.

Now define {Y} by

\displaystyle Y = \{ x \in X: (x_0, \ldots, x_{n-1}) \in Y_1 \cup Y_2 \}.

It is easy to see that two elements of {Y} never have exactly {2m} elements in common, so {x \cdot y \neq 0} for all {x, y \in Y} and {Y} is an independent set. We have

\displaystyle |Y_1| = |Y_2| = \sum_{i=0}^{m-1} \binom{4m-1}{i} =: a_m,

so {|Y| = 4a_m}. Is this any good? Indeed, there is much evidence in favor of it.

2. Results

Let us summarize the results. The independent set {Y} was, as far as I know, first described in literature by Frankl in 1986. Furthermore, he showed the following.

Theorem 1 (Frankl (1986)) We have {\alpha(X) = 4a_m} for {m = p^k} for an odd prime {p}.

For {m=2} it is easy to show that {\alpha(X) = 32}. This leaves {m=4} as the first interesting case. This was solved by Etienne de Klerk and Dmitrii Pasechnik.

Theorem 2 (de Klerk, Pasechnik (2007)) We have {\alpha(X) = 4a_m} for {m = 4}.

They used Lex Schrijver‘s semidefinite programming bound for their result (which I discussed earlier here in a different context). Recently, Hajime Tanaka and I added this result which is going to be published by Combinatorica soon, I was told:

Theorem 3 (I., Tanaka (2020)) We have {\alpha(X) = 4a_m} for {m = 2^k}.

Obviously, this is the one prime not covered in Frankl’s result. The first open case is {24}, but one of our referees pointed out that {m=6} can be solved by a generalization of Schrijver’s semidefinite programming bound, see here.

Our result looks very similar to Frankl’s result. Indeed, when you look at our paper, it is essentially Frankl’s proof, just that we divide by {2} at one point. The basic idea is discussed in this previous post of mine on various spectral techniques. So how did this remain unknown for 34 years? Lack of interest in the problem? Definitely not, as many people worked on it. It was simply a case of no one reading Frankl’s paper from 1986.

3. Literature Study

So what is the complete history of the research on the topic? Here is a timeline:

  • Frankl (1986): Constructs the example {Y} and shows {\alpha(X) = 4a_m} for {m = p^k}, {p} an odd prime.
  • Frankl and Rödl (1987): They show {\alpha(X) \leq (1-\epsilon)^n} for some constant {\epsilon > 0}. This is better than the trivial bound of {2^n/n} for sufficiently large {n}. Interestingly, they also write that in Frankl (1986) it is conjectured that {\alpha(X) = 4a_m} for all {m}, while Frankl (1986) does not explicitely contain this conjecture.
  • Galliard (2001): Viktor Galliard’s diploma thesis discusses the case {m=2^k} as it is relevant for quantum computing and the concept of pseudo-telepathy. He cites Frankl and Rödl (1987), but overlooks Frankl (1986). Hence, he rediscovers {Y} and conjecture, all of this limited to {m=2^k}, that {\alpha(X) = 4a_m}. (Viktor Galliard did not go into research, but he has an engineering company.)
  • Newman (2004), Godsil and Newman (2008): Mike Newman generalized everything in Galliard (2001) to general {m} as part of his PhD thesis under the Chris Godsil‘s supervision. He also cites Frankl and Rödl (1987), but does not know about Frankl (1986). Hence, he conjectures {\alpha(X) = 4a_m} for all {m}. He also shows that the trivial bound {2^n/n} is never tight for {n > 12}.
  • De Klerk and Pasechnik (2008): Knowing Schrijver’s SDP bound and reading Newman’s PhD thesis, De Klerk and Pasechnik show that {\alpha(X) = 4a_n} for {m=4}. They too are unaware of Frankl (1986).
  • I., Tanaka (late 2018): I visit Hajime Tanaka at Tohoku University in Sendai. One problem that we want to work on was to generalize De Klerk and Pasechnik (2008). While studying the literature, we notice Frankl (1986). It turns out that with some fiddling around we could generalize Frankl’s result to {m=2^k}. As this was the case relevant for Galliard’s pseudo-telepathy related problem, we decided to publish it.
  • I., Tanaka (early 2019): Luckily, the referees agreed with us on the relevance of the results and, as mentioned before, it soon be assigned to an issue of Combinatorica. One of the referees points our that semidefinite programming also covers {m=6}. The smallest open case is now {m=10}, so {n=40}. This graph is {2^{40}} vertices, so a computational verification seems to be out of reach.

I want to mention that many of the papers are actually motivated by investigating the chromatic number {\chi(X)}. All of them mention it at least. Usually, investigating the independence number is easier and one can use {\chi(X) \alpha(X) \leq |X|} to connect both of them. This is what all of this work is actually doing.

4. Conclusion

It is always good to read the literature carefully. In this case, I am thankful that a long list of people did not for 30 years, as otherwise me and Hajime Tanaka would not have a paper. All the other people, who worked on this, are very clever and one of them would have surely figured out how to generalize Frankl’s bound to our case.

The conjecture is very nice and it is slightly tantalizing that no one could find a nice proof so far that covers all the cases. That said, Frankl’s proof is very short and beautiful for all {m = p^k} with {p} prime. Including {p=2} if you add “{/2}” at one point in his proof as we essentially did (I want to emphasize that our modifications of Frankl’s proof were originally more complicated. Only after some simplifications they boild down to dividing at one point by {2}).

Anyway, I hope that some day someone will find a nice, short proof which solves the problem for all {m}.

 

3 comments

  1. Perhaps worth mentioning is that these graphs have quantum chromatic number equal to n = 4m, but chromatic number great than this for m >= 3. Interestingly, though the quantum chromatic number is likely undecidable in general, we know the quantum chromatic number but not chromatic number (merely NP-hard) for this class of graphs (unless I have also missed something in the literature :P).

    Liked by 1 person

    Reply

    1. Indeed. Showing that there is a gap between the chromatic number and the quantum chromatic number was Galliard’s motivation.

      I never really know what to think about the relationship between the complexity classes of problems in general and specific instances for very symmetric graphs such as the orthogonality graph. This behaviour does not seem so unusual. Lovasz-Theta function gives you a lower bound for free and then one just need to hope for a good construction. At this point I would like to provide another example for this behaviour to support my claim, but the quantum chromatic numbers of my favorite very symmetric graphs seems to be mostly unknown.

      Like

      Reply
  2. Pingback: How to Phrase/Make a Conjecture | Ratio Bound – A Combinatorics Blog

Leave a comment