JOURNAL OF COMBINATORIAL THEORY, Series A 49, 180-187 (1988) Note On Induced Subgraphs of the Cube F. R. K. CHUNG Bell Communication Research, Morristown, New Jersey 07960 ZOLTAN F~REDI AT & T Bell Laboratories, Murray Hill, New Jersey 07974, Mathematical Institute of the Hungarian Academy of Science, 1364 Budapest Pf 127, Hungary, and Department of Mathematics, Massachusetls Institute of Technology, Cambridge, Massachusetts 02139 R. L. GRAHAM AT & T Bell Laboratories, Murray Hill, New Jersey 07974 AND P. SEYMOUR Bell Communication Research, Morristown, New Jersey 07960 Communicated by the Managing Editors Received April 4, 1987 Consider the usual graph Q” defined by the n-dimensional cube (having 2” ver- tices and n2”-’ edges). We prove that if G is an induced subgraph of Q” with more than 2” - ’ vertices then the maximum degree in G is at least (4 - o( 1)) log n. On the other hand, we construct an example which shows that this is not true for maximum degree larger than & + 1. 0 1988 Academic POW, inc. 1. PRELIMINARIES Denote by Q” the graph of the n-dimensional cube, i.e., the vertex set of Qfl consists of all the (0, 1)-vectors of length n, and two vectors x, ye (0, l}” are adjacent if they differ from each other in exactly one 180 0097-3165/88 $3.00 Copyright 0 1988 by Academic Press, Inc. All rights of reproduction in any form reserved.INDUCEDSUBGRAPHSOFTHECUBE 181 component. For a graph G = (V, E) we denote the maximum degree by d(G), i.e., d(G) = us;;, deg,(u). The average degree d(G) is defined to be C,, Y(GJ deg,(v)/l V(G)J. We say GE Q”(N) if G is an induced subgraph of Q” with N vertices, i.e., I V(G)1 = N V(G) E (0, I>“, and E(G) = E(Q”)n (V(G) x V(G)). Qfl is a bipartite graph, so we have a GE Q”(2”- ‘) without any edge, namely, G”,,, and GzVf,,,, where V(G”,,,)= {x~ (0, I}“: C;=r xi= 1 (mod 2)}, V(Gf&) = (0, l}“- V(G&). Our main result shows that even though the average degree of a graph GE Q”(2”- ’ + 1) can be very small (only 2n/(2”- ’ + l)), these graphs must have large degree. THEOREM 1.1. Let G be an induced subgraph of Q” with at least 2”- ’ + 1 vertices. Then for some vertex v of G we have deg,( v) > f log n - t log log n + 1. (1.1) On the other hand, there exists a GE Q”(2”-’ + 1) with LqG)qG+ 1. (1.2) 2. RELATED RESULTS AND PROBLEMS FROM COMPUTER SCIENCE A (Boolean) function f: (0, 1 }” -+ { 0, I} is said to depend on coordinate i if there exists an input vector x such that f (x) differs from f (x”‘), where x(‘) agrees with x in every coordinate except the ith. In this case x is said to be critical for f with respect to i. The function f is called nondegenerate if it depends on all n coordinates. For an input vector x, let c(f, x) denote the number of coordinates i such that x is critical for f with respect to i, and let c(f) :=max{c(f, x): XE (0, I}“}. c(f) is called the critical complexity off: This notion is due to Cook and Dwork [3] and Reischuk [S], who showed that log, c(f) is a lower bound to the time needed by a parallel RAM to compute the function f (where A = +(5 + fi) =4.7.. .). (A parallel RAM is a collection of synchronous parallel processors sharing a global memory with no write-conflicts allowed. For precise delfinitions, see Cl].) Simon [6] showed that the critical complexity of any nondegenerate Boolean function is at least a(n):=$logn-floglogn++, (2-l 1182 CHUNGETAL. which implies a O(log log n) lower bound for parallel complexity. More results on this topic can be found in [7]. Call a subgraph G of Qfl nondegenerate if E(G) contains edges from each of the n directions. Thus, the crucial point of the above problem can be reformulated as follows: Let U, V be a partition of (0, 11” and consider the induced bipartite graph G(U, V). If G( U, V) is nondegenerate then A(G) > a(n). (2.2) This is completely analogous to our theorem (even the proof is similar). However, we need a slightly more powerful lemma (see Lemma 4.1). Reischuk (see [S] ) has a simple example proving that in (2.2), d(G) = Llog n_l+ 2 is possible, and it is very likely that this is the right value of b(n) = min{d(G): G as is in (2.2)}. Another interesting property of the induced bipartite graphs is proved by Ben-Or and Linial [2] (also dealing with a problem arising in theoretical computer science): If U, V is a partition of (0, 1 }” then there exists a direction i such that at least min{ 1 UI, 1 VI }/n edges go from U to V parallel to i. (2.3) They have an upper bound of log n min{ 1 UI, I VI }/n and also this seems to be the right order of magnitude. 3. FWXF OF THE UPPER BOUND Denote the set of integers { 1, 2, . . . . n} by [n]. Since there is a natural bijection between (0, 1 }” and 2[“‘, so we will speak about families of finite sets with the underlying set [n]. There exists a partition of [n] = F, u ... u Fk such that Ik- &I < 1 and I IFJ-&l<l, l<i<k. Define the family X as follows: consider all the even sets (i.e., subsets of [n] with cardinality an even number) which contain some Fi, 1~ i< k, and all the odd sets which do not contain any Fj. Claim 3.1. 1x1 = 2” ~ ’ f 1 according to whether n + k is odd or even. Claim 3.2. For the subgraphs induced by X and 2[“‘-X we have A<k. Remark. We can generalize the above construction in the followingINDUCED SUBGRAPHS OF THE CUBE 183 way. Let F c 2[“’ be a collection of finite sets. (Later we will see that it is enough to consider Sperner families, with u F = [n].) Define X(F) = {SC [n]: ISI = even, and there exists FE F with F c S) u {Sc[n]:lSl=odd,F\S#@forallF~F). Let G(F) be the induced subgraph of Qn with vertex set X(F),