A LOVAZS TYPE THEOREM

Abstract

Let C(n) be the set of all n-dimensional boolean vectors and C(n, k) be the set of all a = (a1, ..., an) ∈C(n) such that a1 + ... + an = k. For a ∈ C(n, k) let δ_i a denotes the vector of C(n-1) obtained from a by deleting the i-component of a The shadow of a is defined to be ∆a = {δ_i a: 1≤i≤n and ai = 0} and that of A∈C(n, k) is ∆A=∪_(a∈A) ∆a. In this paper we will prove a Lovazs type theorem: If A∈C(n, k) with |A|=(■(x@k)) then|∆A|=(■(x-1@k)), after showing that |(∆C(A)≤|∆C|)|where C(A) is the first |Al vectors of C(n,k) in V-order.