Authors Alexander Golovnev, Ishay Haviv,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22
www.theoryofcomputing.org
The (Generalized) Orthogonality
Dimension of (Generalized) Kneser
Graphs: Bounds and Applications
Alexander Golovnevβ Ishay Havivβ
Received October 1, 2021; Revised August 21, 2022; Published December 29, 2022
Abstract. The orthogonality dimension of a graph πΊ = (π , πΈ) over a field π½ is the
smallest integer π‘ for which there exists an assignment of a vector π’π£ β π½ π‘ with
hπ’π£ , π’π£ i β 0 to every vertex π£ β π, such that hπ’π£ , π’π€ i = 0 whenever π£ and π€ are
adjacent vertices in πΊ. The study of the orthogonality dimension of graphs is
motivated by various applications in information theory and in theoretical computer
science. The contribution of the present work is twofold.
First, we prove that there exists a constant π such that for every sufficiently large
fixed integer π‘, it is NP-hard to distinguish between the cases that the orthogonality
dimension over β of an input graph is at most π‘ and at least 3π‘/2 β π. At the heart
of the proof lies a geometric result, which might be of independent interest, on a
generalization of the orthogonality dimension parameter (where vertices correspond
A conference version of this paper appeared in the Proceedings of the 36th Computational Complexity Conference,
2021 (CCCβ21) [21].
β Partially supported by a Rabin Postdoctoral Fellowship.
β Partially supported by the Israel Science Foundation (grant No. 1218/20).
ACM Classification: F.2.2, G.2.2
AMS Classification: 05C50, 68Q06, 68Q17, 68R10
Key words and phrases: orthogonality dimension, minrank, Kneser graphs, hardness of
approximation, circuit complexity
Β© 2022 Alexander Golovnev and Ishay Haviv
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2022.v018.a022
A LEXANDER G OLOVNEV AND I SHAY H AVIV
to subspaces rather than vectors) for the family of Kneser graphs. The result is related to
a long-standing graph-theoretic conjecture due to Stahl (J. Combin. TheoryβB, 1976).
Second, we study the smallest possible orthogonality dimension over finite
fields of the complement of graphs that do not contain certain fixed subgraphs. In
particular, we provide an explicit construction of triangle-free π-vertex graphs whose
complement has orthogonality dimension over the binary field at most π 1βπΏ for some
constant πΏ > 0. Our results involve constructions from a family of generalized Kneser
graphs (namely, threshold Kneser graphs) and are motivated by the rigidity approach
to circuit lower bounds. We use them to answer questions raised by Codenotti,
PudlΓ‘k, and Resta (Theoret. Comput. Sci., 2000), and in particular, to disprove their
Odd Alternating Cycle Conjecture over every finite field.
1 Introduction
A π‘-dimensional orthogonal representation of a graph πΊ = (π , πΈ) over a field π½ is an assignment
of a vector π’π£ β π½ π‘ with hπ’π£ , π’π£ i β 0 to every vertex π£ β π, such that hπ’π£ , π’π£0 i = 0 whenever π£
and π£ 0 are adjacent vertices in πΊ. The orthogonality dimension of a graph πΊ over π½ , denoted by
π(πΊ, π½ ), is the smallest integer π‘ for which there exists a π‘-dimensional orthogonal representation
of πΊ over π½ .1 Orthogonality dimension is closely related to several other well-studied graph
parameters. In particular, for every graph πΊ and every field π½ , π(πΊ, π½ ) is sandwiched between
the clique number and the chromatic number of πΊ, that is, π(πΊ) β€ π(πΊ, π½ ) β€ π(πΊ).
Orthogonal representations of graphs have been found useful over the years for various
applications in information theory and in theoretical computer science. They were originally
introduced over the real field in a seminal paper by LovΓ‘sz [35], where they were used to
define the influential LovΓ‘sz π-function. The latter was used in [35] to determine the Shannon
capacity, a notoriously difficult information-theoretic graph parameter, of the cycle on five
vertices, and in the subsequent decades it was successfully applied in combinatorics, algorithms,
and complexity theory (see, e. g., [46, 31, 19, 3]). The orthogonality dimension of graphs
plays an important role in several areas of computational complexity. Over finite fields, the
orthogonality dimension and its relaxation due to Haemers [23, 24], called minrank, are related
to Valiantβs concept of matrix rigidity [47] (see, e. g., [13, 40, 22]). Over the complex field,
the orthogonality dimension was used in a characterization of the quantum communication
complexity of promise equality problems [14, 6, 7] and in the study of the quantum chromatic
number [10, 42]. Orthogonality dimension has also been investigated in the contexts of hardness
of approximation [39, 32], integrality gaps for linear programming [29, 28], and algorithms
based on semidefinite programming [11, 26].
In the present paper we study two aspects of the orthogonality dimension of graphs. First,
we prove an NP-hardness result for approximating the orthogonality dimension of graphs over
1Orthogonal representations of graphs have originally been defined by LovΓ‘sz [35] as orthogonal representations
of the complement in our sense, i. e., LovΓ‘szβs definition requires vectors associated with non-adjacent vertices to
be orthogonal. We have decided to use here the other definition (following, e. g., [14, 6, 7]), but one may view the
notation π(πΊ, π½ ) as standing for π(πΊ, π½ ).
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 2
T HE (G ENERALIZED ) O RTHOGONALITY D IMENSION OF (G ENERALIZED ) K NESER G RAPHS
the real field β. At the heart of the proof lies a geometric result, which might be of independent
interest, on a generalization of the orthogonality dimension parameter for the family of Kneser
graphs. The result is related to a long-standing graph-theoretic conjecture due to Stahl [43]. The
second aspect of the orthogonality dimension considered in this paper, motivated by the area of
circuit complexity, is that of determining the smallest possible orthogonality dimension over
finite fields of the complement of graphs that do not contain certain fixed subgraphs. In this
context, we prove an upper bound on the minrank over finite fields for a family of generalized
Kneser graphs (namely, threshold Kneser graphs). The bound is used to settle some questions
raised by Codenotti, PudlΓ‘k, and Resta in [13] and to disprove their Odd Alternating Cycle
Conjecture over every finite field.
1.1 Our contribution
1.1.1 The generalized orthogonality dimension of Kneser graphs
We start by considering the computational hardness of determining the orthogonality dimension
of graphs over the real field β. The challenge of understanding the hardness of this parameter
was posed already in the late eighties by LovΓ‘sz, Saks, and SchrΔ³ver [37] (see also [36, Chapter 10]),
and yet, the problem is far from being well-understood. It is easy to see that deciding whether
an input graph πΊ satisfies π(πΊ, β) β€ π‘ can be solved in polynomial time for π‘ β {1, 2}, and
Peeters [39] has shown that it is NP-hard for π‘ β₯ 3. His result is known to imply that for every
π‘ β₯ 6 it is NP-hard to decide whether an input graph πΊ satisfies π(πΊ, β) β€ π‘ or π(πΊ, β) β₯ d4π‘/3e
(see [26]). In the present paper, we improve on the 4/3 multiplicative gap and prove the
following.
Theorem 1.1. There exist constants π and π‘0 such that for every fixed integer π‘ β₯ π‘0 , it is NP-hard to
distinguish between the graphs πΊ that satisfy π(πΊ, β) β€ π‘ from those satisfying π(πΊ, β) β₯ 3π‘/2 β π.
It is worth noting that in order to obtain hardness results for the orthogonality dimension, it
is natural to employ known hardness results regarding the closely related chromatic number of
graphs. Indeed, it is easy to verify (see, e. g., [26]) that every graph πΊ satisfies
log3 π(πΊ) β€ π(πΊ, β) β€ π(πΊ),
hence hardness of deciding whether an input graph πΊ satisfies π(πΊ) β€ π‘1 or π(πΊ) β₯ π‘2
immediately implies the hardness of deciding whether it satisfies π(πΊ, β) β€ π‘1 or π(πΊ, β) β₯
log3 π‘2 . In particular, a result of Dinur, Mossel, and Regev [16] on the hardness of the chromatic
number implies that deciding whether a given graph πΊ satisfies π(πΊ, β) β€ 3 or π(πΊ, β) β₯ π‘
is UG0-hard, where UG0 refers to some variant of βUnique Gamesβ (namely, the βB<-shapedβ
variant).
However, if one is interested in standard NP-hardness for the orthogonality dimension, the
state of the art for the hardness of the chromatic number does not imply any NP-hardness results
using the above reasoning, despite some remarkable recent progress [5, 48]. Moreover, most
hardness proofs for the chromatic number crucially use the fact that an upper bound on the
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 3
A LEXANDER G OLOVNEV AND I SHAY H AVIV
independence number of a graph implies a strong lower bound on its chromatic number (namely,
π(πΊ) β₯ |π(πΊ)|
πΌ(πΊ)
), whereas an analogue of such a statement for the orthogonality dimension does
not hold in general (see, e. g., [26, Proposition 2.2]).
One technique for proving hardness results for the chromatic number that can be applied
to the orthogonality dimension is that of Garey and Johnson [20], who have related hardness
of graph coloring to the multichromatic numbers of Kneser graphs. The π-chromatic number of a
graph πΊ, denoted by π π (πΊ), is the smallest number of colors needed in order to assign to every
vertex of πΊ a set of π colors so that adjacent vertices are assigned to disjoint sets. Notice that
π1 (πΊ) is simply the standard chromatic number π(πΊ). The family of Kneser graphs is defined as
follows.
Definition 1.2 (Kneser Graphs). For integers π β₯ 2π , the Kneser graph πΎ(π, π ) is the graph whose
vertices are all the π -subsets of [π] = {1, . . . , π}, where two sets are adjacent if they are disjoint.
Note that the multichromatic numbers can be defined in terms of Kneser graphs, namely, π π (πΊ)
is the smallest integer π for which there exists a homomorphism from πΊ to πΎ(π, π).
In the seventies, Stahl [43] made the following conjecture.
Conjecture 1.3 (Stahlβs Conjecture [43]). For all integers π and π β₯ 2π ,
lπm
π π (πΎ(π, π )) = Β· (π β 2π ) + 2π.
π
Stahlβs conjecture has received significant attention in the literature over the years. Even
very recently, it was related to Hedetniemiβs well-known, recently disproved, conjecture [45].
Nevertheless, more than forty years since it was proposed, Stahlβs conjecture is still open. It
is known that the right-hand side in Conjecture 1.3 forms an upper bound on π π (πΎ(π, π )), and
that this bound is tight up to an additive constant that depends solely on π [12, 44]. The precise
statement of the conjecture was confirmed only for a few special cases. This includes the case of
π = 1 proved by LovΓ‘sz [34], the cases of π β€ 2, π β€ π , π = 2π + 1, and π divisible by π proved by
Stahl [43, 44], and the case of π = 3 and π = 4 proved by Garey and Johnson [20] (extended to
π = 3 with any π in [44]). The result of [20] was combined there with a simple reduction to show
that for every π‘ β₯ 6, it is NP-hard to distinguish for a given graph πΊ between the cases π(πΊ) β€ π‘
and π(πΊ) β₯ 2π‘ β 4.
The recent paper [26] has suggested to borrow the reduction of [20] to prove hardness
results for the orthogonality dimension. This approach requires the following generalization of
orthogonal representations of graphs over the reals.
Definition 1.4 (Orthogonal Subspace Representation2). A π‘-dimensional orthogonal π-subspace
representation of a graph πΊ = (π , πΈ) is an assignment of a subspace ππ£ β βπ‘ with dim(ππ£ ) = π to
every vertex π£ β π, such that the subspaces ππ£ and ππ£0 are orthogonal whenever π£ and π£ 0 are
adjacent in πΊ. For a graph πΊ, let π π (πΊ, β) denote the smallest integer π‘ for which there exists a
π‘-dimensional orthogonal π-subspace representation of πΊ.
2Over the complex field, the definition is equivalent to the notion of a projective representation from [38,
Definition 6.1].
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 4
T HE (G ENERALIZED ) O RTHOGONALITY D IMENSION OF (G ENERALIZED ) K NESER G RAPHS
Note that for π = 1, Definition 1.4 coincides with the orthogonality dimension over the reals,
and that for every graph πΊ and every π it holds that π π (πΊ, β) β€ π π (πΊ).
A combination of the hardness result of Peeters [39] and the reduction of [20] implies the
following.
Proposition 1.5 ([26, Theorem 1.3]). For every graph πΉ, it is NP-hard to distinguish for an input graph
πΊ between the cases π(πΊ, β) β€ π3 (πΉ, β) and π(πΊ, β) β₯ π4 (πΉ, β).
With Proposition 1.5 in hand, it is of interest to find graphs πΉ with a large gap between π3 (πΉ, β)
and π4 (πΉ, β). In the light of Conjecture 1.3, it is natural to consider the generalized orthogonality
dimension for the family of Kneser graphs. For π = 1, it was shown in [28] that the standard
chromatic number and the standard orthogonality dimension over β coincide on all Kneser
graphs. In addition, a result of Bukh and Cox [8, Proposition 23] implies that for every π β₯ 2π
and every π, it holds that π π (πΎ(π, π ), β) β₯ ππ/π . This implies that π π and π π (Β·, β) coincide on
πΎ(π, π ) whenever π is divisible by π .
In this article we initiate a systematic study of the generalized orthogonality dimension
of Kneser graphs, analogously to Conjecture 1.3. Let us already mention that the arguments
applied in the study of Stahlβs conjecture do not seem to extend to our question. The main reason
is that the proofs in [43, 20, 12, 44] use HiltonβMilner-type theorems to characterize the possible
structures of the independent sets induced by generalized colorings of Kneser graphs, whereas
in our setting, orthogonal subspace representations do not naturally induce large independent
sets and the problem seems to require a more geometric approach.
The first non-trivial case is that of Kneser graphs πΎ(π, π ) with π = 2, for which we show that
the generalized orthogonality dimension is equal to the multichromatic number.
Theorem 1.6. For all integers π β₯ 1 and π β₯ 4,
lπm
π π (πΎ(π, 2), β) = Β· (π β 4) + 2π.
2
We proceed by considering a general π β₯ 3 and prove the following lower bound.
Theorem 1.7. For all integers π β₯ π β₯ 3 there exists π = π(π , π) such that for all integers π β₯ 2π ,
π β d π+1
π e+1
π π (πΎ(π, π ), β) β₯ Β· π β π.
π β1
The proofs of Theorems 1.6 and 1.7 use an inductive argument on π. Note that for π = β Β· π β 1
where β is an integer, the bound provided by Theorem 1.7 is tight up to the additive constant π.
Indeed, in this case we get that there exists a constant π such that for all integers π β₯ 2π it holds
that
β Β· π β π β€ πβ Β·π β1 (πΎ(π, π ), β) β€ πβ Β·π β1 (πΎ(π, π )) β€ β Β· π β 2,
where the last inequality follows from the fact that the right-hand side in Conjecture 1.3 is an
upper bound on the left-hand side [43]. Note further that for the special case of π = 4 and
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 5
A LEXANDER G OLOVNEV AND I SHAY H AVIV
π = 3, Theorem 1.7 implies that there exists a constant π such that π4 (πΎ(π, 3), β) β₯ 3π/2 β π for
every sufficiently large integer π. This, combined with Proposition 1.5 and with the fact that
π3 (πΎ(π, 3), β) = π, yields our hardness result Theorem 1.1. Let us emphasize that the proof
relies on elementary ideas in the spirit of the hardness proof of [20] for the chromatic number
rather than on the PCP theory.
It will be interesting to figure out if the bounds given in Theorem 1.7 can be tightened to
the quantity given in the right-hand side of Conjecture 1.3, at least up to an additive term
independent of π, as is known to hold for the multichromatic numbers [44]. In particular, it
would be nice to decide whether for all integers π β₯ 6 it holds that π4 (πΎ(π, 3), β) = 2π β 4.
A positive answer would imply that for every π‘ β₯ 6, it is NP-hard to decide whether an
input graph πΊ satisfies π(πΊ) β€ π‘ or π(πΊ) β₯ 2π‘ β 4. We remark, however, that the approach
suggested by Proposition 1.5 for the hardness of the orthogonality dimension cannot yield
a multiplicative hardness gap larger than 2, as it is easy to see that every graph πΉ satisfies
π4 (πΉ, β) β€ π(πΉ, β) + π3 (πΉ, β) β€ 2 Β· π3 (πΉ, β).
We note that known relations between the tractable π-function and the orthogonality
dimension over the reals [35] imply that the latter can be approximated in polynomial time to
within a factor of π(π/log2 π), where π stands for the number of vertices. It would be interesting
to decide if for every π > 0, it is NP-hard to approximate the orthogonality dimension to within
a factor of π 1βπ , as is the case for the chromatic number [49].
1.1.2 The orthogonality dimension of threshold Kneser graphs
We next study the orthogonality dimension over finite fields of the complement of graphs that
do not contain some fixed subgraphs. In fact, in this context we consider a relaxation of the
orthogonality dimension, called minrank, that was introduced by Haemers in [23, 24] and is
defined as follows.
Definition 1.8 (Minrank). Let π· = (π , πΈ) be a directed graph on the vertex set π = [π] and let π½
be a field. We say that an π by π matrix π over π½ represents π· if π π,π β 0 for every π β π, and
π π,π = 0 for every distinct π, π β π such that (π, π) β πΈ. The minrank of π· over π½ is defined as
minrkπ½ (π·) = min{rankπ½ (π) | π represents π· over π½ }.
The definition is naturally extended to (undirected) graphs by replacing every undirected edge
with two oppositely directed edges.
Note that for every graph πΊ and every field π½ , minrkπ½ (πΊ) β€ π(πΊ, π½ ).3
We consider here the question of whether there are graphs with no short odd cycles and yet
low minrank over finite fields. This question is motivated by an attempted superlinear lower
bound on the rigidity of explicit matrices for target rank Ξ©(π) [13]. The rigidity of an π by π
3Indeed, given a π‘-dimensional orthogonal representation of an π-vertex graph πΊ over a field π½ , let π΅ β π½ πΓπ‘
denote the matrix whose rows contain the vectors associated with the vertices of πΊ. Then, the π by π matrix π΅ Β· π΅π
represents πΊ and has rank at most π‘ over π½ , hence minrkπ½ (πΊ) β€ π‘.
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 6
T HE (G ENERALIZED ) O RTHOGONALITY D IMENSION OF (G ENERALIZED ) K NESER G RAPHS
matrix π over a field π½ with respect to a given parameter π (the target rank) is the smallest
number of entries that one has to change in π in order to reduce its rank over π½ to below π.
Roughly speaking, it was shown in [47, 9] that for π by π matrices π΄ with rigidity π(π) for
π = π Β· π, where π > 0 is a constant, the computation of the linear transformation π₯ β¦β π΄π₯ by
series-parallel arithmetic circuits requires superlinear size. While Valiant has shown that almost
all matrices are highly rigid, no explicit construction of matrices of superlinear rigidity for linear
target rank is known.
In 2000, Codenotti, PudlΓ‘k, and Resta [13] proposed the Odd Alternating Cycle Conjecture,
stated below. By an alternating odd cycle we refer to a directed graph which forms an odd cycle
when the orientation of the edges is ignored, and such that the orientation of the edges alternates
with one exception.
Conjecture 1.9 (The Odd Alternating Cycle Conjecture [13]). For every field π½ there exist π > 0
and an odd integer β such that every π-vertex directed graph π· with minrkπ½ (π·) β€ π Β· π contains an
alternating cycle of length β .
It was proved in [13] that Conjecture 1.9 implies, if true, that certain explicit π by π circulant
matrices have superlinear rigidity, namely, Ξ©(π Β· logπΏ π) for a constant πΏ > 0. It was further
proved in [13] that every π-vertex (undirected) graph πΊ that is free of cycles of length 4 satisfies
minrkβ (πΊ) > π/6, whereas there are π-vertex (undirected) triangle-free graphs πΊ satisfying
minrkπ½ (πΊ) β€ π(π 3/4 ) for every field π½ . It was left open whether Conjecture 1.9 holds for larger
odd values of β . The conjecture was recently disproved [27] over the reals, but remained open
for finite fields which are of particular interest in circuit complexity. For the orthogonality
dimension over the binary field π½ 2 , it was shown in [13] that there exist triangle-free π-vertex
graphs πΊ satisfying π(πΊ, π½ 2 ) = π/4 + 2. It was asked there whether every π-vertex graph πΊ
satisfying π(πΊ, π½ 2 ) β€ π/4 + 1 must contain a triangle.
In this article we prove an upper bound on the minrank of threshold Kneser graphs (see
Definition 3.1) over finite fields. In these graphs, the vertices are all the π -subsets of the universe
[π], where two sets are adjacent if their intersection size is smaller than some integer π. Note
that for π = 1 we get the standard family of Kneser graphs (see Definition 1.2). In the proof
we modify and extend an argument of [27], which is based on linear spaces of multivariate
polynomials, building on previous work by Alon [2]. For the precise statement, see Theorem 3.2.
Now we turn to describing several applications of our bound.
As a first application, we establish an explicit construction of graphs that do not contain
short odd cycles and yet have low minrank over every finite field.
Theorem 1.10. For every odd integer β β₯ 3 there exists πΏ = πΏ(β ) > 0 such that for every sufficiently
large integer π, there exists an π-vertex graph πΊ with no odd cycle of length at most β such that for every
finite field π½ ,
minrkπ½ (πΊ) β€ π 1βπΏ .
Theorem 1.10 immediately implies that the Odd Alternating Cycle Conjecture is false over
every finite field, even for undirected graphs. This rules out the approach suggested in [13] for
lower bounds on the rigidity of certain circulant matrices and thus falls into the recent line of
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 7
A LEXANDER G OLOVNEV AND I SHAY H AVIV
non-rigidity results based on the polynomial method (see, e. g., [1, 17, 18]). We note, however,
that the general upper bound of [18] on the rigidity of π by π circulant matrices is insufficient to
disprove the Alternating Cycle Conjecture (because in [18] the upper bound is π 1+π where π > 0
goes to zero at an unspecified (slow) rate as π β β, whereas in [13] the rigidity is only claimed
to be Ξ©(π Β· logπΏ π) for a constant πΏ > 0).
We next consider the behavior of the orthogonality dimension over the binary field of
the complement of triangle-free graphs. It is relevant to mention here that in the proof of
Theorem 1.10, the matrices that imply the stated bound on the minrank are symmetric (see
Remark 3.3). For the binary field, this can be combined with a matrix decomposition result due
to Lempel [33] to obtain the following theorem, which answers a question of [13] negatively.
Theorem 1.11. There exists a constant πΏ > 0 such that for every sufficiently large integer π there exists a
triangle-free π-vertex graph πΊ such that π(πΊ, π½ 2 ) β€ π 1βπΏ .
The above result can also be stated in terms of nearly orthogonal systems. For a field π½ ,
a system of vectors in π½ π is said to be nearly orthogonal if none of the vectors of the system
is isotropic (self-orthogonal) and any set of three of them contains an orthogonal pair. For
the real field, it was proved by Rosenfeld [41] that every nearly orthogonal system in β π has
size at most 2π. Theorem 1.11 shows that the situation is quite different over the binary field.
Namely, it implies that there exists a constant πΏ > 0 such that for infinitely many integers π
there exists a nearly orthogonal system in π½ 2π of size at least π 1+πΏ . To see this, consider the
triangle-free π-vertex graph πΊ given by Theorem 1.11, put π = π(πΊ, π½ 2 ) β€ π 1βπΏ , and observe that
the triangle-freeness of πΊ implies that the π vectors assigned by an π-dimensional orthogonal
representation of πΊ over π½ 2 form a nearly orthogonal system in π½ 2π .
We finally mention that our bound on the minrank of threshold Kneser graphs can be used to
obtain graphs with a constant vector chromatic number πv (see Definition 3.8) whose complement
has a polynomially large minrank over every finite field.
Theorem 1.12. There exists a constant πΏ > 0 such that for infinitely many integers π there exists an
π-vertex graph πΊ such that πv (πΊ) β€ 3 and yet minrkπ½ (πΊ) β₯ π πΏ for every finite field π½ .
The interest in such graphs comes from the semidefinite programming algorithmic approach
applied in [11] for approximating the minrank. As explained in [25], the existence of such
graphs implies a limitation on this approach, which is based on the constant vector chromatic
number of the complement of the instances. Theorem 1.12 improves on [25, Theorem 1.3] where
the bound on the minrank is shown only for sufficiently large finite fields.
1.2 Outline
The rest of the paper is organized as follows. In Section 2, we prove our bounds on the
generalized orthogonality dimension of Kneser graphs (Theorems 1.6 and 1.7) and derive our
hardness result (Theorem 1.1). In Section 3, we prove our bound on the minrank of threshold
Kneser graphs over finite fields and deduce Theorems 1.10, 1.11, and 1.12.
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 8
T HE (G ENERALIZED ) O RTHOGONALITY D IMENSION OF (G ENERALIZED ) K NESER G RAPHS
2 The generalized orthogonality dimension of Kneser graphs
In this section we study the generalized orthogonality dimension of Kneser graphs, i. e., the
quantities π π (πΎ(π, π )) (recall Definitions 1.2 and 1.4), and prove Theorems 1.6 and 1.7. We start
with a linear algebra lemma that will be useful in our proofs.
2.1 Linear algebra lemma
Lemma 2.1. For a real vector space π, let π be a subspace of π with dim(π) = β , let π² be a finite
collection of subspaces of π, and let β 0 β€ β be an integer satisfying dim(π β© π) β€ β 0 for every π β π².
Then, there exists a subspace π 0 of π with dim(π 0) = β β β 0 such that dim(π 0 β© π) = 0 for every
π β π².
Intuitively, given a subspace π and a collection π² as in the lemma, a generic subspace π 0 of
π with dimension β β β 0 is expected to have a trivial intersection with each of the subspaces of
π², and thus to satisfy the assertion of the lemma. For a proof, see, e. g., [4, Chapter 3.1.4].
2.2 The case π = 2
Now we turn to the proof of Theorem 1.6 which determines the generalized orthogonality
dimension of the Kneser graphs πΎ(π, π ) for π = 2.
Proof of Theorem 1.6. Fix an integer π β₯ 1. For the upper bound, recall that for all integers π β₯ 4
we have lπm
π π (πΎ(π, 2), β) β€ π π (πΎ(π, 2)) = Β· (π β 4) + 2π,
2
where the equality holds because Conjecture 1.3 is valid for π = 2 [44].
For the lower bound, we consider the induced subgraph of πΎ(π, 2), denoted by πΎ β (π, 2),
obtained from πΎ(π, 2) by removing one of its vertices, say, the vertex {1, 2}. Next we prove that
for all integers π β₯ 4 it holds that
lπm
π π (πΎ β (π, 2), β) β₯ Β· (π β 4) + 2π, (2.1)
2
which immediately implies the required lower bound on π π (πΎ(π, 2), β) as well. We proceed
by induction on π. For π = 4, the graph πΎ(π, 2) is a perfect matching on 6 vertices, hence its
subgraph πΎ β (π, 2) clearly contains an edge. Since every orthogonal π-subspace representation
of this graph assigns to the vertices of this edge orthogonal π-subspaces it follows that
π π (πΎ β (4, 2), β) β₯ 2π,
as desired. Now, fix some π > 4. Assuming that (2.1) holds for π β 1, we prove it for π.
Recall that the vertex set π of πΎ β (π, 2) consists of all the 2-subsets of [π] except {1, 2}. Let
(ππ΄ )π΄βπ be a π‘-dimensional orthogonal π-subspace representation of πΎ β (π, 2). We proceed by
considering the following two cases.
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 9
A LEXANDER G OLOVNEV AND I SHAY H AVIV
Assume first that there exists some π β₯ 4 for which
lπm
dim(π{1,3} β© π{1,π} ) β₯ . (2.2)
2
In this case, consider the induced subgraph of πΎ β (π, 2) on the vertex set π 0 obtained from π
by removing the vertex {3, π} and all the vertices that include the element 1. Notice that this
subgraph is isomorphic to πΎ β (π β 1, 2) and that every vertex of π 0 is disjoint from either {1, 3}
or from {1, π} (or both). This implies that the restriction (ππ΄ )π΄βπ 0 of the given assignment to
the vertices of π 0 forms an orthogonal π-subspace representation of πΎ β (π β 1, 2), all of whose
subspaces lie in the subspace of βπ‘ that is orthogonal to π = π{1,3} β© π{1,π} . By applying an
orthogonal linear transformation from this subspace to βπ‘βdim(π) , we obtain that
lπm
π π (πΎ β (π β 1, 2), β) β€ π‘ β dim(π) β€ π‘ β ,
2
where in the second inequality we have used (2.2). Using the induction hypothesis, this implies
that lπm lπm lπm lπm
π‘ β₯ π π (πΎ β (π β 1, 2), β) + β₯ Β· (π β 5) + 2π + = Β· (π β 4) + 2π,
2 2 2 2
and we are done.
We are left with the case where for every π β₯ 4 it holds that
lπm
dim(π{1,3} β© π{1,π} ) β€ β 1.
2
Apply Lemma 2.1 to the π-subspace π{1,3} and the collection {π{1,π} | 4 β€ π β€ π}. It follows that
there exists a subspace π of π{1,3} with dim(π) = π β (d 2π e β 1) β₯ d 2π e such that for every π β₯ 4 it
holds that dim(π β© π{1,π} ) = 0. Consider the induced subgraph of πΎ β (π, 2) on the vertex set π 0
obtained from π by removing the vertex {2, 3} and all the vertices that include the element 1.
As before, this subgraph is isomorphic to the graph πΎ β (π β 1, 2).
We define an orthogonal π-subspace representation of this graph as follows. Let π΅ be a set in
π 0. If 3 β π΅ we define πeπ΅ = ππ΅ . Otherwise we have π΅ = {3, π} for some π β₯ 4, and we let π e{3,π}
π‘
be the projection of π{1,π} to the subspace of β that is orthogonal to π. Note that the fact that
dim(π β© π{1,π} ) = 0 guarantees that dim(π e{3,π} ) = dim(π{1,π} ) = π.
To prove that the assignment (π eπ΅ )π΅βπ 0 forms an orthogonal π-subspace representation of the
graph, let π΅1 and π΅2 be disjoint sets in π 0. If 3 β π΅1 βͺ π΅2 then we have π eπ΅1 = ππ΅1 and πeπ΅ 2 = π π΅ 2 ,
so it is clear that π
eπ΅1 and π
eπ΅2 are orthogonal. Otherwise, assume without loss of generality that
π΅1 = {3, π} for some π β₯ 4 and that 3 β π΅2 . In this case we have π eπ΅2 = ππ΅2 , and since π΅2 is disjoint
from π΅1 it is also disjoint from {1, π} and from {1, 3}, hence π eπ΅2 is orthogonal to both π{1,π} and
π{1,3} as well as to the projection πeπ΅1 of π{1,π} to the subspace orthogonal to π β π{1,3} . We get
that πeπ΅1 and π eπ΅2 are orthogonal, as required.
Finally, observe that all the subspaces π eπ΅ lie in the subspace of βπ‘ that is orthogonal to π.
Indeed, for sets π΅ with 3 β π΅ this follows from the definition of π eπ΅ , and for the other sets this
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 10
T HE (G ENERALIZED ) O RTHOGONALITY D IMENSION OF (G ENERALIZED ) K NESER G RAPHS
holds because they are disjoint from {1, 3}. By applying an orthogonal linear transformation
from this subspace to βπ‘βdim(π) , we obtain that
lπm
π π (πΎ β (π β 1, 2), β) β€ π‘ β dim(π) β€ π‘ β ,
2
and as in the previous case, by the induction hypothesis it follows that π‘ β₯ d 2π e Β· (π β 4) + 2π,
completing the proof.
2.3 General π
We now prove Theorem 1.7 which provides a lower bound on the generalized orthogonality
dimension of Kneser graphs πΎ(π, π ) for π β₯ 3. The approach resembles the one applied for π = 2
in the proof of Theorem 1.6.
Proof of Theorem 1.7. Fix integers π β₯ π β₯ 3 and denote π = d π+1 π e. Let π0 = π0 (π , π) be a
sufficiently large integer to be determined later. We apply an induction on π. To do so, we
define π = π(π , π) to be sufficiently large, say, π = πβπ+1
π β1 Β· (π0 + π β 2), so that the statement of the
theorem trivially holds for all integers π β€ π0 + π β 2, and turn to the proof of the statement for
π β₯ π0 assuming that it holds for π β (π β 1).
Let (ππ΄ )π΄βπ be a π‘-dimensional orthogonal π-subspace representation of πΎ(π, π ). We start
with some notation. For an π -subset π΄ of [π], an element π β π΄, and an π -subset π΅ of [π] satisfying
π΄ β© π΅ = {π}, we let π’π΄,π (π΅) denote the collection that consists of the set π΅ and all the sets obtained
from π΅ by replacing π with some element from π΄\{π}. Note that |π’π΄,π (π΅)| = π . We say that a vertex
π΄ of πΎ(π, π ) is good (with respect to the given orthogonal subspace representation) if there exists
an π β π΄ such that for every vertex π΅ satisfying π΄ β© π΅ = {π} it holds that dim(ππ΄ β© ππΆ ) β€ π β 1
for some πΆ β π’π΄,π (π΅).
Assume first that there exists a good vertex π΄ in πΎ(π, π ) associated with an element π β π΄.
Applying Lemma 2.1, we get that there exists a (π β π + 1)-subspace π of ππ΄ such that for
every vertex π΅ satisfying π΄ β© π΅ = {π} it holds that dim(π β© ππΆ ) = 0 for some πΆ β π’π΄,π (π΅). We
define an orthogonal π-subspace representation of the graph πΎ(π β (π β 1), π ) on the ground
set [π] \ (π΄ \ {π}) as follows. Let π΅ be an π -subset of [π] \ (π΄ \ {π}). If π β π΅ we define π eπ΅ = π π΅ .
Otherwise, we have π΄ β© π΅ = {π}, and we let ππ΅ be the projection of ππΆ to the subspace of βπ‘
e
orthogonal to π, where πΆ β π’π΄,π (π΅) is a set satisfying dim(π β© ππΆ ) = 0. Note that this condition
guarantees that dim(π eπ΅ ) = dim(ππΆ ) = π.
We claim that the subspaces π eπ΅ form an orthogonal π-subspace representation of the graph
πΎ(π β (π β 1), π ). To see this, let π΅1 and π΅2 be disjoint π -subsets of [π] \ (π΄ \ {π}). If π β π΅1 βͺ π΅2 then
we have π eπ΅1 = ππ΅1 and π eπ΅2 = ππ΅2 , so it is clear that πeπ΅1 and π eπ΅2 are orthogonal. Otherwise,
assume without loss of generality that π β π΅1 and π β π΅2 . In this case, π eπ΅2 = ππ΅2 , and π eπ΅1 is
π‘
the projection of ππΆ to the subspace of β orthogonal to π for some πΆ β π’π΄,π (π΅1 ). Since π΅2 is
disjoint from π΄, it follows that the subspace π eπ΅2 is orthogonal to ππ΄ as well as to its subspace π.
It also follows that π΅2 is disjoint from every set in π’π΄,π (π΅1 ), hence the subspace π eπ΅2 is orthogonal
to ππΆ . We get that ππ΅2 is orthogonal to ππ΅1 , as required.
e e
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 11
A LEXANDER G OLOVNEV AND I SHAY H AVIV
Now, observe that the above orthogonal π-subspace representation of πΎ(π β (π β 1), π ) lies in
the subspace of βπ‘ that is orthogonal to the (π β π + 1)-subspace π. Indeed, for sets π΅ with π β π΅
this follows from the definition of πeπ΅ , and for the other sets this holds because they are disjoint
from π΄. By applying an orthogonal linear transformation from this subspace to βπ‘βdim(π) , it
follows that
π π (πΎ(π β (π β 1), π ), β) β€ π‘ β dim(π) = π‘ β (π β π + 1).
Using the induction hypothesis, this implies that
πβπ+1 πβπ+1
π‘β₯ Β· (π β (π β 1)) β π + (π β π + 1) = Β· π β π,
π β1 π β1
and we are done.
We are left with the case where no vertex of πΎ(π, π ) is good, for which we need the following
lemma.
Lemma 2.2. If a vertex π΄ of πΎ(π, π ) is not good then there exists a nonzero vector π’π΄ β ππ΄ such that the
number of vertices π· of πΎ(π, π ) for which ππ· is not orthogonal to π’π΄ is at most
πβ2
2π β 1
Β· .
2 π β2
We first show how Lemma 2.2 completes the proof of the theorem. Assume that no vertex
of πΎ(π, π ) is good, and consider the following process: We start with the entire vertex set of
πΎ(π, π ), and in every iteration we choose an arbitrary vertex π΄ associated with its nonzero vector
π’π΄ β ππ΄ from Lemma 2.2 and eliminate all vertices whose subspaces are not orthogonal to π’π΄ .
The nonzero vectors associated with the chosen vertices are clearly pairwise orthogonal, and
their number, just like the number of iterations in the process, is at least
π
π πβπ+1
β₯ Β· π β π,
2π β1
Β· π β2πβ2 π β1
2
where the inequality holds for every π β₯ π0 assuming that π0 = π0 (π , π) is sufficiently large
(because the left-hand side of the inequality is quadratic in π whereas the right-hand side is
linear in π). However, the size of the obtained orthogonal set cannot exceed the dimension π‘,
hence
πβπ+1
π‘β₯ Β· π β π,
π β1
and we are done. It remains to prove Lemma 2.2.
Proof of Lemma 2.2. Assume that π΄ is not a good vertex of πΎ(π, π ) and fix an arbitrary π β π΄.
Then there exists a vertex π΅ satisfying π΄ β© π΅ = {π} such that dim(ππ΄ β© ππΆ ) β₯ π for every vertex
πΆ β π’π΄,π (π΅). Denote π’π΄,π (π΅) = {πΆ1 , . . . , πΆ π }, and recall that every set πΆ π intersects π΄ at one
distinct element. For every π β [π ] define ππ = ππ΄ β© ππΆ π and ππ = π1 + Β· Β· Β· + ππ . Note that
π1 β π2 β Β· Β· Β· β ππ β ππ΄ .
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 12
T HE (G ENERALIZED ) O RTHOGONALITY D IMENSION OF (G ENERALIZED ) K NESER G RAPHS
Since dim(π1 ) = dim(π1 ) β₯ π and dim(ππ΄ ) = π < π Β· π , there must exist some π β [π β 1] for
which
dim(ππ+1 ) β dim(ππ ) < π. (2.3)
For this π, we have
dim(ππ+1 β© ππ ) = dim(ππ+1 ) + dim(ππ ) β dim(ππ+1 + ππ )
= dim(ππ+1 ) + dim(ππ ) β dim(ππ+1 ) > π β π = 0,
where the inequality follows by combining (2.3) with the fact that dim(ππ+1 ) β₯ π. This implies
that there exists a nonzero vector π’π΄ in ππ+1 β© ππ . Observe that
π’π΄ β ππ΄ β© ππΆ π+1 β© (ππΆ1 + Β· Β· Β· + ππΆ π ).
Now, consider a vertex π· of πΎ(π, π ) whose subspace ππ· is not orthogonal to π’π΄ . It follows that
ππ· is not orthogonal to ππ΄ , to ππΆ π+1 , and to ππΆ1 + Β· Β· Β· + ππΆ π , hence π· intersects the sets π΄ and
πΆ π+1 as well as at least one of the sets πΆ1 , . . . , πΆ π . We claim that π· must include at least two
elements from π΄ βͺ π΅. Indeed, π· intersects π΄ but if π· includes from π΄ βͺ π΅ only one element
and this element belongs to π΄ then π· either does not intersect πΆ π+1 or does not intersect any
of πΆ1 , . . . , πΆ π . It follows that the number of vertices π· for which ππ· is not orthogonal to π’π΄ is
bounded from above by the number of π -subsets of [π] that include at least two elements from
πβ2
the 2π β 1 elements of π΄ βͺ π΅. The latter is at most 2π β1 2 Β· π β2 , as required.
The proof of Theorem 1.7 is completed.
As immediate corollaries of Theorem 1.7, we obtain the following.
Corollary 2.3. For every integers π β₯ 3 and β β₯ 2 there exists π = π(π , β ) such that for all integers
π β₯ 2π ,
πβ Β·π β1 (πΎ(π, π ), β) β₯ β Β· π β π.
As mentioned before, the bound given in Corollary 2.3 is tight up to the additive constant π.
Corollary 2.4. There exists an absolute constant π such that for all integers π β₯ 6,
π4 (πΎ(π, 3), β) β₯ 3π/2 β π.
Equipped with Corollary 2.4, we are ready to deduce Theorem 1.1.
Proof of Theorem 1.1. Let π‘ be a sufficiently large integer. Recall that a result of [8] implies that
π3 (πΎ(π‘, 3), β) = π‘, whereas Corollary 2.4 implies that π4 (πΎ(π‘, 3), β) β₯ 3π‘/2 β π for an absolute
constant π. Applying Proposition 1.5 with πΉ = πΎ(π‘, 3), it follows that it is NP-hard to distinguish
between the graphs πΊ that satisfy π(πΊ, β) β€ π‘ from those satisfying π(πΊ, β) β₯ 3π‘/2 β π, as
desired.
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 13
A LEXANDER G OLOVNEV AND I SHAY H AVIV
3 The minrank of threshold Kneser graphs
In this section we consider a generalization of the family of Kneser graphs, defined as follows.
Definition 3.1 (Threshold Kneser Graphs). For integers π β€ π β€ π, the threshold Kneser graph
πΎ < (π, π , π) is the graph whose vertices are all the π -subsets of [π], and two sets, π΄, π΅, are adjacent
if |π΄ β© π΅| < π.
For this family of graphs, we prove the following upper bound on the minrank over finite
fields (recall Definition 1.8).
Theorem 3.2. For all integers π β€ π β€ π and for every finite field π½ ,
π βπ
Γ π
<
minrkπ½ (πΎ (π, π , π)) β€ .
π
π=0
Moreover, the bound on the minrank can be achieved by a symmetric matrix.
Remark 3.3. Theorem 3.2 guarantees that the bound on the minrank can be achieved by a
symmetric matrix. This will be crucial for one of our applications, namely, for a construction
of triangle-free graphs whose complement has low orthogonality dimension over the binary
field π½ 2 (see Section 3.3.2). We remark, however, that for undirected graphs and for fields of
characteristic different from 2, attaining the bound on the minrank by a symmetric matrix can be
achieved easily with a factor of 2 worse bound on the minrank. Indeed, if a matrix π represents
a graph πΊ over a field π½ of characteristic different from 2 and satisfies rankπ½ (π) = π then the
matrix π + π π also represents πΊ and has rank at most 2π over π½ . This argument does not hold
over fields of characteristic 2, since in this case the diagonal entries of π + π π are all zero.
As in the previous section, we start with a simple linear algebra lemma.
3.1 Linear algebra lemma
Lemma 3.4. For a graph πΊ on the vertex set [π], let π β β€πΓπ be an integer matrix such that π π,π = 1
for every π β [π], and π π,π = 0 for every pair of distinct non-adjacent vertices π and π in πΊ. Then, for
every finite field π½ , minrkπ½ (πΊ) β€ rankβ (π).
Proof. The lemma follows from the fact that for every finite field π½ , it holds that rankπ½ (π) β€
rankβ (π).
3.2 Proof of Theorem 3.2
We are ready to prove Theorem 3.2.
Proof of Theorem 3.2. Consider the polynomial π β β[π₯] defined by
π₯βπ
1
π(π₯) = = Β· (π₯ β π)(π₯ β (π + 1)) Β· Β· Β· (π₯ β (π β 1)).
π βπ (π β π)!
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 14
T HE (G ENERALIZED ) O RTHOGONALITY D IMENSION OF (G ENERALIZED ) K NESER G RAPHS
Observe that π is an integer-valued polynomial of degree π β π. Let π : {0, 1} π Γ {0, 1} π β β be
the function defined by
π
Γ
π (π₯, π¦) = π π₯ π π¦π
π=1
for every π₯, π¦ β {0, 1} π . Expanding π as a linear combination of monomials, the relation π§ 2 = π§
for π§ β {0, 1} implies that one can reduce to 1 the exponent of each variable occuring in a
monomial. It follows that π can be represented as a multilinear polynomial in the 2π variables
of π₯ and π¦. By combining terms involving the same monomial in the variables of π₯, one can
write π as
π
Γ
π (π₯, π¦) = π π (π₯)β π (π¦)
π=1
for an integer π
and functions π π , β π : {0, 1} π β β, π β [π
], such that the π π βs are distinct
π
multilinear monomials of total degree at most π β π in π variables. It follows that π
β€ π βπ
Γ
π=0 π .
Now, let π1 and π2 be the 2π Γ π
matrices whose rows are indexed by {0, 1} π and whose
columns are indexed by [π
], defined by (π1 )π₯,π = π π (π₯) and (π2 )π₯,π = β π (π₯). Then, the rank over
β of the matrix π = π1 Β· π2π is at most π
and for every π₯, π¦ β {0, 1} π it holds that π π₯,π¦ = π (π₯, π¦).
By the definition of π the matrix π is symmetric, and since π is an integer-valued polynomial,
all of its entries are integer.
Finally, let π be the vertex set of πΎ < (π, π , π), that is, the collection of all π -subsets of [π], and
identify every vertex π΄ β π with an indicator vector π π΄ β {0, 1} π in the natural way. Observe
that for every π΄, π΅ β π we have
π π π΄ ,π π΅ = π (π π΄ , π π΅ ) = π(|π΄ β© π΅|).
Hence, for every π΄ β π we have |π΄| = π and thus π π π΄ ,π π΄ = π(π ) = 1, whereas for every distinct
non-adjacent π΄, π΅ β π we have π β€ |π΄ β© π΅| β€ π β 1 and thus π π π΄ ,π π΅ = π(|π΄ β© π΅|) = 0. Since the
restriction of π to π Γ π is symmetric and has rank at most π
over the reals, Lemma 3.4 implies
that minrkπ½ (πΎ < (π, π , π)) β€ π
for every finite field π½ and that the bound can be achieved by a
symmetric matrix, as desired.
3.3 Applications
We gather below several applications of Theorem 3.2.
3.3.1 The Odd Alternating Cycle Conjecture over finite fields
In this section we disprove Conjecture 1.9 over every finite field. We will use the simple fact that
threshold Kneser graphs do not contain short odd cycles, as stated below (see, e. g., [15, 27]).
Lemma 3.5. Let β β₯ 3 be an odd integer. For every even integer π and an integer π β€ 2βπ , the graph
πΎ < (π, π2 , π) contains no odd cycle of length at most β .
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 15
A LEXANDER G OLOVNEV AND I SHAY H AVIV
We prove the following theorem, confirming Theorem 1.10.
Theorem 3.6. For every odd integer β β₯ 3 there exists πΏ = πΏ(β ) > 0 such that for every sufficiently large
integer π, there exists an π-vertex graph πΊ with no odd cycle of length at most β such that for every finite
field π½ ,
minrkπ½ (πΊ) β€ π 1βπΏ .
Moreover, the bound on the minrank can be achieved by a symmetric matrix.
Proof. Fix an odd integer β β₯ 3. For an integer π divisible by 2β , consider the graph πΊ =
πΎ < (π, 2π , π) where π = 2βπ . By Lemma 3.5, πΊ contains no odd cycle of length at most β . As for
the minrank parameter, Theorem 3.2 implies that for every finite field π½ ,
π/2βπ
Γ π
1 π
β€ 2π»( 2 β π )Β·π = 2π»( 2 β 2β )Β·π ,
1 1
minrkπ½ (πΊ) β€
π
π=0
π
where π» stands for the binary entropy function. Since πΊ has |π | = π/2 = 2(1βπ(1))Β·π vertices, for
any πΏ > 0 such that π»( 12 β 2β1 ) < 1 β πΏ we have minrkπ½ (πΊ) β€ |π | 1βπΏ for every sufficiently large
integer π. The proof is completed by considering, for every sufficiently large integer π, some
π-vertex subgraph of the graph defined above, where π is the smallest integer divisible by 2β
π
such that π β€ π/2 .
3.3.2 Triangle-free graphs and the orthogonality dimension over the binary field
Now we turn to the proof of Theorem 1.11. Its proof adopts the following special case of a result
due to Lempel [33].
Lemma 3.7 ([33]). Let π be an π by π symmetric matrix over the binary field π½ 2 with at least one
nonzero diagonal entry and rank π. Then, there exists an π by π matrix π΅ over π½ 2 satisfying π = π΅ Β· π΅π .
Proof of Theorem 1.11. Apply Theorem 3.6 with β = 3 to obtain some πΏ > 0 such that for every
sufficiently large integer π, there exist a triangle-free π-vertex graph πΊ and an π by π symmetric
matrix π over π½ 2 of rank π = rankπ½ 2 (π) β€ π 1βπΏ that represents πΊ. By Lemma 3.7, there exists an
π by π matrix π΅ over π½ 2 satisfying π = π΅ Β· π΅π . By assigning the π-th row of π΅ to the π-th vertex of πΊ
we get an π-dimensional orthogonal representation of πΊ over π½ 2 , hence π(πΊ, π½ 2 ) β€ π β€ π 1βπΏ .
3.3.3 The vector chromatic number vs. minrank
The vector chromatic number of graphs, introduced by Karger, Motwani, and Sudan in [30], is
defined as follows.
Definition 3.8 (Vector Chromatic Number). For a graph πΊ = (π , πΈ) the vector chromatic number
of πΊ, denoted by πv (πΊ), is the minimal real value of π
> 1 such that there exists an assignment
of a unit vector π€ π£ to every vertex π£ β π satisfying the inequality hπ€ π£ , π€ π£0 i β€ β π
β1
1
whenever π£
and π£ are adjacent in πΊ.
0
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 16
T HE (G ENERALIZED ) O RTHOGONALITY D IMENSION OF (G ENERALIZED ) K NESER G RAPHS
To prove Theorem 1.12, we need the following simple fact that relates the minrank of a graph
to the minrank of its complement (see, e. g., [39, Remark 2.2]).
Fact 3.9. For every field π½ and an π-vertex graph πΊ, minrkπ½ (πΊ) Β· minrkπ½ (πΊ) β₯ π.
Proof of Theorem 1.12. For an integer π divisible by 8, consider the graph πΊ = πΎ < (π, π2 , π) where
π = 8π . We first claim that πv (πΊ) β€ 3. To see this, assign to every vertex π΄ of πΊ, representing
a π2 -subset of [π], the unit vector π€ π΄ β β π defined by (π€ π΄ )π = β1 if π β π΄ and (π€ π΄ )π = β β1
π π
otherwise. Observe that every two distinct vertices π΄ and π΅ that are adjacent in πΊ satisfy
πβ2Β·|π΄4π΅|
|π΄ β© π΅| < π8 and thus |π΄ 4 π΅| > 3π 4 , implying that hπ€ π΄ , π€ π΅ i = π < β 12 . This implies that
πv (πΊ) β€ 3, as claimed. As for the minrank parameter, Theorem 3.2 implies that for every finite
field π½ ,
π/2βπ
Γ π
1 π
minrkπ½ (πΊ) β€ β€ 2π»( 2 β π )Β·π = 2π»(3/8)Β·π ,
π
π=0
π
where π» stands for the binary entropy function. Since πΊ has π = π/2 = 2(1βπ(1))Β·π vertices, for
any πΏ < 1 β π»(3/8) we have minrkπ½ (πΊ) β€ π 1βπΏ assuming that π is sufficiently large. By Fact 3.9,
this implies that minrkπ½ (πΊ) β₯ π πΏ , and we are done.
Acknowledgements
We would like to thank LΓ‘szlΓ³ Babai, Jop BriΓ«t, and the anonymous referees for their very
helpful suggestions that improved the presentation of the paper.
References
[1] Josh Alman and R. Ryan Williams: Probabilistic rank and matrix rigidity. In Proc. 49th
STOC, pp. 641β652. ACM Press, 2017. [doi:10.1145/3055399.3055484] 8
[2] Noga Alon: The Shannon capacity of a union. Combinatorica, 18(3):301β310, 1998.
[doi:10.1007/PL00009824] 7
[3] Noga Alon and Nabil Kahale: Approximating the independence number via the π-
function. Math. Programming, 80(3):253β264, 1998. [doi:10.1007/BF01581168] 2
[4] LΓ‘szlΓ³ Babai and PΓ©ter Frankl: Linear Algebra Methods in Combinatorics. Unpublished
manuscript, 2.2 edition, 1992β2022. Available at authorβs website. 9
[5] Libor Barto, Jakub BulΓn, Andrei A. Krokhin, and Jakub OprΕ‘al: Algebraic approach
to promise constraint satisfaction. J. ACM, 68(4):28:1β66, 2021. Preliminary version in
STOCβ19. [doi:10.1145/3457606] 3
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 17
A LEXANDER G OLOVNEV AND I SHAY H AVIV
[6] Jop BriΓ«t, Harry Buhrman, Debbie Leung, Teresa Piovesan, and Florian Speelman: Round
elimination in exact communication complexity. In Proc. 10th Conf. Theory of Quantum
Computation, Communication and Cryptography (TQCβ15), volume 44 of LIPIcs, pp. 206β225,
2015. [doi:10.4230/LIPIcs.TQC.2015.206] 2
[7] Jop BriΓ«t and Jeroen Zuiddam: On the orthogonal rank of Cayley graphs and impossibility
of quantum round elimination. Quantum Inf. Comput., 17(1β2):106β116, 2017. ACM DL. 2
[8] Boris Bukh and Christopher Cox: On a fractional version of Haemersβ bound. IEEE Trans.
Inform. Theory, 65(6):3340β3348, 2019. [doi:10.1109/TIT.2018.2889108] 5, 13
[9] Chris Calabro: A lower bound on the size of series-parallel graphs dense in long paths.
Electron. Colloq. Comput. Complexity, TR08-110, 2008. [ECCC] 7
[10] Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Severini, and
Andreas J. Winter: On the quantum chromatic number of a graph. Electr. J. Combinat.,
14(1):R81:1β15, 2007. [doi:10.37236/999] 2
[11] Eden ChlamtΓ‘Δ and Ishay Haviv: Linear index coding via semidefinite program-
ming. Combin. Probab. Comput., 23(2):223β247, 2014. Preliminary version in SODAβ12.
[doi:10.1017/S0963548313000564] 2, 8
[12] VaΕ‘ek ChvΓ‘tal, Michael R. Garey, and David S. Johnson: Two results concerning mul-
ticoloring. Ann. Discr. Math., 2:151β154, 1978. [doi:10.1016/S0167-5060(08)70329-7] 4,
5
[13] Bruno Codenotti, Pavel PudlΓ‘k, and Giovanni Resta: Some structural properties of
low-rank matrices related to computational complexity. Theoret. Comput. Sci., 235(1):89β107,
2000. [doi:10.1016/S0304-3975(99)00185-1, ECCC:TR97-043] 2, 3, 6, 7, 8
[14] Ronald de Wolf: Quantum Computing and Communication Complexity. Ph. D. thesis,
Universiteit van Amsterdam, 2001. Available at authorβs home page. 2
[15] Tristan Denley: The odd girth of the generalised Kneser graph. Europ. J. Combinat.,
18(6):607β611, 1997. [doi:10.1006/eujc.1996.0122] 15
[16] Irit Dinur, Elchanan Mossel, and Oded Regev: Conditional hardness for approxi-
mate coloring. SIAM J. Comput., 39(3):843β873, 2009. Preliminary version in STOCβ06.
[doi:10.1137/07068062X] 3
[17] Zeev Dvir and Benjamin L. Edelman: Matrix rigidity and the Croot-Lev-Pach lemma.
Theory of Computing, 15(8):1β7, 2019. [doi:10.4086/toc.2019.v015a008] 8
[18] Zeev Dvir and Allen Liu: Fourier and circulant matrices are not rigid. Theory of Computing,
16(20):1β48, 2020. Preliminary version in CCCβ19. [doi:10.4086/toc.2020.v016a020] 8
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 18
T HE (G ENERALIZED ) O RTHOGONALITY D IMENSION OF (G ENERALIZED ) K NESER G RAPHS
[19] Uriel Feige: Randomized graph products, chromatic numbers, and the LovΓ‘sz π-function.
Combinatorica, 17(1):79β90, 1997. Preliminary version in STOCβ95. [doi:10.1007/BF01196133]
2
[20] Michael R. Garey and David S. Johnson: The complexity of near-optimal graph coloring.
J. ACM, 23(1):43β49, 1976. [doi:10.1145/321921.321926] 4, 5, 6
[21] Alexander Golovnev and Ishay Haviv: The (generalized) orthogonality dimension of
(generalized) Kneser graphs: Bounds and applications. In Proc. 36th Comput. Complexity
Conf. (CCCβ21), pp. 8:1β15. Schloss DagstuhlβLeibniz-Zentrum fuer Informatik, 2021.
[doi:10.4230/LIPIcs.CCC.2021.8] 1
[22] Alexander Golovnev, Oded Regev, and Omri Weinstein: The minrank of random graphs.
IEEE Trans. Inform. Theory, 64(11):6990β6995, 2018. Preliminary version in RANDOMβ17.
[doi:10.1109/TIT.2018.2810384] 2
[23] Willem H. Haemers: On some problems of LovΓ‘sz concerning the Shannon capacity of a
graph. IEEE Trans. Inform. Theory, 25(2):231β232, 1979. [doi:10.1109/TIT.1979.1056027] 2, 6
[24] Willem H. Haemers: An upper bound for the Shannon capacity of a graph. In LΓ‘szlΓ³ LovΓ‘sz
and Vera T. SΓ³s, editors, Algebraic Methods in Graph Theory, Szeged, 1978, volume 25/I of
Colloquia Mathematica Societatis JΓ‘nos Bolyai, pp. 267β272. Bolyai Society and North-Holland,
1981. Avaliable at Tilburg University. 2, 6
[25] Ishay Haviv: On minrank and the LovΓ‘sz theta function. In Proc. 21st Internat. Conf. on Ap-
proximation Algorithms for Combinat. Opt. Probl. (APPROXβ18), pp. 13:1β15. Schloss Dagstuhlβ
Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-RANDOM.2018.13]
8
[26] Ishay Haviv: Approximating the orthogonality dimension of graphs and hypergraphs.
In Proc. Internat. Symp. Math. Foundations of Comp. Sci. (MFCSβ19), pp. 39:1β15. Schloss
DagstuhlβLeibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.MFCS.2019.39] 2, 3,
4, 5
[27] Ishay Haviv: On minrank and forbidden subgraphs. ACM Trans. Comput. Theory, 11(4):20:1β
13, 2019. Preliminary version in RANDOMβ18. [doi:10.1145/3322817] 7, 15
[28] Ishay Haviv: Topological bounds on the dimension of orthogonal representations of graphs.
Europ. J. Combinat., 81:84β97, 2019. [doi:10.1016/j.ejc.2019.04.006] 2, 5
[29] Sihuang Hu, Itzhak Tamo, and Ofer Shayevitz: A bound on the Shannon capacity via a
linear programming variation. SIAM J. Discr. Math., 32(3):2229β2241, 2018. Preliminary
version in ISITβ17. [doi:10.1137/17M115565X] 2
[30] David R. Karger, Rajeev Motwani, and Madhu Sudan: Approximate graph coloring by
semidefinite programming. J. ACM, 45(2):246β265, 1998. Preliminary version in FOCSβ94.
[doi:10.1145/274787.274791] 16
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 19
A LEXANDER G OLOVNEV AND I SHAY H AVIV
[31] Donald E. Knuth: The sandwich theorem. Electr. J. Combinat., 1(1):A1:1β48, 1994.
[doi:10.37236/1193] 2
[32] Michael Langberg and Alexander Sprintson: On the hardness of approximating the
network coding capacity. IEEE Trans. Inform. Theory, 57(2):1008β1014, 2011. Preliminary
version in ISITβ08. [doi:10.1109/TIT.2010.2094910] 2
[33] Abraham Lempel: Matrix factorization over πΊπΉ(2) and trace-orthogonal bases of πΊπΉ(2π ).
SIAM J. Comput., 4(2):175β186, 1975. [doi:10.1137/0204014] 8, 16
[34] LΓ‘szlΓ³ LovΓ‘sz: Kneserβs conjecture, chromatic number, and homotopy. J. Combin. TheoryβA,
25(3):319β324, 1978. [doi:10.1016/0097-3165(78)90022-5] 4
[35] LΓ‘szlΓ³ LovΓ‘sz: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(1):1β7,
1979. [doi:10.1109/TIT.1979.1055985] 2, 6
[36] LΓ‘szlΓ³ LovΓ‘sz: Graphs and Geometry. Volume 65 of Colloquium Publications. Amer. Math.
Soc., 2019. [doi:10.1090/coll/065] 3
[37] LΓ‘szlΓ³ LovΓ‘sz, Michael Saks, and Alexander Schrijver: Orthogonal representations and
connectivity of graphs. Lin. Alg. Appl., 114β115:439β454, 1989. Special Issue Dedicated to
Alan J. Hoffman. [doi:10.1016/0024-3795(89)90475-8] 3
[38] Laura ManΔinska and David E. Roberson: Quantum homomorphisms. J. Combin. TheoryβB,
118:228β267, 2016. [doi:10.1016/j.jctb.2015.12.009] 4
[39] RenΓ© Peeters: Orthogonal representations over finite fields and the chromatic number of
graphs. Combinatorica, 16(3):417β431, 1996. [doi:10.1007/BF01261326] 2, 3, 5, 17
[40] SΓΈren Riis: Information flows, graphs and their guessing numbers. Electr. J. Combinat.,
14(1):R44:1β17, 2007. Preliminary version in WiOptβ06. [doi:10.37236/962] 2
[41] Moshe Rosenfeld: Almost orthogonal lines in πΈ π . In Bernd Sturmfels and Peter Gritzmann,
editors, Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, volume 4 of
DIMACS Ser. in Discr. Math., pp. 489β492. 1991. [doi:10.1090/dimacs/004] 8
[42] Giannicola Scarpa and Simone Severini: Kochen-Specker sets and the rank-1
quantum chromatic number. IEEE Trans. Inform. Theory, 58(4):2524β2529, 2012.
[doi:10.1109/TIT.2011.2178018] 2
[43] Saul Stahl: π-tuple colorings and associated graphs. J. Combin. TheoryβB, 20(2):185β203,
1976. [doi:10.1016/0095-8956(76)90010-1] 3, 4, 5
[44] Saul Stahl: The multichromatic numbers of some Kneser graphs. Discr. Math., 185(1β
3):287β291, 1998. [doi:10.1016/S0012-365X(97)00211-2] 4, 5, 6, 9
[45] Claude Tardif and Xuding Zhu: A note on Hedetniemiβs conjecture, Stahlβs conjecture and
the Poljak-RΓΆdl function. Electr. J. Combinat., 26(4):P4.32:1β5, 2019. [doi:10.37236/8787] 4
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 20
T HE (G ENERALIZED ) O RTHOGONALITY D IMENSION OF (G ENERALIZED ) K NESER G RAPHS
[46] Γva Tardos: The gap between monotone and non-monotone circuit complexity is exponen-
tial. Combinatorica, 8(1):141β142, 1988. [doi:10.1007/BF02122563] 2
[47] Leslie G. Valiant: Graph-theoretic arguments in low-level complexity. In Proc. Internat.
Symp. Math. Foundations of Comp. Sci. (MFCSβ77), pp. 162β176. Springer, 1977. [doi:10.1007/3-
540-08353-7_135] 2, 7
[48] Marcin Wrochna and Stanislav Ε½ivnΓ½: Improved hardness for π»-colourings of πΊ-
colourable graphs. In Proc. 31st Ann. ACMβSIAM Symp. on Discrete Algorithms (SODAβ20),
pp. 1426β1435. SIAM, 2020. ACM DL. 3
[49] David Zuckerman: Linear degree extractors and the inapproximability of max clique and
chromatic number. Theory of Computing, 3(6):103β128, 2007. Preliminary version in STOCβ06.
[doi:10.4086/toc.2007.v003a006] 6
AUTHORS
Alexander Golovnev
Assistant professor
Department of Computer Science
Georgetown University
Washington, D. C, USA
alexgolovnev gamil com
https://golovnev.org/
Ishay Haviv
Associate professor
The Academic College of Tel Aviv-Yaffo
Tel Aviv, Israel
ishayhav mta ac il
http://www2.mta.ac.il/~ishayhav
ABOUT THE AUTHORS
Alexander Golovnev is an assistant professor at Georgetown University. Prior to
this, he was a Rabin postdoctoral fellow at Harvard University, a postdoctoral
fellow at Columbia University, and a research scientist at Yahoo Research. He
received his Ph. D. from the Courant Institute of Mathematical Sciences at
New York University where he was supervised by Oded Regev and Yevgeniy
Dodis. His interest in computational lower bounds was instilled by Alexander
S. Kulikovβlargely against his will.
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 21
A LEXANDER G OLOVNEV AND I SHAY H AVIV
Ishay Haviv is an associate professor at the school of Computer Science in the
Academic College of Tel Aviv-Yaffo. He received his Ph. D. from Tel Aviv
University where he was supervised by Oded Regev. His research lies in the
theoretical aspects of Computer Science and in their interactions with other fields
like Information Theory and classical areas of mathematics.
T HEORY OF C OMPUTING, Volume 18 (22), 2022, pp. 1β22 22