SUBCLOSE FAMILIES, THRESHOLD GRAPHS, AND THE WEIGHT HIERARCHY OF GRASSMANN AND SCHUBERT

CODES

SUDHIR R. GHORPADE, ARUNKUMAR R. PATIL, AND HARISH K. PILLAI

Dedicated to Gilles Lachaud on his sixtieth birthday

Abstract. We discuss the problem of determining the complete weight hierarchy of linear error correcting codes associated to Grassmann varieties and, more generally, to Schubert varieties in Grassmannians. In geometric terms, this corresponds to determining the maximum number of 𝔽_{q}-rational points on sections of Schubert varieties (with nondegenerate Plücker embedding) by linear subvarieties of a fixed (co)dimension. The problem is partially solved in the case of Grassmann codes, and one of the solutions uses the combinatorial notion of a closed family. We propose a generalization of this to what is called a subclose family. A number of properties of subclose families are proved, and its connection with the notion of threshold graphs and graphs with maximum sum of squares of vertex degrees is outlined.

1. Introduction

It has been almost a decade since the first named author and Gilles Lachaud wrote [5] where alternative proofs of Nogin’s results on higher weights of Grassmann codes [14] were given and Schubert codes were introduced. Originally, much of [5] was conceived as a side remark in [6]. But in retrospect, it appears to have been a good idea to write [5] as an independent article and use the opportunity to propose therein a conjecture concerning the minimum distance of Schubert codes. This conjecture has been of some interest, and after being proved, in the affirmative, in a number of special cases (cf. [1, 17, 7, 9]), the general case appears to have been settled very recently by Xiang [19]. The time sees ripe, therefore, to up the ante and think about more general questions. It is with this in view, that we discuss in this paper the problem of determining the complete weight hierarchy of Schubert codes and, in particular, the Grassmann codes. In fact, the case of Grassmann codes and the determination of higher weights in the cases not covered by the result in [14] and [5] has already been considered in some recent work (cf. [10, 11, 8]). What is proposed here is basically a plausible approach to tackle the general case.

This paper is organized as follows. In Section 2 below we recall the combinatorial notion of a close family, and introduce a more general notion of a subclose family. A number of elementary properties of subclose families are proved here, including a nice duality that prevails among these. Basic notions concerning linear error correcting codes, such as the minimum distance and more generally, the higher weights are reviewed in Section 3. Further, we state here a general conjecture that relates the higher weights of Grassmann codes and Schubert codes with subclose families. Finally, in Section 4, we recall threshold graphs and optimal graphs and then show that, in a special case, subclose families are closely related to these wellstudied notions in graph theory. As an application we obtain explicit bounds on the sum of squares of degrees of a simple graph in terms of the number of vertices and edges, which seem to ameliorate and complement some of the known results on this topic that has been of some interest in graph theory (cf. [3, 2, 15]).

Date: April 11, 2008.

2000 Mathematics Subject Classification. 94B05, 05C07, 05C35, 14M15.

Key words and phrases. Linear code, higher weight, Grassmann variety, Grassmann code, Schubert variety, Schubert code, threshold graph, optimal graph.

2. Close Families and Subclose Families

Fix integers ℓ, m such that 1 ≤ ℓ ≤ m. Set

k := \binom{m}{ℓ} and μ := max\{ℓ, m − ℓ\} + 1.

Let [m] denote the set {1, …, m} of first m positive integers. Given any nonnegative integer j, let I_{j}[m] denote the set of all subsets of [m] of cardinality j.

Let Λ ⊆ I_{ℓ}[m]. Following [6], we call Λ a close family if |A ∩ B| = ℓ − 1 for all A, B ∈ Λ. Suppose |Λ| = r. Then Λ is said to be of Type I if if there exists S ∈ I_{ℓ−1}[m] and T ⊆ [m] \ S with |T | = r such that

Λ = {S ∪ {t} : t ∈ T },

whereas Λ is said to be of Type II if there exists S ∈ I_{ℓ−r+1}[m] and T ⊆ [m] \ S with |T | = r such that

Λ = {S ∪ T \ {t} : t ∈ T }.

Basic results about close families are as follows.

Proposition 1 (Structure Theorem for Close Families). Let Λ ⊆ I_{ℓ}[m]. Then Λ is close if and only if Λ is either of Type I or of Type II.

This is proved in [6, Thm. 4.2]. An immediate consequence is the following.

Corollary 2. Let r be a nonnegative integer. A close family in I_{ℓ}[m] of cardinality r exists if and only if r ≤ μ. In greater details, a close family of Type I in I_{ℓ}[m] exists if and only if r ≤ m − ℓ + 1, whereas a close family of Type II in I_{ℓ}[m] exists if and only if r ≤ ℓ + 1.

We use this opportunity to state the following elementary result which complements Proposition 1. This is not stated explicitly in [5, 6], but a related result is proved in [8] where we obtain an algebraic counterpart of Proposition 1 in the setting of exterior algebras and the Hodge star operator.

Proposition 3 (Duality). Given Λ ⊆ I_{ℓ}[m], let Λ^{∗} := {[m]\A : A ∈ Λ} ⊆ I_{m−ℓ}[m]. Then Λ is close in I_{ℓ}[m] of type I if and only if Λ^{∗} is close in I_{m−ℓ}[m] of type II.

Proof. Given S ∈ I_{ℓ−1}[m] and T ⊆ [m] \ S with |T | = r, observe that

[m] \ (S ∪ {t}) = ([m] \ (S ∪ T)) ∪ T \ {t}

for every t ∈ T. □

As explained in [5], Corollary 2 essentially accounts for the barrier on r for which the higher weights d_{r} of Grassmann codes C(ℓ, m) are hitherto known. (See, e.g., [14, 5].) Recently some attempts have been made to break this barrier (cf. [10, 11, 8]) but the complete weight hierarchy {d_{r} : 1 ≤ r ≤ k} is still not known. We will comment more on this in Section 3. For the time being, we introduce a combinatorial generalization of close families which may play some role in the determination of higher weights.

Given a subset Λ = {A_{1}, ⋯, A_{r}} of I_{ℓ}[m], we define

K_{Λ} = ∑_{i<j} |A_{i} ∩ A_{j}|.

Further, given any nonnegative integer r ≤ k, we define

K_{r}(ℓ, m) := max{K_{Λ} : Λ ⊆ I_{ℓ}[m] and |Λ| = r}.

We call Λ a subclose family if K_{Λ} = K_{r}(ℓ, m) where r = |Λ|. It is clear that for each nonnegative integer r ≤ k, there exists a subclose family of cardinality r.

Proposition 4. Given Λ ⊆ I_{ℓ}[m], we have

K_{Λ} ≤ (ℓ − 1)\binom{|Λ|}{2}.

Moreover, equality holds if and only if Λ is a close family. Consequently, for any nonnegative integer r ≤ k, we have

K_{r}(ℓ, m) ≤ (ℓ − 1)\binom{r}{2}.

Moreover, equality holds if and only if r ≤ μ.

Proof. The last assertion follows from Corollary 2. The remaining assertions are obvious. □

It is an interesting question to determine K_{r}(ℓ, m) for any r. The first few values are given by the above result. We shall now determine some more. To this end, let us first observe the following analogue of Proposition 3.

Proposition 5 (First Duality Theorem). Given Λ ⊆ I_{ℓ}[m], consider the family of complements of sets in Λ, viz., Λ^{∗} := {[m] \ A : A ∈ Λ} ⊆ I_{m−ℓ}[m]. Then Λ is a subclose family in I_{ℓ}[m] if and only if Λ^{∗} is a subclose family in I_{m−ℓ}[m]. Moreover,

K_{r}(ℓ, m) = \binom{r}{2}(2ℓ − m) + K_{r}(m − ℓ, m) for 0 ≤ r ≤ k.

Proof: Write A^{c} for [m] \ A for A ∈ I_{ℓ}[m]. Then for any A, B ∈ I_{ℓ}[m], we have

|A ∩ B| = m − |A^{c} ∪ B^{c}| = m − (m − ℓ) − (m − ℓ) + |A^{c} ∩ B^{c}| = (2ℓ − m) + |A^{c} ∩ B^{c}|.

Thus if r := |Λ| and we write Λ = {A_{1}, …, A_{r}}, then

K_{Λ} = ∑_{1≤i<j≤r}(2ℓ − m) + |A_{i}^{c} ∩ A_{j}^{c}| = \binom{r}{2}(2ℓ − m) + K_{Λ^{∗}}.

Now as Λ varies over families in I_{ℓ}[m] of cardinality r, the dual Λ^{∗} varies over families in I_{m−ℓ}[m] of cardinality r. It follows that Λ is a subclose family in I_{ℓ}[m] if and only if Λ^{∗} is a subclose family in I_{m−ℓ}[m]. Moreover,

K_{r}(ℓ, m) = \binom{r}{2}(2ℓ − m) + K_{r}(m − ℓ, m) for 0 ≤ r ≤ k.  □

Recall that given any a, b ∈ ℤ, the binomial coefficient \binom{a}{b} is defined by

\binom{a}{b} := \{ \begin{matrix}\frac{a(a − 1) ⋯ (a − b + 1)}{b!} & if b ≥ 0, \\ 0 & if b < 0. \end{matrix}

With this in view, we may permit a and b to take negative values. We record some elementary properties of binomial coefficients, which will be useful in the sequel.

Lemma 6. Given any integers a, b, c, d, e, we have the following.

(i) \binom{a}{b} = \binom{a}{a − b} if and only if either a ≥ 0 or a < b < 0
(ii) \binom{a}{b} = 0 if and only if either b < 0 or b > a ≥ 0

(iii) \binom{a}{b}\binom{b}{c} = \binom{a}{c}\binom{a − c}{b − c}.

(iv) \binom{a + b}{c − e} = ∑_{j=e}^{c} \binom{a + d}{c − j}\binom{b − d}{j − e}.

Proof. Both (i) and (ii) are straightforward. Proofs of (iii) and (iv) are also elementary. See, for example, Lemma 3.2 and Corollary 3.4 of [4]. □

The value of K_{r}(ℓ, m) for the maximum permissible parameter r is determined below.

Proposition 7.

K_{k}(ℓ, m) = m\binom{ν}{2}, where ν := \binom{m − 1}{ℓ − 1}.

Proof. Observe that \frac{m}{ℓ}ν = \binom{m}{ℓ} = k, i.e., ν = ℓk/m. Write I_{ℓ}[m] = \{A_{1}, …, A_{k}\}. Then

(1) K_{k}(ℓ, m) = ∑_{1≤i<j≤k} |A_{i} ∩ A_{j}| = \frac{1}{2} (∑_{i,j} |A_{i} ∩ A_{j}| − ∑_{1≤i=j≤k} ℓ) = \frac{1}{2} [U − kℓ] ,

where

U := ∑_{A,B∈I_{ℓ}[m]} |A ∩ B|.

Thus it suffices to determine U, which is more symmetric than K_{k}(ℓ, m). To find U, note that for any A, B ∈ I_{ℓ}[m], the intersection A ∩ B is a subset E, say, of [m] of cardinality i ≤ ℓ. Thus,

U = _{∑_{E⊆[m]} ; |E|≤ℓ} _{∑_{A,B∈I_{ℓ}[m]} ; A∩B=E}|E|

= ∑_{i=0}^{ℓ}_{∑_{E⊆[m]} ; |E|=i}i|{(A, B) ∈ I_{ℓ}[m] × I_{ℓ}[m] : A ∩ B = E}|

= ∑_{i=0}^{ℓ} \binom{m}{i} [i\binom{m − i}{ℓ − i}\binom{m − ℓ}{ℓ − i}]

= ∑_{i=0}^{ℓ} i\binom{m}{i} [\binom{m − i}{m − ℓ}\binom{m − ℓ}{ℓ − i}]  [by Lemma 6 (i)]

= ∑_{i=1}^{ℓ} m [\binom{m − 1}{m − i}\binom{m − i}{m − ℓ}] \binom{m − ℓ}{ℓ − i}  [by Lemma 6 (ii)]

= m\binom{m − 1}{m − ℓ} ∑_{i=1}^{ℓ} \binom{ℓ − 1}{ℓ − i}\binom{m − ℓ}{ℓ − i}  [by Lemma 6 (iii)]

= m\binom{m − 1}{ℓ − 1} ∑_{i=1}^{ℓ} \binom{ℓ − 1}{i − 1}\binom{m − ℓ}{ℓ − i}  [by Lemma 6 (i)]

= m\binom{m − 1}{ℓ − 1}\binom{m − 1}{ℓ − 1}  [by Lemma 6 (iv)]
= mν^{2}.

Therefore, equation (1) becomes

K_{k}(ℓ, m) = \frac{1}{2} [U − kℓ] = \frac{1}{2} [mν^{2} − mν] = m\binom{ν}{2},

as desired. □

The above result will help us establish yet another version of duality among subclose families. But first we need a preliminary result whose proof is similar in spirit to the proof above.

Lemma 8. Given any A ∈ I_{ℓ}[m], we have

∑_{B∈I_{ℓ}[m]} ; B≠A|A ∩ B| = ℓ(ν − 1), where ν := \binom{m − 1}{ℓ − 1}.

Proof. As in the proof of Proposition 7, we have

∑_{B∈I_{ℓ}[m]} ; B≠A|A ∩ B| = ∑_{i=0}^{ℓ−1} _{∑_{E⊆A} ; |E|=i} _{∑_{B∈I_{ℓ}[m]} ; B∩A=E}|E|

= ∑_{i=0}^{ℓ−1} \binom{ℓ}{i}i\binom{m − ℓ}{ℓ − i}

= ℓ ∑_{i=1}^{ℓ−1} \binom{ℓ − 1}{i − 1}\binom{m − ℓ}{ℓ − i}

= ℓ [−1 + ∑_{i=1}^{ℓ} \binom{ℓ − 1}{i − 1}\binom{m − ℓ}{ℓ − i}]

= ℓ [\binom{m − 1}{ℓ − 1} − 1] ,

where the last equality follows from part (iv) of Lemma 6. □

Proposition 9 (Second Duality Theorem). Given Λ ⊆ I_{ℓ}[m], consider the complement Λ^{c} := I_{ℓ}[m] \ Λ. Then Λ is a subclose family in I_{ℓ}[m] if and only if Λ^{c} is a subclose family in I_{ℓ}[m]. Moreover, if we let r := |Λ| and ν := \binom{m−1}{ℓ−1}, then

(2)  K_{Λ^{c}} = m\binom{ν}{2} − rℓ(ν − 1) + K_{Λ}.

Consequently,

(3)  K_{k−r}(ℓ, m) = m\binom{ν}{2} − rℓ(ν − 1) + K_{r}(ℓ, m) for 0 ≤ r ≤ k.

Proof. Let Λ ⊆ I_{ℓ}[m]. In view of Proposition 7, we have

m\binom{ν}{2} = K_{k}(ℓ, m) = K_{I_{ℓ}[m]} = K_{Λ} + K_{Λ^{c}} + ∑_{A∈Λ} ∑_{B∈Λ^{c}} |A ∩ B|.

Further, in view of Lemma 8, we can write

∑_{A∈Λ} ∑_{B∈Λ^{c}} |A ∩ B| = ∑_{A∈Λ} (_{∑_{B∈I_{ℓ}[m]} ; B≠A}|A ∩ B| − ∑_{B∈Λ} ; B≠A |A ∩ B|)

= ∑_{A∈Λ} ℓ(ν − 1) − ∑_{A∈Λ} ∑_{B∈Λ} ; B≠A |A ∩ B|

= rℓ(ν − 1) − 2K_{Λ}.

It follows that

K_{Λ^{c}} = m\binom{ν}{2} − rℓ(ν − 1) + K_{Λ}.

This implies that K_{Λ^{c}} ≤ m\binom{ν}{2} − rℓ(ν − 1) + K_{r}(ℓ, m), and the equality holds if and only if Λ is subclose. Consequently,

K_{k−r}(ℓ, m) = m\binom{ν}{2} − rℓ(ν − 1) + K_{r}(ℓ, m),

and moreover, Λ is subclose if and only if Λ^{c} is subclose. □

Corollary 10. If s ∈ ℤ is such that k − μ ≤ s ≤ k, then

K_{s}(ℓ, m) = m\binom{ν}{2} − ℓ(ν − 1)(k − s) + (ℓ − 1)\binom{k − s}{2}, where ν := \binom{m − 1}{ℓ − 1}.

In particular, if m ≥ 4, then

K_{s}(2, m) = m\binom{m − 1}{2}−2 (k − s) (m−2)+\binom{k − s}{2}, for \binom{m − 1}{2} ≤ s ≤ \binom{m}{2}.

Proof. Given s ∈ ℤ with k − μ ≤ s ≤ k, observe that r := k − s satisfies 0 ≤ r ≤ μ. Now use (3) together with Proposition 4 to obtain the first equality. The second equality follows from the first by noting that if ℓ = 2 and m ≥ 4, then μ = m−1 = ν and k − μ = \binom{m−1}{2}. □

Example 11. Using the above results, one can readily compile a table of values of K_{r}(ℓ, m) for ℓ = 2 and for small values of m. For example, we have

\begin{matrix}r & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ K_{r}(2, 5) & 0 & 1 & 3 & 6 & 8 & 12 & 15 & 19 & 24 & 30 \end{matrix}

and

\begin{matrix}r & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ K_{r}(2, 6) & 0 & 1 & 3 & 6 & 10 & 12 & 15 & 19 & 24 & 30 & 34 & 39 & 45 & 52 & 60 \end{matrix}

where it may be noted that the barrier μ on the values of r is 4 in the first table and 5 in the second table. That is where the pattern begins to change.

3. Higher Weights of Grassmann Codes and Schubert Codes

We have made it amply clear in the Introduction that the combinatorial considerations in the preceding section were motivated by problems in Coding Theory, more specifically, the determination of the higher weights of linear codes associated to Grassmann and Schubert varieties. In this section, we begin by describing some relevant background, set up some notation, and then state a precise conjecture relating the said higher weights to subclose families.

Fix integers k, n with 1 ≤ k ≤ n and a prime power q. Let C be a linear [n, k]_{q}- code, i.e., let C be a k-dimensional subspace of the n-dimensional vector space 𝔽_{q}^{n} over the finite field 𝔽_{q} with q elements. Given any x = (x_{1}, …, x_{n}) in 𝔽_{q}^{n}, let

supp(x) := {i : x_{i} ≠ 0} and ∥x∥ := |supp(x)|

denote the support and the (Hamming) norm of x. More generally, for D ⊆ 𝔽_{q}^{n}, let

supp(D) := {i : x_{i} ≠ 0 for some x = (x_{1}, …, x_{n}) ∈ D} and ∥D∥ := |supp(D)|

denote the support and the (Hamming) norm of D. The minimum distance or the Hamming weight of C is defined by d(C) := min{∥x∥ : x ∈ C with x ≠ 0}. More generally, following [18], for any positive integer r, the r^{th} higher weight or the r^{th} generalized Hamming weight d_{r} = d_{r}(C) of the code C is defined by

d_{r}(C) := min {∥D∥ : D is a subspace of C with dim D = r} .

Note that d_{1}(C) = d(C). If C is nondegenerate, i.e., if C is not contained in a coordinate hyperplane of 𝔽_{q}^{n}, then it is easy to see that

0 < d_{1}(C) < d_{2}(C) < ⋯ < d_{k}(C) = n.

See, for example, [16] for a proof as well as a great deal of basic information about higher weights of codes. The set {d_{r}(C) : 1 ≤ r ≤ k} is often referred to as the (complete) weight hierarchy of the code C. It is usually interesting, and difficult, to determine the complete weight hierarchy of a given code.

An equivalent way of describing codes is via the language of projective systems, explained, for example in [16, 14, 5]. A [n, k]_{q}-projective system X is a (multi)set of n points in the projective space ℙ^{k−1} over 𝔽_{q}. We say X is nondegenerate if it is not contained in a hyperplane of ℙ^{k−1}. An [n, k]_{q}-nondegenerate projective system gives rise to a unique (up to isomorphism) nondegenerate [n, k]_{q}-linear code C_{X}. The minimum distance of C_{X} corresponds to maximizing the number of points of hyperplane sections of X, while the r^{th} higher weight corresponds to maximizing the number of points of sections of X by codimension r projective linear subspaces. More precisely, for 0 ≤ r ≤ k, we have

d_{r}(C_{X}) = n−max {|X ∩ Π| : Π is a projective subspace of codimension r in ℙ^{k−1}} .

Linear codes associated to projective systems given by the 𝔽_{q}-rational points of higher dimensional projective algebraic varieties defined over 𝔽_{q} have been of much interest lately, and we refer to the recent survey by Little [12] for more on this. We are particularly interested in the case of Grassmann variety G_{ℓ,m} and its Schubert subvarieties Ω_{α} = Ω_{α}(ℓ, m) with its nondegenerate Plücker embedding in ℙ^{k−1} and ℙ^{k_{α}−1}, respectively. Here, as in Section 2, ℓ, m are fixed positive integers with ℓ ≤ m and k := \binom{m}{ℓ}, while α varies over the natural indexing set for points of ℙ^{k−1}, namely,

I(ℓ, m) := {β = (β_{1}, …, β_{ℓ}) ∈ ℤ^{ℓ} : 1 ≤ β_{1} < ⋯ < β_{ℓ} ≤ m},

and for any α ∈ I(ℓ, m),

k_{α} := |I_{α}(ℓ, m)| where I_{α}(ℓ, m) := {β ∈ I(ℓ, m) : β_{i} ≤ α_{i} for all i = 1, …, ℓ}.

We identify ℙ^{k_{α}−1} with {p = (p_{β}) ∈ ℙ^{k−1} : p_{β} = 0 for all β ∈ I(ℓ, m) \ I_{α}(ℓ, m)} so that Ω_{α}(ℓ, m) = G_{ℓ,m} ∩ ℙ^{k_{α}−1}. For precise definitions of G_{ℓ,m} and Ω_{α}, and their Plücker embeddings, we refer to [5] and [7] or the references therein. The linear codes corresponding to G_{ℓ,m} and Ω_{α}(ℓ, m) are denoted by C(ℓ, m) and C_{α}(ℓ, m) respectively. The length n of C(ℓ, m) and n_{α} of C_{α}(ℓ, m) are respectively given by

n = |G_{ℓ,m}(𝔽_{q})| = \left[{m \atop ℓ}\right]_{q} := \frac{(q^{m} − 1)(q^{m} − q) ⋯ (q^{m} − q^{ℓ−1})}{(q^{ℓ} − 1)(q^{ℓ} − q) ⋯ (q^{ℓ} − q^{ℓ−1})} and n_{α} = |Ω_{α}(𝔽_{q})|.

The dimension k of C(ℓ, m) and k_{α} of C_{α}(ℓ, m) are respectively given by

k = |I(ℓ, m)| = \binom{m}{ℓ} and k_{α} := |I_{α}(ℓ, m)| .

A number of explicit formulas for n_{α} and k_{α} are given in [7].

Given any Λ ⊆ I(ℓ, m), we let Π_{Λ} denote the intersection of the corresponding Plücker coordinate hyperplanes; more precisely,

Π_{Λ} := {p = (p_{β}) ∈ ℙ^{k−1} : p_{β} = 0 for all β ∈ Λ} .

Note that Π_{Λ} is a projective linear subspace of codimension |Λ| in ℙ^{k−1}, and also that if Λ ⊆ I_{α}(ℓ, m), then Π_{Λ} ∩ℙ^{k_{α}−1} is a projective linear subspace of codimension |Λ| in ℙ^{k_{α}−1}.

There is a natural one-to-one correspondence between the indexing set I(ℓ, m) and the set I_{ℓ}[m] defined in the previous section, given simply by

β = (β_{1}, …, β_{ℓ}) ⟼ β̄ = {β_{1}, …, β_{ℓ}}.

With this in view, we shall identify I(ℓ, m) with I_{ℓ}[m], and apply the notions and results of Section 2 for I_{ℓ}[m] and its subfamilies to I(ℓ, m) and its subfamilies. In particular, we can talk about subclose families in I(ℓ, m). We are now ready to propose a plausible fact about the higher weights of C(ℓ, m) and C_{α}(ℓ, m).

Conjecture 12. Let r be a positive integer. If r ≤ k, then the r^{th} higher weight of the Grassmann code C(ℓ, m) is given by

d_{r}(C(ℓ, m)) = \left[{m \atop ℓ}\right]_{q}− max \{|G_{ℓ,m}(𝔽_{q}) ∩ Π_{Λ}| : Λ ⊆ I(ℓ, m) is subclose and |Λ| = r\} .

More generally, given any α ∈ I(ℓ, m), if r ≤ k_{α}, then the r^{th} higher weight of the Schubert code C_{α}(ℓ, m) is given by

d_{r}(C_{α}(ℓ, m)) = n_{α} − max {|Ω_{α}(𝔽_{q}) ∩ Π_{Λ}| : Λ ⊆ I_{α}(ℓ, m) is subclose and |Λ| = r} .

The evidence we have in favor of this conjecture is as follows.

(i) The conjecture is true in the case of C(ℓ, m) for 1 ≤ r ≤ max{ℓ, m−ℓ}+1. (See [5].)

(ii) The conjecture is true in the case of C(2, m) for r = max{2, m − 2} + 2.

(See [8].) (iii) The conjecture is true in the case of C_{α}(ℓ, m) for r = 1. (See [19].) (iv) The conjecture is true in the case of C_{α}(ℓ, m) where α is a submaximal element of I_{α}(ℓ, m) [so that the corresponding Schubert variety Ω_{α} is of codimension 1 in G_{ℓ,m}] for 1 ≤ r ≤ max{ℓ, m − ℓ}. (See [7].)

It may be remarked that the notion of a subclose family and the above conjecture is similar to, yet distinct from, the notion of a Schubert union introduced in [10] and the corresponding conjecture of Hansen, Johnsen and Ranestad [10, 11] that the higher weights are attained by Schubert unions. It may also be noted that for a given r, there may be more than one subclose family of cardinality r. Thus the above conjecture does not pinpoint to a single such family but simply narrows down the search for such a family.

4. Threshold Graphs, Optimal Graphs and Subclose Families

When ℓ = 2, the elements of the family I_{ℓ}[m] of ℓ-subsets of [m] := {1, …, m} can be viewed as the edges of a graph. It is, therefore, natural to investigate if the combinatorial notions and results in Section 2 have analogues and extensions in the rich and diverse field of graph theory. We will attempt to address these concerns in this section.

Given any Λ ⊆ I_{2}[m], we denote by G_{Λ} the graph whose vertex set is [m] and the edge set is Λ. Note that this is a simple (undirected) graph. Conversely, any simple graph on [m] is of the form G_{Λ} for a unique Λ ⊆ I_{2}[m]. To say that Λ is close corresponds to saying that any two edges of G_{Λ} are incident. Thus, Proposition 1 corresponds to the following elementary result in graph theory.

Proposition 13. A simple graph in which any two edges are incident is either a star or a triangle.

The analogue of subclose family is more interesting. Before explaining this, let us recall some notions from graph theory.^{1} Let G be a (m, r)-graph, i.e., a graph with m vertices (assumed to be elements of the set [m]) and r edges. We denote by g_{i} = g_{i}(G) the degree of the vertex i, viz., the number of edges emanating from it. The sequence (g_{1}, …, g_{m}) is called the degree sequence of G. It is well-known and easy to see that

(4)  ∑_{i=1}^{m} g_{i} = 2r.

A simple graph G is said to be a threshold graph if G can be constructed from a one-vertex graph by repeatedly adding an isolated vertex or a universal one (i.e., a vertex adjacent to every other vertex). A simple (m, r)-graph G is said to be (m, r)-optimal, or simply, optimal if

Σ(G) := ∑_{i=1}^{m} g_{i}(G)^{2}

is maximum among all simple (m, r)-graphs. Threshold graphs are a topic of considerable interest in graph theory, and we refer to [13] for more on this. It is easy to see that an optimal graph is a threshold graph (cf. [15, Fact 3]). In [15] it is shown that an optimal graph is one among certain six explicit classes of graphs. However, as the authors of [15] say, the complete characterization of optimal graphs remains an open question. The following explicit bound for Σ(G) for a (m, r)-graph G is given by de Caen [3].

(5) Σ(G) ≤ C(r, m) for m ≥ 2, where C(r, m) := r (\frac{2r}{m − 1} + m − 2) .

A somewhat more general bound has been obtained by Das [2]; however, this bound is not a pure function of m and r, but involves the maximum and the minimum among the vertex degrees g_{1}, …, g_{m}.

The relation between optimal graphs and subclose families is given below.

Proposition 14. Let Λ be a subset of I_{2}[m] with |Λ| = r. Then

K_{Λ} = \frac{1}{2}Σ(G_{Λ}) − r or equivalently, Σ(G_{Λ}) = 2K_{Λ} + 2r.

1We are using here a notation that is consistent with the notation of Section 2. Inconvenience caused, if any, to graph theorists, who may be more used to letting n be the number of vertices, e the number of edges, and d_{i} the degree of the vertex i, is regretted.

Consequently, Λ is a subclose family if and only if G_{Λ} is an optimal graph. Moreover,

max{Σ(G) : G is a simple (m, r)-graph} = 2K_{r}(2, m) + 2r.

Proof. Write Λ = {A_{1}, …, A_{r}}. Note that A_{i} ∩ A_{j} is either empty or singleton for 1 ≤ i < j ≤ r. Thus,

K_{Λ} = ∑_{i<j} |A_{i} ∩ A_{j}| = ∑_{i<j} ∑_{v∈A_{i}∩A_{j}} 1 = ∑_{v∈[m]}_{∑_{i<j} ; v∈A_{i}∩A_{j}}1 = ∑_{v∈[m]} \binom{g_{v}}{2}.

Further, in view of (4), we have

K_{Λ} = \frac{1}{2} ∑_{v∈[m]} g_{v}^{2} − r = \frac{1}{2}Σ(G_{Λ}) − r.

Since G_{Λ} varies over all simple (m, r)-graphs as Λ varies over subsets of I_{2}[m] of cardinality r, it follows that Λ is subclose if and only if G_{Λ} optimal, and moreover,

max{Σ(G) : G is a simple (m, r)-graph} = 2K_{r}(2, m) + 2r,

as desired. □

Corollary 15. Assume that m ≥ 4. Then for any simple (m, r)-graph G, we have

(6)  Σ(G) ≤ r(r + 1) for r ≤ m − 1,

and the equality holds if and only if G is a star with r + 1 vertices (and m − r − 1 isolated vertices).

Proof. Since m ≥ 4, we have μ := max\{2, m−2\}+1 = m−1. Thus, K_{r}(2, m) ≤ \binom{r}{2} for r ≤ m − 1, thanks to Proposition 4. Now apply Proposition 14 to obtain (6). The assertion about the equality follows from Proposition 13. □

Already, the trivial bound given by the Corollary above is superior to de Caen’s bound (5) in several cases. Indeed, an easy calculation shows that

C(r, m) − r(r + 1) = \frac{r(m − 3)(m − 1 − r)}{m − 1} > 0 for r < m − 1 and m ≥ 4.

The above result may also be compared with one of the cases where equality holds in a bound for Σ(G) obtained by Das [2].

It is well-known that dual graphs \overline{G} of optimal graphs G [defined in such a way that the non-edges of G are the edges of \overline{G}] are optimal (cf. [15, Fact 1]). This corresponds precisely to the special case ℓ = 2 of the Second Duality Theorem (Proposition 9). Further, it is easy to see that when ℓ = 2, equation (2) corresponds precisely to the following elementary relation for simple (m, r)-graphs G:

Σ(\overline{G}) = m(m − 1)^{2} − 4r(m − 1) + Σ(G).

The following bound, dual to the trivial bound given by (6), appears to be new.

Corollary 16. If G is a simple (m, r)-graph such that \binom{m−1}{2} ≤ r ≤ \binom{m}{2}, then

Σ(G) ≤ m(m−1)(m−2)+(k−r)(k−r−1)−4(k−r)(m−2)+2r, where k := \binom{m}{2}.

Proof. Follows from Corollary 10 and Proposition 14. □

Finally, we remark that the First Duality Theorem (Proposition 5) has no analogue in the setting of optimal graphs for the simple reason that it relates optimal graphs to objects that are not graphs, but hypergraphs. Indeed, as far as we know, not much seems to be known about threshold hypergraphs and optimal hypergraphs. Perhaps the notion of a subclose family and the results of Section 2 may be of some help in this direction.

Acknowledgments

We are grateful to Murali Srinivasan for helpful discussions and bringing [15] to our attention.

References

[1] H. Chen, On the minimum distance of Schubert codes, IEEE Trans. Inform. Theory, 46 (2000) 1535–1538.

[2] K. C. Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Math. 285 (2004) 57–66.

[3] D. de Caen, An upper bound on the sum of the squares of degrees of a graph, Discrete Math. 185 (1998) 245–248.

[4] S. R. Ghorpade, Young multitableaux and higher dimensional determinants, Adv. Math. 121 (1996) 167–195.

[5] S. R. Ghorpade and G. Lachaud, Higher weights of Grassmann codes, Coding Theory, Cryptography and Related Areas (Guanajuato, Mexico, 1998), pp. 122–131, Springer-Verlag, Berlin/Heidelberg, 2000.

[6] S. R. Ghorpade and G. Lachaud, Hyperplane sections of Grassmannians and the number of MDS linear codes. Finite Fields Appl. 7 (2001) 468–506.

[7] S. R. Ghorpade and M. A. Tsfasman, Schubert varieties, linear codes and enumerative combinatorics, Finite Fields Appl. 11 (2005) 684–699.

[8] S. R. Ghorpade, A. R. Patil and H. K. Pillai, Decomposable subspaces, linear sections of Grassmann varieties, and higher weights of Grassmann codes, arXiv.cs.IT/0710.5161 (2007).

[9] L. Guerra and R. Vincenti, On the linear codes arising from Schubert varieties, Des. Codes Cryptogr., 33 (2004) 173–180.

[10] J. P. Hansen, T. Johnsen, and K. Ranestad, Schubert unions in Grassmann varieties, Finite Fields Appl. 13 (2007) 738–750.

[11] J. P. Hansen, T. Johnsen, and K. Ranestad, Grassmann codes and Schubert unions, Arithmetic, Geometry and Coding Theory (AGCT-2005, Luminy), Séminaires et Congrès, Soc. Math. France, Paris, to appear.

[12] J. B. Little, Algebraic geometry codes from higher dimensional varieties, arXiv.cs.IT/0802.2349 (2008).

[13] N. V. R. Mahadev and U. N. Peled, Threshold Graphs and Related Topics, Ann. Discrete Math. 56, North Holland, Amsterdam, 1995.

[14] D. Yu. Nogin, Codes associated to Grassmannians, Arithmetic, Geometry and Coding Theory (Luminy, 1993), pp. 145–154, Walter de Gruyter, Berlin/New York, 1996.

[15] U. N. Peled, A. Petreschi and A. Sterbini, (n, e)-Graphs with maximum sum of squares of degrees, J. Graph Theory 31 (1999) 281–285.

[16] M. A. Tsfasman and S. G. Vlăduţ, Geometric approach to higher weights, IEEE Trans. Inform. Theory 41 (1995) 1564–1588.

[17] R. Vincenti, On some classical varieties and codes, Rapporto Technico 20/2000, Dip. Mat., Univ. di Perugia, Italy, 2000.

[18] V. K. Wei, Generalized Hamming weights for linear codes, IEEE Trans. Inform. Theory 37 (1991) 1412–1418.

[19] Xu Xiang, On the minimum distance conjecture of Schubert variety codes, IEEE Trans. Inform. Theory, 54 (2008) 486–488.

Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India.

E-mail address: srg@math.iitb.ac.in

Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India and Shri Guru Gobind Shinghji Institute of Engineering & Technology, Vishnupuri, Nanded 431 606, India

E-mail address: arun.iitb@gmail.com

Department of Electrical Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India.

E-mail address: hp@ee.iitb.ac.in