Sourav Chakraborty
email: sourav@cmi.ac.in.

On the sensitivity of cyclically-invariant Boolean functions

Keywords:

In this paper we construct a cyclically invariant Boolean function whose sensitivity is Θ(n 1/3 ). This result answers two previously published questions. Turán (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity Ω( √ n). Kenyon and Kutin (2004) asked whether for a "nice" function the product of 0-sensitivity and 1-sensitivity is Ω(n). Our function answers both questions in the negative.

We also prove that for minterm-transitive functions (a natural class of Boolean functions including our example) the sensitivity is Ω(n 1/3 ). Hence for this class of functions sensitivity and block sensitivity are polynomially related.

Introduction

Cook, Dwork and Reischuk [START_REF] Cook | Upper and lower time bounds for parallel random access machines without simultaneous writes[END_REF] originally introduced sensitivity as a simple combinatorial complexity measure for Boolean functions providing lower bounds on the time needed by a CREW PRAM. [START_REF] Nisan | Crew prams and decision trees[END_REF] introduced the concept of block sensitivity and demonstrated the remarkable fact that block sensitivity and CREW PRAM complexity are polynomially related.

Whether block sensitivity and sensitivity are polynomially related is still an open question. So far the quadratic gap found by [START_REF] Rubinstein | Sensitivity vs. block sensitivity of boolean functions[END_REF] is the largest known. But for an arbitrary Boolean function the best known upper bound on block sensitivity in terms of sensitivity is exponential. H.-U. [START_REF] Simon | A tight ω(log log n)-bound on the time for parallel ram's to compute nondegenerated boolean functions[END_REF] gave the best possible lower bound on sensitivity in terms of the number of effective variables. From that it follows that block sensitivity of a function f is O(s(f )4 s(f ) ), where s(f ) is the sensitivity of the function f . Kenyon and Kutin [START_REF] Kenyon | Sensitivity, block sensitivity, and -block sensitivity of boolean functions[END_REF] gave the best known upper bound on block sensitivity in terms of sensitivity; their bound is O e √ 2π e s(f ) s(f ) . Nisan pointed out [START_REF] Nisan | Crew prams and decision trees[END_REF] that for monotone Boolean functions sensitivity and block sensitivity are equal.

A natural direction in the study of the gap between sensitivity and block sensitivity is to restrict attention to Boolean functions with symmetry. We note that a slight modification of Rubinstein's construction (Example 2.15) gives a Boolean function, invariant under the cyclic shift of the variables, which still shows the quadratic gap between sensitivity and block sensitivity. Turán pointed out [START_REF] Turán | The critical complexity of graph properties[END_REF] that for symmetric functions (functions invariant under all permutations of the variables), block sensitivity is within a factor of two of sensitivity. For any non-trivial graph property (the n = V 2 variables indicate the adjacency relation among the V vertices), [START_REF] Turán | The critical complexity of graph properties[END_REF] proved that sensitivity is at least V = Θ( √ n) and therefore the gap is at most quadratic. In the same paper he also asked the following question:

Problem [START_REF] Turán | The critical complexity of graph properties[END_REF]: Does a lower bound of similar order hold still if we generalize graph properties to Boolean functions invariant under a transitive group of permutations?

In Section 3 we give a cyclically invariant function with sensitivity Θ(n 1/3 ). This example gives a negative answer to Turán's question.

Kenyon and Kutin [START_REF] Kenyon | Sensitivity, block sensitivity, and -block sensitivity of boolean functions[END_REF] observed that for "nice" functions the product of 0sensitivity and 1-sensitivity tends to be linear in the input length. Whether this observation extends to all "nice" functions was given as a (vaguely stated) open problem in that paper. In Section 3 we also construct a cyclically invariant Boolean function for which the product of 0-sensitivity and 1-sensitivity is Θ( √ n). Thus our function also gives a counterexample to Kenyon and Kutin's suggestion. In Section 2.1 we define a class of Boolean functions called the minterm-transitive functions (Definition 2.14). This class of function is a subclass of the class of functions invariant under some transitive group (Definition 2.8) and contains our new functions (that we give in Section 3). In Section 4 we prove that for minterm-transitive functions sensitivity is Ω(n 1/3 ) (where n is the input size) and the product of 0-sensitivity and 1-sensitivity is Ω( √ n). We also show that for this class of functions the sensitivity and block sensitivity is quadratically related. Our lower bound results generalizes to some bigger classes of Boolean functions (Section 5).

Preliminaries

Definitions

We use the notation [n] = {1, 2, 3, ..., n}. Let f : {0, 1} n → {0, 1} be a Boolean function. We call the elements of {0, 1} n "words." For any word x and 1 ≤ i ≤ n we denote by x i the word obtained by switching the ith bit of x. For a word x and A ⊆ [n] we use x A to denote the word obtained from x by switching all the bits in A. For a word x = x 1 , x 2 , ..., x n we define supp(x) as {i | x i = 1}. Weight of x, denoted wt(x), is |supp(x)|, i.e., number of 1s in x.

Definition 2.1 The sensitivity of f on the word x is defined as the number of bits on which the function is sensitive:

s(f, x) = |{i : f (x) = f (x i )}|.
We define the sensitivity of f as s(f

) = max{s(f, x) : x ∈ {0, 1} n } We define 0-sensitivity of f as s 0 (f ) = max{s(f, x) : x ∈ {0, 1} n , f (x) = 0} We define 1-sensitivity of f as s 1 (f ) = max{s(f, x) : x ∈ {0, 1} n , f (x) = 1}. Definition 2.2 The block sensitivity bs(f, x) of a function f on an input x is the maximum number of disjoint subsets B 1 , B 2 , ..., B r of [n] such that for all j, f (x) = f (x Bj ).
The block sensitivity of f , denoted by bs(f ), is max x bs(f, x).

Best known lower bound on sensitivity †

Least sensitivity for which an example is known General Functions

( 1 2 log m -1 2 log log m + 1 2 ) 1 2 log n + 1 4 log log n + O(1) Symmetric Functions n+1 2 n+1 2 Monotone Functions ( 1 2 log m -1 2 log log m + 1 2 ) 1 2 log n + 1 4 log log n + O(1)
Graph Properties on graphs with vertex set

V |V | 2 (|V | -1)
Cyclically Invariant Functions

( 1 2 log n -1 2 log log n + 1 2 ) Θ(n 1/3 ) Minterm Transitive Func- tions (2n) 1/3 Θ(n 1/3
) † For the lower bounds m denotes the number of relevant indices. An index i is said to be relevant for

f if there exist x ∈ {0, 1} n such that f (x) = f (x i ).
Tab. 1: Current knowledge about sensitivity of some classes of Boolean functions Definition 2.3 A partial assignment is a function p : S → {0, 1} where S ⊆ [n]. We call S the support of this partial assignment. The weight of a partial assignment is the number of elements in S that are mapped to 1. We call x a (full) assignment if x : [n] → {0, 1}. (Note than any word x ∈ {0, 1} n can be thought of as a full assignment.) We say p ⊆ x if x is an extension of p, i.e., the restriction of x to S denoted x| S = p. Definition 2.4 A 1-certificate is a partial assignment, p : S → {0, 1}, which forces the value of the function to be 1.

Thus if x| S = p then f (x) = 1. Definition 2.5 If F is a set of partial assignments then we define m F : {0, 1} n → {0, 1} as m F (x) = 1 ⇐⇒ (∃p ∈ F) such that (p ⊆ x).
Note that each member of F is a 1-certificate for m F and m F is the unique smallest such function. (Here the ordering is pointwise, i.e., f ≤ g if for all x we have f (x) ≤ g(x)).

Definition 2.6 A minterm is a minimal 1-certificate, that is, no sub-assignment is a 1-certificate. Definition 2.7 Let S ⊆ [n] and let π ∈ S n . Then we define S π to be {π(i) | i ∈ S}.
Let G be a permutation group acting on [n]. Then the sets S π , where π ∈ G, are called the G-shifts of S. If p : S → {0, 1} is a partial assignment then we define p π : S π → {0, 1} as p π (i) = p(π -1 i).

Definition 2.8 Let G be a subgroup of S n , i.e., a permutation group acting on [n]. A function f : {0, 1} n → {0, 1} is said to be invariant under the group G if for all permutations π ∈ G we have f (x π ) = f (x) for all x ∈ {0, 1} n . Definition 2.9 Let x = x 1 x 2 ...x n ∈ {0, 1} n be a word. Then for 0 < < n, we denote by cs (x) the word x +1 x +2 ...x n x 1 x 2 ...x , i.e., the cyclic shift of the variables of x by positions.

Definition 2.10 A function f : {0, 1} n → {0, 1} is called cyclically invariant if f (x) = f (cs 1 (x)) for all x ∈ {0, 1} n .
Note that a cyclically invariant function is invariant under the group of cyclic shifts.

Proposition 2.11 Let G be a permutation group. Let p : S → {0, 1} be a partial assignment and let

F = {p π | π ∈ G}. Then p is a minterm for the function m F .
The function m F will be denoted p G . Note that the function p G is invariant under the group G. When G is the group of cyclic shifts we denote the function p cyc . The function p cyc is cyclically invariant.

Proof of Proposition 2.11: If p has k zeros then for any word x with fewer than k zeros m F (x) = 0, since all the element of F has same number of 1s and 0s. But if q is a 1-certificate with fewer than k zeros we can have a word x by extending q to a full assignment by filling the rest with 1s, satisfying f (x) = 1 (since q ⊆ x). But x contains fewer than k zeros, a contradiction. So no minterm of m F has fewer than k zeros.

Similarly if p has k ones then no minterm of F can have less than k ones. So no proper sub-assignment of p can be a 1-certificate. Hence p is a minterm of m F . 2

Definition 2.12 Let G be a permutation group on [n]. G is called transitive if for all 1 ≤ i, j ≤ n there exists a π ∈ G such that π(i) = j.

Definition 2.13 Let C(n, k) be the set of Boolean functions f on n variables such that there exists a partial assignment p : S → {0, 1} with support k( = 0) for which f = p cyc . Let C(n) = ∪ n k=1 C(n, k). We will call the functions in C(n) minterm-cyclic. These are the simplest cyclically invariant functions.

Definition 2.14 Let G be a permutation group on [n]. We define D G (n, k) (for k = 0) to be the set of Boolean functions f on n variables such that there exists a partial assignment p : S → {0, 1} with support k for which f = p G . We define D G (n) to be ∪ n k=1 D G (n, k). This is a class of simple Ginvariant Boolean functions. We define D(n) to be ∪ G D G (n) where G ranges over all transitive groups. We call these functions minterm-transitive. Note that the class of minterm-cyclic functions is a subset of the class of minterm-transitive functions.

Previous Results

The largest known gap between sensitivity and block sensitivity is quadratic, given by Rubinstein [START_REF] Rubinstein | Sensitivity vs. block sensitivity of boolean functions[END_REF]. Although Rubinstein's example is not cyclically invariant, the following slight modification is cyclically invariant with a similar gap between sensitivity and block sensitivity.

Example 2.15 Let g : {0, 1} k → {0, 1} be such that g(x) = 1 iff x contains two consecutive ones and the rest of the bits are 0. In function f : {0, 1} k 2 → {0, 1} the variables are divided into groups B 1 , . . . , B k each containing k variables.

f (x) = g(B 1 ) ∨ g(B 2 ) ∨ • • • ∨ g(B k
). Using f we define the function f : {0, 1} k 2 → {0, 1} as f (x) = 1 iff f (x ) = 1 for some x which is a cyclic shift of x. The sensitivity of f is 2k while the block sensitivity is k 2 2 . Hans-Ulrich Simon [START_REF] Simon | A tight ω(log log n)-bound on the time for parallel ram's to compute nondegenerated boolean functions[END_REF] proved that for any function f we have s(f ) ≥ ( 1 2 log n-1 2 log log n+ 1 2 ), where n is the number of effective variables (the ith variable is effective if there exist some word x for which f (x) = f (x i )). This bound is tight. Although for various restricted classes of functions better bounds are known. Let f : {0, 1} m → {0, 1} be a Boolean function that takes as input the adjacency matrix of a graph G and evaluates to 1 iff the graph G has a given property. So the input size m is |V | 2 where |V | is the number of vertices in the graph G. Also f (G) = f (H) whenever G and H are isomorphic as graphs. Such a function f is called a graph property. György Turán [START_REF] Turán | The critical complexity of graph properties[END_REF] proved that non-trivial graph properties have sensitivity NisanNisan (1991) pointed out that for monotone functions sensitivity and block sensitivity are the same.

Ω( √ m). A function f is called monotone if f (x) ≤ f (y) whenever supp(x) ⊆ supp(y).
In the definition of block sensitivity (Definition 2.2) if we restrict the block size to be at most then we obtain the concept of -block sensitivity of the function f , denoted s (f ). In [START_REF] Kenyon | Sensitivity, block sensitivity, and -block sensitivity of boolean functions[END_REF] Kutin and Kenyon introduced this definition and proved that bs (f ) ≤ c s(f ) where c is a constant depending on .

Recently [START_REF] Sun | Block sensitivity of weakly symmetric functions[END_REF] proved that for functions that are invariant under some transitive group action the block sensitivity is at least n 1/3 and they gave an example of a function that has block sensitivity O(n 3/7 log n).

Table 1 gives a list of classes of Boolean functions and the current knowledge of sensitivity for these classes of functions.

3 Cyclically Invariant Function with Sensitivity Θ(n 1/3 ) In this section we will construct a cyclically invariant Boolean function which has sensitivity Θ(n 1/3 ). We will also construct a cyclically invariant function for which the product of 0-sensitivity and 1-sensitivity is Θ( √ n).

Theorem 3.1 There is a cyclically invariant function, f : {0, 1} n → {0, 1}, such that, s(f ) = Θ(n 1/3 ).

Theorem 3.2 There is a cyclically invariant function,

f : {0, 1} n → {0, 1}, such that, s 0 (f )s 1 (f ) = Θ( √ n).
For proving the above theorems we will first define an auxiliary function g on k 2 variables (k 2 ≤ n). Then we use g to define our new minterm-cyclic function f on n variables. If we set k = n 1/3 , Theorem 3.1 will follow. Theorem 3.2 follows by setting k = √ n .

The auxiliary function

We first define g : {0, 1} k 2 → {0, 1} where k 2 ≤ n. We divide the input into k blocks of size k each. We define g by a regular expression.

g(z) = 1 z ∈ 110 k-2 k (11111(0 + 1) k-5 k ) k-2 11111(0 + 1) k-8 111 k
We call this regular expression R.

In other words, let z ∈ {0, 1} k 2 and let z = z 1 z 2 ...z k , where each z i ∈ {0, 1} k for all 1 ≤ i ≤ k, i.e., z is broken up into k blocks of size k each. Then g(z) = 1 iff z 1 = (11 00...0

k-2
) and for all 2 ≤ j ≤ k the first five bits of z j are 1 and also the last 3 bits of z k are 1. Note that g does not depend on the rest of the bits.

The new function

Now we define the function f using the auxiliary function g. Let x| [m] denote the word formed by the first m bits of x. Let us set

f (x) = 1 ⇐⇒ ∃ such that g cs (x)| [k 2 ] = 1.
In other words, viewing x as laid out on a cycle, f (x) = 1 iff x contains a contiguous substring y of length k 2 on which g(y) = 1.

Properties of the new function

It follows directly from the definition that f is a cyclically invariant Boolean function.

It is important to note that the function g is so defined that the value of g on input z depends only on (6k -2) bits of z.

Also note that the pattern defining g is so chosen that if g(z) = 1 then there is exactly one set of consecutive (k -2) zeros in z and no other set of consecutive (k -4) zeros. Proof of Claim 3.3: (a) Let x be the following word:

(110 k-2 (111110 k-5 ) k-2 111110 k-8 111)0 n-k 2
Note that f (x) = 1. Also it is easy to see that on this input x 1-sensitivity of f is at least (6k -2). Now let x ∈ {0, 1} n be such that f (x) = 1. Now f (x) = 1 implies that some cyclic shift of x contains a contiguous substring z of length k 2 such that g(z) = 1. But since g depends only on the values of (6k -2) positions so one of those bits has to be switched so that f evaluates to 0. Thus s 1 (f ) ≤ 6k -2.

Combined with the lower bound s

1 (f ) ≥ 6k -2 we conclude s 1 (f ) = Θ(k). (b) Let n k 2 = m and r = (n -k 2 m). Let x be (100 k-2 (111110 k-5 ) k-2 111110 k-8 111) m 0 r
Proof: Let T be a maximal union of disjoint G-shifts of S. Since T is maximal, T hits all G-shifts of S, that is, for all π ∈ G we have T ∩ S π = ∅. Let H ij be the subset of G that sends the ith bit of the minterm to the bit position j. So the bit position j can at most hit

k i=1 |H ij | many G-shifts of S, that is |{π ∈ G | j ∈ S π }| ≤ k i=1 |H ij |.
Since G is transitive, for all i and j we have

|H ij | ≤ |G| n . Therefore ∀j, k i=1 |H ij | ≤ k |G| n . That is each bit position j |{π ∈ G | j ∈ S π }| ≤ k |G| n .
But Proof: By Lemma 4.3 we can have n k 2 disjoint G-shifts of p. The union of these disjoint G-shifts of p defines a partial assignment. Let Ŝ = {s 1 , s 2 , ..., s r } be the support of the partial assignment. And let Y si be the value of the partial assignment in the s i -th entry.

Since the function f is not a constant function, there exists a word z such that f (z) = 0. The i-th bit of z is denoted by z i . We This implies s(f ) ≥ (2n) 1/3 . Now since s 0 (f ) and s 1 (f ) cannot be smaller than 1, it follows from the Lemma 4.2 and Lemma 4.5 that

s 0 (f )s 1 (f ) = max n 2k , k 2 . So s 0 (f )s 1 (f ) ≥ √ n.
and bs(f ) = O(s(f ) 2 ). In particular it is still open whether the best gap between sensitivity and block sensitivity of cyclically invariant functions is quadratic.

The main question in this field is still open: Are sensitivity and block sensitivity polynomially related? Can the gap between them be more than quadratic? The following variant of Turán's question remains open:

Problem: If f is a Boolean function invariant under a transitive group of permutations then is it true that s(f ) = Ω(n c ) for some constant c > 0?

Claim 3. 3

 3 The function f has (a) 1-sensitivity Θ(k) and (b) 0-sensitivity Θ( n k 2 )

  define, T = {j | z j = Y sm , s m = j} Now let P ⊆ T be a maximal subset of T such that f (z P ) = 0. Since P is maximal, if we switch any other bit in T \P the value of the function f will change to 1. So s(f, z P ) ≥ |(T \P )|. Now since f (z P ) = 0 we note that z P does not contain any G-shift of p. But from Lemma 4.3 we know that z T contains n k 2 disjoint G-shifts of p. So |(T \P )| is at least n k 2 and thus s0 (f ) ≥ s(f, z P ) = n k 2 . 2 Corollary 4.5 If f ∈ D G (n, k) then s 0 (f ) ≥ n k 2 .Proof of Theorem 4.1: From the Lemma 4.2 and Corollary 4.5 we obtain, s(f ) = max{s 0 (f ), s 1 (f )

  there are |G| elements in G. So we must have |T | ≥ n k . Hence T must be a union of at least n k 2

disjoint G-shifts of S. And this proves the lemma. 2 Lemma 4.4 Let f : {0, 1} n → {0, 1} be a non-constant Boolean function invariant under a transitive group G. Let S ⊆ [n] and let p : S → {0, 1} be a 1-certificate of f . If the support of p has size k (i.e. |S| = k), then s 0 (f ) ≥ n k 2 .

Acknowledgements

I thank László Babai and Sandy Kutin for giving me lots of useful ideas and suggestions. I also thank Nanda Raghunathan for helpful discussions. Sandy Kutin helped me simplify the proof of Lemma 4.4.

Note that f (x) = 0. But if we switch any of the underlined zero the function evaluates to 1. Note that the function is not sensitive on any other bit. So on this input x the 0-sensitivity of f is m = n k 2 and therefore s 0 (f ) ≥ n k 2 -1. Now let x ∈ {0, 1} n and assume f (x) = 0 while f (x i ) = 1 for some 1 ≤ i ≤ n. By definition, the 0-sensitivity of f is the number of such i. For each such i there exists a contiguous substring z i of length k 2 of some cyclic shift of x i such that g(z i ) = 1. Now consider the z i i ⊆ x (recall z i i denotes the partial assignment obtained by switching the ith bit of z i ). Due to the structure of the pattern R we note that z i has exactly one set of consecutive (k -2) zeros. So z i i either has exactly one set of consecutive (k -1) zeros or exactly one set of consecutive (k -2) zeros or exactly one set of consecutive (k -2) bits with at most one of the bits being 1 while the remaining bits are zero. So the supports of any two z i i have at most three positions in common (since the pattern R begins and ends with 11). Hence the number of distinct

Proof of Theorem 3.1::

Proof of Theorem 3.2:: From Claim 3.3 we obtain s 0 (f )s

Theorem 3.1 answers Turán's problem [START_REF] Turán | The critical complexity of graph properties[END_REF] (see the Introduction) in the negative. In [START_REF] Kenyon | Sensitivity, block sensitivity, and -block sensitivity of boolean functions[END_REF], Kenyon and Kutin asked whether s 0 (f )s 1 (f ) = Ω(n) holds for all "nice" functions f . Although they do not define "nice," arguably our function in Theorem 3.2 is nice enough to answer the Kenyon-Kutin question in the negative.

In the next section we prove that for a minterm-transitive function, sensitivity is Ω(n 1/3 ) and the product of 0-sensitivity and 1-sensitivity is Ω( √ n). Since our example for Theorem 3.1 is also a minterm-transitive function, so our example is the best one can hope for with minterm-transitive functions.

4 Lower Bound on Sensitivity for Some Classes of Boolean Functions

To prove this theorem we will use the following three lemmas. Since f is a minterm-transitive function, i.e., f ∈ D(n), we can say f ∈ D G (n, k) for some transitive group G and some k = 0.

Proof: Let y be the minterm defining f . Without loss of generality wt(y) ≥ k 2 . Let us extend y to a full assignment x by assigning zeros everywhere outside the support of y. Then switching any 1 to 0 changes the value of the function from 1 to 0. So we obtain s(f, x)

The new function we looked at in Theorem 3.1 is minterm-transitive and has sensitivity Θ(n 1 3 ). Thus this lower bound on sensitivity is tight for minterm-transitive functions. Similarly for the function in Theorem 3.2 the product of 0-sensitivity and 1-sensitivity is tight.

We can even give tight upper bound on block sensitivity for minterm-transitive functions in terms of sensitivity.

Theorem 4.6 For a minterm-transitive function f : {0, 1} n → {0, 1} we have s(f ) ≥ bs(f ) k , where k is the size of the minterm.

Proof: Let x be the word for which the block sensitivity is bs(f ). Also let us assume that k ≥ 2 as if the size of the minterm is 1 then then the function becomes trivial with s(f ) = bs(f ) = n.

If f (x) = 1 then x must have at least one minterm. And then any sensitive block must touch that minterm. In that case bs(f ) is at most the size of the minterm, that is k. On the other hand since f is minterm-transitive so s(f ) is at least the k/2 (from Lemma 4.2). And so if f (x) = 1 then

That means x Bi has at least one minterm. Choose any minterm. Now that minterm can intersect at most (k -1) other blocks. By Turan's theorem of independence number of sparse graphs we obtain bs(f ) k blocks such that if we switch any block a minterm will be formed that does not intersects any other block. Let the union of these blocks be B. Now let A ⊂ B be the maximal set such that f (x A ) = f (x). So x A has sensitivity more than B\A. And B\A must have have at least one bit from all the blocks because if any block is switched fully then a minterm is formed because the minterm does not intersect any other block. So |B\A| ≥ (bs(f ) k . Hence s(f, x A ) ≥ bs(f ) k . 2

Corollary 4.7 For miniterm-transitive function, bs(f ) ≤ s(f ) 2 .

Proof: Follows from Theorem 4.6 and Lemma 4.2. 2

Hence for minterm-transitive functions, sensitivity and block sensitivity does not have a gap of more than quadratic. And this is tight.

Generalization of the Results and Open Problems

Note that Lemma 4.4 holds for any function invariant under some transitive group. But unfortunately the proof of Lemma 4.2 does not generalizes for all functions closed under some transitive group action. But the proof of Lemma 4.2 uses the fact that all the minterms of the Boolean function have more than k/2 number of 0 or all of them more than k/2 number of 1. Thus for functions having that property we can prove a similar lemma and hence for these kind of functions the sensitivity is also Ω(n 1/3 ).

For the proof of Theorem 4.6 the fact that is used is that all the minterms are of support less than k. So if a Boolean function, f, that is invariant under some transitive group, has all minterms of size k and weight at least (or at most) k/c for some constant c then the sensitivity of the function is Ω(n 1/3 )


David R Wood

On the number of maximal independent sets in a graph

Keywords: 05C30 Enumeration in graph theory; 05C69 Dominating sets, independent sets, cliques graph, independent sets

 determined the maximum number of maximal independent sets in an n-vertex graph

Let G be a (simple, undirected, finite) graph. A set S ⊆ V (G) is independent if no edge of G has both its endpoints in S. An independent set S is maximal if no independent set of G properly contains S. Let MIS(G) be the set of all maximal independent sets in G. [START_REF] Miller | A problem of maximum consistent subsets[END_REF] and [START_REF] Moon | On cliques in graphs[END_REF] independently proved that the maximum, taken over all n-vertex graphs G, of | MIS(G)| equals

g(n) :=      3 n/3 if n ≡ 0 (mod 3) 4 • 3 (n-4)/3 if n ≡ 1 (mod 3) 2 • 3 (n-2)/3 if n ≡ 2 (mod 3) .
This result is important for various reasons. For example, g(n) bounds the time complexity of various algorithms that output all maximal independent sets [START_REF] Bron | Finding all cliques of an undirected graph[END_REF][START_REF] Lawler | Generating all maximal independent sets: NP-hardness and polynomial-time algorithms[END_REF][START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF][START_REF] Tomita | The worst-case time complexity for generating all maximal cliques and computational experiments[END_REF][START_REF] Johnson | On generating all maximal independent sets[END_REF][START_REF] Eppstein | Small maximal independent sets and faster exact graph coloring[END_REF][START_REF] Eppstein | Listing all maximal cliques in sparse graphs in near-optimal time[END_REF].

Here we give a new and simple proof of this upper bound on | MIS(G)|.

Theorem 1 ( [START_REF] Miller | A problem of maximum consistent subsets[END_REF][START_REF] Moon | On cliques in graphs[END_REF])

For every n-vertex graph G, | MIS(G)| ≤ g(n) .
Proof: We proceed by induction on n. The base case with n ≤ 2 is easily verified. Now assume that n ≥ 3. Let G be a graph with n vertices. Let d be the minimum degree of G. Let v be a vertex of degree † woodd@unimelb.edu.au. Supported by a QEII Research Fellowship from the Australian Research Council.

d in G. Let N [v] be the closed neighbourhood of v. If I ∈ MIS(G) then I ∩ N [v] = ∅, otherwise I ∪ {v} would be an independent set. Moreover, if w ∈ I ∩ N [v] then I \ {w} ∈ MIS(G -N [w]). Thus | MIS(G)| ≤ w∈N G [v] | MIS(G -N G [w])| , Since deg(w) ≥ d and g is non-decreasing, by induction, | MIS(G)| ≤ (d + 1) • g(n -d -1) . Note that 4 • 3 (n-4)/3 ≤ g(n) ≤ 3 n/3 . If d ≥ 3 then | MIS(G)| ≤ (d + 1) • 3 (n-d-1)/3 ≤ 4 • 3 (n-4)/3 ≤ g(n) . If d = 2 then | MIS(G)| ≤ 3 • g(n -3) = g(n) . If d = 1 and n ≡ 1 (mod 3) then since n -2 ≡ 2 (mod 3), MIS(G) ≤ 2 • g(n -2) ≤ 2 • 2 • 3 (n-2-2)/3 = 4 • 3 (n-4)/3 = g(n) . If d = 1 and n ≡ 0 (mod 3) then since n -2 ≡ 1 (mod 3), MIS(G) ≤ 2 • g(n -2) ≤ 2 • 4 • 3 (n-2-4)/3 < 3 n/3 = g(n) .
If d = 1 and n ≡ 2 (mod 3) then since n -2 ≡ 0 (mod 3),

MIS(G) ≤ 2 • g(n -2) ≤ 2 • 3 (n-2)/3 = g(n) .
This proves that | MIS(G)| ≤ g(n), as desired. 2

For completeness we describe the example by [START_REF] Miller | A problem of maximum consistent subsets[END_REF] and [START_REF] Moon | On cliques in graphs[END_REF] that proves that Theorem 1 is best possible. If n ≡ 0 (mod 3) then let M n be the disjoint union of n 3 copies of K 3 . If n ≡ 1 (mod 3) then let M n be the disjoint union of K 4 and n-4 3 copies of K 3 . If n ≡ 2 (mod 3) then let M n be the disjoint union of K 2 and n-2 3 copies of K 3 . Observe that | MIS(M n )| = g(n). Note that [START_REF] Vatter | Maximal independent sets and separating covers[END_REF] gave another proof of Theorem 1, and also described a connection between this result and the question, "What is the largest integer that is the product of positive integers with sum n?" Also note that Dieter Kratsch proved that | MIS(G)| ≤ 3 n/3 using a similar proof to that presented here; see Gaspers (2010, page 177). Thanks to the authors of [START_REF] Vatter | Maximal independent sets and separating covers[END_REF][START_REF] Gaspers | Exponential Time Algorithms: Structures, Measures, and Bounds[END_REF] for pointing out these references.

  1365-8050 c 2011 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France


Ehsan Chiniforooshan
email: chiniforooshan@alumni.uwaterloo.ca

Vašek Chvátal
email: chvatal@cse.concordia.ca

A de Bruijn -Erd ős theorem and metric spaces

Keywords:

De Bruijn and Erdős proved that every noncollinear set of n points in the plane determines at least n distinct lines. Chen and Chvátal suggested a possible generalization of this theorem in the framework of metric spaces. We provide partial results in this direction.

Introduction

Two distinct theorems are referred to as "the de Bruijn -Erdős theorem". One of them [START_REF] De Bruijn | A colour problem for infinite graphs and a problem in the theory of relations[END_REF] concerns the chromatic number of infinite graphs; the other [START_REF] De Bruijn | On a combinatorial problem[END_REF] is our starting point:

Every noncollinear set of n points in the plane determines at least n distinct lines.

This theorem involves neither measurement of distances nor measurement of angles: the only notion employed here is incidence of points and lines. Such theorems are a part of ordered geometry [START_REF] Coxeter | Introduction to geometry[END_REF], which is built around the ternary relation of betweenness: point y is said to lie between points x and z if y is an interior point of the line segment with endpoints x and z. It is customary to write [xyz] for the statement that y lies between x and z. In this notation, a line uv is defined -for any two distinct points u and v -as

{p : [puv]} ∪ {u} ∪ {p : [upv]} ∪ {v} ∪ {p : [uvp]}. (1)
In terms of the Euclidean metric d, we have (2)

For an arbitrary metric space, equivalence (2) defines the ternary relation of metric betweenness introduced in [START_REF] Menger | Untersuchungen über allgemeine Metrik[END_REF] and further studied in [START_REF] Blumenthal | Theory and applications of distance geometry[END_REF][START_REF] Busemann | The geometry of geodesics[END_REF][START_REF] Chvátal | Sylvester-Gallai theorem and metric betweenness[END_REF]; in turn, (1) defines the line uv for any two distinct points u and v in the metric space. The resulting family of lines may have strange properties. For instance, a line can be a proper subset of another: in the metric space with points u, v, x, y, z and

d(u, v) = d(v, x) = d(x, y) = d(y, z) = d(z, u) = 1, d(u, x) = d(v, y) = d(x, z) = d(y, u) = d(z, v) = 2,
we have vy = {v, x, y} and xy = {v, x, y, z}.

Chen [START_REF] Chen | The Sylvester-Chvátal theorem[END_REF] proved that a classic theorem of ordered geometry, the Sylvester-Gallai theorem, generalizes in the framework of metric spaces (when lines in these spaces are defined differently than here). Chen and Chvátal [START_REF] Chen | Problems related to a de Bruijn-Erdős theorem[END_REF] suggested that the de Bruijn -Erdős theorem, too, might generalize in this framework:

True or false? Every finite metric space (X, d) where no line consists of the entire ground set X determines at least |X| distinct lines.

They proved that

• in every metric space on n points, there are at least lg n distinct lines or else some line consists of all n points.

We prove that

• in every metric space on n points, there are Ω((n/ρ) 2/3 ) distinct lines, where ρ is the ratio between the largest distance and the smallest nonzero distance (Theorem 1);

• in every metric space induced by a connected graph on n vertices, there are Ω(n 2/7 ) distinct lines or else some line consists of all n vertices (Corollary 1);

• in every metric space on n points where each nonzero distance equals 1 or 2, there are Ω(n 4/3 ) distinct lines and this bound is tight (Theorem 3).

Lines in hypergraphs

A hypergraph is an ordered pair (X, H) such that X is a set and H is a family of subsets of X; elements of X are the vertices of the hypergraph and members of H are its edges. A hypergraph is called k-uniform if each of its edges consists of k vertices. The definition of lines in a metric space (X, d) depends only on the 3-uniform hypergraph (X, H(d)) where

H(d) = {{a, b, c} : d(a, b) + d(b, c) = d(a, c) and a = b, b = c} :
the line uv equals {u, v} ∪ {w : {u, v, w} ∈ H(d)}. This observation suggests extending the notion of lines in metric spaces to a notion of lines in 3-uniform hypergraphs: for any two distinct vertices u and v in a 3-uniform hypergraph (X, H), the line uv is defined as {u, v} ∪ {w : {u, v, w} ∈ H }. Now every metric space (X, d) and its associated hypergraph (X, H(d)) define the same family of lines. Let f (n) denote the smallest number of lines in a 3-uniform hypergraph on n vertices where no line consists of all n vertices and let g(n) denote the smallest number of lines in a metric space on n points where no line consists of all n points. In this notation, f (n) ≤ g(n) for all n; Chen and Chvátal [START_REF] Chen | Problems related to a de Bruijn-Erdős theorem[END_REF]

proved that lg n ≤ f (n) < c √ lg n
for some positive constant c. (The proof of the lower bound is based on the observation that w ∈ uv if and only if v ∈ uw, and so -unless some line contains all the vertices -the mapping that assigns to each vertex the set of lines containing it is one-to-one.) The upper bound on f (n) does not rule out the possibility of g(n) = n: not all 3-uniform hypergraphs arise from metric spaces (X, d) as (X, H(d)).

(It has been proved ( [START_REF] Chvátal | Sylvester-Gallai theorem and metric betweenness[END_REF][START_REF] Chen | The Sylvester-Chvátal theorem[END_REF]) that the hypergraph consisting of the seven vertices 0, 1, 2, 3, 4, 5, 6 and the seven edges {i mod 7, (i + 1) mod 7, (i + 3) mod 7} with i = 0, 1, 2, 3, 4, 5, 6 does not arise from any metric space. This 3-uniform hypergraph is known as the Fano plane or the projective plane of order two.)

We let K 3 4 denote the 3-uniform hypergraph with four vertices and four edges. Lemma 1 Let H be a 3-uniform hypergraph, let x be a vertex of H, and let T be a set of vertices of H such that (i) x ∈ T and (ii) there are no vertices u, v, w in

T such that x, u, v, w induce a K 3 4 in H. Then H defines at least 2 -1/3 |T | 2/3 -2 -2/3 |T | 1/3
distinct lines.

Proof: Let S denote a largest subset of T such that all the lines xv with v ∈ S are identical. Now H defines at least |T |/|S| distinct lines, which gives the desired conclusion with room to spare when |S| ≤ 2 1/3 |T | 1/3 . We will prove that H defines at least |S|(|S| -1)/2 distinct lines, which gives the desired conclusion when |S| ≥ 2 1/3 |T | 1/3 . More precisely, we will prove that all the lines uv with u, v ∈ S are distinct. For this purpose, consider any three pairwise distinct vertices u, v, w in S. Since xu = xv = xw, all three of {x, u, v}, {x, u, w}, {x, v, w} are edges of H; since x, u, v, w do not induce a K 3 4 , it follows that {u, v, w} is not an edge of H; since w is an arbitrary vertex in S distinct from u and v, the line uv intersects S in {u, v}. 2

Lines in metric spaces

Theorem 1 In every metric space on n points such that n ≥ 2, there are at least

2 -1/3 n -1 ρ 2/3 -2 -2/3 n -1 ρ 1/3
distinct lines, where ρ is the ratio between the largest distance and the smallest nonzero distance.

Proof: Let the metric space be (X, d), let δ denote the smallest nonzero distance and let x be an arbitrary point of X. The n -1 distances d(x, u) with u = x are distributed into buckets [iδ, (i + 1)δ) with i = 1, 2, . . . , ρ . It follows that there are a subset T of X -{x} and a positive integer i such that

u ∈ T ⇒ iδ ≤ d(x, u) < (i + 1)δ
and |T | ≥ (n -1)/ ρ . We will complete the proof by showing that the hypergraph (X, H(d)) satisfies the hypothesis of Lemma 1. For this purpose, consider arbitrary points u, v, w in T such that {x, u, v}, {x, u, w}, {x, v, w} ∈ H(d); we will prove that {u, v, w} ∈ H(d). Since {x, u, v} ∈ H(d)

and |d(x, u) -d(x, v)| < δ ≤ d(u, v), we have d(u, v) = d(x, u) + d(x, v); similarly, d(u, w) = d(x, u) + d(x, w) and d(v, w) = d(x, v) + d(x, w). Since iδ ≤ d(x, u), d(x, v), d(x, w) < (i + 1)δ ≤ 2iδ, we conclude that 2iδ ≤ d(u, v), d(u, w), d(v, w) < 4iδ,
and so {u, v, w} ∈ H(d). 2

Metric spaces induced by graphs

Every finite connected undirected graph induces a metric space, where the distance between vertices u and v is defined as the smallest number of edges in a path from u to v.

Theorem 2 If, in a metric space (X, d) induced by a graph of diameter t, no line equals X, then there are at least t/2 distinct lines.

Proof: There are vertices v 0 , v 1 , . . . , v t such that d(v i , v j ) = j -i whenever 0 ≤ i < j ≤ t. Consider a largest set S of subscripts r such that all lines v r v r+1 are equal. There are at least t/|S| distinct lines; this gives the desired conclusion when |S| ≤ √ 2t. We will complete the argument by proving that there are at least |S|/2 distinct lines, which gives the desired conclusion when |S| ≥ √ 2t. Let u be any vertex outside the line v r v r+1 with r ∈ S. We will prove that at least |S|/2 of the lines uv r with r ∈ S are pairwise distinct: more precisely, for every three subscripts i, j, k in S, at least two of the three lines uv i , uv j , uv k are distinct.

By the triangle inequality and since u ∈ v r v r+1 , we have

| d(u, v r ) -d(u, v r+1 ) | < d(v r , v r+1 ) for all r in S; since d(v r , v r+1 ) = 1, it follows that d(u, v r ) = d(u, v r+1
) for all r in S. Now consider any three subscripts i, j, k in S such that i < j < k. We have

d(v i ,v j )+d(v j ,u) > d(v i+1 ,v j )+d(v j ,u) ≥ d(v i+1 ,u) = d(v i ,u), d(u,v i )+d(v i ,v j ) > d(u,v i )+d(v i+1 ,v j ) = d(u,v i+1 )+d(v i+1 ,v j ) ≥ d(u,v j ),
and so

v j ∈ uv i if and only if d(v i ,u)+d(u,v j ) = d(v i ,v j ). Similarly, v k ∈ uv j if and only if d(v j ,u)+ d(u,v k ) = d(v j ,v k ). Since d(u, v i ) + d(u, v k ) = d(u, v i ) + d(u, v k+1 ) ≥ d(v i , v k+1 ) = k + 1 -i,
Proof of Theorem 3. To see that h(n) ≤ (1 + o(1))βn 4/3 , consider the metric space where the ground set is split into pairwise disjoint groups of sizes as nearly equal as possible, every two points that belong to two different groups have distance 1, and every two points that belong to one group have distance 2.

If each group includes at least three points, then uv = wx if and only if either {u, v} = {w, x} or else there are two distinct groups such that each of the sets {u, v}, {w, x} has one element in each of these two groups. Consequently, when there are n points altogether and (1 + o(1))2 -1/3 n 2/3 groups, there are (1 + o(1))βn 4/3 lines.

To prove that h(n) ≥ (1+o(1))αn 4/3 , consider an arbitrary 1-2 metric space (X, d) and write n = |X|. Let X 1 be any maximal subset of X that does not contain a pair of twins.

CASE 1: |X 1 | ≥ n/2. In this case, consider a largest set of distinct two-point subsets

{u i , v i } (i = 1, 2, . . . , s) of X 1 such that u 1 v 1 = u 2 v 2 = . . . = u s v s .
Since every two-point subset of X 1 determines a line, there are at least

|X 1 | 2 • 1 s
distinct lines; this gives the desired conclusion when s ≤ (n/2) 2/3 . We will complete the argument by proving that there are at least s 2 -5

distinct lines, which gives the desired conclusion when s ≥ (n/2) 2/3 . For this purpose, we may assume that s ≥ 5. Part (iv) of Lemma 2 guarantees that the sets {u i , v i } with d(u i , v i ) = 1 are pairwise disjoint; part (vi) of Lemma 2 guarantees that the sets {u i , v i } with d(u i , v i ) = 2 are pairwise disjoint; part (ii) of Lemma 2 guarantees that each of the sets {u i , v i } with d(u i , v i ) = 1 meets each of the sets {u i , v i } with d(u i , v i ) = 2; now our assumption s ≥ 5 guarantees that all s distances d(u i , v i ) are equal. We are going to prove that there are at least s(s -1)/2 distinct lines: for every choice of subscripts i, j such that 1 ≤ i < j ≤ s, there is a line L ij such that

{u k , v k } ⊆ L ij ⇔ k ∈ {i, j}. SUBCASE 1.1: d(u 1 , v 1 ) = d(u 2 , v 2 ) = . . . = d(u s , v s ) = 1. Since {u j , v j } ⊆ u j v j = u i v i and {u i , v i } ⊆ u i v i = u j v j , we may assume (after switching u j with v j if necessary) that d(u i , u j ) = 2 and d(u i , v j ) = d(u j , v i ) = 1. Now we may set L ij = u i u j : if k ∈ {i, j}, then u j ∈ u j v j = u k v k implies that one of d(u j , u k ) and d(u j , v k ) equals 2, and so {u k , v k } ⊆ u i u j . SUBCASE 1.2: d(u 1 , v 1 ) = d(u 2 , v 2 ) = . . . = d(u s , v s ) = 2. Since u 1 v 1 = u 2 v 2 = .
. . = u s v s , the distance between any point in one of the sets {u 1 , v 1 }, {u 2 , v 2 }, . . . , {u s , v s } and any point in another of these s sets equals 1; it follows that we may set L ij = u i u j .

CASE 2: |X 1 | < n/2. Write X 2 = X -X 1 , consider a largest set S of points in X 2 such that Since every vertex of X 2 has a twin (else it could be added to X 1 ), Lemma 2 guarantees that every two distinct pairs in E 1 ∪ E 2 determine two distinct lines. We complete the argument by pointing out that 1))αn 4/3 : the famous theorem of Turán [START_REF] Turán | Eine Extremalaufgabe aus der Graphentheorie[END_REF][START_REF] Turán | On the theory of graphs[END_REF] The lower bound of Theorem 3 can be easily improved through a more careful analysis of Case 2: a routine exercise in calculus shows that

|E 1 ∪ E 2 | ≥ (1 + o(
x ≥ 3, y ≥ 0 ⇒ 1 2 • x 2 2y + x 2 + y ≥ βx 4/3 - x 2 ,
and so 1))βn 4/3 .

|E 1 ∪ E 2 | ≥ (1 + o(1))β|X 2 | 4/3 . Perhaps h(n) = (1 + o(

[

  abc] ⇔ a, b, c are three distinct points and d(a, b) + d(b, c) = d(a, c).

  u, v ∈ S, u = v ⇒ d(u, v) = 1,and writeE 1 = { {u, v} : u, v ∈ S, u = v}, E 2 = { {u, v} : u, v ∈ X 2 , d(u, v) = 2}.

  guarantees that |S| ≥ |X 2 | 2 2|E 2 | + |X 2 | ,and so|E 2 | < αn 4/3 implies |E 1 | ≥ (1 + o(1)) αn 4/3 . 2

Acknowledgements

This research was carried out in ConCoCO (Concordia Computational Combinatorial Optimization Laboratory) and undertaken, in part, thanks to funding from the Canada Research Chairs Program and from the Natural Sciences and Engineering Research Council of Canada.

In addition to expressing our gratitude for this support, we thank Christian Krattenthaler for his careful reading of the manuscript and suggesting improvements in its presentation.

we have d(u, v i ) > j -i or else d(u, v k ) > k -j. If d(u, v i ) > j -i, then d(v i ,u)+d(u,v j ) > d(v i ,v j ), and so v j ∈ uv i (and v i ∈ uv j ), which implies

, and so v k ∈ uv j (and v j ∈ uv k ), which implies uv j = uv k .

2

Corollary 1 If, in a metric space induced by a connected graph on n vertices, no line consists of all n vertices, then there are at least 2 -8/7 n 2/7 distinct lines.

Proof: If the graph has diameter at most 2 -9/7 n 4/7 , then the bound follows from Theorem 1; else it follows from Theorem 2. 2

5 Metric spaces where each nonzero distance is 1 or 2

By a 1-2 metric space, we mean a metric space where each nonzero distance is 1 or 2.

Theorem 3 The smallest number h(n) of lines in a 1-2 metric space on n points satisfies the inequalities

We say that points u, v in a 1-2 metric space are twins if, and only if, d(u, v) = 2 and d(u, w) = d(v, w) for all w distinct from both u and v. Our proof of Theorem 3 relies on the following lemma, whose proof is routine.

Lemma 2 If u 1 , u 2 , u 3 , u 4 are four distinct points in a 1-2 metric space, then:

and u 4 has a twin other than u 3 , then u 1 u 2 = u 3 u 4 .

If u 1 , u 2 , u 3 are three distinct points in a 1-2 metric space, then:

, and u 3 has a twin other than u 2 , then u 1 u 2 = u 2 u 3 , (vi) if d(u 1 , u 2 ) = d(u 2 , u 3 ) = 2, then u 1 u 2 = u 2 u 3 .

2


Thomas P Hayes
email: hayes@cs.unm.edu.

Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem

Keywords: communication complexity, extremal combinatorics, expander graphs

For every positive integer k, we construct an explicit family of functions f : {0, 1} n → {0, 1} which has (k + 1)party communication complexity O(k) under every partition of the input bits into k + 1 parts of equal size, and k-party communication complexity Ω n k 4 2 k under every partition of the input bits into k parts. This improves an earlier hierarchy theorem due to V. Grolmusz.

Our construction relies on known explicit constructions for a famous open problem of K. Zarankiewicz, namely, to find the maximum number of edges in a graph on n vertices that does not contain Ks,t as a subgraph.

• Worst-case partition: All possible partitions of the input into k parts are considered, and the complexity of f is the maximum of the various complexities.

• Best-case equipartition: All equipartitions of the input (partitions into k parts whose sizes differ by at most one) are considered, and the complexity of f is the minimum of the various complexities.

(If there were no restriction on the sizes of the parts, the complexity would always be zero.)

Our separation result for the multiparty communication complexity hierarchy holds in the strongest possible sense: our lower bound holds for every equipartition (even the best), and our upper bound holds for every partition (even the worst).

Theorem 1 Let k ≥ 2. There exists an explicit family of functions f : {0, 1} n → {0, 1} such that the (k+ 1)-party communication complexity of f is O(k) under any partition, while the k-party communication complexity is Ω n k 4 2 k under any equipartition.

If k is fixed and n → ∞, then this result is optimal up to constant factors:

Corollary 2 For every fixed k ≥ 2, there exists an explicit family of functions having k-party communication complexity Ω(n) under any equipartition of the inputs, and (k + 1)-party communication complexity O(1) under any partition of the inputs.

Our results were inspired by the following result of Grolmusz [START_REF] Grolmusz | Separating the Communication Complexities of MOD m and MOD p Circuits[END_REF], and by its proof.

Proposition 3 (Grolmusz [8]) Let k and k be fixed constants, such that there exists a prime k < p ≤ k .

There exists an explicit family of functions having k-party communication complexity Ω(n) under some equipartition of the inputs, and k -party communication complexity O(1) under any partition of the inputs.

We have improved this by removing the condition k < p ≤ k , and by extending the lower bound to hold for for arbitrary equipartitions.

Related Work

A number of other "communication complexity hierarchies" have been studied previously-see, for instance [START_REF] Papadimitriou | Communication Complexity[END_REF][START_REF] Babai | Complexity classes in communication complexity theory[END_REF][START_REF] Hromkovič | Some hierarchies for the communication complexity measures of cooperating grammar systems[END_REF]. These include, for instance, hierarchies based on the number of rounds, and on communication complexity versions of standard complexity theory hierarchies.

Ďuriš et al. [START_REF] Ďuriš | On Multi-Partition Communication Complexity[END_REF] recently proved a separation result in a two-player multi-partition model of communication complexity. Although their results have some interesting similarities to our own, there does not seem to be any real connection between the models. Some unpublished notes of T. Pitassi [START_REF] Pitassi | Best-Partition Multiparty Communication Complexity[END_REF] present substantially the same construction and results as ours. Although she has graciously conceded priority, we wish to acknowledge her independent discovery.

Preliminaries

In this section, we summarize the definitions and familiar results which form the building blocks of our construction. The family of functions we will construct is defined using a particular class of hypergraphs, which is in turn defined using Zarankiewicz graphs.

Definition 4 Let H be a hypergraph. The function GIP H : {0, 1} V (H) → {0, 1} is defined by

GIP H ( x) := e∈E(H) v∈e x v (mod 2),
and is called the generalized inner product over H.

Remark. The mapping H → GIP H defines a bijection between the set of hypergraphs with vertex set V and the set of all functions f : V → {0, 1}. Indeed, the edges of H correspond to the monomial terms when GIP H is written as a multilinear polynomial over GF [START_REF] Babai | Complexity classes in communication complexity theory[END_REF].

The following observation has long been known, and has appeared in many contexts.

Observation 5 If the largest edge in H contains k -1 vertices, then there is a k-party communication protocol evaluating GIP H using at most k bits of communication.

Proof: By definition GIP H is a polynomial of degree at most k-1 over GF (2). For each monomial, there exists a player who can evaluate it. Assign each monomial to the lowest index player who can evaluate it. Each player evaluates his assigned monomials, then takes their mod 2 sum, adds it to the previous communicated bit, if any, and broadcasts this bit as his message. 2

When H is a perfect matching, GIP H is the usual inner product over GF (2). More generally, when the edges of H are pairwise disjoint and of size k, GIP H = GIP k is the generalized inner product function of Babai, Nisan and Szegedy [START_REF] Babai | Multiparty Protocols, Pseudorandom Generators for Logspace and Time-Space Trade-offs[END_REF]. These authors showed showed that C k (GIP k ) = Ω(n/4 k ). Their result was improved by Chung and Tetali [START_REF] Chung | Communication complexity and quasi randomness[END_REF] to: Proposition 6 Let H be a k-uniform perfect matching on n vertices. Then

C k (GIP H ) = Ω n k2 k .
Remark. A nearly-matching upper bound of O(n/2 k ) is due to Grolmusz [START_REF] Grolmusz | The BNS Lower Bound for Multi-Party Protocols is Nearly Optimal[END_REF].

Definition 7 If H is a hypergraph, and S ⊆ V (H) is a set of vertices, then the sub-hypergraph of H induced by S is the hypergraph G with vertex set S and edge set {e ∈ E(H) | e ⊆ S}.

Proposition 8 If G is a vertex-induced sub-hypergraph of H, as defined above, then C(GIP H ) ≥ C(GIP G ). Proof: Observe that GIP G is the restriction of GIP H induced by setting x v = 0 for all v ∈ V (H)-V (G).
The result is immediate. 2

We will use graphs with the following property in our construction.

Definition 9

Let G be a graph on n vertices, and let c > 0. We say G is c-interconnected if, for every pair of disjoint sets

S 1 , S 2 ⊂ V such that |S 1 | , |S 2 | ≥ c
, there exists at least one edge from S 1 to S 2 . In other words, the complement of G contains no K c,c subgraph.

Remark. Finding the minimum number of edges in a c-interconnected graph is a special case of a notoriously difficult question called the Zarankiewicz problem. This problem is normally phrased as, for positive integers s, t, to find the maximum number of edges in a graph containing no subgraph isomorphic to K s,t . Our question is the complemented version of the case s = t = c. An explicit construction for the Zarankiewicz problem in the case s ≥ t! was found by Kollár, Rónyai and Szabó [START_REF] Kollár | Norm-Graphs and Bipartite Turán Numbers[END_REF], using sophisticated methods from algebraic geometry. For the case s = t = c ≥ 3, even the correct order of magnitude for the right answer is not known, and no explicit constructions approach the naive probabilistic bound below, which appears to be folklore.

Proposition 10 Let G be a random graph on n vertices, with each possible edge independently included with probability p > 0. Then G is (3 ln(n)/p)-interconnected with probability at least 1 -n -3 ln(n)/p .

Proof: The expected number, X, of sets S 1 , S 2 , of size c = 3 ln(n)/p with no edges between them is

EX = n c n -c c (1 -p) c 2 < n 2c e -pc 2 = n -3 ln(n)/p ,
and the claimed result follows by Markov's inequality. 2

For explicit constructions of c-interconnected graphs, we rely on explicit constructions of expanders. The best possible expanders are Ramanujan graphs (defined below). The first explicit constructions of these were by Lubotzky, Philips and Sarnak [START_REF] Lubotzky | Ramanujan graphs[END_REF] and Margulis [START_REF] Margulis | Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators[END_REF].

Definition 11 Let G be a d-regular graph on n vertices. Let d = λ 1 ≥ λ 2 ≥ • • • ≥ λ n be the eigenvalues of G. G is called a Ramanujan graph if all eigenvalues of G are in the set {-d, d}∪[-2 √ d -1, 2 √ d -1].
Remark. When G is connected and non-bipartite, it has a single largest eigenvalue in absolute value, so in this case, the n -

1 other eigenvalues lie in [-2 √ d -1, 2 √ d -1]
. The Expander Mixing Lemma, (see, for instance, [1, Corollary 9.2.5]) implies that connected nonbipartite Ramanujan graphs are highly interconnected. We will make use of the following corollary; a proof is included for completeness. Substituting, we have

m(S, T ) - |S||T |d n = n i=2 α i β i λ i ≤ n i=2 |α i β i |2 √ d -1
By the Cauchy-Schwarz inequality,

n i=2 |α i β i | 2 ≤ n i=1 α 2 i n i=1 β 2 i = |S||T |.
It follows that

m(S, T ) ≥ |S||T |d n -2 |S||T |(d -1) = |S||T |(d -1) |S||T |d n √ d -1 -2 > |S||T |(d -1) c √ d + 1 n -2 .
By the definition of c, this last term is non-negative. Hence m(S, T

) > 0, proving that G is c-intercon- nected. 2
Remark. Alon used the same analysis to give a somewhat stronger result, namely that, for somewhat larger sets S and T , the density of edges between S and T is always approximately the same as the density of edges in the entire graph G.

Results

The next two lemmas present surprising properties of c-interconnected graphs. These will be used in the proof of Theorem 1, but may also be interesting in their own right. First, we find it convenient to generalize the concept of c-interconnectedness:

Definition 13 Let c be a positive integer. We say a graph G = (V, E) is c-starry if the following holds. Let S 1 , S 2 , . . . , S m ⊂ V be pairwise disjoint sets, each of size at least c. Then there exist vertices

v 1 ∈ S 1 , v 2 ∈ S 2 , . . . , v m ∈ S m that form a star in G, i.e. there is an index 1 ≤ j ≤ m such that for all i = j, (v j , v i ) ∈ E.
Remark. Every c-starry graph is c-interconnected, since we can let m = 2 in Definition 13. Surprisingly, the converse is also true:

Lemma 14 Every c-interconnected graph G is c-starry.
Proof: Let G = (V, E) and let S 1 , S 2 , . . . , S m ⊂ V be pairwise disjoint sets, each of size at least c.

For 1 ≤ i ≤ m, let T i = V \ S i \ Γ(S i ) = {v ∈ V \ S i | ∀w ∈ S i , (v, w) / ∈ E}. By hypothesis, |T i | < c, since G contains no edge from T i to S i . Hence |∪ i T i | ≤ (c -1)m < cm = |∪ i S i | ,
so by the pigeonhole principle, there exists an element v j ∈ (∪ j S j ) \ (∪ i T i ), which is the center of the desired star.

2

The following corollary is incidental to our main result, but may be of independent interest.

Corollary 15 Let G = (V, E) be a c-interconnected graph. Let T be any tree on m vertices, and denote

V (T ) = {t 1 , . . . , t m }. Let S 1 , S 2 , . . . , S m ⊂ V be pairwise disjoint sets such that for all i, |S i | ≥ d i c
, where d i is the degree of t i in T . Then there exist vertices

v 1 ∈ S 1 , v 2 ∈ S 2 , . . . , v m ∈ S m such that if (t i , t j ) ∈ E(T ), then (v i , v j ) ∈ E(G).
The proof is a straightforward induction, which we omit. We are now ready to begin our construction.

Definition 16 Let G = (V, E) be a graph. We define the hypergraph of k-stars in G to be the k-uniform hypergraph on vertex set V , whose edges are all k-tuples in which at least one vertex is adjacent to the other k -1.

Lemma 17 Let G = (V, E) be a c-interconnected regular graph of degree d on n vertices. Let H be the hypergraph of k-stars in G. Then, for any equipartition of V into k parts, there exists S ⊂ V , with |S| > n-kc kd , such that the sub-hypergraph of H induced by S consists of pairwise disjoint edges, each of which intersects all k parts nontrivially.

Proof: We define S recursively. Initially, let S be empty. In each stage, apply Lemma 14 to find a star having one vertex in each set of the partition. Add these k vertices to S. Delete the k vertices, and all their neighbors, from G. Repeat, restricting the given partition to the remaining vertices of G.

After i stages, at most ikd vertices have been removed from G, which means each set in the partition still has size at least n/k -ikd. Since G is c-interconnected, Lemma 14 will apply as long as n/k -ikd ≥ c. Thus, the algorithm will run for at least (n -kc)/(k 2 d) stages.

Because H is k-uniform, and at each stage we removed all neighbors of the k vertices added, the sub-hypergraph induced by S contains only one edge for each stage, and these are pairwise disjoint. 2

Lemma 18 Let G = (V, E) be a c-interconnected regular graph of degree d on n vertices. Let H be the hypergraph of k-stars in G. Then, for any equipartition of the inputs into k parts,

C k (GIP H ) = Ω n -kc k 2 d2 k .
But the k+1-party communication complexity is at most k+1, regardless of how the inputs are partitioned.

Proof: By Lemma 17, H contains a sub-hypergraph G of Ω n-kc kd vertices, such that GIP G is exactly the original GIP function of Babai, Nisan and Szegedy [START_REF] Babai | Multiparty Protocols, Pseudorandom Generators for Logspace and Time-Space Trade-offs[END_REF]. By Propositions 8 and 6,

C k (GIP H ) ≥ C k (GIP G ) = Ω n -kc k 2 d2 k .
The upper bound for k + 1 players follows directly from Proposition 5. 2

Theorem 19 Let G be a Ramanujan graph of degree d ≈ 16k 2 . Let H be the hypergraph of k-stars in G.

Then for any partition of the inputs into k equal parts,

C k (GIP H ) = Ω n k 4 2 k .
But the k+1-party communication complexity is at most k+1, regardless of how the inputs are partitioned.

Proof: This follows from composing Lemmas 12 and 18.

2

Theorem 19 implies Theorem 1.

Conclusions and Open Questions

Although it is intuitive that adding more players can reduce communication complexity, the amount gained is not clear. We have seen that, for O(1) players, adding just one player to the game can cause the communication complexity to plummet from Ω(n) to O(1); this is the most that could be hoped for.

However, what if k is a non-constant function of n? A simple counting argument shows that, for a randomly chosen boolean function of kn variables, the k-party communication complexity is Ω(n) with high probability, regardless of the dependence of k on n.

In stark contrast, no explicit family of boolean functions has been shown to have ω(log n) communication complexity for k = ω(log n) players. Even for weaker models of communication such as the Simultaneous Messages model (cf. [START_REF] Kushilevitz | Communication Complexity[END_REF]), no such construction is known. To narrow this gap even slightly is one of the major challenges in communication complexity theory today.

For the question of separating the k-party communication hierarchy, we do not even know of a nonconstructive proof that the k-player versus (k+1)-player separation extends beyond k = O(log n) players, in either the best-case or the worst-case partition models. An answer to this question would be welcome.

Lemma 12

 12 Let G be a d-regular connected non-bipartite Ramanujan graph on n vertices. Then G is 2n √ d+1 -interconnected. Proof: Let c = 2n √ d+1 , and let S, T ⊂ V (G) be disjoint sets of vertices such that |S|, |T | ≥ c. Let x S (resp. x T ) be the characteristic vector of the set S (resp. T ), with respect to some labelling of V (G). Let A be the adjacency matrix of G, with respect to the same labelling. Then we easily see m(S, T ) = x S t Ax T . Let d = λ 1 > λ 2 ≥ λ 3 ≥ • • • ≥ λ n be the eigenvalues of G, and let v 1 , . . . , v n be a corresponding orthonormal basis of eigenvectors. Let us express x S = n i=1 α i v i and x T = n i=1 β i v i in this basis. With this notation, m(S, T ) = x S t Ax T = n i=1 α i β i λ i . It is easy to see that v 1 = (1, 1 . . . , 1)/ √ n, from which we observe that α 1 = |S|/ √ n and β 1 = |T |/ √ n. We also note that |S| = x S


Anita Das

A Combinatorial Approach to the Tanny Sequence

Keywords: Infinite complete binary tree, V LR-ordering, meta-Fibonacci sequence

The Tanny sequence T (i) is a sequence defined recursively as

In the first part of this paper we give combinatorial proofs of all the results regarding T (i), that Tanny proved in his paper "A well-behaved cousin of the Hofstadter sequence", Discrete Mathematics, 105(1992), pp. 227-239, using algebraic means. In most cases our proofs turn out to be simpler and shorter. Moreover, they give a "visual" appeal to the theory developed by Tanny. We also generalize most of Tanny's results. In the second part of the paper we present many new results regarding T (i) and prove them combinatorially. Given two integers n and k, it is interesting to know if T (n) = k or not. In this paper we characterize such numbers.

Introduction

Let G = (V, E) be a simple, finite, undirected graph. For S ⊆ V , G[S] denotes the subgraph of G induced by the vertices in S. Let T be a rooted tree. The depth of T is the number of nodes present in the longest path starting from the root and ending at a leaf. Let T = (V, E) be a tree rooted at a vertex r. For a vertex x ∈ V , all the vertices from r to x are called ancestors of x. If x is an ancestor of y then y is called a descendant of x. Note that x is a descendant of x itself.

A fibonacci sequence is a sequence of numbers defined by the recurrence relation a(n) = a(n -1) + a(n -2) with a(0) = 1 and a(1) = 1. In [START_REF] Hofstadter | An eternal golden braid[END_REF], Hofstadter defined the sequence Q(n) by

Q(n) = Q(n -Q(n -1)) + Q(n -Q(n -2)), n > 2 with Q(1) = Q(2) = 1.
He remarked on the apparent parallel between Q(n) and the usual fibonacci recursion as follows: "Each new value is a sum of two previous values-but not of the immediately two values". Guy [START_REF] Guy | Some suspiciously simple sequences[END_REF] reports that Malm called Q(n) a 'meta-Fibonacci sequence', motivated by the above observation.

In [START_REF] Tanny | A well-behaved cousin of the Hofstadter sequence[END_REF], Tanny defined a sequence recursively as T (n) = T (n -1 -T (n -1)) + T (n -2 -T (n -2)), T (0) = T (1) = T (2) = 1. This sequence is known as Tanny sequence which is a close relative of the 00 Definition 1.1 Let T be a tree rooted at r and has k children, say c 1 , c 2 , . . . , c k . Let T 1 , T 2 , . . . , T k be the subtrees of T rooted at c 1 , c 2 , . . . , c k , respectively. The V LR-traversal of T (also known as pre-order traversal) is defined as follows:

1. Visit the root.

2. Visit T 1 in V LR-order. . . . k + 1. Visit T k in V LR-order.
The ordering of the vertices of T which is associated with the V LR-traversal is known as V LR-ordering.

Let T 2 be an infinite complete binary tree. See Figure 1 for illustration. We assume the leaf of T 2 to be at depth one. The depth of a vertex v, denoted as dep(v), is the number of vertices present in the shortest path starting from v and ending at a leaf. Let T be a subtree of T 2 . A leaf of T is called a true leaf if it is also a leaf of T 2 . The infinite path starting from the left most leaf of T 2 to the root of T 2 is called the back bone of T 2 . (It is shown in bold edges in Figure 1.) Definition 1.2 For a given integer i, i > 0, let d be the integer such that 2 d-1 ≤ i ≤ 2 d -1 and T d 2 be the complete binary tree of depth d. Clearly there exists a subtree of T 2 isomorphic to T d 2 such that the leaves of this subtree are at depth one and its root situated on the backbone of T 2 . A V LR-tree of i nodes, denoted as V LR(i), is a subtree of T 2 induced by the set of first i vertices in the V LR-ordering of such a subtree of T 2 isomorphic to T d 2 . Note that, for a given i, V LR(i) is uniquely defined. The combinatorial interpretation of T (n) developed in [START_REF] Bharadwaj | Isoperimetric Problem and Meta-Fibonacci Sequences[END_REF] is summarized in the following theorem. The discrete isoperimetric problem on G is to find the value of b e (i, G), for each i,

1 ≤ i ≤ |V (G)|.
Discrete isoperimetric inequalities form a very useful and important subject in graph theory and combinatorics. See [START_REF] Alon | λ 1 , isoperimetric inequalities for graphs and super concentrators[END_REF][START_REF] Chung | Isoperimetric inequalities for cartesian product of graphs, Combinatorics[END_REF][START_REF] Margulis | Explicit construction of expander[END_REF][START_REF] Matula | Sparset cuts and bottlenecks in graphs[END_REF] for more details.

Note that the subgraph G[S] induced by the set of vertices of S which gives the minimum edge boundary need not be connected in general. Next we define a special kind of isoperimetric value by putting some restriction on the set S. Definition 1.5 Let i be an integer where 1 ≤ i ≤ |V |. For each i define the connected edge isoperimetric value b c (i, G) of G at i as follows:

b c (i, G) = min S⊆V ;|S|=i; G[S] is connected |δ(S, G)| The discrete connected isoperimetric problem on G is to find the value of b c (i, G), for each i, 1 ≤ i ≤ |V (G)|.
In this paper we deal with infinite complete binary trees only. So, for convenience we denote b c (i, T 2 ) as b c (i). Theorem 1.1 is used in [START_REF] Bharadwaj | Isoperimetric Problem and Meta-Fibonacci Sequences[END_REF] to relate the Tanny value to connected discrete isoperimetric problem on T 2 .

Theorem 1.2 ([2]) For T 2 , b c (i) = i + 2 -2T (i), for each i, i ≥ 1, where T (i) is the Tanny value at i.

Anita Das

The following theorem is from [START_REF] Bharadwaj | Isoperimetric Problem and Meta-Fibonacci Sequences[END_REF] which relates the connected isoperimetric problem on T 2 with the boundary of the V LR tree.

(n) = |δ(V LR(n), T 2 )|. Remark 1. Since T 2 is an infinite complete binary tree, b c (n) ≥ 1, for every positive integer n. Also, it is easy to see from Theorem 1.3 that 1 ≤ b c (n) ≤ log n . Consider the tree V LR(i). Let 2 d-1 ≤ i ≤ 2 d -1. So, the depth of V LR(i) is d.
Let the root of the tree V LR(i) be r and r l and r r be the left child and the right child of r, respectively. By the construction of V LR(i) and by the choice of d, it is easy to see that the descendants of r l in V LR(i) form a complete binary tree of depth d -1. Define a path v 1 , v 2 , . . . , v k in V LR(i) starting from the root as follows:

When i > 2 d-1 , i -2 d-1 vertices of V LR(i) are present in the subtree (of V LR(i)) rooted at r r .
v 1 = r and v j , 2 ≤ j ≤ k, is the right child of v j-1 if the right child of v j-1 is present in V LR(i), otherwise if only the left child of v j-1 is present in V LR(i) then v j is the left child of v j-1 . If both the children of v j-1 are not present in V LR(i) then the path ends at v j-1 , that is v j-1 = v k . This path is called the primary path of V LR(i).
Note that when i = 2 d-1 , the primary path of V LR(i) consists of only one vertex, the root r of V LR(i). In Figure 2, the path a -b -c -d is the primary path of V LR [START_REF] Tucker | Applied Combinatorics[END_REF].

By the definition of the primary path it is easy to see that if e is an outgoing edge of V LR(i) then it is incident on some vertex of the primary path. If u is a vertex in the primary path such that an outgoing edge of V LR(i) is incident on u then either the next node after u in the path is the left child of u or u is the last vertex of the primary path and it is not a true leaf. A vertex of the primary path on which an outgoing edge is incident is called an active vertex. It is easy to see that the first vertex of the primary path, that is the root of the tree V LR(i) is always an active vertex. The end vertex of the primary path is called the terminal vertex. Note that, the terminal vertex need not be an active vertex. The active vertex on the primary path which is situated at the least depth is called the tip of the primary path. In a primary path, the terminal vertex and the tip vertex need not be same, in particular if the terminal vertex is a true leaf, then it cannot be the tip. In V LR [START_REF] Tucker | Applied Combinatorics[END_REF], the terminal vertex and the tip of the primary path are same. See Figure 2 for illustration.

Observation 1. Let P be the primary path of V LR(i), 2 d-1 < i < 2 d -1, and v tip , v t be the tip and the terminal vertex of P , respectively. If v tip = v t , then in V LR(i + 1), the primary path P is the path P ∪ v l , where v l is the left child of v tip in T 2 . If v tip and v t are not same, then the primary path P of V LR(i + 1) is the path P ∪ v r , where v r is the right child of v tip in T 2 .

Observation 2. Let P be the primary path of V LR(i). If the tip of P is at depth two, then V LR(i + 1) contains one more true leaf than V LR(i), otherwise number of true leaves in V LR(i) and V LR(i + 1) are same.

Observation 3. Let P be the primary path of V LR(i) for some i and v be the terminal vertex of P . If |V (P )| ≥ 2 and v is not a true leaf then v is an active vertex and moreover two outgoing edges of V LR(i) are incident on v.

Observation 4. Let P = v 1 , v 2 , . . . , v p , . . . , v q be the primary path of V LR(i), for some positive integer i such that v q is a true leaf and v p is the tip of P . Let P = v 1 , v 2 , . . . , v p and S = {v 1 , v p } ∪ {v i ∈ V (P ) -{v 1 , v p }|v i is not an active vertex of P }. Note that, since the tip of the primary path can never be a true leaf, we have dep(v p ) ≥ 2. Now, clearly V LR(i) contains exactly N = v h ∈S 2 dep(v h )-2 number of true leaves. Let t be the smallest integer such that V LR(t) has N number of true leaves, where N is a given positive integer. For v h ∈ S, let lef t(v h ) denote the complete subtree rooted at the left child of v h . Since V (P ) does not contain any true leaf, the set of true leaves of V LR(t) is exactly the union of true leaves of the complete binary trees {lef t(v h ) : v h ∈ S}. A careful look at V LR(t) will reveal that the vertices of V LR(t) is exactly union of all the vertices in the complete sub-trees {lef t(v h ) : v h ∈ S} and

V (P ). That is, V (V LR(t)) = v h ∈S V (lef t(v h )) ∪ V (P ).
Observation 5. Let N be a positive integer and

N = 2 k1 + 2 k2 + . . . + 2 kp , 0 ≤ k 1 < k 2 < • • • < k p .
Let t be the smallest positive integer such that V LR(t) contains N number of true leaves and P = v 1 , v 2 , . . . , v r be the primary path of V LR(t). Since t is the smallest such number, the terminal vertex of P is the last vertex in the V LR ordering of V LR(i) and v r is a true leaf in V LR(t). Let v tip be the tip of P . By Observation 4, it is clear that the depth of v tip is k 1 + 2. Now, it is easy to see that for j ∈ {t, t + 1, . . . , t + k 1 }, V LR(j) has also N number of true leaves. Moreover, V LR(t + k 1 + 1) has N + 1 true leaves. That is, t + k 1 + 1 is the smallest integer such that V LR(t + k 1 + 1) contains N + 1 number of true leaves.

Graph theoretic proof of properties of T (n)

In this section we reprove the results of [START_REF] Tanny | A well-behaved cousin of the Hofstadter sequence[END_REF] combinatorially using Theorem 1.1 and the properties of V LR(i). In most of the cases we have also generalized the results.

Let T (n) be the Tanny sequence which is defined by the recurrence relation

T (n) = T (n -1 -T (n - 1)) + T (n -2 -T (n -2)), T (0) = T (1) = T (2) = 1.
The following Proposition of [START_REF] Tanny | A well-behaved cousin of the Hofstadter sequence[END_REF] follows from Observation 2.

Proposition 2.1 ( [START_REF] Tanny | A well-behaved cousin of the Hofstadter sequence[END_REF]) For T (n) defined as above,

(a) T (n + 1) = T (n) or T (n + 1) = T (n) + 1. (b) For n ≥ 2, if T (n) is odd, T (n + 1) = T (n) + 1.
We can generalize Proposition 2.1(b) as follows:

Proposition 2.2 If T (n) = 2 k1 + 2 k2 + . . . + 2 kp , 0 ≤ k 1 < k 2 < • • • < k p , then T (n + k 1 + 1) > T (n).
The following theorem follows from Observation 2.

Theorem 2.3 Let P be the primary path of V LR(n). Then, T (n + 1) = T (n) + 1 if and only if the tip of P is at depth 2.

Let ρ(N ) = {n : T (n) = N }. By Proposition 2.1, the elements of ρ(N ) consist of a sequence of consecutive integers. Let |ρ(N )| denotes the cardinality of the set ρ(N ).

Proposition 2.4 ([18]) If N > 1 is odd, then |ρ(N )| = 1. If N is even, then |ρ(N )| ≥ 2.
Proof: By the construction of the V LR tree it is easy to see that for any positive integer N , we can construct a V LR tree such that it contains exactly N number of true leaves. Hence for any N ≥ 1, ρ(N ) = ∅, that is the Tanny sequence hits every positive integer.

If N is odd, then |ρ(N )| = 1 by Proposition 2.1. Next suppose that N is even.

Let N = 2 k1 + 2 k2 + . . . + 2 kp , 0 ≤ k 1 < k 2 < • • • < k p . Since N is even, k 1 ≥ 1. By Observation 5, V LR(t + 1) also contains N number of leaves. Hence |ρ(N )| ≥ 2.
2

It is easy to find the elements of ρ(N ) when N is of certain special form. For example, if N = 2 x for some x ≥ 1, it is easy to find out the elements of ρ(N ). Proof: Let N = 2 x , for some positive integer x and n = 2 x+1 -1. It is easy to see that n is the smallest positive integer such that the number of true leaves in V LR(n) is N . Also the tree V LR(n + 1 = 2 x+1 ) has N number of true leaves. The depth of the tree V LR(2 x+1 ) is x + 2. Let t = 2 x+1 + (x + 1). By the property of the V LR tree, it is easy to see that t is the smallest integer such that V LR(t) contains N + 1 number of true leaves. So, t -1 is the largest integer j such that the tree V LR(j) contains N number of true leaves. Hence, ρ(2

x ) = {2 x+1 -1, 2 x+1 , . . . , 2 x+1 + x} and |ρ(2 x )| = x + 2. 2
A formula for |ρ(N )| for the remaining values of N is given by the following theorem which follows immediately from Observation 5.

Theorem 2.6 Let N be a positive integer and N = 2 k1 + 2 k2 + . . . + 2 kp such that p ≥ 2 and 0

≤ k 1 < k 2 < • • • < k p . Then, |ρ(N )| = k 1 + 1.
The following proposition present in [START_REF] Tanny | A well-behaved cousin of the Hofstadter sequence[END_REF] is an immediate consequence of Theorem 2.6 Proposition 2.7 ( [START_REF] Tanny | A well-behaved cousin of the Hofstadter sequence[END_REF]) Let α be any even integer,

2 ≤ α ≤ 2 x -2, where x ≥ 2. Then |ρ(2 x + α)| = |ρ(2 x-1 + α 2 )| + 1. Proof: Let 2 x + α = 2 x + 2 kp + 2 kp-1 + . . . + 2 k1 , 0 ≤ k 1 < k 2 < • • • < k p . By Theorem 2.6, |ρ(2 x + α)| = k 1 + 1. Now, 2 x-1 + α 2 = 2 x +α 2 = 2 x-1 + 2 kp-1 + 2 kp-2 + . . . + 2 k1-1 , 0 ≤ k 1 -1 < k 2 -1 < • • • < k p -1. By Theorem 2.6, |ρ(2 x-1 + α 2 )| = k 1 . Hence, |ρ(2 x + α)| = |ρ(2 x-1 + α 2 )| + 1. 2
In fact we can easily generalize Proposition 2.7 as following in view of Theorem 2.6.

Theorem 2.8 Let N 1 and N 2 be two positive integers such that

N 1 = 2 α1 + 2 α2 + . . . + 2 α k 1 and N 2 = 2 β1 +2 β2 +. . .+2 β k 2 such that k 1 , k 2 ≥ 2 and 0 ≤ α 1 < α 2 < • • • < α k1 and 0 ≤ β 1 < β 2 < • • • < β k2 . Then, |ρ(N 1 )| = |ρ(N 2 )| if and only if α 1 = β 1 . Proof: Suppose |ρ(N 1 )| = |ρ(N 2 )|. By Theorem 2.6, |ρ(N 1 )| = α 1 + 1 and |ρ(N 2 )| = β 1 + 1. That is, α 1 = β 1 . Next suppose α 1 = β 1 = k. By Theorem 2.6, |ρ(N 1 )| = α 1 +1 = k +1 and |ρ(N 2 )| = β 1 +1 = k +1. That is, |ρ(N 1 )| = |ρ(N 2 )|. Hence the theorem. 2
Proposition 2.9 ( [START_REF] Tanny | A well-behaved cousin of the Hofstadter sequence[END_REF]) Let N be a positive integer and N = 2 α1 + 2 α2 + . . . + 2 αp such that p ≥ 2 and

0 ≤ α 1 < α 2 < • • • < α p .
The greatest element in ρ(N ) is given by 2N + α p -p + 1.

Proof: Let t be the smallest integer such that V LR(t) contains N number of true leaves. Let P = v 1 , v 2 , . . . , v m , . . . , v q be the primary path of V LR(t). Since t is smallest, v q is a true leaf. Let v m be the tip of P . Let P = v 1 , v 2 , . . . , v m and S = {v 1 , v m } ∪ {v i ∈ V (P ) -{v

Let N = 2 α1 + 2 α2 + • • • + 2 αp , 0 ≤ α 1 < α 2 < • • • < α p . If p = 1, then T (n) = n for all α 1 + 2 consecutive integers n = 2 α1+1 -1 to n = 2 α1+1 + α 1 . If p ≥ 2 then T (n) = N for all (α 1 + 1) consecutive integers from n = 2N + (α p -α 1 ) -p + 1 to n = 2N + α p -p + 1. Proof: Let N = 2 α1 + 2 α2 + • • • + 2 αp , 0 ≤ α 1 < α 2 < • • • < α p . If p = 1,
-( 1 n ) log( n+1 2 ) ≤ T (n) n ≤ 1 2 + 1 2n , and T (n) n -→ 1 2 as n -→ ∞. Now, it is easy to see that i = (2 d -1)-(2 t -1 -1) = 2 d -2 t -1 . Putting t -1 = t, we have i = 2 d -2 t , 1 ≤ t ≤ d -2
. Now, combining both the cases, we have i = 2 d -2 t for some t,

1 ≤ t ≤ d -1. 2
For a given j let S j represent the i's such that i+1 2 -T (i) = j 2 . That is, S j = {i : i+1 2 -T (i) = j 2 }. The above result can be generalized as follows:

Lemma 3.2 Let S j = {i : i+1 2 -T (i) = j 2 }
. For a given j, i ∈ S j if and only if there exist integers d, t 1 , t 2 , . . . , t j such that d -2 ≥ t 1 > t 2 > . . . > t j-1 ≥ t j ≥ 1 and i = 2 d -(2 t1 + 2 t2 + . . .

+ 2 tj ) + (j -1). Moreover, |{i ∈ S j : 2 d-1 ≤ i ≤ 2 d -1}| = d j+1 .
Proof: From Equation 2it is easy to see that T (i) = i+1-j 2 if and only if b c (i) = j + 1. Let P be the primary path of V LR(i). We consider the following case:

The terminal vertex of P is a true leaf. In this case P contains d vertices and has exactly j active vertices other than the root. Clearly these j active vertices can be any of the vertices of P other than the root of V LR(i) and the terminal vertex of P . So there are d-2 j , where d = log i , different ways to choose these j active vertices on the primary path. Let a 1 , a 2 , . . . , a j be these active vertices of P and t 1 , t 2 , . . . , t j be their depths, respectively. Clearly d

-1 ≥ t 1 > t 2 > . . . > t j-1 > t j ≥ 2. Now, it is easy to see that i = (2 d -1) -{(2 t 1 -1 -1) + (2 t 2 -1 -1) + . . . + (2 t j -1 -1)} = 2 d -(2 t 1 -1 + 2 t 2 -1 + . . . + 2 t j -1 ) + (j -1). Taking t i -1 = t i , for 1 ≤ i ≤ j, we have i = 2 d -(2 t1 + 2 t2 + . . . + 2 tj ) + (j -1) where d -2 ≥ t 1 > t 2 > . . . > t j-1 > t j ≥ 1.
The terminal vertex of P is not a true leaf. By Observation 3, the terminal vertex of P is an active vertex and two outgoing edges of V LR(i) are incident on it. Since the root of V LR(i) is always an active vertex, P will contain exactly j -2 active vertices other than the root and the terminal vertex. Since the terminal vertex of P is not a true leaf, except the root and the terminal vertex, P can contain at most d -3 vertices. These j -2 active vertices can be chosen in t-2 j-2 many different ways provided t is the length P . Now, noting that t can vary from j to d -3, we have d-1 t=j t -2 j -2 many distinct i's such that V LR(i) has j + 1 out going edges and the primary path of V LR(i) is not a true leaf. Let a 1 , a 2 , . . . , a j-2 be these active vertices of P and t 1 , t 2 , . . . , t j-2 be their depths, respectively. Clearly d -1 ≥ t 1 > t 2 > . . . > t j-2 ≥ 3. Let t j-1 be the depth of the terminal vertex of P . Note that t j-1 ≥ 2. Now, it is easy to see that i = (2 d -1)-{(2 t 1 -1 -1)+(2 t 2 -1 -1)+. . .+(2 t j-2 -1 -1)+2(2 t j-1 -1 -1)} = 2 d -(2 t 1 -1 +2 t 2 -1 +. . .+2 t j-1 )+(j-1), where d-1 ≥ t 1 > t 2 > . . . > t j-1 ≥ 2. Putting t i -1 = t i , for 1 ≤ i ≤ j, we have i = 2 d -(2 t1 +2 t2 +. . .+2 tj-1 )+(j-1) where d-2 ≥ t 1 > t 2 > . . . > t j-1 ≥ 1.

Combining both the above cases, we have i = 2 d -(2 t1 + 2 t2 + . . . + 2 tj-1 + 2 tj ) + (j -1), where d -2 ≥ t 1 > t 2 > . . . > t j-1 ≥ t j ≥ 1.

From the above discussion, we have |{i ∈ S j :

2 d-1 -1 ≤ i ≤ 2 d -1}| = d-2 j + d-1 t=j t -2 j -2 . Claim 1. d-1 t=j t -2 j -2 = d -2 j -1 .
See [START_REF] Tucker | Applied Combinatorics[END_REF] (Chapter 5) for proof of Claim 1. . Case 2. t = j. If t = j, then it is easy to see that T (i) = k.

Case 3. t < j. In this case T (i) may or may not be equal to k. Let t be the smallest positive integer such that 2 t divides x. Note that t ≥ 1 (since x(= 2 d -2k) is even). That is, there is a 1 in t th position of (x) 2 . Since t is largest such number, all the bits after t in (x) 2 are 0. So, if after t th position in (x) 2 there are enough bits, namely j -t bits, then the rest (j -t) number of 1's can be accommodated in (x) 2 after the t th bit. That is, we can find t 1 > t 2 > . . . > t j-1 ≥ t j , which are nothing but the integers corresponding to the position of the j 1's in (x) 2 such that x = 2 t1 + 2 t2 + . . . + 2 tj-1 + 2 tj . So, T (i) = k if and only if t ≥ j -t. But j = i + 1 -2k. So, T (i) = k if and only if t ≥ i + 1 -2k -t. 2

Conclusion

In [START_REF] Isgur | Trees nad Meta-Fibonacci sequences[END_REF], Isgur et. al. have given a combinatorial interpretation in terms of infinite binary trees to certain meta-Fibonacci sequences which can be seen as a generalization of Tanny sequence. As of now we do not know to which other meta-Fibonacci sequences our iso-perimetric analogue can be applied. It would be interesting to explore whether those meta-Fibonacci sequences also can be related to discrete iso-perimetric inequalities.

Fig. 1 :

 1 Fig.1: The infinite complete binary tree T2. The path shown in bold edges is the back bone of T2.

Theorem 1 . 1 (Definition 1 . 4

 1114 [START_REF] Bharadwaj | Isoperimetric Problem and Meta-Fibonacci Sequences[END_REF]) For a positive integer n, the number of true leaves of V LR(n) equals T (n), the Tanny value at n. Definition 1.3 For S ⊆ V , the edge boundary δ(S, G) is the set of edges of G with exactly one end point in S. In other words, δ(S, G) = {(u, v) ∈ E : u ∈ S and v ∈ V -S} An edge which is present in δ(S, G) is called an out going edge of S. Let i be an integer where 1 ≤ i ≤ |V |. For each i define the edge isoperimetric value b e (i, G) of G at i as follows b e (i, G) = min S⊆V ; |S|=i |δ(S, G)|

Theorem 1 . 3 (

 13 [START_REF] Bharadwaj | Isoperimetric Problem and Meta-Fibonacci Sequences[END_REF]) Let T 2 be an infinite complete binary tree. Then for a positive integer n, b c

Fig. 2 :

 2 Fig.2: Illustration of Primary path. The path a-b-c-d is the primary path of V LR[START_REF] Tucker | Applied Combinatorics[END_REF] and all the vertices of the primary path are active vertices.

Proposition 2 . 5 (

 25 [START_REF] Tanny | A well-behaved cousin of the Hofstadter sequence[END_REF]) For every non-negative integer x, ρ(2 x )={2 x+1 -1, 2 x+1 , . . .,2 x+1 + x} and |ρ(2 x )| = x + 2.

  [START_REF] Alon | λ 1 , isoperimetric inequalities for graphs and super concentrators[END_REF] , v m }|v i is not an active vertex of P }. By Observation 4, t is the number of vertices in α2+1 -1) + . . .+ (2 αp+1 -1) = 2N -p. It is easy to see that dep(v 1 ) = α p + 2 and dep(v m ) = α 1 + 2. So, |V (P )| = α p -α 1 + 1. Hence t = 2N + α p -p -α 1 + 1.By Theorem 2.6, t + α 1 is the largest integer such that V LR(t + α 1 ) contains N number of leaves. Hence the greatest element in ρ(N ) is t + α 1 = 2N + α p -p + 1.2

	lef t(v h ) ∪ V (P ). By Observation 5, we
	v h ∈S
	have lef t(v h ) = (2 α1+1 -1) + (2 Proposition 2.10 ([18]) v h ∈S

  then the result follows from Proposition 2.5. If p ≥ 2, then the result follows from Theorem 2.6 and Proposition 2.9.2

	Proposition 2.11 ([18]) 1 2

Anita Das

By Remark 1, we have 1 ≤ b c (i) ≤ log n . This immediately allows us to derive a statement which is slightly better than Proposition 2.11. Proposition 2.12 1 2 -log n -2 2 ≤ T (n) n ≤ 1 2 + 1 2n .

Proof: From Theorem 1.2, we have

3 New results about T (n)

We know from Theorem 1.2 that T (i) ≤ i+1 2 and in fact for any i, i+1 2 -T (i) = j 2 , for some j, 0 ≤ j ≤ log i -1. Keeping this in mind, we ask the following related question: Given a j, 0 ≤ j ≤ d-1, can we characterize the set {i

From Theorem 1.2, we have

Recall from Remark 1 that b c (i) takes the values between 1 and log i . Since the depth of V LR(i) is d,

From Equation 1we have,

where 0

The following theorem gives a characterization of the values of i such that i+1 2 -T (i) = j 2 , for small values of j. Theorem 3.1 (1)

Proof: (1) From Equation 2we have

(2) From Equation 2it is easy to see that

Note that the root of V LR(i) is always an active vertex and therefore one out going edge is always incident on the root. Let P be the primary path of V LR(i). If P consists of one vertex, i.e., the root of V LR(i) only then b c (i) = 2. In this case i = 2 d-1 -1 + 1 = 2 d-1 . Other than this case, b c (i) = 2 when P contains exactly one more active vertex (except the root) and exactly one out going edge is incident on this active vertex. This means that the terminal vertex of P is a true leaf by Observation 3. So, P contains d vertices in this case. Let t be the depth of the active vertex (other than the root of V LR(i)) of P . Clearly 2 ≤ t ≤ d -1.

Anita Das

Though S j is an infinite set, the distribution of the elements of S j over the integers is nice. As shown in Lemma 3.2, The following theorem allows us to get the number of integers i ∈ S j that are strictly below

Claim 1 of Lemma 3.2, we have,

Given two integers i and k it is interesting to know whether T (i) = k or not. In [START_REF] Tanny | A well-behaved cousin of the Hofstadter sequence[END_REF], Tanny has already given a nice solution to this question (see Proposition 2.6 in [START_REF] Tanny | A well-behaved cousin of the Hofstadter sequence[END_REF]). In the following theorem we give a different way of looking at it. The answer to the question whether T (i) = k is encoded in the bit pattern of the binary representation of 2 log i -2k.

In the following theorem we characterize such numbers.

Theorem 3.4 Let x = 2 d -2k where d = log i and let t be the number of 1's in the bit representation of x. Let t be the greatest integer such that 2 t divides x. Then, T (i) = k if and only if t ≥ i + 1 -2k -t.

Proof:

Suppose

In equation 5, j = i + 1 -2k. From Lemma 3.2, we know that for a given j, i ∈ S j if and only if there exists integers d, t 1 , t 2 , . . . , t j such that d

Let x = 2 d -2k, where d = log i . Suppose (x) 2 be the binary representation of x and t be the number of 1's present in (x) 2 . Now, we have the following three cases:

Case 1. t > j. Since x = 2 d -2k = 2 t1 + 2 t2 + . . . + 2 tj-1 + 2 tj , where d -2 ≥ t 1 > t 2 > • • • > t j-1 ≥ t j ≥ 1, it is easy to see that the number of 1's in (x) 2 can be at most j. That is, t ≤ j. So, in this case T (i) cannot be equal to k.


David R Wood

Colouring the Square of the Cartesian Product of Trees

Keywords: cartesian product, colouring, square graph

We prove upper and lower bounds on the chromatic number of the square of the cartesian product of trees. The bounds are equal if each tree has even maximum degree.

Introduction

This paper studies colourings of the square of cartesian products of trees. For simplicity we assume that a tree has at least one edge.

For our purposes, a colouring of a graph G is a function c : V (G) → Z such that c(v) = c(w) for every edge vw of G. The square graph G 2 of G has vertex set V (G), where two vertices are adjacent in G 2 whenever they are adjacent in G or have a common neighbour in G. Thus, a colouring of G 2 corresponds to a colouring of G, such that in addition, vertices with a common neighbour in G are assigned distinct colours.

Let [a, b] := {a, a + 1, . . . , b}. The cartesian product of graphs G 1 , . . . , G d is the graph

G 1 • • • G d with vertex set {(v 1 , . . . , v d ) : v i ∈ V (G i )}
, where vertices v = (v 1 , . . . , v d ) and w = (w 1 , . . . , w d ) are adjacent whenever v i w i ∈ E(G i ) for some i ∈ [1, d], and v j = w j for all j = i. In this case, vw is in dimension i. Let ∆(G) be the maximum degree of G.

Theorem 1 Let T 1 , . . . , T d be trees. Let G := T 1 T 2 • • • T d . Then 1 + d i=1 ∆(T i ) ≤ χ(G 2 ) ≤ 1 + 2 d i=1 1 2 ∆(T i ) .
This upper bound improves upon a similar bound by [START_REF] Jamison | Acyclic colorings of products of trees[END_REF], who proved χ(G 2 ) ≤ 1 + 2 d i=1 (∆(T i ) -1), assuming that each ∆(T i ) ≥ 2. Theorem 1 implies: † woodd@unimelb.edu.au. Supported by a QEII Research Fellowship from the Australian Research Council.

  1365-8050 c 2011 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Corollary 1 Let T 1 , . . . , T d be trees, such that ∆(T i ) is even for all i ∈ [1, d].

This corollary generalises a result of [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF], who proved it when each T i is a path, and thus G is a d-dimensional grid. See [START_REF] Sopena | Coloring the square of the cartesian product of two cycles[END_REF][START_REF] Fertin | Star coloring of graphs[END_REF][START_REF] Pór | Colourings of the Cartesian product of graphs and multiplicative Sidon sets[END_REF][START_REF] Jamison | Acyclic colorings of products of trees[END_REF][START_REF] Chiang | On L(d, 1)-labeling of Cartesian product of a cycle and a path[END_REF] for more related results.

The Proof

For a colouring c of a graph G, the span of an edge vw of G is |c(v) -c(w)|. The following lemma is well known; see [START_REF] Pór | Colourings of the Cartesian product of graphs and multiplicative Sidon sets[END_REF] for example.

Lemma 1 Let G be a graph. If G 2 has a colouring in which every edge of G has span at most s, then G 2 is (2s + 1)-colourable.

Proof: Let c : V (G 2 ) → Z be the given colouring of G 2 . Since every edge of G has span at most s, every edge of G 2 has span at most 2s.

2

Lemma 2 For every tree T and non-negative integer s, T 2 has a colouring such that every edge of T has span in Proof of Theorem 1: The lower bound is well known [START_REF] Jamison | Acyclic colorings of products of trees[END_REF]. In particular, for i ∈ [1, d], let v i be a vertex of maximum degree in T i . Then (v 1 , . . . , v d ) has degree i ∆(T i ) in G. This vertex and its neighbours in G receive distinct colours in any colouring of G 2 . Thus χ(G 2 ) ≥ 1 + i ∆(T i ). Now we prove the upper bound. Let s 1 := 0 and s

Thus the spans of edges in distinct trees are distinct.

Colour

Suppose on the contrary that c(v) = c(w) for some edge vw of G. Say vw is in dimension i. Thus v j = w j for all j = i. Hence c i (v i ) = c i (w i ), and c i is not a colouring of G. This contradiction proves that c is a colouring of G.

Suppose on the contrary that c(x) = c(y) for two vertices x and y with a common neighbour v in G. Say vx is in dimension i, and vy is in dimension j. Thus v = x for all = i, and v = y for all = j. Now

Thus the edges x i v i and y j v j have the same span. Since the spans of edges in distinct trees are distinct, i = j. Hence c i (x i ) = c i (y i ). However, v i is a common neighbour of x i and y i in T i , implying c i is not a colouring of T 2 i . This contradiction proves that c is a colouring of G 2 .

Each edge of G has span at most