Color critical hypergraphs and forbidden configurations

Color critical hypergraphs and forbidden configurations

Richard Anstee

, Balin Fleming

, Zolt´an F¨uredi

and Attila Sali

1Mathematics Department The University of British Columbia Vancouver, B.C., Canada V6T 1Z2

2Department of Mathematics University of Illinois at Urbana-Champaign 1409 W. Green Street Urbana, Illinois 61801-2975, USA

3Alfr´ed R´enyi Instiute of Mathematics Hungarian Academy of Sciences Budapest, P.O.Box 127 H-1364 Hungary

The present paper connects sharpenings of Sauer’s bound on forbidden configurations with color critical hypergraphs.

We define a matrix to besimpleif it is a (0,1)-matrix with no repeated columns. LetF be ak×l(0,1)-matrix (the forbidden configuration). AssumeAis anm×nsimple matrix which has no submatrix which is a row and column permutation ofF. We define forb(m, F)as the best possible upper bound onn, for such a matrixA, which depends onmandF. It is known that forb(m, F) =O(m^k)for anyF, and Sauer’s bond states that forb(m, F) =O(m^k−1) foresimpleF. We give sufficient condition for non-simpleF to have the same bound using linear algebra methods to prove a generalization of a result of Lov´asz on color critical hypergraphs.

Keywords:forbidden configuration, color critical hypergraph, linear algebra method

1 Introduction

Ak-uniform hypergraph(V,E)is 3-color critical if it is not 2-colorable, but for allE∈ Ethe hypergraph (V,E \ {E})is 2-colorable. Lov´asz [12] proved in 1976, that

|E| ≤ n

k−1

for a 3-color criticalk-uniform hypergraph. Here we prove the following that can be considered as gener- alization of Lov´asz’ result.

Theorem 1 LetE ⊆ ^[m]_k

be ak-uniform set system on an underlying setX ofmelements. Let us fix an orderingE1, E2, . . . EtofE and a prescribed partitionAi∪Bi =Ei(Ai∩Bi =∅) for each member ofE. Assume that for alli= 1,2, . . . , tthere exists a partitionC_i∪D_i =X (C_i∩D_i =∅), such that

†Research is supported in part by NSERC

‡Research is supported in part by NSERC

§Research is supported in part by Hungarian National Research Fund (OTKA) numbers T034702 and T037846

¶Research is supported in part by Hungarian National Research Fund (OTKA) numbers T034702 and T037846 and by NSERC of the first author

1365–8050 c2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

E_i∩C_i =A_i andE_i∩D_i =B_i, butE_j∩C_i 6=A_jandE_j∩C_i 6=B_jfor allj < i. (That is, theith partition cuts theith set as it is prescribed, but does not cut any earlier set properly.) Then

t≤ m

k−1

+ m

k−2

+. . .+ m

0

. (1)

Theorem 1 was motivated by the following sharpening of Sauer’s bound for forbidden configurations. Let F be a k×l0-1 matrix, thenforb(m, F)denotes maximumnsuch that there exists anm×nsimple matrixAsuch that no column and/or row permutation ofF is a submatrix ofA. Furthermore, letK_k denote thek×2^ksimple 0-1 matrix consisting of all possible columns.

Theorem 2 LetFbe contained inFB = [Kk|t·(Kk−B)]for ank×(k+ 1)matrixBconsisting of one column of each possible column sum. Thenforb(m, F) =O(m^k−1).

We explain the the connection between Theorem 1 and Theorem 2.

The study of forbidden configurations is a problem in extremal set theory. The language we use here is matrix theory which conveniently encodes the problems. We define asimplematrix as a (0,1)-matrix with no repeated columns. Such a matrix can be thought of a set of subsets of{1,2, . . . , m}with the columns encoding the subsets and the rows indexing the elements. Assume we are give ak×l(0,1)-matrixF. We say that a matrixAhas noconfigurationF if no submatrix ofAis a row and column permutation ofF and soFis referred to as aforbidden configuration(sometimes calledtrace). A variety of combinatorial objects can be defined by forbidden configurations. For a simplem×n matrixA which is assumed to have no configurationF, we seek an upper bound onnwhich will depend onm, F. We denote the best possible upper bound as forb(m, F). Many results have been obtained about forb(m, F)including [2],[3],[5].

At this point all values known for forb(m, F)are of the formΘ(m^e)for some integere. We completed the classification for2×lmatricesFin [2] and for3×lmatricesFin [6]. We also put forward a conjecture on what properties ofF drive the exponente. Roughly speaking, we proposed a set of constructions and guessed that these constructions are sufficient to deduce the exponentein the expressionΘ(m^e).

We use the notationKk to denote thek×2^k simple matrix of all possible columns onkrows. The basic result for forb(m, F)is as follows.

Theorem 3 [Sauer [13], Perles and Shelah [14], Vapnik and Chervonenkis [15]] We have that forb(m, Kk) isΘ(m^k−1).

In fact Theorem 3 is usually stated with forb(m, K_k) = _k−1^m

+ _k−2^m

+· · ·+ ^m₀

but the asymptotic growth ofΘ(m^k−1)was what interested Vapnik and Chervonenkis.

One easy observation is that if we letA^cdenote the 0-1-complement ofAthen forb(m, F^c) =forb(m, F).

Another observation is that ifF⁰is a submatrix ofF, then forb(m, F)≥forb(m, F⁰). We letK_k^sdenote thek× ^k_s

simple matrix of all possible columns of column sums.

We use the notation[A|B]to denote the matrix obtained from concatenating the two matricesAand B. We use the notationk·Ato denote the matrix[A|A| · · · |A]consisting ofkcopies ofAconcatenated together. We give precedence to the operation·(multiplication) over concatenation so that for example [2·A|B]is the matrix consisting of the concatenation ofBwith the concatenation of two copies ofA.

According to an earlier unpublished result of F¨uredi [10] forb(m, F) =O(m^k)forarbitraryk×lcon- figurationF. The goal of this paper is to give sufficient conditions that ensure forb(m, F) =O(m^k−1).

2 The boundary between m

and m

Theorem 3 implies that simple configurations all have forb(m, F) = O(m^k−1), thus we investigatef’s with multiple columns. First, we show that which configurationsFhave forb(m, F) = Ω(m^k)using the direct product construction. LetA(k,2)be defined as a minimal matrix with the property that any pair of rows has

1 1

has both with 1’s in some column and such that deleting a column ofA(k,2)would violate this property.

Lemma 4 LetFbe ak×lconfiguration. forb(m, F) = Ω(m^k)ifFcontains2·K_k^l for2≤l≤k−2 andl= 0, kor ifFcontains[2·K_k¹|A(k,2)].

Proof: We find that forb(m, F)isΩ(m^k)ifF contains2·K_k^l for0 ≤ l ≤kandl 6= 1, k−1. This follows since2·K_k^l is not contained in thek-fold product ofl K_m/k¹ ’s andk−l K_m/k^(m/k)−1’s and so may deduce forb(m,2·K_k^l)isΩ(m^k). To verify this for2 ≤l ≤ k−2, we note that any pair of rows of K_k^l has

1 0 1 0

and so if we have a submatrix that is a row and column permutation ofK_k^l, we can only choose one row from eitherK_m/k¹ or fromK_m/k^(m/k)−1. The verification forK_k⁰orK_k^kis easier.

Forl= 1(the casel=k−1is the (0,1)-complement) we can no longer assert that any pair of rows of K_k^l has

1 0 1 0

merely 0

0

and so can choose two rows from the copy ofK_m/k¹ , one row from each of k−2of theK_m/k^(m/k)−1terms and generate a copy of2·K_k¹. (Theorem 5.1 of [6] shows that forb(m, K_k¹) isΘ(m_k−1)). This is fixed by considering a minimal matrixA(k,2)with the property that any pair of rows has

1 1

has both with 1’s in some column and such that deleting a column ofA(k,2)would violate this. As above, we have that ifFcontains[2·K_k¹|A(k,2)], then forb(m, F)isΩ(m^k). 2 Lemma 4 leaves two possibilities if we want forb(m, f) be bounded away fromm^k. Either F is contained in a matrixFB = [Kk|t·(Kk−B)]for ank×(k+ 1)matrixBconsisting of one column of each possible column sum orF is contained in a matrix[K_k⁰|t·C] whereC is ak-rowed simple matrix consisting of all columns which do not have 1’s in both rows 1 and 2 and also with at least one 1. Note, that these are not mutually exclusive cases. Our main result Theorem 2 is that in the first case forb(m, F) =O(m^k−1).

Proof of Theorem 2: LetAbe anm×nsimple 0-1 matrix, andBbe ak×(k+ 1)matrix consisting of one column of each possible column sum. Suppose thatAdoes not haveFB = [Kk|t·(Kk−B)]

as configuration. This implies that on a givenk-tupleLof rows eitherKk is missing, or if all possible columns of size koccur onL, thent·(Kk −B)must be missing. This latter means, that for some 0≤s≤k, two columns of column sumsoccur at mostt−1times onL, respectively. LetKbe the set ofk-tuples of rows where the latter happens. Using Lemma 5 a set of columns of sizeO(m^k−1)can be removed fromAto obtainA⁰, so that for allL∈ Ka column (in fact two) is missing onLinA⁰. However, this implies thatK_kis not a configuration inA⁰, thus by Theorem 3A⁰has at mostO(m^k−1)columns.2 LetK be a system ofk-tuples of rows such that∀K ∈ Kthere are two (k×1) columns,αK 6= βK

specified. We say that a columnxofAviolates(K, αK), ifx|K =αK, similarly,xviolates(K, βK), if x|K=β_K.

Lemma 5 Assume, that for everyK∈ Kthere are at mostt−1columns ofAthat violate(K, α_K), and at mostt−1columns of Aviolate(K, β_K). Then there exists a subsetX of columns ofA, such that

|X|=O(m^k−1)and no column ofA−Xviolates any of(K, α_K)or(K, β_K).

Proof:It can be assumed without loss of generality that for allK∈ Kα_K =αandβ_K =βindependent ofK. Indeed, there are2^k×2^kpossibleα_K, β_K pairs, that is a constant number of them .Thus,Kcan be partitioned into a constant number of parts, so that in each partα_K =αandβ_K =βholds. We apply induction onkusing the simplification given above.k= 1is obvious.

Consider nowk×1columnsα6=β. Assume first, thatα6=β. That is, there is a coordinate whereα andβagree, say both have 1 as their`th coordinate. The case of a common 0 coordinate is similar. For theith row ofAwe count how many columns have violation so that for someK∈ Kthe`th coordinate in Kis exactly rowi. LetKi,`be the set of thesek-tuples fromK. Columns that have violation onk-tuples fromKi,`have 1 in theith row, letA_i,1denote matrix formed by the set of columns that have 1 in row i. If rowi is removed fromA_i,1, the remaining matrix A⁰_i,1is still simple. LetK⁰_{i,`</sub>denote the set of (k−1)-tuples obtained fromk-tuples ofK<sub>i,`}by removing their`th coordinate,i, furthermore letα<sup>0</sup>(β<sup>0</sup>, respectively) denote the(k−1)×1column obtained fromα(β) by removing the`th coordinate, 1. Note, thatα⁰6=β⁰. A column ofAhas a violation onK∈ K_{i,`</sub>iff its counterpart inA<sup>0</sup><sub>i,1</sub>has a violation on the correspondingK<sup>0</sup> ∈ K<sup>0</sup><sub>i,`}. The number of those columns is at mostc m^k−2by the inductive hypothesis.

SinceK =∪^m_i=1K_i,`, we obtain that the number of columns ofAhaving violation on someK∈ Kis at mostm·c m^k−2.

Let us assume now, thatα = β. A subset J ⊆ Kis calledindependentif there exists an ordering J1, J2, . . . Jg of the elements of J such that for everyJi ∈ J there exists anm×10-1 column that violatesJi and does not violate anyJj ∈ J forj < i. Let us call amaximal independent subsetBof KabasisofK. If a column ofAhas a violation onK ∈ K, then it has a violation on someB ∈ B, as well. Indeed, eitherK∈ Bholds, or ifK6∈ B, then by the maximality ofB,Kcannot be added to it as a

|B|+ 1st element in the order, so the column having violation onKmust have a violation onB∈ B, for someB. By Theorem 1 for a basisBwe have

|B| ≤ m

k−1

+ m

k−2

+. . .+ m

0

,

since a column violating ak-tupleB_ifromB, but none ofB_j forj < i, gives an appropriate partition of the set of rows. Thus, there could be at most(2t−2)h

m k−1

+ _k−2^m

+. . .+ ^m₀i

columns violating

someK∈ K. 2

Proof of Theorem 1:We define a polynomialpi(x)∈R[x1, x2, . . . , xm]for eachEias follows.

pi(x1, x2, . . . , xm) = Y

a∈Ai

(1−xa) Y

b∈Bi

xb+ (−1)^k+1 Y

a∈Ai

xa

Y

b∈Bi

(1−xb) (2)

Polynomials defined by (2) are multilinear of degree at mostk−1, since the productQ

e∈Eixecancels by the coefficient(−1)^k+1. Thus, they are from the space generated by monomials of typeQr

j=1xi_j, for r= 0,1, . . . k−1. The dimension of this space overRis _k−1^m

+ _k−2^m

+. . .+ ^m₀ .

We shall prove that polynomialsp₁(x), p₂(x), . . . p_t(x)are linearly independent overR, which implies (1). Assume that

t

X

i=1

λ_ip_i(x) = 0 (3)

is a linear combination of thep_i(x)’s that is the zero polynomial. Consider the partitionC_t∪D_t=X, and substitutex_c = 0 if c ∈ C_t andx_d = 1 if d ∈ D_t into (3). Thenp_t(x) = 1, but it is easy to see that pk(x) = 0 for k < t. This implies that λt = 0. Now assume by induction on j, that λt= λ_t−1 =. . . =λ_t−j+1 = 0. Take the partitionC_t−j ∪D_t−j =X and substitute into (3)xc = 0 ifc ∈ C_t−j andxd = 1ifd ∈ D_t−j. Then, as before, p_t−j(x) = 1, butpk(x) = 0for k < t−j.

This impliesλ_t−j = 0, as well. Thus, all coefficients in (3) must be 0, hence the polynomials are linearly

independent. 2

References

[1] R.P. ANSTEE, Some Problems Concerning Forbidden Configurations, preprint.

[2] R.P. ANSTEE, J.R. GRIGGS, A. SALI, Small Forbidden Configurations,Graphs and Combinatorics 13(1997),97-118.

[3] R.P. ANSTEE, R. FERGUSON, A. SALI, Small Forbidden Configurations II,Electronic J. Combin.

8(2001), R4 (25pp)

[4] R.P. ANSTEE, Z. F ¨UREDI, Forbidden Submatrices,Discrete Math.62(1986),225-243.

[5] R.P. ANSTEE, N. KAMOOSI, Small Forbidden Configurations III, preprint.

[6] R.P. ANSTEE, A. SALI Small forbidden configurations IV: The 3-rowed case, Combinatorica, to appear.

[7] J. BALOGH, B. BOLLOBAS´ , Unavoidable Traces of Set Systems, to appear, Combinatorica.

[8] B. BOLLOB_AS´ Extremal graph theory. London Mathematical Society Monographs,11Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978.

[9] P. ERDOS˝ , A.H. STONE, On the Structure of Linear Graphs, Bull. Amer. Math. Soc.52(1946), 1089-1091.

[10] Z. F ¨UREDI, personal communication.

[11] T. K ˝OVARI´ , V.T. S ´OS, P. TURAN´ On a problem of K. Zarankiewicz, Colloquium Math.3(1954) 50-57.

[12] L. LOVASZ´ Cromatic number of hypergraphs and linear algebra,Studia Sci. Math. Hung.11(1976) 113-114.

[13] N. SAUER, On the density of families of sets, J. Combin. Th. Ser A 13(1973), 145-147.

[14] S. SHELAH, A combinatorial problem: Stability and order for models and theories in infinitary languages, Pac. J. Math.4(1972), 247-261.

[15] V.N. VAPNIK, A.YA. CHERVONENKIS, On the uniform convergence of relative frequencies of events to their probabilities, Th. Prob. and Applics.16(1971), 264-280.