Given integers
For integers a and b, we use the notation [a, b] to denote the set {a, a + 1, . . . , b}. If a = 1, we abbreviate this to [b]. Let [n] k be the family of all k-sets on the ground set [n]. For a set of integers L ⊂ [0, k -1], an L-system is a family F ⊂ [n] k such that for any distinct sets A, B ∈ F, |A ∩ B| ∈ L.
L-systems correspond to independent sets in generalized Johnson graphs.
In particular, the Kneser graphs are the graphs G(n, k, {1, 2, . . . , k -1}), while the Johnson graphs are the graphs G(n, k, {0, 1, . . . , k -2}).
The correspondence between L-systems and independent sets of generalized Johnson graphs G(n, k, L) implies that if F ⊂ [n] k is an L-system, then |F| ≤ α(G(n, k, L)). In this paper, we study the Lovász number of generalized Johnson graphs G(n, k, L). The Lovász number ϑ(G) is a semidefinite programming approximation for the independence number α(G) of a graph G. The Lovász number is useful to compute the Shannon capacity c(G). 1 The Shannon capacity [20] of a graph G is defined as c(G) = lim n→∞ (α(G n )) 1/n , where G n = G n (recall the strong product of two graphs G and H is the graph G H with vertex set V (G) × V (H ), and (u 1 , v 1 ) ∼ (u 2 , v 2 ) if and only if u 1 = u 2 and v 1 ∼ v 2 or u 1 ∼ u 2 and v 1 = v 2 or u 1 ∼ u 2 and v 1 ∼ v 2 ). The Shannon capacity is notoriously hard to compute, as there is no known algorithm which computes the Shannon capacity in a finite amount of time; in fact, there is not even a known algorithm which can approximate the Shannon capacity to within a constant factor. Lovász [14] proved that α(G) ≤ c(G) ≤ ϑ(G), so if it can be shown that ϑ(G) = α(G) (as Lovász [14,Theorem 13] showed for the Kneser graph), then the Shannon capacity of the graph G is also determined. Indeed, Schrijver [19] (for n → ∞) and Wilson [21] (for the optimal range n ≥ (t +1)(k -t +1)) proved the t-intersecting Erdős-Ko-Rado theorem by showing ϑ(G(n, k, [t, k -1])) = n-t k-t , so it is natural to wonder how good an upper bound for α(G(n, k, L)) can be obtained from ϑ(G(n, k, L)). For example, does ϑ(G(n, k, L)) give the correct order of magnitude for α(G(n, k, L))?
The first main result of this paper is the determination of the leading order term of ϑ(G(n, k, L)) for fixed k and L with n → ∞. Let L = {ℓ 1 , ℓ 2 , . . . , ℓ s } with ℓ 1 < ℓ 2 < • • • < ℓ s . A set of integers {ℓ m , . . . , ℓ m+ p } ⊂ L is a run of consecutive integers in L if ℓ m+i = ℓ m + i for every 0 ≤ i ≤ p. The set {ℓ m , . . . , ℓ m+ p } is a full run of consecutive integers in L if additionally the following two conditions hold: (1) either m = 1 or ℓ m-1 < ℓ m -1; (2) either m + p = s or ℓ m+ p+1 > ℓ m+ p + 1. The set L may be divided uniquely into full runs of consecutive integers. For example, if L = {1, 3, 4, 7, 8, 9, 11}, then L = {1} ∪ {3, 4} ∪ {7, 8, 9} ∪ {11} contains 4 full runs of consecutive integers. The length of a run is the cardinality of the set associated with the run.
Suppose L contains b full runs of consecutive integers. Then, there is a constant c depending on k and L but not on n such that
and a constant C depending on k and L, but not on n such that
where m i is the length of the ith full run of consecutive integers in L for 1 ≤ i ≤ b.
In particular,
Since generalized Johnson graphs can be expressed as unions of graphs from the Johnson scheme, their Lovász number can be expressed as the solution of a linear program, as proved by Schrijver [18]. In Sect. 2, we introduce and analyze this linear program in order to prove Theorem 1.2.
Theorem 1.2 shows that ϑ(G(n, k, L)) is of the same order of magnitude as the two general bounds for the maximum size of a L-system, due to Deza-Erdős-Frankl and Ray-Chaudhuri-Wilson.
k is an L-system, then for n >
The Deza-Erdős-Frankl bound in Theorem 1.3 is always at least as strong as the Ray-Chaudhuri-Wilson bound in Theorem 1.4, but Theorem 1.4 is valid for all n. Schrijver [19,Equation (54)] asked if the Lovász number bound is at least as good as the Deza-Erdős-Frankl bound; that is, is it the case that
as n → ∞? For given n, k, L and L C = [0, k -1] \ L, it follows from an old result of Schrijver (Theorem 2.5 in Sect. 2 of the present paper) that one either has
Note that k k-ℓ > (k -ℓ)(ℓ + 1) when k ≥ ℓ + 2 and ℓ ≥ 3, so the Lovász number is usually worse than both the Ray-Chaudhuri-Wilson bound and the Deza-Erdős-Frankl bound when [8] (see also [9]) proved a general upper bound on the order of magnitude of the maximum size of an L-system in terms of the rank of an L-system, which is defined in terms of so-called intersection structures. Theorem 1.2 is therefore a somewhat negative result from the viewpoint of the question of determining the maximum size of an L-system, as it implies that the Lovász number cannot improve on the known order of magnitude bounds for L-systems as n → ∞ for any k and L.
On the other hand, we can use Theorem 1.2 to give explicit examples of graphs with large gaps between the Shannon capacity and the Lovász number (and a fortiori large gaps between the independence number and the Lovász number). The question of how large the ratio ϑ(G)/α(G) can be for a graph on n vertices is related to the question of how good an approximation ϑ(G) is for the independence number and the Shannon capacity. Lovász noted (see [13]) that for random graphs ϑ(G)/α(G) = (n 1 2 / log n), while Feige [5] gave a randomized construction showing that there is an infinite family of graphs with α(G) = n o (1) and ϑ(G) = n 1-o(1) . However, there does not seem to be much known about explicit constructions which give fairly large values of ϑ(G)/α(G) or ϑ(G)/c(G). Alon and Kahale [1] showed that for any > 0, there is a Frankl-Rödl graph on n vertices with ϑ(G) ≥ ( 1 2 -)n and α(G) = O(n δ ), where δ = δ( ) < 1. Peeters [16,Remark 2.1] showed that the symplectic graphs Sp(2m, 2) have c(Sp(2m, 2)) = log 2 (n + 1) + 1, while ϑ(Sp(2m, 2)) = √ n + 1 + 1, implying a ratio of ϑ/c = (n 1/2 / log n) (the number of vertices for these graphs is n = 2 2m -1).
Our second main result is that for any > 0, for infinitely many n there is an explicit construction of a graph G on n vertices with ratio ϑ(G)/c(G) = (n 1-). This also implies large ratios for ϑ(G)/α(G) and χ(G)/ϑ(G c ). Theorem 1.6 For any > 0 and infinitely many n, there is an explicit construction of a graph G on n vertices with:
ϑ(G)/c(G) = (n 1-).
Our explicit construction is a particular generalized Johnson graph. Generalized Johnson graphs have been used, for example, to give explicit constructions of Ramsey graphs [7] and large gaps between the minrank parameter of a graph and the Lovász number [12,15]. The main technical difference in our construction is that in the generalized Johnson graph we fix k and L and let n → ∞, while in previous constructions n is dependent on k. We give our construction in Sect. 4; in Sect. 3, we recall some tools that will be of use in proving Theorem 1.6, in particular the Haemers bound.
For completeness, we begin with the definition of an association scheme. For further background, we refer to the papers of Schrijver [18,19] and the thesis of Delsarte [3]. Definition 2.1 (Association Scheme) Let X be a finite set, and for an integer n ≥ 1, let R = {R 0 , R 1 , . . . , R n } be a partition of X × X . The pair (X , R) is a symmetric association scheme with n classes if
3. For any triple of integers i, j, k = 0, 1, . . . , n, there are intersection numbers p k i j such that, for all
Let |X | = m. Each pair (X , R i ) may be considered as a graph with vertices from X and edges x y if (x, y) ∈ R i . An alternative statement of Definition 2.1 is that an association scheme is an edge decomposition of the complete graph K m into graphs G 1 , . . . G n such that for 0 ≤ i, j, k ≤ n, A i A j = k p k i j A k , where A 0 = I and A i is the adjacency matrix of the graph G i for 1 ≤ i ≤ n.
One particular example of a symmetric association scheme is the Johnson scheme.
The Johnson scheme is a symmetric association scheme (X , R) where X is the set [n] k for positive integers k and n with n ≥ 2k, and
Generalized Johnson graphs correspond to unions of graphs in the Johnson scheme.
We now give a formal definition of the Lovász number of a graph.
Let G be a graph on n vertices. Let B be the set of all n × n matrices B = b i j such that B is positive semidefinite, trace(B) = 1 and b i j = 0 whenever i j ∈ E. Then,
For general graphs, the Lovász number can only be computed by a semidefinite program. However, as Schrijver [18,Theorem 4] proved, if the graph G is a union of graphs in a symmetric association scheme, then the semidefinite program can be reduced to a linear program. In the following theorem, we first give the general form of the linear program, and then specialize to the specific case of the Johnson scheme on [n] k .
Theorem 2.4 (Schrijver [18]) Let (X , R = {R 0 , . . . , R n }) be a symmetric association scheme and let 0 ∈ M ⊂ {0, . . . , n}. Let G = (X , E) be the graph with edge-set
(
where
For the Johnson scheme on [n] k ,
Note that we define P 0 i = ν i . We refer to the papers of Schrijver [18,19] for a full explanation of the terms μ u , ν i and P u i for general symmetric association schemes. We need a theorem of Schrijver [18] about the Lovász number of symmetric association schemes, which generalizes a result of Delsarte [3].
Theorem 2.5 (Schrijver [18]) Let G = (V , E) be a graph whose edge set is the union of graphs in a symmetric association scheme. Then,
We first prove Theorem 1.5.
To satisfy the u = ℓ + 1 constraint when n is sufficiently large, we need
123
We set a k-ℓ to be the right-hand side of the previous inequality. If u ≤ ℓ, then the leading order term of k-ℓ j=0 (-1)
so the choice of a k-ℓ satisfies these inequalities when n is large enough. If u > ℓ + 1, then the leading order term of k-ℓ j=0 (-1)
so with the choice of a k-ℓ , we have
implying that the inequalities are satisfied as n → ∞.
The expression for ϑ(G(n, k, L )) follows from the expression for ϑ(G(n, k, L)) and Theorem 2.5.
We now prove Theorem 1.2 by analyzing the preceding linear program. In the proof of Theorem 1.5, the important inequality we needed to satisfy was the u = ℓ 1 + 1 inequality. For general L = {ℓ 1 , ℓ 2 , . . . , ℓ s }, the most important inequalities to satisfy will be the inequalities obtained when u ∈ {ℓ 1 + 1, ℓ 2 + 1, . . . , ℓ s + 1}. We note that related arguments for specific L-systems were given by Bukh and Cox [2, Lemma 12 (2)] and by Schrijver [19]) in the proof for the t-intersecting Erdős-Ko-Rado theorem for large n.
for some constant c depending on k and L but not on n. This is sufficient to prove Theorem 1.2, as the same argument with
so Theorem 2.5 and Claim 2.6 (proved below) imply that
which together complete the proof of the claim. Indeed, consider two consecutive entries ℓ i and ℓ i+1 in L (and for the purpose of the following argument, set
and each full run of consecutive integers in L can be obtained in this way. The same argument with full runs in L and consecutive entries in L gives the other equality.
We have
1 , ℓ 2 , . . . , ℓ s }}. We have |X ∩ Y | = t if and only if 1 2 |X Y | = kt, so XY ∈ E(G(n, k, L)) if and only if XY / ∈ ∪ i∈M R i , where M = {0, k -ℓ 1 , . . . , k -ℓ s }. Therefore, by Theorem 2.4, the Lovász number ϑ(G(n, k, L)) is the solution of the following linear program (taking
(3)
Let P be the s × s matrix which has (i, j)-entry P (i, j) = P ℓ i +1 k-ℓ j , so that
Let a be the s × 1 column vector with a i =
. Then, the inequalities from
(3) with u ∈ {ℓ 1 + 1, . . . , ℓ s + 1} can be stated as
Let v be the (s × 1) column vector with
It is not a priori clear that such a v exists, but we will show subsequently in Lemma 2.8 that P is invertible as n → ∞. We claim that as n → ∞, the following is a feasible solution to this linear program:
By construction, any such solution (if the vector v exists) will satisfy the inequalities for u ∈ {ℓ 1 + 1, ℓ 2 + 1, . . . , ℓ s + 1} automatically. We will subsequently verify in Lemma 2.13 that the solution in (4) also satisfies the other inequalities as n → ∞.
We begin with a simple, but useful observation.
Claim 2.7 Let k, L, u be as before. As n → ∞,
). Hence, the leading order term of P u k-ℓ i is the n k-ℓ i -j term, where j ≥ 0 is the smallest nonnegative integer such that k-u k-ℓ i -j > 0, i.e. such that j ≥ u -ℓ i . The claim follows.
Claim 2.7 has two important consequences. First, we use Claim 2.7 to show that P is invertible as n → ∞. In fact, we determine the leading order term of det(P).
Let k and L be as before. As n → ∞,
In particular, P is invertible as n → ∞ and the solution (4) exists.
Proof of Lemma 2.8 By Claim 2.7, we have that
(
Recall the Leibniz formula for the determinant of an n × n matrix A = (a i j ) 1≤i, j≤n :
Recall sgn is the permutation sign function, so that sgn(σ ) = (-1) |inv(σ )| , where
is the set of inversions of σ . By (5), in row i the highest order of magnitude term is of the order n k-ℓ i -1 , so the highest order terms of det(P) are of the order n s i=1 (k-ℓ i -1) = n sk-(ℓ 1 +•••+ℓ s )-s . Let be the set of all permutations σ ∈ S s which have the property that
These are the highest order terms in the Leibniz formula for det(P). We show the following result, which will prove Lemma 2.8.
We prove a claim showing that the permutations in are of a rather restricted type.
Claim 2.9 Let σ ∈ . Then, for any 1 ≤ i ≤ s -1, σ (i) ≤ i + 1. Furthermore, if ℓ i is the last integer in its full run of consecutive integers in L, then σ (i) ≤ i.
Proof of Claim 2.9 Let σ ∈ S s be a permutation with σ (i) ≥ i + 2 for some 1 ≤ i ≤ s -2. Then,
), so the term in the Leibniz product formula corresponding to σ will be of an order smaller than n sk-(ℓ
Similarly, if σ is a permutation with σ (i) ≥ i + 1, where ℓ i is an integer which is last in its full run of consecutive integers, then
), since ℓ i+1 ≥ ℓ i + 2, so again the term in the Leibniz product formula corresponding to σ will be of smaller order. Claim 2.9 implies that every σ ∈ can only permute elements within each full run; that is, there are no ℓ i and ℓ j in different full runs of consecutive integers in L with σ (i) = j. We will therefore consider runs of consecutive integers in L. Let L m = {ℓ m+1 , ℓ m+2 , . . . , ℓ m+ p } be a (not necessarily full) run of p consecutive integers in L with ℓ m+ j+1 = ℓ m+ j + 1 for 1 ≤ j ≤ p -1. We prove a result on the terms of the matrix P coming from L m which will ultimately allow us to prove (6).
Let L m = {ℓ m+1 , ℓ m+2 , . . . , ℓ m+ p } be a run of p consecutive integers in L with ℓ m+ j+1 = ℓ m+ j + 1 for 1 ≤ j ≤ p -1. Let be the set of permutations λ on the set {m + 1, . . . , m + p} with λ(i
Proof of Lemma 2. 10 We proceed by strong induction on p. The case p = 1 follows from (5), as λ(m + 1) = m + 1, so sgn(λ) = 1 and P (m+1,λ(m+1)) = (-1) ℓ m+1 +1 (k-ℓ m+1 -1)! n k-ℓ m+1 -1 + O(n k-ℓ m+1 -2 ). Now suppose the statement of the lemma holds for all 1 ≤ r ≤ p -1; that is, assume that the lemma holds for any run of r consecutive integers {ℓ y , ℓ y+1 , . . . , ℓ y+r -1 } in L. We show that the statement holds for L m under this assumption. Divide the permutations λ in up according to the value of j for which λ(m + j) = m + 1. It follows from the conditions on λ that λ(m + i) = m + i + 1 for 1 ≤ i < j, so that for these permutations λ,
There are j -1 inversions on λ restricted to the set {m + 1, . . . , m + j}, given by the pairs (m + 1, m + j), . . . (m + j -1, m + j). We now note that there are no inversions
m+ j+1,m+ p] )|, where λ [m+ j+1,m+ p] is the restriction of the permutation λ to the set {m + j + 1, . . . , m + p}. Hence, by applying the inductive hypothesis to the set of consecutive integers {ℓ m+ j+1 , . . . , ℓ m+ p }, we obtain that λ∈ λ(m+ j)=m+1 sgn(λ [m+ j+1,m+ p] ) m+ p i=m+ j+1
is equal to
By summing over 1 ≤ j ≤ p, we obtain that λ∈ sgn(λ)
is equal to
completing the proof.
We now deduce (6), and thus Lemma 2.8, from Lemma 2.10. Denote the b (full) runs of consecutive integers in L by r 1 , . . . , r b , and the first integer of the ith full run by ℓ c i , and recall that the length of the ith full run is denoted by m i . By Claim 2.9, each permutation σ ∈ permutes only the elements within each full run r j . Furthermore, |inv(σ
where σ r i denotes the restriction of σ to the ith full run. Therefore, by Lemma 2.10,
The second consequence of Claim 2.7 is that since
. . , a k-ℓ s satisfy the following inequalities ( 7), (8), and ( 9), then they also satisfy (3) for sufficiently large n.
Here ( 8) must be satisfied for
We show that the claimed solution for a k-ℓ 1 , . . . , a k-ℓ s satisfies the inequalities ( 7), ( 8), (9) as n → ∞ for u ∈ [0, k] \ {ℓ 1 + 1, . . . , ℓ s + 1}. We first describe the solution a k-ℓ 1 , a k-ℓ 2 , . . . , a k-ℓ s more precisely.
For each 1 ≤ i ≤ s, let a k-ℓ i be the expression given by (4). Then, a k-ℓ i is a rational expression in n of degree si + 1 with positive leading order term C i , so that
Proof of Lemma 2. 11 We need a basic linear algebraic fact: if A is an n × n invertible matrix, then A -1 = 1 det(A) adj(A), where adj(A) is the adjugate matrix, which has (i, j) entry given by adj(A) i, j = (-1) i+ j det(A ( j,i) ), where A ( j,i) is the matrix obtained by removing the jth row and ith column from A.
We have
, where v is the vector
.
Therefore, we only need to analyze the terms in column s of P -1 . We first determine the leading order term of P -1 (1,s) . We have P -1 (1,s) = (-1) s+1 det(P) det(P (s,1) ). We find the leading order term of det(P (s,1) ) by the Leibniz formula. Let σ be a permutation which contributes to the leading order term of det(P (s,1) ). We claim that σ must be the identity permutation, i.e., σ (m) = m for 1 ≤ m ≤ s -1. By (5), the leading order term in the first row is 1
then σ ( j) ≥ j, and again by (5) we have
Therefore, by Lemma 2.8, as n → ∞ 1) s+i det(P) det(P (s,i) ), so we need to find the leading order term of det(P (s,i) ) by the Leibniz formula. Let * denote the set of permutations of [s -1] which contribute to the leading order term of the Leibniz formula for det(P (s,i) ). We claim that the permutations in * permute the elements in [1, i -1] and the elements in [i, s -1] separately. Claim 2.12 Let σ ∈ * be a permutation which contributes to the leading order term of det(P (s,i) ) in the Leibniz formula. Then, σ ( j
Proof of Claim 2.12 Let χ be a permutation of [s -1] which has χ( j) = z for some 1 ≤ j ≤ i -1 and some z ≥ i. Then, there is some m ≥ i and some 1 ≤ b ≤ i -1 such that χ(m) = b. Let τ be the permutation obtained from χ by swapping b and z, so that τ
which implies that χ / ∈ * . Since τ and χ agree except on j and m, it is enough to compare P ( j,χ ( j)) P (m,χ (m)) and P ( j,τ ( j)) P (m,τ (m)) . By (5), we have that P
), so that
For the permutation τ , there are four cases: if j < b, then P
). In each of the four cases, there is one term of order (n k-ℓ z+1 ) or order (n k-ℓ m -1 ) and one term of order (n k-ℓ b ) or (n k-ℓ j -1 ). Since max{ j, b} ≤ i -1 and min{m, z} ≥ i, it follows that min{ℓ m + 1, ℓ z+1 } > max{ℓ b , ℓ j + 1}, implying that P ( j,χ ( j)) P (m,χ (m)) = o(P ( j,τ ( j)) P (m,τ (m)) ), completing the proof of the claim.
For a permutation σ ∈ * , let σ [1,i-1] be the restriction of σ to the set [1, i -1] and let σ [i,s-1] be the restriction of σ to the set
We first consider the restriction of the permutation σ to the set [1, i -1]. The (i -1) × (i -1) submatrix P i-1 of P (s,i) given by the first i -1 rows and the first i -1 columns of P (s,i) is equivalent to the matrix obtained from the L-system with parameters k and L i-1 := {ℓ 1 , . . . , ℓ i-1 }:
. . . . . . . . .
Hence, by the proof of Lemma 2.8, we have that
where
where for simplicity we have assumed L i-1 has a full runs of consecutive integers with lengths m j for 1 ≤ j ≤ a.
For the restriction of the permutation σ to [i, s -1], by a similar inductive argument as was used for det(P (s,1) ), the only permutation on [i, s -1] which contributes to the leading order term in the Leibniz formula is the identity permutation on [i, s -1], so
where
These calculations give that
Hence, by Lemma 2.8,
where
is a positive constant (here C is the positive constant in the statement of Lemma 2.8).
We now show that the a k-ℓ i satisfy the inequalities in ( 7), ( 8), (9) 13 The solution (4) satisfies the inequalities (7), ( 8), (9)
Proof of Lemma 2.13 By Lemma 2.11, since the leading order term C 1 of a k-ℓ 1 is positive, the inequalities in (7) are satisfied by a k-ℓ 1 , . . . , a k-ℓ s for n sufficiently large.
The inequalities (8) with ℓ m + 2 ≤ u ≤ ℓ m+1 for 1 ≤ m ≤ s -1 will be satisfied for large n as the leading order term on the left-hand side is a k-ℓ m+1
Finally, for u ≥ ℓ s + 2, each term in the sum on the left-hand side of ( 9) is o(1), so these inequalities are satisfied as n → ∞.
We now complete the proof of Theorem 1.2. By Lemma 2.8 and Lemma 2.13, the solution in ( 4) is a feasible solution to (3). Hence, by Lemma 2.11,
It would be interesting to strengthen Theorem 1.2 by finding the exact value of ϑ(G(n, k, L)) (as Theorem 1.5 does if |L| = 1 or |L| = k -1) as n → ∞. We have opted for the computations presented here, as they are sufficient to obtain the order of magnitude of ϑ(G(n, k, L)) and the correct constant in front of the n s term.
We note that the argument used to prove Theorem 1.2 also asymptotically determines the best possible result the Delsarte linear programming bound [3,18] can give for the graphs G(n, k, L). Since the graphs G(n, k, L) are unions of graphs in the Johnson scheme, Delsarte's linear programming bound σ (G(n, k, L)) is equal to Schrijver's variant of the Lovász number [18], which is the same linear program as the linear program for the Lovász number in (1), with the additional restriction that the variables a 0 , a 1 , . . . , a n must all be nonnegative. The solution in the proof of Theorem 1.2 has all a k-ℓ i nonnegative, so (4) is also a feasible solution for Delsarte's linear programming bound, so as n → ∞,
On the other hand, σ (G(n, k, L)) ≤ ϑ(G(n, k, L)) by definition. We summarize this discussion in the following corollary.
Suppose L contains b full runs of consecutive integers. Then, there is a constant c depending on k and L, but not on n such that
and a constant C depending on k and L but not on n such that
where m i is the length of the ith full run of consecutive integers in L for 1 ≤ i ≤ b.
We need a different linear algebraic bound for the Shannon capacity of a graph proven by Haemers [10,11]. Haemers' bound is in terms of the minrank parameter of a graph. Haviv [12] has previously noted that the Haemers bound implies bounds on the minrank of certain generalized Johnson graphs. Indeed, many of the linear algebraic arguments of Frankl and Wilson [7] on the maximum size of an L-system can in fact more strongly be represented as upper bounds on the Shannon capacity of the associated generalized Johnson graph. We give one example of this strengthening.
Frankl and Wilson [7] proved the following theorem using inclusion matrices. Theorem 3.3 (Frankl-Wilson) Let F ⊂ [n] k and let q be a prime power. Suppose that for all distinct F, F ∈ F, |F ∩ F | ≡ k (mod q). Then,
Let G q (n, k) be the generalized Johnson graph corresponding to the L-system given in Theorem 3.3. Lubetzky and Stav [15] and Haviv [12,Proposition 4.5] have noted that essentially the same proof as that of Frankl and Wilson using inclusion matrices gives the following stronger result.
For the generalized Johnson graph G q (n, k), if q is a prime power and q ≤ k + 1, c(G q (n, k)) ≤ minrank F p (G q (n, k)) ≤ n q -1 .
It is this connection that we will use in giving an explicit construction of a graph with large gap between the Shannon capacity and the Lovász number. Note that Theorem 1.5 is already sufficient to obtain explicit generalized Johnson graphs with ratio ϑ/α = (n 1 2 -), as Frankl and Füredi [6] proved that α(G(n, k, L )) = (n max{k-ℓ-1,ℓ} ), where, as in the statement of Theorem 1.5, L = [0, k -1] \ {ℓ}. Furthermore, if ℓ + 1 is a prime power, then by setting k = 2ℓ + 1, Proposition 3.4 implies that the generalized Johnson graph G q (n, k) has ratio ϑ/c = (n 1 2 -). We next show how to obtain constructions with larger gap.
We now give our explicit construction.
Proof of Theorem 1. 6 We use a slight variation of the Ramsey construction of Frankl and Wilson [7]. Let q = p m be a prime power and define k = q 2 -1. Then, consider 123 the generalized Johnson graph G q (n, k) on [n] k vertices and with A ∼ B ⇐⇒ |A ∩ B| ≡ -1 (mod q). Proposition 3.4 implies minrank F p (G q (n, k)) ≤ n q -1 , while Theorem 1.2 implies ϑ(G q (n, k)) = (n q 2 -q ).
Therefore, with N = n q 2 -1 = (n q 2 -1 ), for n → ∞ ϑ(G q (n, k))/minrank F p (G q (n, k)) = (N
Given > 0, choosing q sufficiently large implies the second part of Theorem 1.6. The first part of Theorem 1.6 is a consequence of the second part of the theorem and the inequality α(G q (n, k)) ≤ c(G q (n, k)). The third part follows from the inequality χ(G q (n, k)) ≥ N α(G q (n,k)) = (n q 2 -q ) and the fact that ϑ(G q (n, k) C ) = (n q-1 ), which follows from Theorem 2.5. [15] provided a construction of a generalized Johnson graph G with ratio ϑ(G)/minrank F p (G) = (n for any > 0 and prime p, using Theorem 2.5 and the fact [16] that for any field F and n-vertex graph G, minrank F (G) • minrank F (G c ) ≥ n.
We finally note that Theorem 1.6 also holds if the Lovász number is replaced by the Schrijver variant σ (or the Delsarte linear programming bound). In particular, the graphs G q (n, k) again give an explicit construction of a graph G on N vertices with σ (G)/c(G) = (N 1-).
The Shannon capacity is more typically denoted (G). We use the notation c(G) to avoid clashes with the asymptotic notation .