Families of Forbidden Configurations by Christina Louise Koch B.A., St. Olaf College, 2005 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in The Faculty of Graduate Studies (Mathematics) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) April 2013 c Christina Louise Koch 2013 Abstract The forbidden configuration problem arises from a question in extremal set theory. The question seeks a bound on the maximum number of subsets of an m-set given that some trace is forbidden. In terms of hypergraphs, we seek the maximum number of edges on a simple hypergraph of m vertices such that this hypergraph does not contain a forbidden sub-hypergraph. We will use the notation of matrices to describe the problem as follows. We call a (0, 1)-matrix simple if it has no repeated columns; this will be the analogue of a simple hypergraph. Let F be a given matrix. We say that a (0,1)-matrix A contains F as a configuration if there is some submatrix of A that is a row and column permutation of F. This is equivalent to a hypergraph containing some sub-hypergraph. F need not be simple. We define forb(m, F ) as the maximum number of columns possible for a simple, m-rowed, (0,1)-matrix that does not contain F as a configuration. A variation of the forbidden configuration problem forbids a family of configurations F = {F1 , F2 , . . . Fn } instead of a single configuration F . Thus, forb(m, F) becomes the maximum number of columns possible for a simple, m-rowed, (0, 1)matrix that does not contain any one of the Fi ∈ F as a configuration. We will present a series of results organized by the character of forb(m, F). These include a classification of families F such that forb(m, F) is a constant and the unexpected result that for a certain family, forb(m, F) is on the order of m3/2 , where previous results typically had forb(m, F ) on the order of integer powers of m. We will conclude with a case study of families of forbidden configurations and suggestions for future work. ii Preface The question of forbidden configurations was introduced to me by my supervisor Dr. Richard Anstee, and the choice to explore families of forbidden configurations came at both his suggestion and that of his previous PhD student Dr. Miguel Raggi. There are two sections of the paper that contain work done by other people. The first is a result of Balin Fleming included in Section 2.4, which is used with his permission and clearly identified as his work. The second is the proof of the result in Chapter 4, which borrows from the proof for a very similar bound originally included in a paper by Dr. Anstee, Dr. Attila Sali, and Dr. Raggi. However, the necessary modifications to the proof for the new result are the original work of Dr. Anstee and myself. All other results contained in this paper were produced by myself, some jointly with Dr. Anstee. iii Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . 1.1 Extremal problems and hypergraphs . . . . 1.2 Definitions and notation . . . . . . . . . . . 1.2.1 (0,1)-matrices . . . . . . . . . . . . . 1.2.2 Forbidden configurations and bounds 1.2.3 Matrix constructions . . . . . . . . . 1.2.4 Set system terminology . . . . . . . . 1.3 History of results . . . . . . . . . . . . . . . 1.3.1 Single forbidden configurations . . . 1.3.2 Families of forbidden configurations . 1.3.3 Elementary remarks and lemmas . . 1.4 Basic methods . . . . . . . . . . . . . . . . . 1.4.1 Standard induction . . . . . . . . . . 1.4.2 What is missing . . . . . . . . . . . . 1.4.3 Linear algebra reduction . . . . . . . . . . . . . . . . . . . . . . 1 1 4 4 5 6 9 9 10 11 13 14 14 15 16 2 Families With a Constant Bound . . . . . . . . . . . . . . . . . . . . . 2.1 A classification for families of constant bound . . . . . . . . . . . . . 18 18 iv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 20 21 22 23 27 28 3 Families With a Linear Bound . . . . . . . . . . . . 3.1 Families of minimal quadratic configurations . . . . 3.1.1 Families proved using basic methods . . . . 3.1.2 Families proved using a structure argument 3.2 Other linear results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 31 33 36 39 4 Families With a Super-linear Bound . . . . . . . 4.1 Unexpected bound for product configurations . . 4.1.1 Introduction . . . . . . . . . . . . . . . . . 4.1.2 Theorem and proof . . . . . . . . . . . . . 4.2 A similar bound for larger product configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 40 40 41 51 5 A Case Study: Families of 5.1 Constant families . . . . 5.2 Linear families . . . . . . 5.3 Table of results . . . . . 5.4 Critical subfamilies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 56 58 60 60 6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Summary of results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 62 63 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2.2 2.3 2.4 2.1.1 A constant construction . . . . . . Failed monotonicity of the constant bound Exact bound for blocks of 0’s and 1’s . . . 2.3.1 Column bound . . . . . . . . . . . 2.3.2 A sharp boundary . . . . . . . . . . 2.3.3 Other bounds and constructions . . Constant bound for another family . . . . 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x 2 Configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Tables 3.1 3.2 Minimal Quadratic Configurations . . . . . . . . . . . . . . . . . . . . Pairs of Minimal Quadratic Configurations . . . . . . . . . . . . . . . 32 33 5.1 5.2 List of 2 x 2 Configurations . . . . . . . . . . . . . . . . . . . . . . . Summary of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 60 vi Acknowledgements First, an enormous thank you goes to my supervisor, Richard Anstee. I am deeply grateful for his generosity which includes but is not limited to: large blocks of his time, collaboration on proofs, brief lectures on linear programming, advice on teaching, digressions into antique collecting, gentle reminders to keep writing up results, and of course, numerous cups of tea and coffee. An additional thanks to Miguel Raggi and Attila Sali for agreeing to modify a previously submitted paper to include one of my results. Also, thanks to Balin Fleming for permission to include one of his unpublished results. A special thanks to Jozsef Solymosi for serving as second reader for this thesis. This degree wouldn’t have been nearly as enjoyable as it was without the faculty, staff, and students of the math department. Thanks to all my professors, the office staff, and especially my graduate colleagues with whom I’ve facilitated workshops, tutored students, graded exams, written a wiki, and discussed many an assignment. Profound thanks to the friends both near and far who have supported me over the past two years: the Songbirds, the Bon House girls, everyone at the Hope, my house mates, my community group, other Regent and St. Olaf friends, my First Lutheran, First Trinity and Fairview families . . . it’s truly a wonderful thing to have so many people who believe in me. And finally, thank you to my family. vii Chapter 1 Introduction In this chapter we provide an introduction to the topic of this paper: the question of forbidden configurations. We begin with the origin of the research question and its statement. We then provide a list of all necessary notation and definitions for understanding the content of the paper, including a re-statement of the research question. This leads to a section summarizing a history of relevant results. We conclude with an overview of the basic methods that will be used to prove results. 1.1 Extremal problems and hypergraphs At its heart, combinatorics is a field of mathematics that asks “how many?” This initial question is often modified as follows: given some condition to be met, what is the maximum (or minimum) family such that the condition holds, or conversely, that the condition fails? In extremal combinatorics we are not always able to obtain exact maximum or minimum bounds, and in these cases seek an asymptotic bound. Our combinatorial question for this paper relates to similar questions from graph theory, so we will begin with the following basic definitions. Definition 1.1.1. A simple graph G is an ordered pair G = (V, E) where V stands for a set of vertices and E stands for a set of edges, where edges are unique 2-element subsets of V . Definition 1.1.2. The complete graph on n vertices, denoted Kn , is a graph on n vertices such that every possible edge is included in E. 1 Forbidden configurations, the subject of this paper, relate to theorems in extremal graph theory. These theorems address the following combinatorial question: supposing that a graph G on n vertices has no subgraph isomorphic to a graph H, what is the maximum number of edges permissible for G? One can also ask the dual question: given n vertices what is the minimum number of edges in G such that you are guaranteed a copy of the subgraph H? The first theorem, by Tur´an (and Mantel for k = 3), answers this question for H as the complete graph Kk as follows: Theorem 1.1.3. [17] Let G = (V, E) be a simple graph on n vertices with the property 2 that there is no triangle. Then |E| ≤ n4 . Theorem 1.1.4. [22] Let G be any simple graph on n vertices. Then the minimum number of edges in G such that G must contain a subgraph isomorphic to Kk is bounded above by k − 2 n2 1 n2 · or 1 − · k−1 2 k−1 2 Erd˝os and Simonovits extended a previous result of Erd˝os and Stone to present a limit bound when forbidding any subgraph H. It uses the chromatic number of the subgraph H. Definition 1.1.5. The chromatic number of a graph G, or χ(G), is the smallest natural number c such that the vertices of G can be colored with c colors and no two vertices of the same color share an edge. Theorem 1.1.6. [12, 13] Let n, H be given. We define ex(n, H) as the maximum number of edges in an n vertex (simple) graph that has no subgraph isomorphic to H. Then for all > 0, there exists some N such that for all n > N : n2 2 1− 1 − 1 − χ(H) ≤ ex(n, H) ≤ n2 2 1− 1 + 1 − χ(H) . Not only does this theorem provide an asymptotic bound for all forbidden subgraphs, H, it also connects the idea of a forbidden subgraph with the chromatic 2 number of that subgraph. We will conjecture a similar notion is helpful when looking at forbidden configurations. We will now generalize this problem of a forbidden subgraph to hypergraphs. We begin with our original definition of a graph G as an ordered pair G = (V, E) and generalize this definition to a hypergraph. Definition 1.1.7. Let X be a finite set, with 2X denoting the set of all subsets of X, or the power set of X. Definition 1.1.8. A hypergraph is an ordered pair H = (X, E), where X is a finite set of elements called vertices, E is a multiset of sets in 2X , that is, for each E ∈ E, we have E ∈ 2X . The elements of E are called edges. The hypergraph H is called simple if the elements E ∈ E are unique. i.e. E is a set. Definition 1.1.9. A set system A on X is a family of subsets of X, that is, A ⊆ 2X . It should be clear that the set system A is equivalent to the simple hypergraph H = (X, E) if A is defined on X and for all E ∈ E, E ∈ A. A simple graph as defined in Definition 1.1.1 is equivalent to a simple hypergraph where all edges have size 2. There is some disagreement over whether the edge set E can include the empty edge, where the empty edge is the set ∅ ∈ 2X . In the understanding of a hypergraph as a set system, inclusion of the empty set is sensible; however, there is value to avoiding the empty edge when considering the transversal of a hypergraph. In the next section, when we recast the forbidden subgraph problem in matrix notation, we will include the empty edge as a viable edge for the hypergraph. Definition 1.1.10. A sub-hypergraph is an ordered pair (S, ES ), where, given a hypergraph H = (X, E), S ⊆ X and ES consists of all sets E ∈ E restricted to the elements in S. Note that the sub-hypergraph of a simple hypergraph may not itself be simple; two edges that both contain the same subset of vertices will be the same if they are restricted to that subset. Also, as in the case of the hypergraph, it is possible for the empty edge to be included in the edge set of the sub-hypergraph. Hypergraphs are a generalization of the initial notion of a graph; it is thus natural to ask if the combinatorial question motivating Theorem 1.1.4 and Theorem 1.1.6 can be applied to hypergraphs. For example, given a hypergraph H = (X, E), where 3 |X| = m, what is the maximum possible size of E so that H does not contain a sub-hypergraph F ? This is precisely the question founding the study of forbidden configurations. In the rest of this paper, we will approach this question using the language of matrices. 1.2 1.2.1 Definitions and notation (0,1)-matrices Recall that a simple hypergraph H = (X, E) can be thought as a set system A on X. We will now translate a set system A to a (0, 1)-matrix A. Let A be a set system defined on the set X. Let |X| = m and |A| = n. For each set B ∈ A, we generate an incidence vector β, where β is a single column with m entries. As an incidence vector, β has a 1 in a row i if i ∈ B and 0 otherwise. We can thus describe all our sets in A as incidence vectors. We join these vectors together side by side to form the m × n (0, 1)-matrix A. The elements of X index the rows of A and the sets B ∈ A index the columns. Note that row and column order is not so important to the combinatorial object and so when we refer to such a matrix A we are actually thinking of the equivalence class of matrices that could be obtained from A by row and column permutations. We say a matrix A is simple if it is a (0, 1)-matrix with no repeated columns. A simple matrix A can be written as a set system A by reversing the process described above: if the rows of A are indexed by the elements of the set X, each column β can be interpreted as a set B ∈ A ⊆ 2X , where the elements of X included in B are those with a 1 in the corresponding row in β. We use the notation [m] to mean the set {1, 2, 3, . . . , m}. We will often use [m] to index the rows of A. We use the notation A to describe the number of columns in a matrix A. Let a set S be a subset of the rows of a matrix A. We use the notation A|S to describe the matrix A restricted to S, that is, the submatrix of A consisting of the rows indexed by elements of S. Given a (0, 1)-matrix A, the (0,1)-complement of the matrix, Ac , is the matrix that results from replacing all the 1’s in A with 0’s and all the 0’s with 1’s. 4 1.2.2 Forbidden configurations and bounds In our matrix interpretation of hypergraphs, a sub-hypergraph becomes a configuration. We define that A contains F as a configuration, written F ≺ A, if there is a submatrix of A that is a row and column permutation of F . For example, let F = 1 1 1 0 0 0 0 1 and A = 0 1 0 0 . 0 0 1 1 Then F ≺ A. We see this by looking at the 2 × 2 submatrix of A given by rows 1 and 3 and columns 3 and 4. On the other hand, we say that A avoids F , or F ≺ A if there is no submatrix in A that is a row and column permutation of F . For example, let F = 1 1 1 0 0 1 0 0 and A = 0 0 1 0 . 0 0 0 1 Then F ≺ A. If A is a simple (0, 1)-matrix with m rows that avoids F , we use the following notation: A ∈ Avoid(m, F ). So: Avoid(m, F ) = {A : A simple, m-rowed matrix; F ≺ A}. The primary question of forbidden configurations concerns the following function: forb(m, F ) = max{ A : A ∈ Avoid(m, F )}. In other words, forb(m, F ) is the largest value n such that there exists an m×n simple (0, 1)-matrix A where A ∈ Avoid(m, F ). This is simply a restatement of the question from Section 1.1 translated into a matrix representation: given a simple (0, 1)-matrix A on m rows, what is the maximum number of columns in A so that A does not contain a configuration F ? For this paper, we intend to modify the forbidden configuration question slightly by forbidding a family of configurations instead of a single configuration. 5 A forbidden family is a finite set of forbidden configurations, denoted F = {F1 , F2 , . . . , Ft }. We define Avoid(m, F) = {A : A simple, m-rowed matrix; Fi ≺ A for i = 1, 2, . . . , t}. Our previous definition of forb(m, F ) naturally generalizes to: forb(m, F) = max{ A : A ∈ Avoid(m, F)}. So forb(m, F) is the largest value n such that there exists an m × n simple (0, 1)matrix A where A ∈ Avoid(m, F). In order to find forb(m, F), there are often separate arguments to establish a lower bound and upper bound. The lower bound is frequently established by a construction of appropriate size that avoids F, while the upper bound is proved separately. Certain standard techniques for establishing an upper bound will be discussed in Section 1.4. Often it is not possible to determine exact bounds for the columns of A. In this case, we must be satisfied with determining asymptotic upper and lower bounds, expressed in big-O notation. • forb(m, F) is O(mk ) if there exists c ∈ R such that for sufficiently large m forb(m, F) ≤ cmk . • forb(m, F) is Ω(mk ) if there exists c ∈ R such that for sufficiently large m forb(m, F) ≥ cmk . • forb(m, F) is Θ(mk ) if there exists c1 , c2 ∈ R such that for sufficiently large m, we have c1 mk ≤ forb(m, F) ≤ c2 mk . 1.2.3 Matrix constructions We will use the following notation to describe various matrix configurations and constructions. We define 1k to be the column of k 1’s and 0k to be the column of k 0’s. We say that a (0, 1)-column α has column sum s when it contains s 1’s. We define Kk as the complete object on k rows, that is, the k × 2k simple matrix of all possible columns on k rows. We define Kks as the k × ks simple matrix of all 6 columns of column sum s on a matrix of k rows. For example: K42 = 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 . A cycle of length k is a graph on k vertices with edges of size 2, such that we can order the vertices x1 , x2 , . . . , xk and we have k −1 edges (xj , xj+1 ) for j = 1, 2, . . . k −1 and the edge (xk , x1 ). We will define Ck to be the vertex-edge incidence matrix of the cycle of length k, where the vertices of the cycle index the rows and the columns indicate which vertices are connected by an edge. Note that the matrix Ck will have column sum 2 for all columns and row sum 2 for all rows. For example, C4 = 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 . In our configurations and constructions, we will frequently see the following three matrices: 1 , consists of an m × m matrix with 1’s The identity matrix on m rows, or Im or Km on the diagonal and 0’s everywhere else. It corresponds to the set system of singleton sets on m elements. For example, I4 = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 . c m−1 The identity complement matrix on m rows, or Im or Km , is the (0, 1)−complement of Im , or an m × m matrix with 0’s on the diagonal and 1’s everywhere else. It cor- 7 responds to a set system of sets of size m − 1 on m elements. For example, I4c = 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 . The upper triangular matrix on m rows, or Tm , consists of an m × m matrix with columns of strictly increasing column sum, with 1’s justified towards the top of the matrix. It corresponds to the set system {{1}, {1, 2}, {1, 2, 3}, . . . , {1, 2, . . . , m}}. For example, 1 1 1 1 0 1 1 1 T4 = 0 0 1 1 . 0 0 0 1 We will also refer to this matrix as a tower matrix. We use the notation [A|B] to denote the matrix obtained from concatenating the two matrices A and B. We use the notation k · A to denote the matrix [A|A| . . . |A] consisting of k copies of A concatenated together. We give precedence to the operation · (multiplication) over concatenation so that for example [2 · A|B] is the matrix consisting of the concatenation of B with the concatenation of two copies of A. We will use the notation AT to denote the matrix transpose of A. If A is an m1 × n1 simple matrix and B an m2 × n2 simple matrix, we define the product A × B as the (m1 + m2 ) × (n1 n2 ) matrix of all possible combinations of columns of A over columns of B. Note that this is a different definition than the conventional notion of matrix multiplication. An example of I2 × I2 is shown below. 1 0 0 1 × = 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 . It is interesting to note that after some row and column permutation, I2 × I2 is the same matrix as the C4 shown earlier. 8 1.2.4 Set system terminology The following definitions appropriate terminology used for set systems (comparable, disjoint, laminar) and recast them in our matrix notation. Let α, β be two columns of a (0, 1)-matrix, with the entry in the ith row denoted αi , βi respectively. We say that α and β are comparable, with α ≤ β (or α ≥ β) if for all rows i, αi ≤ βi (or αi ≥ βi ). We say that α and β are disjoint if on every row i, αi and βi are not both 1. For example, let 1 0 1 1 1 0 α= 1 , β = 1 , γ = 0 . 0 0 1 Then α and β are comparable, with β ≤ α; β and γ are disjoint; and α and γ are neither comparable nor disjoint. We define a laminar family as the following: given a set system A, for all B, C ∈ A, B ⊆ C, C ⊆ B or B ∩ C = ∅. A laminar matrix is defined similarly: given a (0, 1)matrix A, for all columns α, β ∈ A, α and β are comparable or α and β are disjoint. Another way to define a laminar matrix is by forbidding a configuration or observing what columns are missing on any triple of rows in a matrix A (see Section 1.4 for more detail on “what is missing”). Let 1 1 FL = 1 0 , 0 1 i 1 i 1 L1 = j 1 , L2 = j 0 . k 0 k 1 Remark 1.2.1. Let A be a (0, 1)-matrix with no configuration FL . Then A is laminar. Remark 1.2.2. Let A be a (0, 1)-matrix such that on every triple of rows S = {a, b, c} there is a bijection σ : S → {i, j, k} such that A|S has no L1 and L2 as indexed. Then FL ≺ A and so A is laminar. 1.3 History of results Here we present a history of results for the forbidden configuration problem. Many of these results will be used to motivate or prove results given in the research chapters 9 of this paper. 1.3.1 Single forbidden configurations The primary result in the study of forbidden configurations is the following theorem, proved independently by Sauer and Perles, Shelah, and Vapnik and Chervonenkis. Theorem 1.3.1. [20, 21, 23] We have that forb(m, Kk ) = m m m + + ··· + . k−1 k−2 0 This implies that forb(m, Kk ) is Θ(mk−1 ). Corollary 1.3.2. For any simple configuration F on k rows, forb(m, F ) is O(mk−1 ). Anstee and F¨ uredi proved a generalization of Theorem 1.3.1 as follows: Theorem 1.3.3. [5] For fixed k, t, as m → ∞, forb(m, t · Kk ) = m m m (t − 2) (1 − o(1)) + + ··· + . k k−1 0 (k + 1) Corollary 1.3.4. For any k-rowed (0, 1)-matrix F , we have that forb(m, F ) is O(mk ). These results establish a maximum upper bound for all single forbidden configurations: in the case of a simple k-rowed configuration, Corollary 1.3.2 gives a bound of at most O(mk−1 ), while for all other k-rowed configurations, Theorem 1.3.3 gives a bound of at most O(mk ). When generating constructions to achieve a lower bound for forb(m, F ), three matrices frequently occur. These are the I (identity), I c (identity complement), and T (upper triangular) matrix, or products of the three. The prevalence of these three matrices gave rise to the following conjecture of Anstee and Sali. They have established the conjecture for all 3-rowed F . Conjecture 1.3.5. [8] Let X(F ) be the smallest p such that F ≺ A1 × A2 × · · · × Ap c for every Ai as Im/p , Im/p or Tm/p . Then forb(m, F ) = Θ(mX(F )−1 ). 10 The notation X(F ) is a direct allusion to Theorem 1.1.6 which linked chromatic number of a graph (denoted χ(G)) to bounds of this kind. Here, Anstee and Sali conjecture that matrix products of the identity, identity complement, and triangular matrices provide sufficient constructions to achieve the asymptotic bounds for forb(m, F ) for any forbidden configuration F . The three matrices of Conjecture 1.3.5 will appear shortly in a result regarding forbidden families, indicating that while Conjecture 1.3.5 remains unproven, the use of the identity, identity complement and triangular matrix is somehow fundamental to solving questions about forbidden configurations. 1.3.2 Families of forbidden configurations Because the focus of this paper will be on families of forbidden configurations, we now shift our attention to results that pertain specifically to forbidden families. For our first result, we present a theorem of Balogh and Bollob´as Theorem 1.3.6. [9] Let k be given. Then forb(m, {Ik , Ikc , Tk }) is O(1). In other words, when we forbid all three matrices used for constructions in Conjecture 1.3.5, the resulting matrices A ∈ Avoid(m, {Ik , Ikc , Tk }) all have a constant upper bound. We should point out that the bound increases dramatically with k and the asymptotics as a function of k are not fully understood. However, the following remark gives an easy lower bound. Proposition 1.3.7. [11] Let k be given. Then forb(m, {Ik , Ikc , Tk }) ≥ 2k−2 k−1 . We establish this result in Proposition 2.1.3. We have two further results that provide more exact bounds for specific instances of families for which Theorem 1.3.6 would apply. The first set of bounds comes from Anstee and Dunwoody, and are exact bounds for the families of Theorem 1.3.6 for k = 1, k = 2 and k = 3. Theorem 1.3.8. [11] We have forb(m, {I1 , I1c , T1 }) = 0, forb(m, {I2 , I2c , T2 }) = 2, and forb(m, {I3 , I3c , T3 }) = 6. A result of Fleming provides a more precise (if not exact) upper bound for a family in which the matrices are all sub-matrices of those used in Theorem 1.3.6 11 Theorem 1.3.9. [14] Let Fa = 10 01 |t · 00 , Fb = If t ≥ 2, forb(m, {Fa , Fb , Fc }) ≤ 6t − 6. 10 |t 01 · 1 1 and Fc = t · 011 001 . c Note that Fa ≺ It+2 , Fb ≺ It+2 and Fc ≺ T3t We will take up this result in greater detail in Section 2.4, while discussing forbidden families with a constant bound. Once we forbid only two of the three matrices of Conjecture 1.3.5, a non-constant bound results, as the following three theorems, proved by Balogh, Keevash and Sudakov, indicate. Theorem 1.3.10. [10] Let k ≥ 2. Then forb(m, {Ik , Ikc }) is Θ(mk−1 ). Theorem 1.3.11. [10] Let k ≥ 2. Then forb(m, {Ikc , Tk }) is Θ(mk−1 ). Theorem 1.3.12. [10] Let k ≥ 2. Then forb(m, {Ik , Tk }) is Θ(mk−2 ). Forbidding families of forbidden configurations also results in asymptotic bounds with non-integer exponents. Theorem 1.3.13. [1] We have forb(m, {C4 , 13 }) is Θ(m3/2 ). This theorem is linked to another family with the same bound. Theorem 1.3.14. [7] We have forb(m, {I2 × I2 , T2 × T2 , I2 × T2 }) is Θ(m3/2 ). The previous result was in a preliminary version of [7] and in Section 4.1 we will prove a stronger result, Theorem 4.1.3. Finally, we have a result regarding families of balanced and totally balanced matrices. The cycle-incidence matrices of the family {C3 , C4 , C5 , . . . } are also called balanced matrices; the matrices of the family {C3 , C5 , C7 , . . . } are called totally balanced. It turns out that the bound on these infinite families is dependent simply on the bound for C3 , i.e. Theorem 1.3.15. [2] We have forb(m, C3 ) = forb(m, {C3 , C5 , C7 . . . }) = m m m + + . 2 1 0 Thus we have a series of results characterizing forbidden families that contain the three matrices of Conjecture 1.3.5, as well as some more precise constant bounds, and finally, a set of results relating to balanced and totally balanced matrices. 12 1.3.3 Elementary remarks and lemmas In addition to the results described above, one can easily make a series of helpful remarks and lemmas regarding forb(m, F ) and forb(m, F) simply by using the definitions from Section 1.2. Remark 1.3.16. (Complementarity) Assume F = {F1 , F2 , . . . , Ft } and F c = {F1c , F2c , . . . , Ftc }. Then forb(m, Fi ) = forb(m, Fic ) and forb(m, F) = forb(m, F c ). Lemma 1.3.17. (Monotonicity) Suppose F , F are configurations. If F ≺ F , then forb(m, F ) ≤ forb(m, F ). Proof. Any matrix that contains F will also contain F , and any matrix that avoids F will also avoid F . The lemma follows. Lemma 1.3.18. (Induced lower bound) If F ⊆ F, then forb(m, F ) ≥ forb(m, F). Proof. If A avoids F it will also avoid F , however there may be a better (larger) construction for F that does not avoid the configurations in F \ F . Note that this lemma is superficially the exact opposite of the previous lemma. In Lemma 1.3.17, a smaller configuration F means a smaller bound forb(m, F ), while in Lemma 1.3.18 a smaller family F means a larger bound forb(m, F). Lemma 1.3.19. (Induced upper bound) If F = {F1 , F2 , . . . , Ft }, then forb(m, F) ≤ mini∈[t] (forb(m, Fi )). Furthermore, forb(m, F) ≤ minF ⊆F {forb(m, F )}. Proof. Because each F ∈ F must be avoided, forb(m, F) can be no larger than the smallest forb(m, F ) for all F ∈ F or the smallest forb(m, F ) for all F ⊆ F. We conclude with a final lemma that, while easy to state and simple to prove, will be remarkably powerful, particularly in conjunction with Theorem 1.3.6 regarding forbidden families with a constant bound. Lemma 1.3.20. Let F = {F1 , F2 , . . . , Ft }. Suppose F is a family such that for each j ∈ [t], there exists F ∈ F such that F ≺ Fj . Then forb(m, F ) ≤ forb(m, F). 13 Proof. Let F and F be as stated above. Suppose forb(m, F ) > forb(m, F). This implies that there is a construction A of size m × forb(m, F ) that avoids F . For any Fi ∈ F, if there is F ≺ F , such that F ≺ Fi , then Fi ≺ A. However, by our hypothesis, this is true for all Fi ∈ F. Thus A avoids F and forb(m, F) ≥ forb(m, F ), a contradiction. 1.4 1.4.1 Basic methods Standard induction One way to establish an upper bound on forb(m, F) is by inducting on m, the number of rows. The name for this process is standard induction, and it is a common proof technique used in the field of forbidden configurations. As we will use it in several results, it is worth describing in some detail here. Let A ∈ Avoid(m, F), with A = forb(m, F) for some forbidden family F. Standard induction is based on the following decomposition: Choose a row r in A. Sort the columns of A based on their entry in column r. Now suppose we delete r. Certain columns in A[m]\r may now be repeated. These repeated columns form the sub-matrix Cr . The non-repeated columns with a 0 in row r form the submatrix Br . Non-repeated columns with a 1 in row r form the submatrix Dr . After this sorting of rows and columns, the decomposition appears as: A= r [m] \ r 0...0 1...1 Br Cr Cr Dr . (1.1) Note that Br , Cr , and Dr are all simple matrices in their own right and the matrix [Br |Cr |Dr ] is also simple. We also know that because F ≺ A, F ≺ [Br |Cr |Dr ], so [Br |Cr |Dr ] ∈ Avoid(m − 1, F). However A = Cr + [Br |Cr |Dr ] . Thus if we can find an upper bound for Cr , the upper bound for A arises from induction on the rows of A as follows: forb(m, F) ≤ Cr + forb(m − 1, F). (1.2) In order to establish an upper bound on Cr , we will frequently use what we have termed inductive children, that is, sub-configurations that must be avoided in 14 Cr in order that Fi ≺ [01] × Cr for all Fi ∈ F. Consider the following example: 0 0 0 1 F = 1 1 0 1 , 0 1 1 0 1 1 1 1 . 1 1 Inductive Children of F : 1 0 0 0 1 0 , 0 1 1 0 0 1 , 1 0 1 0 1 1 1 , 1 , 1 1 1 1 1 . If either of the last two inductive children are present in Cr , the second configuration of our forbidden family will appear in the original matrix. Similarly, if any of the first three inductive children are present in Cr , we will have the first configuration of our forbidden family. If the forbidden family of inductive children is “simpler” than the original forbidden family, it will sometimes be easier to construct a bound or apply a previous result. Then by induction, a bound can be found for the original family. 1.4.2 What is missing Another proof technique is that of considering “what is missing” or “in short supply”. For this technique, we have a configuration of k rows. On any k-tuple of rows we consider which k-rowed columns must be absent (missing), so that the configuration is avoided, or which k-rowed columns must have a maximum number of copies to avoid the configuration. For example, if F = 0 1 1 0 0 1 0 0 0 1 1 1 , on any 2-tuple of rows, i, j either there are ‘absent’ columns: no i j 0 0 no or i j 1 1 , or one column appears ‘in short supply,’ which in this case, appears at most once, namely either 15 ≤1 i j 1 0 . or the same with the roles of i, j reversed. If this is true for all pairs of rows in A then we can see that indeed A ∈ Avoid(m, F ). In general for a set of rows S ∈ [m] with |S| = k and for a k × 1 (0, 1)-column α, we say that α is in short supply on S (in A) if there is a small bound on the number of times α appears in A|S . Note that here we are considering α as a submatrix of A|S not as a configuration; order matters. Also when α appears no times in A|S then we say α is absent on S. One basic result that follows from a “what is missing?” analysis is as follows: given a matrix A, if for each k-tuple of rows from A, some k × 1 column with k entries is missing, then A has no Kk and the bound from Corollary 1.3.2 applies, making A be O(mk−1 ). 1.4.3 Linear algebra reduction In the previous section, we noted that a matrix with at least one k ×1 column missing on each k-tuple of rows contains no Kk and is thus of size at most O(mk−1 ). In this section we will present a method of Anstee and Fleming that reduces a matrix to this scenario by eliminating O(mk−1 ) columns, making the bound for the total matrix also O(mk−1 ) [4]. This method presupposes that we have already performed an analysis of what is missing or in short supply, and all k-tuples of rows are either missing a column or have at least two columns in short supply. Theorem 1.4.1. Let t be given. Let A be an m-rowed simple matrix such that for each S ∈ [m] , either A|S has one column absent or has two columns αS , βS which k are in short supply, say appearing at most t times. Then A is O(mk−1 ). Proof. Let S be the set of all k-tuples of rows S such that there are at least two columns in short supply on S. Let S ∈ S with columns α and β its columns in short supply. We will first define a multi-linear indicator polynomial gS such that, for all columns γ in the matrix A, gS (γ) is non-zero only when γ|S = α or γ|S = β. We first define a 16 multi-linear expression that tracks each α and β on a k-tuple of rows, S. If each row r in A is assigned a variable xr , this will be: (xr − (α)r ). fS,α = r∈S And similarly for β. We combine these expressions into our multi-linear polynomial: gS = fS,α − fS,β Note that the combination of leading terms for each fS,α , fS,β cancels out, leaving gS with degree k − 1. We choose pairs Si ∈ [m] and γi (a column of A) for i = 1, 2, . . . , p such that k γi |Si is either α or β. In addition we assume that for all pairs i < j, that γj |Si = α, β and for any column γ of A we have that there is an i with 1 ≤ i ≤ p, such that γ|Si = α or β. We can achieve this by greedily seeking such pairs Si , γi until no more are possible. We form indicator polynomials for each i namely gSi = fSi ,α − fSi ,β which are nonzero for any column γ that has γ|Si = α or β. We recall that the highest degree terms in fSi ,δ are j∈Si xj and so gSi = fSi ,α − fSi ,β has degree at most k − 1. Our choice of pairs has for i < j, that gSi (γj ) = 0 and gSj (γj ) = 0. Thus the p polynomials gSi are linearly independent. But the polynomials lie in a space of m m dimension k−1 + k−2 + · · · + m0 and so we have the wonderful conclusion that p is at most this dimension and so is O(mk−1 ). We now remove from A all columns γ which have for some i, γ|Si = α or β. There can be at most 2tp such columns which is O(mk−1 ). Our resulting matrix A has the property that for every S ∈ [m] , we have that A |S has (at least) one absent column k and so A has no Kk . Thus A is O(mk−1 ). The number of deleted columns is also O(mk−1 ) and so A is O(mk−1 ). 17 Chapter 2 Families With a Constant Bound In this chapter we will discuss results pertaining to forbidden families that have a constant bound. We will use a previously cited result of Balogh and Bollob´as to classify all forbidden families that have a constant upper bound. We will also show that the complement of this set is all families with at least a linear lower bound. We will then briefly discuss how the constant bound for these forbidden families is not monotonic, that is, the constant bound is not weakly decreasing as the number of rows in the matrix A increases. Finally we will discuss exact bounds for two forbidden families of constant bound: both an exact bound for a specific forbidden family and a maximal upper bound for another forbidden family. 2.1 A classification for families of constant bound In Section 1.2, we stated an important result of Balogh and Bollob`as regarding forbidden families, Theorem 1.3.6. This theorem states that for each k ∈ N, forbidding the family F = {Ik , Ikc , Tk } will yield a constant bound on forb(m, F). We will now prove that this theorem in fact characterizes all forbidden families of constant bound. Theorem 2.1.1. Let F be a finite forbidden family. Then forb(m, F) is O(1) if and only if there exists Fi , Fj , F ∈ F (not necessarily distinct configurations) such that for some value k ∈ N, Fi ≺ Ik , Fj ≺ Ikc , and F ≺ Tk . Proof. We prove the forward direction by the contrapositive. Let F be a forbidden family, where Fi ∈ F is an mi × ni configuration. We choose d to be the maximum c of {{mi }, {ni }} over i. Now suppose there is at least one matrix of I2d , I2d , or T2d 18 (without loss of generality, we will assume I2d ) where for all Fi ∈ F, Fi ≺ I2d . Then for all Fi ∈ F, Fi ≺ Im for m ≥ 2d and so there exists a linear construction A ∈ Avoid(m, F), namely, A = Im . Therefore forb(m, F) is Ω(m) and cannot have a constant upper bound. The reverse direction is straightforward to prove using Lemma 1.3.20. As stated in the hypothesis, suppose there exists Fi , Fj , F (not necessarily unique configurations) in our family F such that for some value k ∈ N, Fi ≺ Ik , Fj ≺ Ikc , and F ≺ Tk . Then by Lemma 1.3.20, forb(m, F) ≤ forb(m, {Ik , Ikc , Tk }). But by Theorem 1.3.6 forb(m, {Ik , Ikc , Tk }) is O(1), so forb(m, F) is also O(1). The proof of this classification suggests the following proposition. Proposition 2.1.2. For all forbidden families F with a non-constant upper bound, forb(m, F) is Ω(m). Proof. By Theorem 2.1.1, a family has a non-constant upper bound if there is some matrix from Ik , Ikc , Tk such that for all Fi ∈ F, none of the Fi are contained in this matrix. Without loss of generality, let this matrix be Ik . Then for m ≥ k the linear matrix Im ∈ Avoid(m, F) and so there is at least a linear construction in Avoid(m, F). Thus forb(m, F) is Ω(m). These two results together tell us that there is no family F such that forb(m, F) is Θ(m ) where 0 < < 1. 2.1.1 A constant construction Dunwoody describes the following construction that avoids the family {Ik , Tk , Ikc }. Proposition 2.1.3. [11] We select for A all columns from the (k − 1)-fold product [0k−1 |Tk−1 ] × [0k−1 |Tk−1 ] × · · · × [0k−1 |Tk−1 ] that have column sum at most k − 1. A is a (k − 1)2 × 2k−2 simple matrix in Avoid((k − 1)2 , {Ik , Ikc , Tk }). k−1 Proof. We readily see that Tk ≺ A since A has no column with k 1’s. We also see that Ik ≺ A since if Ik ≺ A, then it must use two rows from one of the products Tk−1 but every two rows of Ik contains I2 and no two rows of Tk−1 contain I2 . Similarly Ikc ≺ A So A ∈ Avoid((k − 1)2 , {Ik , Ikc , Tk }). We note that [0k−1 |Tk−1 ] contains exactly one column of sum i for each i with 0 ≤ i ≤ k−1. We create a bijection between the elements of 2k−2 and the columns as k−1 19 follows. We consider 1, 2, . . . , 2k−2 and imagine choosing k−1 entries a1 < a2 < · · · < ak−1 . Then we choose the column of sum a1 − 1 from the first Tk−1 and the column of sum ai −ai−1 −1 from the ith Tk−1 (from the k −1-fold product) for i = 2, 3, . . . , k −1. We verify that sum of column sums is at most k − 1 (a1 − 1 + k−1 i=2 (ai − ai−1 − 1) = ak−1 − k − 1 and we use ak−1 ≤ 2k − 2) and no column sum chosen from a Tk−1 exceeds k − 1 (By our choice of ai ’s we have i ≤ ai ≤ 2k − 2 − (k − 1 − i) and so ai ≤ k + i − 1 and ai−1 ≥ i − 1 and so 0 ≤ ai − ai−1 − 1 ≤ k − 1). This construction is interesting for two reasons. First, it establishes a lower bound for forb(m, {Ik , Tk , Ikc }), as seen in Proposition 1.3.7. Second, in contrast to the bounds that we will present in Section 2.3 and Section 2.4, this is quite a substantial constant bound, demonstrating that even though the asymptotic bound of the family is constant by Theorem 1.3.6, there is still room for a large construction that will avoid the family. 2.2 Failed monotonicity of the constant bound When considering forb(m, F ) and forb(m, F), a natural question arises about whether the bound is monotonic with respect to the number of rows, i.e. as m increases, is forb(m, F ) or forb(m, F) weakly decreasing? We have one result of Raggi that states that forb(m, F ) is monotonic for single configurations of a certain kind. Proposition 2.2.1. [18] Let F be a (0, 1)-matrix that does not contain a row of 0’s, a row of 1’s, or a repeated row. Then for all m, forb(m, F ) ≤ forb(m + 1, F ). While we have this result for single configurations of the type described above, when considering forb(m, F), particularly for families with a constant bound, the monotonicity conjecture fails almost immediately. There is a simple family with a constant bound where forb(m, F) does not satisfy the inequality forb(m, F) ≤ forb(m + 1, F), namely the 2 × 2 block of 0’s and the 2 × 2 block of 1’s 20 Theorem 2.2.2. We have forb m, 0 0 0 0 , 2 if m = 1, m ≥ 7 . = 4 if m = 2, 5, 6 6 if m = 3, 4 1 1 1 1 Proof. The proof for m = 1, 2 is trivial; on one row the complete matrix [01] avoids the family and on two rows the complete matrix K2 (with four columns) also avoids the family. For m = 3 and m = 4 we use Proposition 2.3.10 to prove the upper bound of 6( − 1) = 6(1) = 6 and then the construction K42 achieves the bound (for m = 3, simply delete one of the rows of the matrix construction for m = 4). For m = 5 and m = 6 we have a construction with four columns, which is (K42 )T . However, we must show that the upper bound for these rows is no greater than 4. Suppose there is a matrix of five columns on five or six rows that avoids our family. We analyze this matrix by rows. In the first row there must be at least three 1’s or three 0’s. Without loss of generality, we assume there are at least three 1’s. We now restrict our attention to the remaining rows in the columns underneath these 1’s. These rows must have at least two 0’s, otherwise we generate the block of 1’s. However, we cannot repeat any of these rows with two 0’s because that will generate the block of 0’s. There are are only 3 possible ways to order the two 0 s and one 1 in these three columns before creating a repeat. Thus it is not possible to go beyond four rows, and forb(m, F) for m = 5, m = 6 must be less than 5. Finally, the bound and construction for m ≥ 7 follows from both Theorem 2.3.4 and Theorem 2.3.6. The pattern of bounds in this proof suggests that while the bound on a forbidden family need not be always monotonic, forb(m, F) may be eventually monotonic, for m sufficiently large. 2.3 Exact bound for blocks of 0’s and 1’s In this section, we offer a refinement of the constant bound of Theorem 1.3.6 by giving an exact bound for forbidden families consisting of a block of zeros and block of ones, 21 of which the family in Theorem 2.2.2 is an example. Definition 2.3.1. Let k, , p, q be positive integers. We define 0j as a k × block of 0’s and Jpq as a p × q block of 1’s. These two configurations, 0j and Jpq , are interesting both for for their nonmonotonic bound, and for their frequent appearance in other configurations, particularly Ik , Ikc and Tk . 2.3.1 Column bound Our first theorem will establish an exact bound for forb(m, {0k , Jpq }) for m sufficiently large. We will first prove a series of lemmas. Lemma 2.3.2. Let k, , p, q be given. Let A ∈ Avoid(m, {0k , Jpq }), with A = n. Also let ar denote the number of 0’s in row r of A, and br the number of 1’s in row r so that ar + br = n. Then: m r=1 ar + br q ≤ (k − 1) n Proof. We consider the columns of A. We take all + (p − 1) n . q (2.1) sized subsets of the columns and call them 0-buckets. Similarly, we take all q sized subsets of the columns as 1buckets. We will have n 0-buckets and nq 1-buckets. We then process the rows of A one by one, considering all possible sized and q sized subsets of columns on that row. If one of these subsets contains all 0’s or all 1’s, it makes a contribution to the appropriate 0-bucket or 1-bucket. Thus if there are a 0’s in a row, and b 1’s (where a + b = n), then the row will make contributions to a 0-buckets and qb 1-buckets. The left side of (2.1) is thus the total number of contributions over the rows of A. Each of our n 0-buckets can have a maximum of k − 1 contributions, and similarly, our nq 1-buckets can have a maximum of p − 1 contributions, which produces the right side of the inequality. T . Let A = [K q−1 Lemma 2.3.3. Let m, , q be given with m ≥ +q−2 +q−2 |j · γ] , where q−1 +q−2 γ is a column in K q−1 . Then A is an m × ( + q − 2) simple +q−2 and j = m − q−1 matrix and A ∈ Avoid(m, {01 , J1q }). 22 Proof. By definition A is simple, with m rows and + q − 2 columns. Furthermore, each row has − 1 zeroes and q − 1 ones, so A ∈ Avoid(m, {01 , J1q }. With these two lemmas, we can now establish an upper bound and constructive lower bound for forb(m, {0k , Jpq }). Theorem 2.3.4. Let k, , p, q be given. Then there exists some constant ck that for m ≥ ck pq , we have forb(m, {0k , Jpq }) = + q − 2 pq such Proof. We let d = max{k, , p, q}. We can then say 0k ≺ T2d , 0k ≺ I2d and c . Thus by Theorem 2.1.1, forb(m, {0k , Jpq }) is O(1). Jpq ≺ T2d , Jpq ≺ I2d We wish to show that forb(m, {0k , Jpq }) = + q − 2. From Lemma 2.3.2 we know that the right side of (2.1) is constant based on n, k, , p and q. In order to maintain the inequality in (2.1), the terms of the left side must be zero for most rows r, which means ar < and br < q. Because a + b = n, this requires n ≤ + q − 2. So for sufficiently large m, forb(m, {0k , Jpq }) ≤ + q − 2. It remains to show we have a construction that achieves the bound. Let A = q−1 [K +q−2 |j·γ]T as described in Lemma 2.3.3. By Lemma 2.3.3 A ∈ Avoid(m, {01 , J1q }), and so we know A ∈ Avoid(m, {0k , Jpq }). Furthermore, A = + q − 2. Thus A is a construction that achieves the upper bound and so forb(m, {0k , Jpq }) = q + − 2. 2.3.2 A sharp boundary We have now shown that forb(m, {0k , Jpq }) = +q−2 for m larger than some constant ck pq . We can say something more specific about ck pq when = q or p = k. In fact, in these two cases, we can show that there is a sharp boundary for forb(m, {0k , Jpq }); for m ≤ ck pq , forb(m, {0k , Jpq }) > + q − 2 and for m > ck pq , the bound proved in Theorem 2.3.4 applies. First we consider the case where = q. Lemma 2.3.5. Let = q, A = n and a + b = n. Then the terms of the summand in (2.1) are bounded from below as follows: n 2 + n 2 ≤ 23 a + b . (2.2) n 2 Proof. Note that if a is written as − i for some i ∈ Z, then b = n − a = n − n2 + i = n2 + i. We proceed by induction on i. n n Let a = n2 , and b = n2 . Then a + b ≥ 2 + 2 is true trivially. Now assume for the inequality is true for a = n2 − i, b = n2 + i, for some i ∈ Z. We must show that n 2 − (i + 1) n 2 + n k Using the combinatorial identity the previous expression as n 2 −i l n 2 − + (i + 1) n−1 k−1 = n 2 n n By induction we know that 2 l −i + 2 +i ≥ n n binomial coefficient the difference 2−1+i − 2 n 2 − (i + 1) n−1 k + −i−1 + −1 + n 2 n 2 ≥ n 2 . , we can rewrite the left side of +i + −1 n 2 n 2 +i . n −i−1 −1 + (i + 1) + + 2 and by properties of the ≥ 0. Thus ≥ n 2 + n 2 , as desired. Proposition 2.3.6. Let p, k be given, and l = q. Let A ∈ Avoid(m, {0k , Jp }), with A = n. Then the number of rows m in A is subject to the following bound: m≤ (k + p − 2) n 2 + n (2.3) n 2 Proof. Because Lemma 2.3.5 gives a lower bound for the summand from the left side of (2.1), we know the following is true: m n 2 + m n 2 ≤ r=1 24 αr + βr q We know from Lemma 2.3.2 that the summand above is bounded by (k − 1) n + (p − 1) n q Combining these two inequalities, gives m n 2 + n 2 ≤ (k − 1) n n + (p − 1) , resulting in the bound of (2.3). We can now prove that when = q, the column bound has a sharp boundary where the column bound changes. In particular, the following results also show lack of monotonicity for this constant bound. Theorem 2.3.7. Let p, k be given, and l = q. Then if m ≤ (k−1) 2 −1 +(p−1) 2 −1 , then there exists a matrix A ∈ Avoid(m, {0k , Jp }) such that A > 2 − 2. If m > (k − 1) 2 −1 + (p − 1) 2 −1 then forb(m, {0k , Jpq }) = 2 − 2. Proof. Let l = q and n = 2 − 1. The row bound described by (2.3) is as follows: m ≤ (k + p − 2) −1 + = (k + p − 2) = (k − 1) 2 −1 2 2 −1 + (p − 1) T 2 −1 . Let A = (k − 1) · K2−1 . Then A has (k −1) 2 −1 +(p−1) 2 −1 −1 |(p − 1) · K2 −1 rows and 2 −1 columns. Furthermore, the configuration O1 will appear exactly k −1 times on any subset of columns and the configuration J1 will appear exactly p − 1 times on any subset of columns and thus, A ∈ Avoid(m, {Ok , Jp }). Note that this is a best case scenario with only one contribution per row, and so once we reach the boundary of m = (k − 1) 2 −1 + (p − 1) 2 −1 the left hand side of the inequality in (2.1) will be equal to the right hand side. In the next row, because either ar ≥ or br ≥ , the left hand side will increase by at least one, contradicting 25 (2.1) and thereby proving that for m > (k − 1) 2 −1 + (p − 1) 2 −1 , the bound must drop to 2 − 2 as already proved in Theorem 2.3.4 for m sufficiently large. Similarly to the previous theorem, we can also show that if k = p, the column bound from Theorem 2.3.4 has a sharp boundary. Theorem 2.3.8. Let k, , q be given. Suppose k = p and let n = l + q. Then if m ≤ (k − 1) +q , there exists an A ∈ Avoid(m, {0k , Jkq }) where A = n. Furthermore, for m > (k − 1) +q , forb(m, {0k , Jkp }) < + q. Proof. Let k = p and n = + q. Let A = [(k − 1) · K +q ]T . By definition, A is an (k − 1) +q × ( + q) simple matrix. Now consider all -sized subsets of the columns of A. Each subset will contain all zeroes on exactly k − 1 rows, thus avoiding 0k . Similarly, each q-sized subset of columns will contain all zeroes on exactly k − 1 rows of A, avoiding Jkq . It remains to show that this boundary is sharp. We may apply (2.1) from Lemma 2.3.2. Because k = p and n = + q, where +q = +q , the right hand side q +q of (2.1) can be written as 2(k − 1) . On the left hand side of the inequality, we note that since ar + br = n = + q, we have 2 ≤ ar + bqr , with equality when ar = and br = q. Thus, m 2m ≤ r=1 ar + br q ≤ 2(k − 1) +q Hence for m > (k − 1) +q , forb(m, {0k , Jkp }) < + q. A similar argument can be made for n = l + q − 1, with the same row bound. Theorem 2.3.9. Let k, , q be given. Suppose k = p and let n = l+q−1. Then if m ≤ (k − 1) +q , there exists an A ∈ Avoid(m, {0k , Jkq }) where A = n. Furthermore, for m > (k − 1) +q , forb(m, {0k , Jkp }) < + q − 1. −1 Proof. Let k = p and n = + q − 1. Let A = [(k − 1) · K +q−1 |(k − 1) · K +q−1 ]T . By definition, A is an (k − 1) +q × ( + q − 1) simple matrix. Now consider all -sized subsets of the columns of A. Each subset will contain all zeroes on exactly k − 1 rows in the top half of the matrix, thus avoiding 0k . Similarly, each q-sized subset of columns will contain all zeroes on exactly k − 1 rows of the bottom half of A, avoiding Jkq . 26 It remains to show that this boundary is sharp. We may apply (2.1) from Lemma 2.3.2. Because k = p and n = + q − 1, after some manipulation of the binomials, the right hand side of (2.1) can be written as (k − 1) +q . On the left hand side of the inequality, we note that since ar + br = n = + q − 1, we have 1 ≤ ar + bqr , with equality when ar = or br = q. Thus, m m≤ r=1 Hence for m > (k − 1) 2.3.3 +q ar + br q ≤ (k − 1) +q , forb(m, {0k , Jkp }) < + q − 1. Other bounds and constructions We have now shown that for sufficiently large m, forb(m, {0k , Jpq } = + q − 2 and in certain cases, we know precisely how large m must be before this exact bound applies. However, it is not clear what forb(m, {0k , Jpq }) is for small m. The following results provide some additional insight into upper and lower bounds for forb(m, {0k , Jpq }). The following proposition places an absolute upper bound on forb(m, {0k , Jpq }) for all values of m, provided that k = p = 2 and = q. Proposition 2.3.10. Let k = 2, p = 2 and forb(m, {02 , J2 }) ≤ 6( − 1). = q. For m ≥ 3, Proof. Suppose we have a matrix A which avoids {02 , J2 }. On every subset of 3 rows, the columns of A will be one of the columns of K3 , shown and labeled in (2.4). a b c d e f g h 1 1 1 0 0 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 (2.4) We now consider some subset S of three rows of A. The total number of columns in A can be expressed as a sum a+b+c+d+e+f +g +h, where each letter represents the total number of times that column appears on S. Note that we cannot have more than − 1 copies of a and b in total, because if a + b = we will have 02 . A similar argument applies to a, c; a, d; h, e; h, f ; and h, g. So our question can be interpreted as a linear program where we want to maximize the sum a + b + · · · + g + h under 27 the following constraints: a + b ≤ − 1, h + e ≤ − 1, a + c ≤ − 1, h + f ≤ − 1, a + d ≤ − 1, h + g ≤ − 1. If we add up all our constraints, we get that 3a+b+c+d+e+f +g+3h ≤ 6( −1) so the total number of columns a+b+· · ·+g+h is also bounded by 6( −1). Furthermore, our sum will achieve this bound when a = h = 0 and b = c = d = e = f = g = − 1. While we demonstrated a construction that achieves our upper bound of + q − 2 for m large, we are still searching for helpful constructions for m small. The following proposition describes one such candidate. p Proposition 2.3.11. Let k, , p, q be given. Then Kk+p ∈ Avoid(m, {0k , Jpq }) for ,q > 1 p Proof. Let A = Kk+p . Consider any k-sized subset of the rows of A. Because p A = Kk+p , each k-sized subset will contain all zeroes in only one column of A. Similarly, each p-sized subset of rows will contain all ones in only one column of A. Thus, the rows of A avoid {0k , Jpq } if , q > 1. This construction has k+p columns on k + p rows and thus shows that, for large p k and p, there can be matrices with many columns in Avoid(m, {Ok , Jpq }), even if the final constant bound as given in Theorem 2.3.4 is small. 2.4 Constant bound for another family The previous bound for configurations of 0 s and 1 s is not the first refinement of the constant bound for families of forbidden configurations that have a constant bound. We present the following result of Balin Fleming, taken from his research notes with his permission. Let the configurations Fa , Fb ,and Fc be defined as follows: Fa = 1 0 1 t· , 0 1 1 Fb = 1 0 0 t· 0 1 0 28 Fc = t · 0 1 1 0 0 1 where t is some integer constant. The configurations Fa , Fb , Fc are contained in the c matrices I3t , I3t , T3t respectively, and are thus a family of constant bound as shown by Theorem 2.1.1. The value of the following result is a much smaller constant bound than that implied by Theorem 1.3.6. Proposition 2.4.1. [14] Let Fa , Fb , Fc be as given above, with t ≥ 2. Then forb(m, {Fa , Fb , Fc }) ≤ 6t − 6. Proof. Let A ∈ Avoid(m, {Fa , Fb , Fc }). Either A < 6t−6 (establishing the result) or A > 6t − 5. By pigeonhole principle we know that some row of A has at least 3t − 2 zeroes or 3t − 2 ones. Without loss of generality, we can assume there is some row of A with at least 3t − 2 zeroes (if not, the following argument can proceed using the complement). We call this row i. We now consider the columns of A that have a zero in row i. We call this set of columns A , and the next part of the proof will take place in A , which, by definition, has at least 3t − 2 columns. Assume for a contradiction that no row in A has t · [01]. Assuming this, all rows in A must have at least 2t − 1 ones or 2t − 1 zeroes. We choose rows j and k, with no t · [1], so each row has at least 2t − 1 zeroes. With this number of zeroes, we have at least t · 00 on the row pair (j, k). Since we have this many 00 columns on (j, k), we cannot have an I2 on the other columns of (j, k) as this would create the configuration Fb on these two rows. Hence, either rows j and k are the same or else they are comparable. In either case, each row j, k, has its ones confined to the same columns of A , of which there are at most t − 1. This is true for all row pairs (j, k) where j and k contain no t · [1]. Thus for these rows, all their ones are contained to the same set of t − 1 columns within A . We now repeat this process for all pairs of rows (g, h) where g, h are a pair of rows with no t · [0]. The same proof follows, that all zeroes in these rows must be confined to the same t − 1 (at most) columns in A . Thus we have two sets of t − 1 columns, leaving behind a set of at least t columns that are identical, contradicting the simplicity of A. Therefore, there must be some row with t · [01] in A . Call this row . We now pull back to consider the full width of A, but now in the chosen row . As we have just shown, row has [t · 01]. Assuming A = 6t − 6, then row has either [(3t − 2) · 0|t · 1] or [(3t − 2) · 1|t · 0]. Assume the former. Following our previous argument with row i replaced by row we can show that there is some row p with t · [01] under the zeroes of row . Then there can be no zero in p under the ones of row 29 (else we will have Fb ), so there must be t ones. But this gives a copy of Fc . Thus row cannot have [(3t − 2) · 0|t · 1]. We obtain a similar contradiction if contains [(3t − 2) · 1|t · 0]. Therefore A < 6t − 6. 30 Chapter 3 Families With a Linear Bound In the previous chapter, we presented a characterization of finite forbidden families with a constant bound. The proof of this characterization indicated that there was a gap between forbidden families with constant bound and linear bound, that is, if a the bound for a forbidden family was not constant, it must be at least linear. Thus we now turn our attention to forbidden families with a linear bound. We begin with a set of single configurations with a quadratic bound and determine which families of these configurations yield a linear bound. 3.1 Families of minimal quadratic configurations In our search for families with a linear bound, we first consider a list of minimal configurations with a quadratic bound, shown in Table 3.1. We use the word “minimal” for F with forb(m, F ) being Ω(m2 ) to indicate that for any F ≺ F and F = F , then forb(m, F ) is O(m). In a sense, these are the configurations “closest” to having a linear bound and thus seem like likely candidates for forming families with a linear bound. We hoped that the analysis of bounds would be more tractable with these minimal configurations and this expectation was correct. We will focus our attention on families of size 2 from Table 3.1. By our characterization of constant families through Theorem 2.1.1, we know that some of these families will immediately yield a constant bound; for example any family containing both F1 and F2 will have a constant bound as detailed in Section 2.3. Furthermore, by Corollary 2.1.2 we know that any family without a constant bound must be Ω(m). Thus, our goal is to show that for some of these non-constant families the upper 31 F1 F2 F3 F4 F5 F6 F7 F8 F9 Configuration 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 Bound Construction(s) Reference m 2 + m 1 + m 0 Ic × Ic [16] m 2 + m 1 + m 0 I ×I [16] I × Ic [3] Ic × Ic [20, 21, 23] m2 4 m 2 +m+1 + m 1 + m 0 m 2 + m 1 + m 0 m 2 + m 1 + m 0 m2 4 m 2 m 2 +m+1 + m 1 + m 0 + 2m − 1 Ic × Ic Ic × T T ×T I ×I I ×T T ×T [19] T ×T [1] I ×I [20, 21, 23] I ×T Ic × T [15] Table 3.1: Minimal Quadratic Configurations 32 [19] Pairs of configurations with a constant bound by Theorem 2.1.1. Pairs of configurations with an Ω(m2 ) construction. Pairs of configurations known to have bound Ω(m). {F1 , F2 }, {F2 , F5 }, {F1 , F4 }, {F4 , F6 }, {F5 , F9 }, {F1 , F3 }, {F2 , F7 }, {F3 , F6 }, {F4 , F7 }, {F8 , F9 } {F1 , F6 }, {F1 , F8 },{F2 , F4 }, {F4 , F6 }, {F5 , F8 } {F1 , F5 }, {F2 , F6 }, {F2 , F8 }, {F4 , F8 }, {F5 , F6 }, {F5 , F7 }, {F6 , F7 }, {F6 , F8 }, {F6 , F9 }, {F1 , F7 }, {F1 , F9 }, {F2 , F3 }, {F2 , F9 }, {F3 , F4 }, {F3 , F5 }, {F3 , F7 }, {F3 , F8 }, {F3 , F9 }, {F4 , F9 }, {F7 , F8 }, {F7 , F9 }, Table 3.2: Pairs of Minimal Quadratic Configurations bound is also linear. See row 1 of Table 3.2. Furthermore, we note that some families of the configurations in Table 3.1 will continue to have a quadratic bound. Any family of configurations that shares a construction from column 3 will be Ω(m2 ), and therefore not Θ(m). See row 2 of Table 3.2 Thus our method in examining families of the configurations in Table 3.1 was as follows: attempt to determine the upper bound for families which neither fall under our constant family classification, nor families where a quadratic product construction avoids all configurations in the family. Such families are listed in row 3 of Table 3.2. 3.1.1 Families proved using basic methods The first three considered families all contain the configuration F7 and have similar proofs. Proposition 3.1.1. We have forb(m, {F4 , F7 }) = forb(m, {F7 , F8 }) ≤ 2m. Proof. It suffices to show that forb(m, {F4 , F7 }) ≤ 2m. Let A ∈ Avoid(m, {F4 , F7 }). In a standard decomposition of A using row r, Cr must avoid I2 and 00 . To avoid I2 , the columns of Cr must be pairwise comparable (recall from Section 1.2.4), making them the columns of a triangular matrix. To avoid 00 , the columns of Cr must have a minimum column sum of m − 2 (note that Cr has m − 1 rows). Because there are only two columns in a triangular matrix with column sum greater than or equal to m − 2, there are only two possible columns in Cr . Thus Cr ≤ 2, and by standard 33 induction A ≤ 2m. A construction of I c will create a lower bound of m columns; we have not found a construction that shows the 2m upper bound to be tight. Proposition 3.1.2. We have forb(m, {F1 , F7 }) = forb(m, {F2 , F7 }) ≤ 2m. Proof. It suffices to show that forb(m, {F2 , F7 }) ≤ 2m. Let A ∈ Avoid(m, {F2 , F7 }). In a standard decomposition of A using row r, Cr must avoid I2 and [1 1]. To avoid I2 , the columns of Cr must be pairwise comparable, but to avoid [1 1] they must also be disjoint. The only possible choice for columns would be 0 and some non-zero column α, so Cr ≤ 2 and thus by standard induction A ≤ 2m. A construction of I c will create a lower bound of m columns; we have not found a construction that shows the 2m upper bound to be tight. Proposition 3.1.3. We have forb(m, {F3 , F7 }) ≤ 3m. Proof. Let A ∈ Avoid(m, {F3 , F7 }). In a standard decomposition of A using row r, Cr must avoid I2 and [0 0 1 1]. To avoid I2 , the columns of Cr must be pairwise comparable, thus columns of a triangular matrix. However since we are also avoiding [0 0 1 1] in Cr , this only allows for three columns in Cr . Thus Cr ≤ 3 and by standard induction A ≤ 3m. Any of I, I c or T will create a lower bound of m columns; we have not found a construction showing the 3m upper bound to be tight. The next proposition requires a graph theoretic argument to prove the bound. Proposition 3.1.4. We have forb(m, {F3 , F4 }) = forb(m, {F3 , F8 }) ≤ 3m + 1. Proof. It suffices to show that forb(m, {F3 , F8 }) ≤ 3m+1. Let A ∈ Avoid(m, {F3 , F8 }). The presence of F8 means that all columns in A have column sum at most two. There are m+1 possible columns of column sum 0 and 1. It remains to show that the number of columns of column sum 2 is bounded by 2m. Here we note that in our understanding of a (0, 1)-matrix as a list of incidence vectors for a hypergraph (see Section 1.2.1), columns of column sum 2 correspond to edges on a graph of m vertices. Our second configuration F3 is present when there are two vertices i, j, where the degree of i is at least 3, the degree of j is at least 3, there is an edge joining i, j, and there is an edge disjoint from i and j. Thus, edges from a vertex of large degree can only go to a vertex of degree less than 3, allowing 34 us to bound the number of edges on the graph (and thus the number of columns in A with column sum 2) by counting edges out of small degree vertices. Having selected i, j, it suffices to have more than 2(m − 1) edges to find an edge not going through i, j. Thus a bound of 2m + m + 1 = 3m + 1 suffices for forb(m, {F3 , F8 }). Proposition 3.1.5. We have forb(m, {F3 , F5 }) and forb(m, {F3 , F6 }) being O(m). Proof. It suffices to show forb(m, {F3 , F5 }) is O(m). Let A ∈ Avoid(m, {F3 , F5 }. Then applying our decomposition seen in (1.1), we deduce that Cr has no configurations [0 0 1 1] or I3 . Let R(r) denote a minimal set of rows of Cr such that Cr |R(r) is simple and in particular Cr = Cr |R(r) . We deduce that Cr |R(r) has no row of all 0’s nor a row of all 1’s nor a repeated row. Assume Cr |R(r) has at least 3 rows each of row sum 1. Then we deduce that I3 ≺ Cr |R(r) . Thus we deduce that some row s of Cr |R(r) have only one 0 and at least two 1’s. We then deduce that in A, we have at most one column containing rs 10 , else A has F3 . This works for every row r ∈ [m]. Consider a directed graph where for each row r we have a directed edge r → s in this case. We deduce that in the directed graph we have a directed cycle. Thus there are t rows a1 , a2 , . . . , at for which there is at most one ai 1 column containing ai+1 for i = 1, 2, . . . , t − 1 and at most one column containing 0 ak 1 . We now verify that apart from t columns, all columns of A|{a1 ,a2 ,...,at } are a1 0 either all 0’s or all 1’s. Thus we may delete the t − 1 rows a1 , a2 , . . . , at−1 and up to t columns and obtain a simple matrix. This yields the result by induction using forb(m, {F3 , F5 }) ≤ t + forb(m − t + 1, {F3 , F5 }). The proof of the bound for the following family uses a linear algebra reduction argument of Anstee and Fleming as seen in Section 1.4.3. Proposition 3.1.6. forb(m, {F1 , F3 }) = forb(m, {F2 , F3 }) ≤ 2m Proof. We take the case of {F1 , F3 }. Let A ∈ Avoid(m, {F1 , F3 }). In order to avoid F1 , on each pair of rows in A must contain at most one 00 while to avoid F3 , each pair of rows must have no 00 or no 11 or at most 1 10 . In the case where all pairs of rows have no 00 or no 11 , then the result follows from Theorem 1.3.1. In the case where a pair of rows has only one 10 and therefore, only one of 00 , we have that every pair of rows has two columns in short supply. By the result of Anstee and 35 Fleming (Theorem 1.4.1), we can find O(m) columns to delete so that the resulting matrix has an absent column on each pair of rows. The resulting matrix has no K2 and hance O(m) columns by Theorem 1.3.1. Thus A has O(m) columns. 3.1.2 Families proved using a structure argument The results for several of our families taken from Table 3.1 use a result of Frankl, F¨ uredi, and Pach [15]. The result is as follows: if a matrix A avoids F9 , all columns of A with column sum i will have a particular structure. Let A ∈ Avoid(m, F9 ). Consider the columns of column sum i, labeled in (3.1) as Ti or Si . Then the following structure must exist on these columns: Ai Bi Ci 1 0 .. . Ti 0 ... 1 ... .. . . . . 0 0 .. . 0 0 ... 1 1 1 ... .. . 1 .. . 1 1 ... 1 0 0 ... .. . 0 .. . Ai Bi Ci or 0 0 ... 0 0 1 .. . Si 1 ... 0 ... .. . . . . 1 1 .. . 1 1 ... 0 1 1 ... .. . 1 .. . 1 1 ... 1 0 0 ... .. . 0 .. . (3.1) 0 0 ... 0 Note that for the columns of Ti , |Bi | = i − 1 and for Si , |Bi | = i − (|Ai | − 1). Also Ti = |Ai | and Si = |Ai |. We will use this structure and its properties in the proofs that follow. Proposition 3.1.7. We have forb(m, {F5 , F6 , F9 }) ≤ 2m. Proof. Let A ∈ Avoid(m, {F5 , F6 , F9 }). We sort the columns of A by column sum. Because A avoids F9 , each set of columns with column sum i will have the structure shown in (3.1). However, because A must also avoid F5 and F6 , the maximum number of columns of any column sum i must be less than 3 (otherwise there will be an F5 or F6 on the rows Ai ). Thus the upper bound bound on A is 2m. Proposition 3.1.8. We have forb(m, {F1 , F9 }) = forb(m, {F2 , F9 }) = 2m + 1. 36 Proof. It suffices to show forb(m, {F1 , F9 }) = 2m + 1. Let A ∈ Avoid(m, {F1 , F9 }). We sort the columns of A by column sum, and because A avoids F9 , each set of columns with column sum i will have the structure shown in (3.1). Any matrix formed by two columns of sum at most m − 3 will either contain F1 or F9 or both. So consider the columns of sum m − 2, m − 1 and m. The maximum number of columns occurs with structure Sm−2 , with |Am−2 | = m − 1, structure Sm−1 with |Am−1 | = m and 1m , yielding 2m columns. If we use these columns then we can add precisely one column of smaller sum, namely the column with a single 1 in row m, without creating either F1 or F9 . Thus forb(m, {F1 , F9 }) = 2m + 1. Proposition 3.1.9. We have forb(m, {F4 , F9 }) = forb(m, {F8 , F9 }) = 2m. Proof. It suffices to show that forb(m, {F4 , F9 }) = 2m. Let A ∈ Avoid(m, {F4 , F9 }). We sort the columns of A by column sum, and because A avoids F9 , each set of columns with column sum i will have the structure shown in (3.1). However, we also know that A cannot contain F4 and thus it must have column sum of m − 2 or greater on all columns. This means we can have the columns of sum m − 2, m − 1 in the two types of structures Si and Ti and in fact, we can take Sm−2 with |Am−2 | = m − 1, the structure Sm−1 with |Am−1 | = m and the column 1m , yielding 2m columns total. Proposition 3.1.10. We have forb(m, {F7 , F9 }) is O(m). Proof. Let A ∈ Avoid(m, {F7 , F9 }). Let AT denote the columns where columns of sum i form the structure Ti from (3.1) and let AS denote the columns where columns of sum i form the structure Si . Then A ≤ 2m + AT + AS , where there at most 2 columns of column sum i not in AT or AS . It suffices to show that AT ≤ 2m; we will then know AS ≤ 2m by taking (0, 1)-complements, as F7c is F7 and F9c is F9 . Note that for all i where columns of sum i are in AT , Ti is bounded by the number of rows containing the identity, or |Ai |. Thus, in order to show that forb(m, {F7 , F9 }) is O(m), it suffices to show that |Ai | is O(m). If Ai ∩ Aj = ∅ for all pairs i, j then i |Ai | = m and we are done. Now suppose there are i, j column sums with i > j such that Ai ∩ Aj = ∅. Then |Ai ∩ Aj | < 2. Suppose not. Then there are two rows in Ai ∩ Aj that contain [I2 |I2 ] on the columns of sum i and j. Furthermore, because i > j, |Bi | > |Bj |, so there is some row b ∈ Bi , b ∈ Bj . Therefore b must be all 1 s in the columns of column sum i and mostly 0’s in 37 the columns of column sum j. Combining row b with the rows in the intersection of Ai ∩ Aj , we create F7 , a contradiction. So |Ai ∩ Aj | = 1. We now consider Bi , Bj where |Bi | > |Bj |. If Bj \Bi = ∅ then Bi \Bj = ∅. We find a copy of F7 on rows p, q, r where p = Ai ∩ Aj , q ∈ Bj \Bi and r ∈ Bi \Bj . So we may assume Bj ⊂ Bi . Among the column sums of type T , choose three with i > j > k and we may assume i is the largest column sum. Assume Ai ∩ Aj = {a}, (a row index) and Ai ∩ Ak = {b}. If a = b, then for some c ∈ Bi \Bj , we find a copy of F7 on the rows a, b, c. Recall that Bk ⊂ Bj ⊂ Bi and so such a c c can be chosen. Choosing two columns of sum i that have an I2 on rows a and b, one column of sum j with a 1 in row a (and necessarily a 0 in row b) and one column of sum k with a 1 in row b, will generate an F7 on rows a, b, c. So we may assume a = b. With these properties in hand for AT we now prove that AT ≤ 2m by induction on m. In particular the sets At for t of type T , have the properties that |Ai | ≥ 3 and |Ai ∩ Aj | ≤ 1. They can be ordered by the index i so that if we have three indices i > j > k and Ai ∩ Aj = {a} and Ai ∩ Ak = {b}, then a = b. By choosing the largest index i we reduce the family by eliminating Ai and the remaining sets are on the elements [m]\(Ai \a) have the same properties so we can apply induction. Thus t |At | = |Ai | + 2(m − |Ai | + 1) ≤ 2m. Theorem 3.1.11. We have that forb(m, {F3 , F9 }) is O(m). Proof. We establish that forb(m, {F3 , F9 }) ≤ 12m. Let A ∈ Avoid(m, {F3 , F9 }). Let AT denote the columns where columns of sum i form the structure Ti from (3.1) and let AS denote the columns where columns of sum i form the structure Si . Then A ≤ 2m + AT + AS , where there at most 2 columns of column sum i not in AT or AS . We will show AT ≤ 5m and then we deduce AS ≤ 5m by taking (0,1)-complements (we note that F3c is F3 and F9c = F9 as configurations). This yields the bound. We have that AT = i |Ai | where the sum is only over those i for which AT has columns of sum i. We note that for i < j, we cannot have |Bi \Bj | ≥ 2. Else let p, q ∈ Bi \Bj . Then since |Aj | ≥ 3, there is always a column β of sum j with 0’s in rows p, q. Now a column α of sum i has 1’s in rows p, q. We deduce that [α β] has F9 . Thus for i < j, we have |Bi \Bj | ≤ 1. Now assume i |Ai | ≥ 5m. Then there is a quintuple i1 < i2 < i3 < i4 < i5 38 with some row r ∈ Ai1 ∩ Ai2 ∩ Ai3 ∩ Ai4 ∩ Ai5 . We will consider i1 , i3 , i5 . We have |Bi3 | ≤ |Bi5 | − 2 and so let s, t ∈ Bi5 \Bi3 . Now |Bi1 | ≤ |Bi3 | − 2 and yet |Bi1 \Bi3 | ≤ 1. Thus without loss of generality we may assume s ∈ Bi1 . We now claim that we have F3 in rows r, s. In the columns of sum i5 with r ∈ Ai5 and s ∈ Bi5 we find r 0 0 1 . s 1 1 1 Now in both the columns of sum i1 and also in columns of sum i3 , we may find r 0 1 , s 0 0 using the fact that i1 ∈ / Bi1 and i3 ∈ Bi3 . This yields a copy of F3 and so we may deduce i |Ai | ≤ 5m which completes our proof. 3.2 Other linear results Based on a result of Balogh, Keevash and Sudakov, we have the following theorem: Theorem 3.2.1. [10] Let k ≥ 2 be given. Then forb(m, {Ik , Tk }) is Θ(mk−2 ) From this theorem we can conclude the following. Corollary 3.2.2. We have that forb(m, {I3 , T3 }) is O(m). Note that Conjecture 1.3.5 states that for single configurations, if forb(m, F ) is Θ(mk ), then there is a construction that avoids F consisting of a k-fold product of three matrices: I, I c and T . Thus, if this conjecture were true for forbidden families, if a family of configurations was contained in all possible two-fold products of I, I c and T , then its bound would have to be linear. The conjecture remains unproven (and likely requires a different statement for forbidden families - see Chapter 4), but its statement suggests which forbidden families would likely have a linear upper bound, a bound which must then must be proved. 39 Chapter 4 Families With a Super-linear Bound The first section of this chapter will contain a proof that refines a previous result, showing that a certain family of matrices defined as the product of 2 × 2 matrices has a bound of Θ(m3/2 ). In the second section of the chapter we will present another family of matrices, also obtained by taking the product of small 2-rowed matrices. We conjecture that this family has the same Θ(m3/2 ) bound and present the outline for a possible proof. 4.1 4.1.1 Unexpected bound for product configurations Introduction Conjecture 1.3.5 implies that for a single forbidden configuration, the power of m in the asymptotic bound is an integer. A logical question might be whether a similar (or even the same) conjecture applies to the asymptotic bound of forbidden families. However when considering a family of two configurations, Anstee and Sali found a bound of Θ(m3/2 ). The general idea is as follows. Let ex(m, H) is the maximum number of edges in a (simple) graph G on m vertices that has no subgraph H. A ∈ Avoid(m, 13 ) will be a matrix with up to m+1 columns of sum 0 or sum 1 plus columns of sum 2 which can be viewed as the vertex-edge incidence matrix of a graph. Assume p = |V (H)| and q = |E(H)|. Let I(H) denote the p × q vertex-edge incidence matrix associated with H. 40 Remark 4.1.1. forb(m, {13 , I(H)}) = m + 1 + ex(m, H). We first encountered this with I2 × I2 which is I(C4 ), the vertex-edge incidence matrix of the cycle of length 4. Theorem 4.1.2. [1] forb(m, {13 , C4 }) = m + 1 + ex(m, I(C4 )) which is Θ(m3/2 ). However we explored the result from the point of view of I2 × I2 and various product constructions. This resulted in the statement and proof of Theorem 1.3.14. The matrices used in Theorem 1.3.14 are the products of a small identity matrix and a small triangular matrix as follows: I2 = I2 × I2 = 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 , , T2 = T2 × T2 = 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 , , I2 × T2 = 1 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 . A preliminary version of [7] contained Theorem 1.3.14, which proved that forb(m, {I2 × I2 , T2 × T2 , I2 × T2 }) is Θ(m3/2 ). However, a closer examination of this family revealed that while there are Ω(m2 ) constructions for the families {I2 × I2 , I2 × T2 } and {T2 × T2 , I2 × T2 }, the best construction that could be achieved for the family {I2 × I2 , T2 × T2 } was Ω(m3/2 ). This led to the conjecture of the theorem that follows, which we were able to prove by extending the result of Anstee, Raggi and Sali for F = {I2 × I2 , T2 × T2 , I2 × T2 }. 4.1.2 Theorem and proof Theorem 4.1.3. We have forb(m, {I2 × I2 , T2 × T2 }) is Θ(m3/2 ). Before we proceed to the main body of the proof, we will make a few remarks and present three lemmas. The proof will use a standard induction argument (recall from Section 1.4.1). Given our two forbidden configurations I2 × I2 and T2 × T2 , when performing the 41 standard decomposition using any row r in A, then Cr cannot contain the following inductive children: 1 1 F1 = 1 0 , 1 1 1 0 1 0 F2 = 0 1 0 1 . 1 1 0 0 Configuration F1 in Cr will produce T2 × T2 and configuration F2 in Cr will produce I2 × I2 . Lemma 4.1.4. We have f orb(m, {F1 , F2 }) ≤ 2m. Proof. Let A ∈ Avoid(m, {F1 , F2 }) be a simple matrix. We proceed by standard induction. In order to avoid F2 , the columns of C must avoid its inductive child, I2 . This implies that the columns of C must be pairwise comparable (recall the definitions of Section 1.2.4), creating a tower matrix. By definition, C is simple so all the columns must be unique. If C ≥ 3, there will be an F1 contained in two of the columns. Thus C ≤ 2, and by induction A has at most 2m columns. It is worth nothing that in order to achieve the bound of C = 2 in the previous proof, it is necessary for the columns in C to be the column of 0’s and a column of sum 1. Of course, there may be only one of these columns present, but for our purposes there must be at least one, as a further restriction will preclude that C is empty. Definition 4.1.5. Let A, r, be given with the decomposition (1.1). If there is a row r in a subset of rows S ⊆ [m] such that r can be deleted and simplicity maintained in Cr |S\r , then we call r deletable. Definition 4.1.6. Let A, r, be given with the decomposition (1.1). We define R(r) ∈ [m] to be a minimal set of rows with the property that Cr |R(r) is simple, with no deletable rows. We use the previous lemma to prove the following lemma about the size of R(r). Lemma 4.1.7. Let A, r, be given with the decomposition (1.1). Given R(r) as described in Definition 4.1.6, we have that |R(r)| ≥ Cr /2. 42 Proof. Consider the matrix Cr |R(r) . Note that Cr |R(r) = Cr . We know that Cr |R(r) must avoid {F1 , F2 } (because Cr avoids {F1 , F2 }) and so by Lemma 4.1.4, Cr |R(r) ≤ 2|R(r)|, which becomes |R(r)| ≥ Cr /2, as desired. Lemma 4.1.8. Let A, r, be given with the decomposition (1.1). Given R(r) as described in Definition 4.1.6, we can choose a set of rows S(r) ⊆ R(r) such that Cr |S(r) contains I|S(r)| and |S(r)| ≥ |R(r)|/2. Proof. We choose R(r) as described for the proof of Lemma 4.1.7. Let s ∈ R(r) and perform the standard decomposition of Cr |R(r) using row s into Es , Gs , and Hs ; see (4.1) Cr |R(r) = s R(r) \ s 0...0 1...1 Es Gs Gs Hs . (4.1) This scenario is analogous to the situation in Lemma 4.1.4, with Cr |R(r) as A , Es as B , Gs as C and Hs as D . Therefore, as seen in the proof of Lemma 4.1.4, Gs is restricted to at most two columns, in fact, a column of sum 0, a column of sum 1 or both. Furthermore, in our case, with Cr restricted to the rows R(r), Gs cannot be empty. Otherwise s could be deleted while preserving the simplicity of Cr |R(r) , a contradiction to how we chose R(r). Thus, in the matrix Cr |R(r) , each row s ∈ R(r) is associated with one or both of the following column types: Case 1. There is a a zero column in Gs , which yields a column of sum 1 in Cr |R(r) with its 1 in row s. Case 2. There is a column of sum 1 in Gs , which yields a column of column sum 2 with 1’s in rows s and some row t and a column of column sum 1 with a 1 in row t. To choose our set S(r) ⊆ R(r), with I|S(r)| ≺ Cr |S(r) and |S(r)| ≥ |R(r)|/2, we will generate a directed graph on the rows of R(r) and then use properties of the graph to choose an appropriate S(r). We define D to be a directed graph, where there is an directed edge from vertex s → t if in the decomposition of Cr |R(r) based on row s, Case 2 occurs. We define the set T as the set of all rows t ∈ R(r) such that Cr |R(r) has a column of column sum 1 with a 1 in row t. Let U = R(r) \ T . For each edge u ∈ U , there is an edge u → v, where, by our choice of T , v ∈ T . Let V be a subset of T such that each vertex in V has an associated u-vertex in U , i.e. let V = {v ∈ T : there is a u ∈ U with u → v}. Finally, we define S(r) = U ∪ (T \ V ). In words, we have chosen a subset of rows in R(r), where each row is associated with 43 a column of sum 2 (U ), but the row containing the second 1 (V ) has been omitted. We have also included some extra rows associated with columns of column sum 1 that are distinct from the columns associated with this first set (T \ V ). Thus each row in S(r) is associated with a distinct column of column sum 1 and so Cr |S(r) contains an I|S(r)| , potentially with some extra or repeated columns. We can confirm that |S(r)| ≥ |R(r)|/2 by noting that in fact S(r) = U ∪ (T \ V ) = R(r) \ V , so |S(r)| = |R(r)| − |V |, and as |V | ≤ |U |, this gives |S(r)| ≥ |R(r)|/2. With these lemmas proved, we can now proceed with proof of Theorem 4.1.3. Proof of Theorem 4.1.3. By a previous result of Anstee, Raggi and Sali, we know that forb(m, {I2 × I2 , I2 × T2 , T2 × T2 }) is Θ(m3/2 ). The construction that achieves this bound is as follows. For each p a prime power, there is known to exist a projective plane of order p 2 +p+1] which consists of p2 + p + 1 subsets each in [p p+1 such that for any two subsets L1 , L2 , we have |L1 ∩L2 | = 1 and for each pair of elements a, b there is a unique subset La,b containing both. A major open problem is whether there exist projective planes of non-prime power order but we do not concern ourselves with that question. It is natural to think of elements as points and subsets as lines. The resulting (p2 + p + 1) × (p2 + p + 1) element-set incidence matrix has (p + 1)(p2 + p + 1) 1’s and no 2 × 2 submatrix of four 1’s. We may create a 2(p2 + p + 1) × (p + 1)(p2 + p + 1) simple matrix so that for each pair of a element/point a and subset/line L with a ∈ L, we have a column with a 1 in row a and a 1 in row p2 + p + 1 + L. We verify that the resulting matrix has no I2 × I2 nor T2 × T2 and that the number of columns (p + 1)(p2 + p + 1) is Θ((2(p2 + p + 1))3/2 ). We can pad this matrix with rows of 0’s to obtain a matrix of order m with Θ(m3/2 ) columns. Because the construction for this bound avoids {I2 × I2 , I2 × T2 , T2 × T2 }, it also avoids the family of our theorem {I2 × I2 , T2 × T2 }. Thus forb(m, {I2 × I2 , T2 × T2 }) is Ω(m3/2 ). It remains to show that the bound is tight, i.e., that forb(m, {I2 ×I2 , T2 ×T2 }) is O(m3/2 ). If we perform the standard decomposition on A, we would be done by induction if we could show that Cr ≤ cm1/2 for some row r and some constant c. For this proof, we will use c = 20. We will assume Cr ≥ 20m1/2 for all r and arrive at a contradiction as follows: we will show that we can associate matrix Cr with a set of rows S(r) where |S(r)| ≥ Cr /4. Then we show that we can choose a set Q ⊆ S(r) 44 with |Q(r)| ≥ |S(r)|/3 such that for every choice rp , rq ∈ Q we have |S(rp )∩S(rq )| ≤ 5. Thus for t = 5/3m1/2 choices r1 , r2 , . . . , rt ∈ S(r) we show that |S(ri ) ∩ S(rj )| < 6 and so obtain disjoint sets of rows S(r1 ), S(r2 )\S(r1 ), S(r3 )\(S(r1 ) ∪ S(r2 )), . . . S(rt )\(S(r1 ) ∪ S(r2 ) ∪ · · · ∪ S(rt−1 )). If we sum the size of these disjoint sets of rows, we get: 5m1/2 + (5m1/2 − 5) + (5m1/2 − 10) + · · · + (5m1/2 − 5(t − 1)) > m a contradiction given that we have m rows. Let r be a row in A so Cr > 20m1/2 . We first choose a set of rows R(r) ⊆ [m] as described in Definition 4.1.6. By Lemma 4.1.7 we know that |R(r)| ≥ Cr /2. We continue by choosing a set of row S(r) ⊂ R(r) as described in Lemma 4.1.8; again, we know that |S(r)| ≤ |R(r)|/2, thus |S(r)| ≥ Cr /4, and by our choice of S(r), we know that Cr |S(r) contains an I|S(r)| . We now focus our attention on the matrix A|S(r) . In particular, if we perform the standard decomposition on A using a row rj ∈ S(r), we wish to know what happens on the columns of Crj |S(r)\rj . Let rj ∈ S(r). Perform the standard decomposition using rj on the original matrix A and then restrict to the rows in S(r) ∪ r. In the decomposition, the columns of Crj |S(r) must correspond to columns of A which appear with a 1 and 0 in row rj and are the same elsewhere, in particular, on the rows r ∪ (S(r) \ rj ). We thus have columns in Crj as follows: rj 0 1 (4.2) S(r) \ rj α α . r a a We now consider A|S(r) in this arrangement. We will extract two conclusions from the structure in (4.2), first from the case where a = 0 and second from the case where a = 1. We begin with the case where a = 0. Note that since a = 0 is in row r, the columns of Crj with this feature correspond to columns in [Br Cr ] in the original decomposition (1.1), and thus, by Lemma 4.1.10, these columns are laminar. Returning to the decomposition based on rj , as shown in (4.2); suppose there exist 45 two non-zero choices for α, say β = γ. We have the following situation for columns in Crj : rj 0 0 1 1 S(r)\rj { β γ β γ . r 0 0 0 0 (4.3) We know that on the rows S(r), the columns from (4.3) must form a laminar family, as they have a zero in row r and are thus in [Br Cr ]|S(r) . Columns 3 and 4 have 1’s in common on row rj and we deduce without loss of generality that β ≤ γ and β = γ. Now, considering columns 2, 3, and the fact that 0 = β, we violate the nested family property of laminar families, a contradiction. Thus there is only one non-zero choice for α in Crj when a = 0. Furthermore, if α is repeated, it must have column sum 1. If α has column sum greater than 1 and it is repeated, it creates a T2 × T2 . This happens because A is a simple matrix and so on some row r the columns of Crj must differ, yielding the following, with T2 × T2 on the first three rows plus row r . rj S(r) \ rj r 0 1 1 α 0 0 1 1 α 1 1 1 1 α 0 1 1 1 α 1 . We prove a slightly different result when a = 1. This case will be simpler since the fact that a = 1 will automatically yield a row of ones on row r, naturally generating a row of T2 × T2 . We will show that the columns in Crj must be disjoint on the rows S(r) \ rj . Suppose there are two non-zero columns β, γ in Crj |S(r)\rj . rj 0 1 0 1 S(r)\rj { β β γ γ . r 1 1 1 1 Now suppose β and γ both have entry 1 on some row r ∈ S(r) \ rj . Also, like above, because A is a simple matrix, there is some row r (r = r, r , rj ) where the 46 columns of Crj differ. The situation is then as follows: rj r S(r) \ (rj ∪ r ) r r 0 1 β 0 1 0 1 1 1 γ β 1 0 1 1 1 1 γ 1 1 . This creates a T2 × T2 , therefore all of our non-zero columns α in Crj |S(r)\rj , with 1’s in row r cannot have a 1 entry on the same row. Thus we have shown that for any column in Crp |S(r) , where rp ∈ S(r), there are two results. If the entry of a column in row r is 0, then those columns can be 0 or a single non-zero column α: if α is of size 1 it may be repeated, otherwise there is only one copy. If the entry of a column in row r is 1, the columns of Crp |S(r) must be disjoint. We now use these facts to consider what occurs in the rows of Crp |S(r)\rp (denoted X below). On the columns of Crp with a 0 in row r, we have two cases for the rows of S(r)\rj . If α is of size 1 and repeated, there will be one “bad” row, say rs ∈ S(r) \ rp , that contains multiple ones in these columns. The remaining rows will contain all zeroes on these columns. In the other case, if the non-zero α is of size greater than 1 and therefore not repeated, all rows in S(r) \ rp will have at most one 1. Thus for all rows in S(r) \ rp with the exception of the previously described “bad” row, the remaining rows will have at most one 1 on the columns of Crp . On the columns of Crp with a 1 in row r, the rows of S(r) \ rj will contain only one 1 each. We can now show that once we choose rp ∈ S(r) for all but one rq ∈ S(r) \ rp , |S(rp ) ∩ S(rq )| < 6. We decompose the matrix A based on row rp ∈ S(r): Crp Crp 0T 1T X X rp S(r) \ rp . We choose rp and rq so that neither is a “bad” row for the other. By Lemma 4.1.9 we know that we can choose at least a third of the rows from S(r) such that each row rq is not a “bad” row for all other rows chosen. We decompose A first using rp and 47 then using rq . rp rq S(rp ) ∩ S(rq ) Crp Crp 1 0 T β βT , I I rp rq S(rp ) ∩ S(rq ) Crq Crq γT γT 1 0 . I I Note that by our choice of rp and rq , β T and γ T contain at most two 1’s each and therefore must be mostly 0’s. We consider the columns in Crp that have entry 0 in row rq . By our assumption about the size of S(rp ) ∩ S(rq ), we know these columns must contain an I2 , underneath 1’s in row rp and 0’s in rq . We now consider the same columns in Crq . We can find at least two columns with 0 in row rp and 1 in rq , containing an I2 underneath. Furthermore, these two pairs of columns are distinct, as they have different entries on rp and rq . When put together they create an I2 × I2 . Therefore |S(rp ) ∩ S(rq )| ≤ 5. We finally generate the series of disjoint sets described at the beginning of this proof and arrive at our contradiction. Lemma 4.1.9. Given a row p ∈ R(r), we say row q ∈ R(r) \ p is a bad row for row p is there is more than one column of Cp with a 0 in row r and a 1 in row q. Assume for each row r ∈ (s(r) there is at most one bad row s ∈ S(r). Then there is a set of rows Q ⊆ S(r) such that |Q| ≥ |S(r)|/3 and for any pair of rows rp , rq ∈ Q, we have rp and rq are not bad rows for each other. Proof. We will interpret this question as a graph theory problem. We create a graph with |S(r)| vertices and assign each row of S(r) to a vertex. We assign a directed edge to two vertices (ri , rj ) if rj is a “bad” row for ri . Because for each edge/row ri there can only be one “bad” row rj , the out-degree of any vertex vi is at most one. A set of rows that has our desired property is equivalent to choosing an independent set on our graph. We can choose an independent set by coloring the graph-each color will correspond to an independent set of vertices. We will show that we can three-color our graph. We use induction on the number of vertices. Suppose there exists a v ∈ V such that v has in-degree 0. Let G be the induced subgraph of G \ v . Directed graph G maintains our property of maximum out-degree 1, so we color G with 3 colors and then add v back with an appropriate color. Suppose there is no vertex v ∈ V with in-degree 0. In this case all vertices 48 have in-degree 1 and out-degree 1, and so the edges of G form the union of disjoint cycles, which we can color with 3 colors. Since each color corresponds to an independent set, we can choose an independent set that is at least a third of the remaining rows. Lemma 4.1.10. Assume we have obtained S(r) as described in Lemma 4.1.8. Then on all triples of rows in S(r), the columns in [Br Cr ] must form a laminar family. Proof. Recall our description of the “what is missing” method in Section 1.4.2. Using a computer program written in C++ by Miguel Raggi (download at http://www.math.ubc.ca/∼anstee/FConfThesisVersion.tar.gz) we are able to compute what is missing on any quadruple of rows in A in order to avoid I2 × I2 and T2 × T2 . There are five possibilities, and on any quadruple of rows in A, one must apply. no 0 Q0 = 1 0 1 no 0 0 1 1 no 1 1, 1 1 no 1 Q2 = 1 1 0 no 0 1 0 1 no 0 0 1 1 no 1 Q4 = 1 0 0 no 0 Q1 = 1 0 1 no 1 0, 1 1 no 1 0 1 0 no 1 1 0 1 no 0 0 1 1 no 1 0 1 1 no 0 1, 1 1 no 1 Q3 = 1 1 0 no 1 0 0 1 no 0 1 0 1 no 0 0, 1 1 no 0 1 1 0 no 1 0 0 1 no 0 1 0 1 no 0 0. 1 1 When we perform the standard decomposition of A based on row r and consider a quadruple of rows r, i, j, k, we can determine what is missing in Cr on the triple of rows i, j, k. We would be able to delete rows from Cr and preserve simplicity if we find a copy of “K2 ” in what is missing. That is, if on the triple i, j, k, there is a pair 49 of rows i, j with all 4 columns of K2 appearing as follows: no no no no i 0 0 1 1 j 0 1 0 1 k a b c d where a, b, c, d ∈ {0, 1}, then we could delete row k from Cr and preserve simplicity, a contradiction. The reason for this is that on the three rows i, j, k, the only columns possibly present would be i 0 j 0 a k 0 1 b 1 0 c 1 1 d where x denotes the (0,1)-complement of x. We can see that deleting row k will not result in repeated columns assuming Cr has no repeated columns. We note that Q3 and Q4 both have the property that if any row is deleted, there will be a K2 contained on two of the remaining three rows and so we can ignore the cases represented by Q3 and Q4 . In the remaining cases to avoid leaving a K2 after deleting a row we must delete a certain row(s) from a quadruple. We note that Q2 has K2 on rows 1 and 2 and so to avoid leaving a copy of K2 row r must either be row 1 or row 2 of such quadruples. Similarly, r must be row 1 of Q1 and could be any row of Q0 . We use Pi to denote a triple arising from the quadruple Qi in these ways. no no no no no no 1 0 0 0 1 1 P0 = or or 0 1 1 0 1 1 1 1 1 1 1 1 no no no no no no 0 0 1 0 0 1 or 1 0 1 1 0 1 1 1 1 0 1 1 50 no no no no no no no no no no no 1 1 0 0 1 1 1 0 1 0 1 P1 = P2 = or . 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 These then, are the possibilities for what is missing in A, including A|S(r) . Because we know that the columns of A contain an identity matrix on the rows S(r) we know that the final three cases of P0 and the second set of case of P2 can not be what is missing on for A|S(r) . Among the remaining options for what is missing (the first case for P0 , P1 and P2 ), by looking at Q0 , Q1 and Q2 , we see that below the zeroes in row r, each triple of rows in S(r) is missing two columns of sum 2. This means that on all triples of rows in S(r), the columns in [Br Cr ] must form a laminar family. 4.2 A similar bound for larger product configurations Extending the previous result, we considered another family of configurations formed by the product of small matrices. As before, these small matrices were taken from the three matrices of Theorem 1.3.6 and Conjecture 1.3.5, I, I c , and T . In this case, we used the following three configurations: E1 = 0 1 0 0 0 1 , E2 = 0 1 1 0 0 1 , E3 = 1 1 0 1 0 1 . Note that E1 ≺ I3 , E2 ≺ T3 and E3 ≺ I3c . We then forbid all possible products of these sub-configurations, namely the family {E1 ×E1 , E1 ×E2 , E1 ×E3 , E2 ×E2 , E2 ×E3 , E3 ×E3 }. If only five of these products are forbidden, there is a product construction of size Ω(m2 ) that avoids the five included matrices. However, when all six are forbidden, the best lower bound is Ω(m3/2 ) from a construction of Anstee, Raggi and Sali [7]. This leads us to the following conjecture: Conjecture 4.2.1. Given the family F = {Ei ×Ej : i, j = 1, 2, 3} we have forb(m, F) 51 is Θ(m3/2 ). The lower bound has already been given, thus the main goal is to establish the upper bound that forb(m, F) is O(m3/2 ). We here outline some steps of a potential proof that we were unable to complete. The argument will proceed by induction. Let A ∈ Avoid(m, F). Then using the decomposition shown in (1.1), Cr cannot contain the following inductive children of our family: 0 0 0 1 1 1 F1 = 0 1 0 0 1 0 , 0 0 1 0 0 1 0 0 F3 = 1 1 1 0 0 0 0 1 1 1 F2 = 0 1 1 0 1 1 , 0 0 1 0 0 1 0 1 1 1 0 1 1 0 . 1 1 0 1 Similarly to the last proof, we have two lemmas relating to the inductive children and rows of A. Lemma 4.2.2. We have f orb(m, {F1 , F2 , F3 }) ≤ 2m. Proof. Let A ∈ Avoid(m, {F1 , F2 , F3 }) be a simple matrix. We proceed by standard induction. In order to avoid {F1 , F2 , F3 }, the columns of C must avoid the subconfigurations E1 , E2 and E3 . But because E1 ≺ I3 , E2 ≺ T3 and E3 ≺ I3c , by Lemma 1.3.20, C must be constant. A simple pigeonhole argument proves that C ≤ 2. Using Definition 4.1.6 as in the previous proof, we define R(r) ∈ [m] to be a minimal set of rows with the property that Cr |R(r) is simple, with no deletable rows. The result of Lemma 4.1.7 again applies to |R(r)|, so |R(r)| ≥ Cr /2. Similarly to the previous proof, we want to show that for all r, Cr is O(m1/2 ), which yields an upper bound of O(m3/2 ) for the matrix A by induction. We will attempt to do so by contradiction: assume that for all r that Cr is Ω(m1/2 ) and then choose a subset of the rows in such a way that we arrive at a contradiction regarding the number of rows. We now need to show that there exists some constant c (say c = 1/3) and some S(r) ⊆ R(r) such that |S(r)| ≥ c|R(r)| and Cr |S(r) contains either a I|S(r)| , T|S(r)| , or 52 c I|S(r)| . Such a statement would parallel the statement of Lemma 4.1.8. This is the primary missing element of the proof. If such a statement could be proved, the rest of the proof would proceed as follows. Supposing we can choose this S(r) for all rows r ∈ [m], there must be at least a third of the rows in [m] such that S(r) contains I|S(r)| , a third of rows such that c S(r) contains T|S(r)| , or a third of rows in S(r) contain I|S(r)| . Thus without loss of generality, we can choose a set Q(r) ⊂ [m] of size Θ(m1/2 ) such that for all r ∈ Q(r) Cr |S(r) contains a I|S(r)| . We now consider the standard decomposition of A based on rows rp , rq ∈ Q(r). Suppose |S(rp ) ∩ S(rq )| ≥ 5. If we decompose A based on rp (and then rq ), we have the following: Crp 00 . . . . . . 00 0...0 1...1 I I rp rq S(rp ) ∩ S(rq ) Crp 11 . . . . . . 11 0...0 1...1 . I I Using our assumption about |S(rp ) ∩ S(rq )|, and the pigeonhole principle, we can assume that one of the two following configurations will occur in the above decomposition: 0 0 1 0 0 0 0 0 1 0 rp rq S(rp ) ∩ S(rq ) 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 1 1 1 or 1 0 S(rp ) ∩ S(rq ) S(rp ) ∩ S(rq ) 0 1 0 0 (4.4) We now consider a decomposition again using rp and rq ; however, this time the decomposition begins with rq . rp rq rp rq Crq 0...0 1...1 00 . . . . . . 00 I I 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 Crq 0...0 1...1 11 . . . . . . 11 . I I Note that the columns of Crq with a 1 in row rq will be disjoint from the columns 53 1 1 0 0 1 . of the first configuration in (4.4) and the columns of Crq will be disjoint from the columns of the second configuration in (4.4). Now the columns of Crq with a 1 in row rq will be forced to contain one of the following configurations: rp rq S(rp ) ∩ S(rq ) 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 rp rq or S(rp ) ∩ S(rq ) 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 . (4.5) These configurations are both disjoint from the first configuration in (4.4) and thus, taken together, produce either an E1 ×E1 in the first case or E1 ×E2 in the second case. If we consider the cases of (4.5) with 0’s in row rq (one of which must occur), these will be disjoint from the 2nd case listed above, and again, taken together, produce a E1 × E2 or an E1 × E3 . In each case the E1 occurs in the rows of S(rp ) ∩ S(rq ) and the other matrix of the product occurs in rp ∪ rq . Thus |S(rp ) ∩ S(rq )| ≤ 4. Finally, we consider the following sequence of sets. We assume that |S(r)| > Km1/2 for some suitably large K. For all ri ∈ S(r), we form disjoint sets S (ri ) as follows: i−1 S (ri ) = S(ri ) \ S(rj ). j=1 Note that S (ri ), S (rj ) are disjoint for all ri , rj ∈ Q(r). We then consider the size of these sets: |S (r1 )| + |S (r2 )| + |S (r3 )| + · · · + |S (rt )|, where t = m1/2 . This sum size of these sets is thus: Km1/2 + (Km1/2 − 4) + (Km1/2 − 8) + . . . which is greater than m for K suitably large, a contradiction. 54 Chapter 5 A Case Study: Families of 2 x 2 Configurations When first investigating families of forbidden configurations, we chose to take the set of all seven 2 × 2 configurations (described and indexed in Table 5.1) and find forb(m, F) for all 27 − 1 non-trivial families of these configurations, with the goal of using these families as case studies for other families with larger configurations. F1 F2 F3 F4 F5 F6 F7 Configuration 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 Bound m 2 m 2 Construction Contained in c c Im × Im I4 , T4 m+1 c [Im |1] I3 , T3 m+2 c [Im |0|1] or [Im |0|1] T3 m+1 c [Im |0] or [Im |1] T3 m+1 [Tm |0] I2 , I2c m+1 [Im |0] T2 , I3c Im × Im T3 , I4c + + m 1 m 1 + + m 0 m 0 Table 5.1: List of 2 x 2 Configurations 55 These families proved both a good starting point for exploration, and a helpful way to demonstrate the use of our results and techniques used to prove bounds. 5.1 Constant families We can use many results previously shown in this paper in order to simplify our classification of families. The first is Theorem 2.1.1, which allows us to identify families with a constant bound. For example, the family {F1 , F7 } has the property that F1 ≺ I4 , F7 ≺ T3 , and F7 ≺ I4c and thus by Theorem 2.1.1 forb(m, {F1 , F7 }) is O(1). There are many pairs of configurations that have this property and thus a constant bound. They are as follows: {F1 , F5 }, {F1 , F6 }, {F1 , F7 }, {F2 , F5 }, {F2 , F6 }, {F2 , F7 }, {F3 , F5 }, {F4 , F5 }, {F5 , F6 }, {F5 , F7 }. (5.1) Now by Remark 1.3.19, we know that forb(m, F) must be no larger than forb(m, F ) for all F ⊆ F. Thus any family that contains one of the families in (5.1) can have at most a constant bound. We can determine the exact bound for families of 2 × 2 configurations that have a constant bound. We will prove bounds for ten minimal families of configurations taken from Table 5.1. Any family with a constant bound will contain a sub-family identical to one of our ten minimal families for which we have proved an exact upper bound. By Remark 1.3.19, the bound of the entire family will be the smallest bound of the subfamilies; thus the bound for a family with a constant bound will be given by one of our ten minimal families. Proposition 5.1.1. Let m ≥ 2. We have forb(m, {F1 , F5 }) = forb(m, {F3 , F5 }) = forb(m, {F5 , F7 }) = 3. Proof. Let A ∈ Avoid(m, F), for one of the families above. Because our matrix A must avoid F5 , our columns must be pairwise comparable, so that for any α, β ∈ A, α ≤ β or β ≤ α. Thus our matrix will be a selection of columns chosen from the triangular matrix [Tm |0]. If we we choose four or more columns from this matrix, on some subset of rows there will be a T4 or [T3 |0], both of which contain F1 , F3 , and F7 . Thus the bound must be less than 4. The following constructions achieve the bound 56 of 3: {F1 , F5 } : 1 1 0 .. . 1 0 0 .. . 0 0 0 .. . {F4 , F5 } : 1 1 .. . 1 0 .. . 0 0 .. . or 1 0 0 1 1 .. . 0 1 .. . 0 0 .. . . 1 1 0 The construction for {F5 , F7 } is the complement of the construction for {F1 , F5 }, per Remark 1.3.16. Proposition 5.1.2. We have forb(m, {F4 , F5 }) = forb(m, {F2 , F5 }) = forb(m, {F5 , F6 }) = 2. Proof. Let A ∈ Avoid(m, F), for one of the families above. Similarly to the previous proof, in order to avoid F5 , A will be taken from columns of the triangular matrix [Tm |0]. But any three columns chosen from [Tm |0] will include the submatrices T3 or [T2 |0], both of which contain F2 , F4 , and F6 . Thus the bound must be less than 3. The constructions that achieve the bound of for {F4 , F5 } are as follows: 1 0 .. . 0 0 .. . or 0 0 0 1 .. . 1 1 .. . . 1 1 The construction that achieves the bound of 2 for {F2 , F5 }, {F5 , F6 } is [1|0]. Proposition 5.1.3. Let m ≥ 7. Then forb(m, {F1 , F7 }) = 2. Proof. For proof of this bound, see Section 2.3 and Theorem 2.3.4. For any column α, a construction of [α|αc ] achieves the bound. Proposition 5.1.4. We have forb(m, {F2 , F6 }) = 2. Proof. Let A ∈ Avoid(m, {F2 , F6 }). Suppose our matrix A has 3 columns. Without loss of generality, we can suppose the first row has two 1’s and one 0. Because A is simple, for some row below the columns containing these two 1’s, these columns must contain a [10]. However, such a matrix contains F6 . A similar argument works for the complement. Thus forb(m, {F2 , F6 }) < 3. For any column α, a construction of [α|αc ] achieves the bound. 57 Proposition 5.1.5. We have forb(m, {F1 , F6 }) = forb(m, {F2 , F7 }) = 2. Proof. We will demonstrate the argument for forb(m, {F1 , F6 }; forb(m, {F2 , F7 } follows by Remark 1.3.16. Let A ∈ Avoid(m, {F1 , F6 }. Suppose our matrix A has 3 columns. Suppose that the first row has two 1s and one 0. Then A cannot avoid F6 by the same argument as the previous family. Now suppose the first row has one 1 and two 0s. We consider the two columns α and β containing the 0s. After the first row, [α|β] cannot contain [00] on any row, otherwise A will contain F1 . In addition, because A is simple, on some row [α|β] must contain [01]. Therefore [α|β] can never contain [11] on a row (to avoid F6 ). In the row containing [10] in columns [α|β], the third column must contain a 0 in order to avoid F6 . However, if this row is repeated more than once, we have F1 . Thus an A ∈ Avoid(m, {F1 , F6 }) with 3 columns is not possible and forb(m, {F1 , F6 } < 3. For any column α, a construction of [α|αc ] achieves the bound. Proposition 5.1.6. For m ≥ 5, We have forb(m, {F1 , F4 , F6 }) = forb(m, {F1 , F4 , F7 }) = forb(m, {F2 , F4 , F6 }) = forb(m, {F2 , F4 , F7 }) = 1. Proof. Suppose there is a two-column construction A avoiding these families. There are four options for the rows of A: [00], [11], [01] or [10]. If any one of these rows is repeated more than once, we will have a F1 , F7 , F4 , or F4 respectively. Thus for the family {F1 , F4 , F6 }, the only row that can be repeated is [11]. However, because this is a simple matrix, at some point we must have the row [01] or [10]. This generates an F6 , which is forbidden. A similar argument can be used for the other families listed above. Any column α will achieve the bound. 5.2 Linear families We know from Proposition 2.1.2 that if a family does not have a constant bound, its bound is at least linear. Thus all families of 2 × 2 configurations that do not have a constant bound must have at least a linear bound. What is the upper bound of these families? In fact, most of the 2 × 2 configurations listed in Table 5.1 have a linear bound. Thus by Remark 1.3.19, we know that forb(m, F) is O(m) for any F containing 58 F2 , F3 , . . . F6 . The only family with the potential to have a greater than linear bound would be the two configurations with a quadratic bound, namely {F1 , F7 }, which we have already shown to have a constant bound. Thus for all families of size greater than 1, forb(m, F) has at most a linear upper bound. Therefore all families of 2 × 2 configurations that do not have a constant bound must have a linear bound, i.e. are Θ(m). Carefully examining the list of pairs of configurations that give a constant bound, we find that the only families of 2 × 2 configurations that do not contain a family from our list of constant-bounded families (5.1) are the families {F1 , F2 , F3 , F4 } or {F3 , F4 , F6 , F7 } and all of their subfamilies. To show that forb(m, F) is Θ(m) for these families, it remains to show that they admit a linear construction. We will do so by giving exact bounds for two scenarios. First, we consider all possible pairs of 2 × 2 configurations that do not yield a constant bound. These pairs are contained in the family of either {F1 , F2 , F3 , F4 } or {F3 , F4 , F6 , F7 }, or alternatively, are not contained in (5.1)). {F1 , F2 }, {F1 , F4 }, {F2 , F3 }, {F2 , F4 }, {F3 , F4 } (5.2) {F3 , F4 }, {F3 , F6 }, {F4 , F6 }, {F4 , F7 }, {F6 , F7 } (5.3) {F1 , F3 }, {F3 , F7 } (5.4) Remark 5.2.1. The families in (5.2) and (5.3) have a bound of m + 1. The families listed in (5.2) and (5.3) have at least one configuration with a bound of m + 1. Thus the bound for each of the families listed in (5.2) and (5.3) is m + 1, a consequence of Remark 1.3.19. In all cases there is also a linear construction that c achieves the bound. In the case of families in (5.2), the matrix [Im |1] avoids each pair of configurations, as well as any union of them. Similarly, for families in (5.3), the matrix [Im |0] avoids each family and any union of them. Remark 5.2.2. The families in (5.4) have a bound of m + 2. Each configuration individually has a bound of m+2, enforcing a maximum upper c bound of m + 2 (again by Remark 1.3.19) and the configurations [Im |1|0] and [Im |1|0] achieve this bound by avoiding {F1 , F3 } and {F3 , F7 } respectively. 59 5.3 Table of results The following table (Table 5.2) summarizes the results preceding this section. These results should completely characterize forb(m, F) where F is a family of 2 × 2 configurations. Given such a family F, the first line of the table which contains a subfamily contained in F gives the bound and construction for the entire family F. F forb(m, F) {F1 , F4 , F6 }, {F1 , F4 , F7 }, 1 {F2 , F4 , F6 }, {F2 , F4 , F7 } {F1 , F7 } 2 {F2 , F6 } 2 {F1 , F6 }, {F2 , F7 } 2 {F2 , F5 }, {F4 , F5 }, {F5 , F6 } 2 {F1 , F5 }, {F3 , F5 }, {F5 , F7 } 3 {F1 , F2 }, {F1 , F4 }, {F2 , F3 }, m + 1 {F2 , F4 }, {F3 , F4 } {F3 , F4 }, {F3 , F6 }, {F4 , F6 }, m + 1 {F4 , F7 }, {F6 , F7 } {F1 , F3 } m+2 {F3 , F7 } m+2 Construction any column Proof Proposition 5.1.6 [α|αc ] [α|αc ] [α|αc ] Proposition 5.1.2 Proposition 5.1.1 [I c |1] Theorem 2.3.4 Proposition 5.1.4 Proposition 5.1.5 Proposition 5.1.2 Proposition 5.1.1 Remark 5.2.1 [I|0] Remark 5.2.1 c |0|1] [Im [Im |0|1] Remark 5.2.2 Remark 5.2.2 Table 5.2: Summary of Results 5.4 Critical subfamilies Our results here suggest an interesting parallel to previous results from the study of single forbidden configurations. When forbidding a single configuration F , the configuration may have a subconfiguration F ≺ F such that forb(m, F ) = forb(m, F ). If this F is minimal, that is, if for all F ≺ F , forb(m, F ) < forb(m, F ), F is called a critical substructure of F [6]. Such a sub-configuration is called critical, because the larger configuration’s bound somehow depends on the bound of this substructure and its presence in the larger configuration. For example, when forbidding the complete object K4 , there are seven critical substructures, whose bound is the same as that of K4 . Theorem 5.4.1. [18] The critical substructures of K4 are 04 , 14 , I4 , I4c , K42 , [2 · 03 ], [2 · 13 ]. 60 This means that forbidding, say, 14 , has the same “power” as forbidding all of K4 , in that forb(m, 14 ) = forb(m, K4 ). We can extend this idea of critical substructures to our forbidden families, where a subfamily F ⊂ F is called a critical subfamily if forb(m, F ) = forb(m, F) and F is minimal, that is, for all F ⊂ F , forb(m, F ) > forb(m, F). This definition can also be seen as a further refinement of Remark 1.3.19, which states this very idea: that the upper bound of a family is restricted by the bounds of all its subfamilies. We can see this idea clearly at work in the bounds established in the previous sections of this chapter. For example the family {F1 , F2 , F3 , F4 } has a bound of m + 1, with critical subfamilies {F2 }, and {F4 }, as they each also have a bound of m + 1. Our implicit classification of all families of 2 × 2 configurations with constant bound also uses this principal: if a family F contains at least one of our ten proven families as a subfamily, then that subfamily serves as a critical subfamily, restricting the bound for F. One of the results described in Section 1.3 was that forb(m, C3 ) = forb(m, {C3 , C4 , C5 , . . . }) and forb(m, C3 ) = forb(m, {C3 , C5 , C7 , . . . }). Thus {C3 } is a critical subfamily of {C3 , C4 , C5 , . . . } and {C3 , C5 , C7 , . . . }. It should be noted that while critical subfamilies can be a useful way to determine bounds for larger families, the bound for a forbidden family may not always arise from a critical subfamily. In the case of {F1 , F7 }, forb(m, {F1 , F7 }) is constant. However, the only subfamilies of {F1 , F7 } are the single configurations {F1 } and {F7 }, both of which have a quadratic bound. Thus the bound in this case arises from the interaction of the two configurations and Theorem 1.3.6, not the bound of a critical subfamily. 61 Chapter 6 Conclusion 6.1 Summary of results The first type of result in this paper is a classification, seen in Chapter 2 where we classify all families with a constant bound. While the classification theorem is based on a result not original to this paper, its conjecture and proof is a strong statement both about families of forbidden configurations and the interaction of the three key matrices of Conjecture 1.3.5. First, the classification allows us to not only identify, almost at a glance, which forbidden families have a constant upper bound, but tells us therefore which families have at least a linear construction. Furthermore, the strength and completeness of the result supports the premise of Conjecture 1.3.5, c that somehow the matrices Im , Im and Tm are integral to understanding forbidden configurations. However, the bulk of this paper has been devoted to establishing and proving both exact and asymptotic bounds for specific families of forbidden configurations. It is by no means an exhaustive survey, and we did not reach any other grand classification schemes; however, many of our results present interesting aspects of the forbidden configuration problem when it is extended to families. For example, the theorem and proof of Section 4.1 both show that the asymptotic bound can be a fractional exponent of m, not merely an integer exponent of m. The results regarding forbidden blocks of zeroes and ones in Section 2.3 illustrate the failed monotonicity of the (constant) bound for a family of forbidden configurations. However, almost as important as the final bounds discussed in the paper are the techniques used to prove them. Proofs in Section 2.3 used basic combinatorics, a 62 bucketing approach from computer science, and a variation of linear programming. The proofs of certain linear bounds used a previous result about the structure of matrices that avoid a certain configuration (F9 in Table 3.1). The proof of the bound in Section 4.1 is a fresh spin on standard induction, and also includes the method of “what is missing.” Finally, the results in this paper suggest various other ideas parallelling previous work in single forbidden configurations (for example, the idea of critical subfamilies discussed in Section 5.4). These are not results per se, but we have noted all such correspondences, or other patterns of note. In conclusion, this paper presents both refinements and extensions of previous work, as well as original results. The results will provide either tools or a jumping off point for continued research in the field. Thus this paper could be used as a helpful starting reference for anyone seeking to continue working in the field of forbidden configurations, as it combines a summary of previous important results, presents an important classification, provides illustration of most known proof techniques, and suggests areas for exploration. 6.2 Future work There are several possibilities for future work regarding families of forbidden configurations. The first would be an extension of Conjecture 1.3.5 from single forbidden configurations to families. As alluded to in Chapter 4, Conjecture 1.3.5 fails in the case of forbidden families. However, there might be an alternative statement for which it holds. One example might be that the conclusions of Conjecture 1.3.5 hold if the configurations in a forbidden family represent all the inductive children of a single forbidden configuration. There may be another claim to be made about the size or type of a forbidden family on the asymptotic power of its bound. Another avenue of exploration would be more theorems to classify families of a certain bound, like Theorem 1.3.6 and Theorem 2.1.1. Similarly, in Section 5.4, we discussed families which “force” a certain asymptotic bound. Part of classifying families may be finding all of these critical families or types of critical families for which a certain bound occurs. In the proof of Theorem 4.1.3, we used a new technique based on standard induction and proof by contradiction. This technique was originally used in a similar proof, 63 and its adaptability to the new result indicates that it may be a useful addition to the standard repertoire of methods used to solve problems in forbidden configurations. In addition, the analysis of “what is missing” was a useful tool in determining various bounds. In our results, we have often used pre-established results from the study of single forbidden configurations. In return, the study of forbidden families might be of use when studying single configurations. In particular, the use of standard induction can change the problem from avoiding a single configuration in A to avoiding a family of inductive children in Cr . Knowledge of certain common families could then help prove upper bounds for these single configurations. 64 Bibliography [1] R.P. Anstee. A survey of forbidden configuration results. The Electronic Journal of Combinatorics, 20:DS20, 2013. (Dynamic Survey). [2] R.P Anstee and M. Farber. Characterizations of totally balanced matrices. Journal of Algorithms, 5(2):215 – 230, 1984. [3] R.P Anstee, R. Ferguson, and A. Sali. Small forbidden configurations II. Electronic Journal of Combinatorics, 8(1):R4, 2001. [4] R.P. Anstee and B. Fleming. Linear algebra methods for forbidden configurations. Combinatorica, 31:1–19, 2011. [5] R.P. Anstee and Z. F¨ uredi. Forbidden submatrices. Discrete Math, 62:225–243, 1986. [6] R.P. Anstee and S.N. Karp. Forbidden configurations: exact bounds determined by critical substructures. Electronic Journal of Combinatorics, 17, 2012. [7] R.P. Anstee, Christina Koch, Miguel Raggi, and A. Sali. Forbidden configurations and product constructions. Submitted to Graphs and Combinatorics. [8] R.P Anstee and A. Sali. Small forbidden configurations IV: The 3 rowed case. Combinatorica, 25(5):503–518, 2005. [9] J. Balogh and B. Bollob´as. Unavoidable traces of set systems. Combinatorica, 25(6):633–643, 2005. [10] J. Balogh, P. Keevash, and B. Sudakov. Disjoining representability of sets and their complements. Journal of Combinatorical Theory, 95:12–28, 2005. [11] Laura Dunwoody. Notes. Research notes, 2005. 65 [12] P. Erd˝os and M. Simonovits. A limit theorem in graph theory. Studia Scientiarum Mathematicarum Hungarica, 1:51–57, 1966. [13] P. Erd˝os and A.H. Stone. On the structure of linear graphs. Bulletin of the American Mathematical Society, 52:1089 – 1091, 1946. [14] Balin Fleming. Some families of forbidden configurations. Research notes, 2003. [15] P. Frankl, Z. F¨ uredi, and J. Pach. Bounding one-way differences. Graphs and Combinatorics, 3:341–347, 1987. [16] H.O.F. Gronau. An extremal set theory problem. Studia Scientiarum Mathematicarum Hungarica, 15:29–30, 1980. [17] W. Mantel. Problem 28 solution. Wiskundige Opgavem, 10:60–61, 1907. [18] Miguel Raggi. Forbidden Configurations. PhD thesis, University of British Columbia, 2011. [19] H.J. Ryser. A fundamental matrix equation for finite sets. Proceedings of the American Mathematical Society, 34:332–336, 1972. [20] N. Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145 – 147, 1972. [21] S. Shelah. A combinatorial problem stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247 – 261, 1972. [22] Paul Tur´an. Eine extremalaufgabe aus der graphentheorie. Matematikai ´es Fizikai Lapok, 48:436 – 452, 1941. [23] V.N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Applications, 25:264–280, 1971. 66
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Families of forbidden configurations
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Families of forbidden configurations Koch, Christina Louise 2013
pdf
Page Metadata
Item Metadata
Title | Families of forbidden configurations |
Creator |
Koch, Christina Louise |
Publisher | University of British Columbia |
Date Issued | 2013 |
Description | The forbidden configuration problem arises from a question in extremal set theory. The question seeks a bound on the maximum number of subsets of an m-set given that some trace is forbidden. In terms of hypergraphs, we seek the maximum number of edges on a simple hypergraph of m vertices such that this hypergraph does not contain a forbidden sub-hypergraph. We will use the notation of matrices to describe the problem as follows. We call a (0,1)-matrix simple if it has no repeated columns; this will be the analogue of a simple hypergraph. Let F be a given matrix. We say that a (0,1)-matrix A contains F as a configuration if there is some submatrix of A that is a row and column permutation of F. This is equivalent to a hypergraph containing some sub-hypergraph. F need not be simple. We define forb(m, F ) as the maximum number of columns possible for a simple, m-rowed, (0,1)-matrix that does not contain F as a configuration. A variation of the forbidden configuration problem forbids a family of configurations F = {F₁, F₂, ... Fn} instead of a single configuration F. Thus, forb(m, F) becomes the maximum number of columns possible for a simple, m-rowed, (0,1)-matrix that does not contain any one of the matrices in the family as a configuration. We will present a series of results organized by the character of forb(m, F). These include a classification of families such that forb(m, F) is a constant and the unexpected result that for a certain family, forb(m, F) is on the order of m³/², where previous results typically had forb(m, F) on the order of integer powers of m. We will conclude with a case study of families of forbidden configurations and suggestions for future work. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2013-04-17 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0073659 |
URI | http://hdl.handle.net/2429/44225 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2013-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2013_spring_koch_christina.pdf [ 488.15kB ]
- Metadata
- JSON: 24-1.0073659.json
- JSON-LD: 24-1.0073659-ld.json
- RDF/XML (Pretty): 24-1.0073659-rdf.xml
- RDF/JSON: 24-1.0073659-rdf.json
- Turtle: 24-1.0073659-turtle.txt
- N-Triples: 24-1.0073659-rdf-ntriples.txt
- Original Record: 24-1.0073659-source.json
- Full Text
- 24-1.0073659-fulltext.txt
- Citation
- 24-1.0073659.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0073659/manifest