Printer Friendly

Exponential multivalued forbidden configurations.

1 Introduction

We call a matrix simple if it has no repeated columns. Every set system (or simple hypergraph) corresponds to a simple (0,1)-matrix via its element-set incidence matrix, and such matrices provide a convenient language for extremal set theory. We generalize this situation to r-matrices, which have entries in {0,1,..., r - 1}. Such matrices can be thought of as r-coloured set systems or as representations of collections of functions from a given finite set into {0,1,..., r - 1}.

For two matrices F and A, we say that F is a configuration of A, denoted F < A, if A contains a submatrix which is a row and column permutation of F. If F < A, we say that A avoids F. Configurations of simple (0, 1)-matrices correspond to traces of set systems or hypergraphs. For a given finite collection J of matrices, we denote by Avoid(m, r, I) the collection of m-rowed, simple r-matrices that avoid every matrix F [member of] F.We let |A| denote the number of columns of A. The main extremal function in the study of forbidden configurations is

forb(m, r,F) = max{|A| : A [member of] Avoid(m, r, F)}.

When r = 2 we usually write forb(m, F) in place of forb(m, 2, F). We also use forb(m, r, F) instead of the more cumbersome forb(m, r, {F}). We will use several simple properties of this function. For example, if F < F' then forb(m, r, F) [less than or equal to] forb(m, r, F'). Also, we let [F.sup.c] denote the complement of the (0, 1)-matrix F, where each 0 is replaced by a 1 and vice versa; then forb(m, r, F) = forb(m, r, [F.sup.c]).

The foundational result in the theory of forbidden configurations is Sauer's theorem (proven in [10], also by Perles and Shelah [11] and Vapnik and Chervonenkis [12]). Let [K.sub.k] denote the complete k * [2.sup.k] simple (0, 1)-configuration (corresponding to the power set of a k-element set).

Theorem 1.1. For every positive integer m,

[mathematical expression not reproducible]

Alon [1] gave a generalization for complete r-matrices, but the forbidden number is exponential when r > 2. This is a special case of a more general phenomenon proved by Furedi and Sali [9].

Theorem 1.2. Let F be a family of r-matrices. If for every pair i,j [member of] {0,1,... , r - 1} there is an (i, j) -matrix in F, then forb(m, r, F) = O([m.sup.k]) for some positive integer k. IfFhasno (i,j)-matrixfor some pair i, j [member of] {0,1,..., r - 1}, then forb(m, r, F) = [OMEGA]([2.sup.m]).

Extensive investigations have been undertaken for forbidden configurations of simple (0, 1)-matrices; see, for example, the excellent dynamic survey of Anstee [3]. On the other hand, the more general case of r-matrices is not so well-explored. Previous papers mainly focus on providing bounds on the forbidden number for special classes of sets in the polynomial case [5, 6]. In this paper, we dive into exponential forbidden numbers and provide exact bounds when (0, 1)-configurations of r-matrices are forbidden. This is similar in flavour to a recent paper of Furedi, Kostochka, and Luo [7], which proves several minimumdegree conditions that guarantee cycles in hypergraphs; by dropping the assumption of uniformity, their bounds jump from polynomial to exponential.

The structure of the paper is as follows. Section 2 provides a method to transfer bounds for r = 2 to larger values of r. The following three sections calculate forbidden numbers of specific classes of matrices. We obtain exact results when r > 3 and bounds for r = 3 that differ from the forbidden number by an additive constant. We also prove a stability result for the identity configuration. Our work culminates in Section 6, which provides exact forbidden numbers for all two-rowed (0, 1)-configurations for every r > 3 and a large class of two-rowed (0,1) configurations when r = 3. The main tool in both cases a reduction lemma. Finally, Section 7 applies the method of Section 2 to obtain a nearly complete classification of (0, 1)-configurations of size 3 * 2 and 3 * 3.

2 General bounds

For a given configuration A, let A denote its underlying simple configuration. If A has m columns and S [subset] [m], then we let [A|.sub.S] be the restriction of A to the rows with indices in S. By convention, we set forb(0, F) = 1 for all F. In general, if F has t rows, then forb(k, F) = [2.sup.k] when 0 [less than or equal to] k < t.

Lemma 2.1. If F is a (0, 1)-matrix andr [greater than or equal to] 3, then

[mathematical expression not reproducible] (2.1)

Proof: Let A [member of] Avoid(m, r, F), and let X be a k-element subset of the rows. Consider the matrix C obtained by taking all columns of A that have 0's and 1's in exactly the rows in X, and let C' = [C|.sub.X]. We know that |C'| [less than or equal to] forb[(k , F). Each column in C' appears with multiplicity at most (r - 2).sup.m-k] in [C|.sub.X], so |C| [less than or equal to] [(r - 2).sup.m-k] forb(k, F). To finish the proof, we sum over all subsets of the rows.

The bound given by this lemma may be quite bad, especially if F is not simple. However, for simple matrices, we have the following lower bound.

Lemma 2.2. Let F be a simple (0, 1)-matrix with n rows and fix r [greater than or equal to] 3. Suppose that [mathematical expression not reproducible] is a sequence of (0, 1)-matrices that avoids F, where [A.sub.k] has k rows, such that Ak|S [subset] [A.sub.n] for every k [greater than or equal to] n and S [member of] [mathematical expression not reproducible]. If we set |[A.sub.0]| = 1, then

[mathematical expression not reproducible] (2.2)

Proof: We construct a configuration that avoids F as follows. Let k [member of] [m]. For each k-set X of rows, we choose the [(r - 2).sup.m-k] columns that contain a copy of [A.sub.k] in the rows of X and have elements of {2,..., r - 1} in every other position. Let A be the configuration that contains all such columns. If F < A, then F < [A|.sub.S] for some n-set of rows S. But every column in [A|.sub.S] appears in [A.sub.n], so F < An, a contradiction.

The condition that F is simple is absolutely essential. For simple matrices, however, this lemma can easily extend bounds from the classical case to the generalized one. In particular, combining Lemmas 2.1 and 2.2 proves the following.

Lemma 2.3. Let F be a simple n-rowed (0,1)-matrix. If there exists a sequence [mathematical expression not reproducible] of (0,1)matrices, each of which avoids F, such that

* [A.sub.k] has k rows,

* |[A.sub.k]| = forb(k,F), and

* Ak|S is contained in [A.sub.n] for every k [greater than or equal to] n and n-set S [subset] [k], then

[mathematical expression not reproducible] (2.3)

3 Complete configurations

Proposition 3.1. We have forb [mathematical expression not reproducible], then forb [mathematical expression not reproducible].

Proof: We first prove that forb [mathematical expression not reproducible]. Let [A.sub.n] denote the n-rowed configuration that contains every column with at most k - 1 zeros. Then ([A.sub.n]) satisfies the conditions of Lemma 2.3, so Theorem 1.1 implies that

[mathematical expression not reproducible]

Now we prove the forbidden number for all p. The configuration that contains every column with at most k -1 zeros avoids [K.sub.k]. If [(r - 1).sup.m-k] >p-1, for each k-set of rows, we may append p - 1 columns to this matrix that have zeros in that k-set and nowhere else. The resulting configuration avoids p-[K.sub.k] and has [mathematical expression not reproducible] columns.

Now suppose that A [member of] Avoid(m, r,p * [K.sub.k]). For each k-set X of rows, there is a column of [K.sub.k] that appears at mostp - 1 times in [A|.sub.X]. Let A' be the configuration obtained by deleting the corresponding columns of A for all k-sets. Since [K.sub.k] is symmetric, no row-permutation of [K.sub.k] is a subset of [A'|.sub.X], so [K.sub.k] < [A'|.sub.X] for every k-set X. Therefore [K.sub.k] < A', which implies that

[mathematical expression not reproducible]

as claimed.

Proposition 3.1 is enough to determine the logarithmic growth rate of forb(m, r, F) asymptotically for every (0, 1)-configuration F.

Corollary 3.2. The asymptotic formula logforb(m, r, F) ~ mlog(r - 1) holds as m [right arrow] [infinity] for every fixed (0,1)-configuration F andr [greater than or equal to] 3.

Proof: Since F < p * [K.sub.k] for some p and k, Proposition 3.1 guarantees a constant C > 0 so that forb[(m,r,F) [less than or equal to] C [m.sup.k-1](r - 1).sup.m] for every m and r. We may assume by complementation that F contains at least one 0, in which case the configuration that contains every column with no 0's avoids F; this implies that forb[(m, r, F) [greater than or equal to] (r - 1).sup.m] for every m, r [member of] N. If r [greater than or equal to] 3 is fixed, then the logarithmic growth rates of the lower and upper bounds are asymptotically equal as m [right arrow] [infinity].

The trivial bound forb[(m, r, F) [less than or equal to] [r.sup.m] combined with the lower bound forb(m, r, F) [greater than or equal to] (r -1).sup.m] shows that forb(m, r, F) = [THETA]([r.sup.m]) if m is fixed and forb(m, r, F) is regarded as a function of r.

Going back to exact results, let [mathematical expression not reproducible] denote the [mathematical expression not reproducible] configuration of zeros and ones in which every column contains s ones, called the complete uniform configuration of weight s. Furedi and Quinn proved in [8] that forb [mathematical expression not reproducible]. The configuration where s ones never appear above k - s zeros provides the lower bound; since [mathematical expression not reproducible] Sauer's theorem provides the upper bound. The construction easily extends, yielding the following result.

Proposition 3.3. Ifs [less than or equal to] k, then forb[mathematical expression not reproducible], then forb [mathematical expression not reproducible].

Proof: Let [A.sub.n] be the n-rowed configuration that contains every column in which s ones do not appear above k - s zeros. The sequence ([A.sub.n]) satisfies the conditions of Lemma 2.3, and an identical calculation to the one in the proof of Proposition 3.1 proves the first statement.

The proof of the upper bound for the second statement is identical to the one in Proposition 3.1. For the lower bound, let A be the configuration that contains every column where s ones never appear above k - s zeros; this configuration avoids [mathematical expression not reproducible]. If [(r - 2).sup.m-k] [greater than or equal to]p-1, then for each [mathematical expression not reproducible] we can append p - 1 columns to A that have s ones above k - s zeros in the rows of X and non-binary digits elsewhere. The resulting configuration avoids [mathematical expression not reproducible] and has [mathematical expression not reproducible] columns.

A matrix is called p-simple if each column has multiplicity at most p.

Corollary 3.4. Assume that F is a k-rowed p-simple matrix such that [mathematical expression not reproducible] for some 0 [less than or equal to] s [less than or equal to] k. If[(r-2).sup.m-k] > p-1,then

[mathematical expression not reproducible]

IfF is simple and [mathematical expression not reproducible], then [mathematical expression not reproducible] for all m [member of] N and r [greater than or equal to] 2.

Proof: Since [mathematical expression not reproducible], the statement follows from Propositions 3.1 and 3.3.

The result for non-simple matrices in Proposition 3.3 is only applicable when r > 3. The argument can be modified to show that [mathematical expression not reproducible] is at most an additive constant away from [mathematical expression not reproducible].

Proposition 3.5. Suppose p > 1 and a = [[log.sub.2](p - 1)]. Then

[mathematical expression not reproducible]

Proof: Let A be the configuration with all columns that do not contain s ones above k - s zeros. For every k-set X with elements [i.sub.1] < [i.sub.2] < * * * < [i.sub.k] and [i.sub.s] + (m - [i.sub.s+1]) - k > [log.sub.2] (p - 1), we may append p - 1 columns to A with entries [c.sub.i] given by

[mathematical expression not reproducible]

For each such column c, there is exactly one k-set S (namely S = X) so that c|S is s ones above k - s zeros. Therefore, the resulting configuration A' avoids [mathematical expression not reproducible].

To determine the number of columns added to A, we count the number of choices of X with [i.sub.s] + (m [i.sub.s+1])-k < [log.sub.2] (p - 1). The number of choices with [mathematical expression not reproducible], so the number of choices of X not covered in our strategy is

[mathematical expression not reproducible]

In total, then A' contains [mathematical expression not reproducible] more columns than A.

Corollary 3.6. [mathematical expression not reproducible].

Proof: Applying Proposition 3.5 with p = 2 gives the lower bound, and the upper bound follows from Proposition 3.1 together with [mathematical expression not reproducible].

4 Identity matrices

Noting that [mathematical expression not reproducible] yields the following corollary of Proposition 3.3.

Corollary 4.1. Ifr > 3, then [mathematical expression not reproducible] for all m such that [(r - 2).sup.m-k] [greater than or equal to]p-1.

The main result of this section is a stability theorem for [I.sub.2]. It would be interesting to see similar stability theorems for other complete uniform configurations.

With each configuration A [member of] Avoid(m, r, [I.sub.2]) we can associate a tournament on m vertices. Direct an edge from i to j if there is no column in which 0 appears in row i and 1 appears in row j. If both ij and ji are possible edges, choose just one. Since A avoids [I.sub.2], there must be an edge between each pair of vertices, so this construction gives a tournament [T.sub.A] on m vertices.

Proposition 4.2. Let r [greater than or equal to] 2 and A [member of] Avoid(m, r, [I.sub.2]) such that TA is not transitive. Then |A| [less than or equal to] m[(r - 1).sup.m-1] + [(r - 1).sup.m] - 2[(r - 1).sup.m-3].

Proof: We first prove the case r = 2: If A [member of] Avoid(k, 2, [I.sub.2]) such that [T.sub.A] is not transitive, then |A| [less than or equal to] m - 1. Since [T.sub.A] is not transitive, it contains a 3-cycle ijk. The only possible columns in [A|.sub.{i,j,k}] are [mathematical expression not reproducible] and [mathematical expression not reproducible]. If we delete rows i and j, then the resulting configuration A' is simple and avoids [I.sub.2], so A| = |A' [less than or equal to] forb(m - 2, [I.sub.2]) = m - 1.

We now proceed with the general case. Suppose that A [member of] Avoid(m, r, [I.sub.2]) with [T.sub.A] not transitive. As before, there is a 3-cycle ijk in [T.sub.A]. Applying the argument used in the proof of Lemma 2.1 and splitting the sum over sets that do or do not contain {i, j, k} gives the bound

[mathematical expression not reproducible]

The left sum simplifies to

[mathematical expression not reproducible]

and the right sum is

[mathematical expression not reproducible]

Combining the two evaluations completes the proof.

Theorem 4.3. For each integer r [greater than or equal to] 2, there is a unique extremal r-configuration with m rows that avoids [I.sub.2].

Proof: By Proposition 4.2, if A is extremal, then [T.sub.A] is transitive. Therefore there is an ordering [i.sub.1],...,[i.sub.m] of [m] so that [i.sub.s][i.sub.t] is an edge of T if and only if s < t. After permuting the rows of A according to this order, no 0 appears above a 1. There are m[(r - 1).sup.m-1] such columns that contain a 0 and [(r - 1).sup.m] columns with no 0. Since A is extremal, it contains all these columns. Up to row and column permutation, therefore, A is unique.

Thus, there is a gap between the unique extremal configuration that avoids [I.sub.2] and any other configuration that avoids [I.sub.2] but is not a subconfiguration of the extremal one.

In another direction, Propositions 3.1 and 3.3 and Corollary 3.6 show that forb(m, 3, p*[I.sub.2]) = forb(m, 3, p* [K.sub.2]) when p = 1 or p = 2. However, equality does not hold for higher values of p. The following exact evaluation of forb(m, r, 3 * [I.sub.2]) shows that forb(m, 3,p * [I.sub.k]) = forb(m, 3,p* [K.sub.k])in general. In contrast, Corollary 4.1 states that forb(m, r,p * [I.sub.k]) = forb(m, r, p * [K.sub.k]) for every p > 1 when r > 3.

Proposition 4.4. Ifm [greater than or equal to] 4, then forb(m, 3, 3 * [I.sub.2]) = forb(m, 3, 3 * [K.sub.2]) - 1.

Proof: Let A be the configuration constructed in the proof of Proposition 3.5 with forb(m, 3,3 * [K.sub.2]) - 2 columns that avoids 3 * [I.sub.2]. Appending the column c with c1 = 1, [c.sub.m] = 0, and [c.sub.i] = 2 for every 1 < i < m creates a configuration with forb(m, 3, 3 * [K.sub.2]) - 1 columns that avoids 3 * [I.sub.2].

We now show that any 3-configuration that avoids 3 * [I.sub.2] has at most forb(m, 3, 3 * [K.sub.2]) - 1 columns. In each pair of rows, either [mathematical expression not reproducible] or [mathematical expression not reproducible] appears at most twice. Permuting the corresponding columns to the right end of the configuration A, we create a decomposition A = [BC] where [mathematical expression not reproducible] and B avoids [I.sub.2].IfB is not the unique extremal configuration that avoids [I.sub.2], then

[mathematical expression not reproducible]

Otherwise, Theorem 4.3 shows that we may permute the rows of B so it contains every column where no 0 appears above a 1. Since B has at least four rows, [B|.sub.{ij}] contains at least four columns of the form [mathematical expression not reproducible] for every i, j [member of] [m] with i < j.

We mark the pair i < j for each time that 0 appears in row i and 1 appears in row j in the configuration C. Since A avoids 3 * [I.sub.2] and [B|.sub.{i,j}] already contains four columns of the form [mathematical expression not reproducible], each pair has at most two marks. Each column of C contributes at least one mark. If the pair (1, m) has at most one mark, then there are at most [mathematical expression not reproducible] columns in C. If (1, m) has two marks, then there is a column c in C with [c.sub.1] = 0, [c.sub.m] = 1, and [c.sub.s] = 2 for some 1 < s < m. In this case the column c contributes at least two marks: one for (1, m), and one for either (1, s) or (s, m). So in this case, too, there are at most [mathematical expression not reproducible] columns in C. In either case,

|A| = |B| + |C| < forb(m, 3, 3 * [K.sub.2]) - 1,

proving the lower bound.

The upper bound in this argument shows that forb(m, 3,p * [K.sub.2]) < forb(m, 3,p * [I.sub.2]) for all p [greater than or equal to] 3. Indeed, by following this mark argument, one can calculate exact forbidden numbers for larger p. It's not too hard to show, for example, that forb(m, 3,4 * [I.sub.2]) = forb(m, 3,4 * [K.sub.2]) - 2 and forb(m, 3, 5 * [I.sub.2]) = forb(m, 3, 5 * [K.sub.2]) - 5. The computations, however, rapidly become rather case-heavy as p increases. In general, the mark argument can be extended to show that the difference between forb(m, 3,p * [I.sub.2]) and forb(m, 3, p* [K.sub.2])is superlinear inp; for example,

[mathematical expression not reproducible] (4.1)

although this is not sharp.

5 Block matrices

Proposition 5.1. If [(r - 2).sup.m-a-b] [greater than or equal to] p - 1, then

[mathematical expression not reproducible] (5.1)

Proof: Any maximal matrix that avoids [mathematical expression not reproducible] contains all columns that have fewer than a zeros or fewer than b ones. This accounts for the first three terms of (5.1). Thus we need only bound the number of columns that contain at least a zeros and at least b ones. There are [(r - 2).sup.m-a-b] columns that contain exactly a zeros and b ones for a fixed a-set X and b-set Y of rows. If [(r - 2).sup.m-a-b] [greater than or equal to] p - 1, then for each disjoint X,Y [subset] [m] with |X| = a and |Y| = b, we may takep - 1 columns with 0's in the rows in X and 1's in the rows of Y and entries in {2,..., r - 1} elsewhere. This is [mathematical expression not reproducible] columns, which provides the lower bound.

For the upper bound, we again use a mark argument. Consider the set of ordered pairs (X, Y) where X, Y [subset] [m] are disjoint, |X | = a, and |Y| = b. Given a matrix A, we place a mark on the pair (X, Y) for every column c [member of] A such that [c|.sub.X] contains only zeros and c|Y contains only ones. There can be at most [mathematical expression not reproducible] marks in total if the matrix A avoids F. Every column that contains at least a zeros and b ones contributes at least one mark, so there are at most [mathematical expression not reproducible] such columns, which gives the upper bound.

Corollary 5.2. If[(r - 2).sup.m-2] [greater than or equal to] p - 1, then

[mathematical expression not reproducible]

6 Forbidden configurations with 2 rows

We define the general 2-rowed (0, 1)-forbidden configuration

[mathematical expression not reproducible] (61)

Our main tools will be two reduction lemmas.

Lemma 6.1 [(Reduction Lemma for r > 3). Suppose b, c [greater than or equal to] 1 and set b' = min{b, c}. If(r - 2).sup.m-2] [greater than or equal to] 2(max{b,c}-1),then

forb(m, r, F(a, b, c, d)) = forb(m, r, F(a, b' , b', d)).

Proof: Ifb = c the statement is trivial, so suppose without loss of generality that b < c. We set F := F(a, b, c, d) and F' = F(a,b,b,d). It follows from F' < F that forb(m,r,F') [less than or equal to] forb(m, r, F). To prove the reverse inequality, we want to show that |A| [less than or equal to] forb(m, r, F') for every A [member of] Avoid(m, r, F). This is true if A avoids F', so suppose instead that F' < A. By permuting the rows of A, we may assume that some instance of F' appears in its first two rows. We write A in the block form

[mathematical expression not reproducible] (6.2)

Because F' appears in the first two rows, we know that |[A.sub.0,0]| > a, that |[A.sub.0,1]|, |[A.sub.1,0]| [greater than or equal to] b, and that |[A.sub.1,1]| > d. If either of [A.sub.0,1 ]or [A.sub.1,0] contains at least c columns, then A contains F in the first two rows. But A avoids F, so |[A.sub.1,0]|,|[A.sub.0,1]| < c. We assumed that [(r-2).sup.m-2] > 2(c- 1), so it is possible to delete the columns with [mathematical expression not reproducible] or [mathematical expression not reproducible] inthe first two rows and append |[A.sub.0,1] | + |[A.sub.1,0]| distinct columns c to A with [c.sub.1] = 0, [c.sub.2] = 1, and [c.sub.i] [member of] {0,1} for i > 2. The resulting configuration does not contain [I.sub.2] in its first two rows, so it does not contain F' in the first two rows, either. Moreover, this operation does not create a new instance of F' in A.

Iterating this process for every appearance of F' in A produces a matrix with the same number of columns as A that avoids F'. Thus |A| [less than or equal to] forb(m, r, F'), as desired.

Theorem 6.2 (Forbidden numbers for 2-rowed (0, 1)-matrices with r > 3). Let F = F(a, b, c, d) and [alpha] = max{a, d, min{b, c}}, and suppose [(r - 2).sup.m-2] [greater than or equal to] 2max{a, b, c, d}. If[alpha] > 0, then

[mathematical expression not reproducible] (6.3)

Otherwise, [mathematical expression not reproducible] and

[mathematical expression not reproducible] (6.4)

Proof: The case [mathematical expression not reproducible] is given by Corollary 5.2. We prove the statement for [alpha] > 0 in cases.

Case 1: [alpha] = a and b, c [greater than or equal to] 1. By Lemma 6.1, we may assume that b = c. Then [0.sub.2*a] < F and F is a-simple, so the statement follows from Corollary 3.4. Taking the (0, 1)-complement of F handles the case [alpha] = d with b, c [greater than or equal to] 1.

Case 2: [alpha] = min{b, c}. This implies b, c [greater than or equal to] 1, so by Lemma 6.1, we may assume b = c. Then c * [I.sub.2] < F < c * [K.sub.2], so the upper bound follows from Proposition 3.1 and the lower bound from Corollary 4.1 with k = 2.

Case 3: b = 0 or c = 0. By possibly taking the complement, we may assume that b = 0. Since the arguments are symmetric, suppose a [greater than or equal to] d, which implies that [alpha] = a. Then F < F(a, 1, max{1, c}, d), so by Lemma 6.1,

forb(m, r, a * [0.sub.2]) [greater than or equal to] forb(m, r, F) [greater than or equal to] forb(m, r, F(a, 1,1, d)).

The lower and upper bounds are equal by Corollary 3.4 and Case 1.

Proving a reduction lemma for r = 3 requires a different approach.

Lemma 6.3 (Reduction Lemma for r = 3). Let b' = min{b, c}. If [2.sup.m-2] [greater than or equal to] (max{a, b, c, d} - 1)[m.sup.2] and b' [greater than or equal to] 1, then

forb(m, 3, F(a, b, c, d)) = forb(m, 3, F(a, b', b', d)).

Proof: Letp = max{a, b, c, d}, so that F := F(a, b, c, d) is p-simple, and set F' = F(a, b', b', d). As above, forb(m, r, F') [less than or equal to] forb(m, r, F) follows from the observation that F' < F.

Now let A [member of] Avoid(m, 3, F). We want to show that |A| [less than or equal to] forb(m, r, F'). If A does not contain F', this is clear, so we assume that F' < A. We write A in block form as

[mathematical expression not reproducible] (6.5)

By possibly taking the complement of F, we may assume that b [less than or equal to] c. Moreover, since the statement is trivial if b = c, we assume that strict inequality holds. Since F' < A but F < A, we have that b < |[A.sub.0,1]|, |[A.sub.1,0]| < c If there is a column in B that is not in D, then we may delete the column [mathematical expression not reproducible] and insert the column [mathematical expression not reproducible] without introducing F as a configuration. By replacing binary digits in the first two rows with 2's in this manner, we may assume that

[mathematical expression not reproducible]

The matrices [mathematical expression not reproducible] and [mathematical expression not reproducible] both avoid F, so |DEH| + |FGH| [less than or equal to] 2 forb(m - 1,3, F). Also, B [union] C [subset] H. From inclusion-exclusion, |B| + |C| - |H| [less than or equal to] |B [intersection] C|. Because A avoids p * [K.sub.2], we know that B [intersection] C avoidsp * [K.sub.1], so |B n C| [less than or equal to] [2.sup.m-2] + (p-1)(m- 2). Therefore

|A| [less than or equal to] 2(c - 1) + 2 forb(m - 1, 3, F) + [2.sup.m-2] + (p - 1)(m - 2).

Exponential multivalued forbidden configurations

If [2.sup.m-2 ]> (p - 1)[m.sup.2], then Proposition 3.1 implies

|A| [less than or equal to] 2(p - 1) + 2 forb(m - 1, 3,p * [K.sub.2]) + [2.sub.m-2] + (p - 1)(m - 2) = (m - 1)[2.sup.m-1] + [2.sup.m] + [2.sup.m-2] + (p - 1)m(m - 1) + (p - 1)m [less than or equal to] [m2.sup.m-1]+[2.sup.m] = forb(m,3,[I.sub.2]).

Since [I.sub.2] [??] F', this shows that |A| < forb(m, 3, F'), completing the proof.

Theorem 6.4. Suppose max{a, d} [greater than or equal to] min{b, c}. If[2.sup.m-2] > (max{a, b, c, d} - 1)[m.sup.2], then forb(m, 3, F(a, b, c, d)) = [(r - 1).sup.m] + [m(r - 1).sup.m-1] + (max{a, d} - 1) ( m /2) (6.6)

Proof: Since all arguments are symmetric, we assume that a [less than or equal to] d and b [less than or equal to] c. If b [greater than or equal to] 1, then

d*[1.sub.2] [??]F(a,b,b,d) [??]d*[K.sub.2].

The forbidden numbers of both bounding configurations are equal by Corollary 3.4, and applying Lemma 6.3 shows that F(a, b,b, d) and F(a, b, c, d) have the same forbidden number. If b = 0 then F(a, 0, c, d) [??] F(a, 1, max{1, c}, d). We have d * [1.sub.2] [??] F(a, 0, c, d), and by Lemma 6.3,

forb(m, 3, F(a, 1, max{1, c}, d)) = forb(m, 3, F(a, 1,1, d)) < forb(m, 3, d * [K.sub.2]).

Again the upper and lower bounds are equal by Corollary 3.4.

The remaining question is to evaluate forb(m, 3, F(a, b, c, d)) when min{b, c} > max{a, d}. By the Reduction Lemma, we need only consider the case b = c. The smallest 2-rowed (0,1)-matrix whose forbidden number is not known when r = 3 is

[mathematical expression not reproducible]

7 Forbidden configurations with 3 rows

Lemma 2.3 provides a handful of results on 3-rowed forbidden matrices for free.

Corollary 7.1. The following forbidden numbers are exact for allr > 2 when m > 3.
F                                           forb(m, r, F)
[mathematical expression not reproducible]  [m(r - 1).sup.m-1] +
                                            [2(r - 1).sup.m] -
                                            [(r - 2).sup.m] -
                                            [m(r - 2).sup.m-1]
[mathematical expression not reproducible]  [2m(r-1).sup.m-1] +
                                            [(r-2).sup.m].


Proof: Theorem 3.2 of [4] proves that the configuration [A.sub.m] = [[0.sub.m][I.sub.m][1.sub.m]] is extremal for the second matrix in the first row of the table when r = 2, and it is not too hard to see that [A.sub.m] is extremal for the first matrix, as well. The sequence ([A.sub.m]) satisfies the conditions of Lemma 2.3, and |[A.sub.m]| = m + 1 if m G {0,1} and |[A.sub.m]| = m + 2 otherwise, so for either matrix F, we have

[mathematical expression not reproducible]

simplifying this sum yields the expression in the first row of the table.

Let [U.sub.m] denote the m x m upper-triangular matrix with 1's on and above the diagonal and 0's elsewhere. Theorem 3.3 of [4] proves that [A.sub.m] = [U.sub.m] U [I.sup.c.sub.m] U [0.sub.m] is an extremal configuration (when r = 2) for both matrices in the second row of the table. Both [U.sub.m] and [I.sup.c.sub.m] have a column with exactly one 0 and are otherwise disjoint, so |[A.sub.m]| = 2m for m > 1, and |[A.sub.0]| = 1 by convention. As before, ([A.sub.m]) satisfies the conditions of Lemma 2.3, so for either forbidden matrix F,

[mathematical expression not reproducible]

as claimed.

The matrices [mathematical expression not reproducible] and [mathematical expression not reproducible] are sandwiched between the two matrices in the second row of Corollary 7.1, so they have the same forbidden number. Our results, together with (0, 1)-complementation, evaluate the exact forbidden number for all 3 x 2 and 3 x 3 simple matrices for r [greater than or equal to] 3 except F = [mathematical expression not reproducible]. We can, however, bound forb(m, r, F) using our previous results. Theorem 3.3 in [2] states that forb(m, F) [less than or equal to] 3/2 m + 1; applications of our Lemma 2.1 and Proposition 3.3 show that

m[(r - 1).sup.m-1] + [(r - 1).sup.m] < forb(m, r, F) < 3/2 [m(r - 1).sup.m-1] + [(r - 1).sup.m].

References

[1] Noga Alon, On the density of sets of vectors, Discrete Mathematics 46 (1983), no. 2, 199-202.

[2] Richard Anstee, Some problems concerning forbidden configurations, preprint.

[3] Richard Anstee, A survey of forbidden configuration results, The Electronic Journal of Combinatorics 20 (2013), no. 1.

[4] Richard Anstee, Jerrold Griggs, and Attila Sali, Small forbidden configurations, Graphs and Combinatorics 13 (1997), 97-118.

[5] Richard Anstee and Linyuan Lu, Unavoidable multicoloured families of configurations, 2014, arXiv: 1409.4123.

[6] Keaton Ellis, Baian Liu, and Attila Sali, Multi-symbol forbidden configurations, Discrete Applied Mathematics 276 (2020), 24 - 36.

[7] Zoltan Furedi, Alexander Kostochka, and Ruth Luo, Berge cycles in non-uniform hypergraphs, 2020, arXiv:2002.01597.

[8] Zoltan Furedi and F. Quinn, Traces of finite sets, Ars Combinatoria 18 (1984), 195-200.

[9] Zoltan Furedi and Attila Sali, Optimal multivalued shattering, SIAM Journal on Discrete Mathematics 26 (2012), 737-744.

[10] Norbert Sauer, On the density of families of sets, Journal of Combinatorial Theory, Series A 13 (1972), 145-147.

[11] Saharon Shelah, A combinatorial problem: Stability and order for models and theories in infinitary language, Pacific Journal of Mathematics 41 (1972), 247-261.

[12] Vladimir Vapnik and Alexey Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and Its Applications 16 (1971), 264-280.

Travis Dillon (1*)

Attila Sali (2,3[dagger])

(1) Lawrence University, WI, USA

(2) Alfred Renyi Institute of Mathematics, Budapest, Hungary

(3) Department of Computer Science, Budapest University of Technology and Economics, Budapest, Hungary

received 2 July 2020, revised 2nd Mar. 2021, accepted 8 Mar. 2021.

(*) Research conducted under the auspices of the Budapest Semesters in Mathematics program.

([dagger]) This author's work is partially supported by the National Research, Development and Innovation Office (NKFIH) [grant K-116769 and K-132696]; the National Research, Development and Innovation Fund [TUDFO/51757/2019-ITM, Thematic Excellence Program]; the BME NC TKP2020 grant of NKFIH Hungary; and the BME-Artificial Intelligence FIKP grant of EMMI [BME FIKP-MI/SC]. It is also connected to the "Development of quality-oriented and harmonized R+D+I strategy and functional model at BME" project supported by the New Hungary Development Plan [Project ID: TAMOP-4.2.1/B-09/1/KMR-2010-0002].
COPYRIGHT 2021 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2021 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Dillon, Travis; Sali, Attila
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2021
Words:5485
Previous Article:Efficient Enumeration of Non-isomorphic Interval Graphs.
Next Article:On BMRN*-colouring of planar digraphs.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |