Families of Forbidden Con gurations 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 2013Abstract The forbidden con guration 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 con guration 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 de ne 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 con guration. A variation of the forbidden con guration problem forbids a family of con gu- rations F = fF1; F2; : : : Fng instead of a single con guration 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 2 F as a con guration. We will present a series of results organized by the character of forb(m;F). These include a classi cation of families F such that forb(m;F) is a constant and the un- expected 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 con gurations and suggestions for future work. iiPreface The question of forbidden con gurations was introduced to me by my supervisor Dr. Richard Anstee, and the choice to explore families of forbidden con gurations 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 rst is a result of Balin Fleming included in Section 2.4, which is used with his permission and clearly identi ed 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 modi cations 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. iiiContents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Extremal problems and hypergraphs . . . . . . . . . . . . . . . . . . 1 1.2 De nitions and notation . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 (0,1)-matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Forbidden con gurations and bounds . . . . . . . . . . . . . . 5 1.2.3 Matrix constructions . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.4 Set system terminology . . . . . . . . . . . . . . . . . . . . . . 9 1.3 History of results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.1 Single forbidden con gurations . . . . . . . . . . . . . . . . . 10 1.3.2 Families of forbidden con gurations . . . . . . . . . . . . . . . 11 1.3.3 Elementary remarks and lemmas . . . . . . . . . . . . . . . . 13 1.4 Basic methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.1 Standard induction . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.2 What is missing . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4.3 Linear algebra reduction . . . . . . . . . . . . . . . . . . . . . 16 2 Families With a Constant Bound . . . . . . . . . . . . . . . . . . . . . 18 2.1 A classi cation for families of constant bound . . . . . . . . . . . . . 18 iv2.1.1 A constant construction . . . . . . . . . . . . . . . . . . . . . 19 2.2 Failed monotonicity of the constant bound . . . . . . . . . . . . . . . 20 2.3 Exact bound for blocks of 0’s and 1’s . . . . . . . . . . . . . . . . . . 21 2.3.1 Column bound . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3.2 A sharp boundary . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3.3 Other bounds and constructions . . . . . . . . . . . . . . . . . 27 2.4 Constant bound for another family . . . . . . . . . . . . . . . . . . . 28 3 Families With a Linear Bound . . . . . . . . . . . . . . . . . . . . . . 31 3.1 Families of minimal quadratic con gurations . . . . . . . . . . . . . . 31 3.1.1 Families proved using basic methods . . . . . . . . . . . . . . 33 3.1.2 Families proved using a structure argument . . . . . . . . . . 36 3.2 Other linear results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4 Families With a Super-linear Bound . . . . . . . . . . . . . . . . . . 40 4.1 Unexpected bound for product con gurations . . . . . . . . . . . . . 40 4.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.1.2 Theorem and proof . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2 A similar bound for larger product con gurations . . . . . . . . . . . 51 5 A Case Study: Families of 2 x 2 Con gurations . . . . . . . . . . . 55 5.1 Constant families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.2 Linear families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.3 Table of results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.4 Critical subfamilies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6.1 Summary of results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 vList of Tables 3.1 Minimal Quadratic Con gurations . . . . . . . . . . . . . . . . . . . . 32 3.2 Pairs of Minimal Quadratic Con gurations . . . . . . . . . . . . . . . 33 5.1 List of 2 x 2 Con gurations . . . . . . . . . . . . . . . . . . . . . . . 55 5.2 Summary of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 viAcknowledgements 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 co ee. 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, sta , and students of the math department. Thanks to all my professors, the o ce sta , 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 nally, thank you to my family. viiChapter 1 Introduction In this chapter we provide an introduction to the topic of this paper: the question of forbidden con gurations. We begin with the origin of the research question and its statement. We then provide a list of all necessary notation and de nitions 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 eld of mathematics that asks \how many?" This initial question is often modi ed 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 de nitions. De nition 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 . De nition 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. 1Forbidden con gurations, the subject of this paper, relate to theorems in extremal graph theory. These theorems address the following combinatorial question: suppos- ing 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 ques- tion: given n vertices what is the minimum number of edges in G such that you are guaranteed a copy of the subgraph H? The rst 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 that there is no triangle. Then jEj n 2 4 . 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 k 1 n2 2 or 1 1 k 1 n2 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. De nition 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 de ne 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 sub- graphs, H, it also connects the idea of a forbidden subgraph with the chromatic 2number of that subgraph. We will conjecture a similar notion is helpful when looking at forbidden con gurations. We will now generalize this problem of a forbidden subgraph to hypergraphs. We begin with our original de nition of a graph G as an ordered pair G = (V;E) and generalize this de nition to a hypergraph. De nition 1.1.7. Let X be a nite set, with 2X denoting the set of all subsets of X, or the power set of X. De nition 1.1.8. A hypergraph is an ordered pair H = (X; E), where X is a nite set of elements called vertices, E is a multiset of sets in 2X , that is, for each E 2 E, we have E 2 2X . The elements of E are called edges. The hypergraph H is called simple if the elements E 2 E are unique. i.e. E is a set. De nition 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 de ned on X and for all E 2 E , E 2 A. A simple graph as de ned in De nition 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 ; 2 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. De nition 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 2 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 3jXj = 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 con gurations. In the rest of this paper, we will approach this question using the language of matrices. 1.2 De nitions and notation 1.2.1 (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 de ned on the set X. Let jXj = m and jAj = n. For each set B 2 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 2 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 2 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 2 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 f1; 2; 3; : : : ;mg. We will often use [m] to index the rows of A. We use the notation kAk 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 AjS 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. 41.2.2 Forbidden con gurations and bounds In our matrix interpretation of hypergraphs, a sub-hypergraph becomes a con gura- tion. We de ne that A contains F as a con guration, 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 # and A = 2 6 4 0 0 0 1 0 1 0 0 0 0 1 1 3 7 5 : 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 6 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 # and A = 2 6 4 0 1 0 0 0 0 1 0 0 0 0 1 3 7 5 : Then F 6 A. If A is a simple (0; 1)-matrix with m rows that avoids F , we use the following notation: A 2 Avoid(m;F ). So: Avoid(m;F ) = fA : A simple, m-rowed matrix; F 6 Ag: The primary question of forbidden con gurations concerns the following function: forb(m;F ) = maxfkAk : A 2 Avoid(m;F )g: 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 2 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 con guration F? For this paper, we intend to modify the forbidden con guration question slightly by forbidding a family of con gurations instead of a single con guration. 5A forbidden family is a nite set of forbidden con gurations, denoted F = fF1; F2; : : : ; Ftg. We de ne Avoid(m;F) = fA : A simple, m-rowed matrix; Fi 6 A for i = 1; 2; : : : ; tg: Our previous de nition of forb(m;F ) naturally generalizes to: forb(m;F) = maxfkAk : A 2 Avoid(m;F)g: So forb(m;F) is the largest value n such that there exists an m n simple (0; 1)- matrix A where A 2 Avoid(m;F). In order to nd 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 satis ed with determining asymptotic upper and lower bounds, expressed in big-O notation. forb(m;F) is O(mk) if there exists c 2 R such that for su ciently large m forb(m;F) cmk. forb(m;F) is (mk) if there exists c 2 R such that for su ciently large m forb(m;F) cmk. forb(m;F) is (mk) if there exists c1; c2 2 R such that for su ciently large m, we have c1mk forb(m;F) c2mk. 1.2.3 Matrix constructions We will use the following notation to describe various matrix con gurations and constructions. We de ne 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 de ne Kk as the complete object on k rows, that is, the k 2k simple matrix of all possible columns on k rows. We de ne Ksk as the k k s simple matrix of all 6columns of column sum s on a matrix of k rows. For example: K24 = 2 6 6 6 6 4 1 1 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 3 7 7 7 7 5 : 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 de ne 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 = 2 6 6 6 6 4 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 3 7 7 7 7 5 : In our con gurations and constructions, we will frequently see the following three matrices: The identity matrix on m rows, or Im or K1m, consists of an m m matrix with 1’s on the diagonal and 0’s everywhere else. It corresponds to the set system of singleton sets on m elements. For example, I4 = 2 6 6 6 6 4 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 3 7 7 7 7 5 : The identity complement matrix onm rows, or Icm orK m 1 m , 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- 7responds to a set system of sets of size m 1 on m elements. For example, Ic4 = 2 6 6 6 6 4 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 3 7 7 7 7 5 : 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 justi ed towards the top of the matrix. It corresponds to the set system ff1g; f1; 2g; f1; 2; 3g; : : : ; f1; 2; : : : ;mgg. For example, T4 = 2 6 6 6 6 4 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 3 7 7 7 7 5 : We will also refer to this matrix as a tower matrix. We use the notation [AjB] to denote the matrix obtained from concatenating the two matrices A and B. We use the notation k A to denote the matrix [AjAj : : : jA] consisting of k copies of A concatenated together. We give precedence to the opera- tion (multiplication) over concatenation so that for example [2 AjB] 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 de ne the product A B as the (m1 + m2) (n1n2) matrix of all possible combinations of columns of A over columns of B. Note that this is a di erent de nition than the conventional notion of matrix multiplication. An example of I2 I2 is shown below. " 1 0 0 1 # " 1 0 0 1 # = 2 6 6 6 6 4 1 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 3 7 7 7 7 5 : It is interesting to note that after some row and column permutation, I2 I2 is the same matrix as the C4 shown earlier. 81.2.4 Set system terminology The following de nitions 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 = 2 6 6 6 6 4 1 1 1 0 3 7 7 7 7 5 ; = 2 6 6 6 6 4 0 1 1 0 3 7 7 7 7 5 ; = 2 6 6 6 6 4 1 0 0 1 3 7 7 7 7 5 : Then and are comparable, with ; and are disjoint; and and are neither comparable nor disjoint. We de ne a laminar family as the following: given a set systemA, for allB;C 2 A, B C, C B or B \ C = ;. A laminar matrix is de ned similarly: given a (0; 1)- matrix A, for all columns ; 2 A, and are comparable or and are disjoint. Another way to de ne a laminar matrix is by forbidding a con guration 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 FL = 2 6 4 1 1 1 0 0 1 3 7 5 ; L1 = i j k 2 6 4 1 1 0 3 7 5 ; L2 = i j k 2 6 4 1 0 1 3 7 5 : Remark 1.2.1. Let A be a (0; 1)-matrix with no con guration FL. Then A is laminar. Remark 1.2.2. Let A be a (0; 1)-matrix such that on every triple of rows S = fa; b; cg there is a bijection : S ! fi; j; kg such that AjS has no L1 and L2 as indexed. Then FL 6 A and so A is laminar. 1.3 History of results Here we present a history of results for the forbidden con guration problem. Many of these results will be used to motivate or prove results given in the research chapters 9of this paper. 1.3.1 Single forbidden con gurations The primary result in the study of forbidden con gurations 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 k 1 + m k 2 + + m 0 : This implies that forb(m;Kk) is (mk 1). Corollary 1.3.2. For any simple con guration 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 xed k; t, as m!1, forb(m; t Kk) = (t 2) (k + 1) (1 o(1)) m k + m k 1 + + m 0 : 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 con gu- rations: in the case of a simple k-rowed con guration, Corollary 1.3.2 gives a bound of at most O(mk 1), while for all other k-rowed con gurations, 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), Ic (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 for every Ai as Im=p; Icm=p or Tm=p. Then forb(m;F ) = (m X(F ) 1). 10The 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 su cient constructions to achieve the asymptotic bounds for forb(m;F ) for any forbidden con guration F . The three ma- trices 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, iden- tity complement and triangular matrix is somehow fundamental to solving questions about forbidden con gurations. 1.3.2 Families of forbidden con gurations Because the focus of this paper will be on families of forbidden con gurations, we now shift our attention to results that pertain speci cally to forbidden families. For our rst result, we present a theorem of Balogh and Bollob as Theorem 1.3.6. [9] Let k be given. Then forb(m; fIk; Ick; Tkg) is O(1). In other words, when we forbid all three matrices used for constructions in Con- jecture 1.3.5, the resulting matrices A 2 Avoid(m; fIk; Ick; Tkg) 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; fIk; Ick; Tkg) 2k 2 k 1 . We establish this result in Proposition 2.1.3. We have two further results that provide more exact bounds for speci c instances of families for which Theorem 1.3.6 would apply. The rst 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; fI1; Ic1; T1g) = 0, forb(m; fI2; I c 2; T2g) = 2, and forb(m; fI3; Ic3; T3g) = 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 11Theorem 1.3.9. [14] Let Fa = 1 0 0 1 jt 0 0 , Fb = 1 0 0 1 jt 1 1 and Fc = t 0 0 1 0 1 1 . If t 2, forb(m; fFa; Fb; Fcg) 6t 6. Note that Fa It+2, Fb Ict+2 and Fc T3t We will take up this result in greater detail in Section 2.4, while discussing for- bidden 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 Su- dakov, indicate. Theorem 1.3.10. [10] Let k 2. Then forb(m; fIk; Ickg) is (m k 1). Theorem 1.3.11. [10] Let k 2. Then forb(m; fIck; Tkg) is (m k 1). Theorem 1.3.12. [10] Let k 2. Then forb(m; fIk; Tkg) is (mk 2). Forbidding families of forbidden con gurations also results in asymptotic bounds with non-integer exponents. Theorem 1.3.13. [1] We have forb(m; fC4;13g) is (m3=2). This theorem is linked to another family with the same bound. Theorem 1.3.14. [7] We have forb(m; fI2 I2; T2 T2; I2 T2g) 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 ma- trices. The cycle-incidence matrices of the family fC3; C4; C5; : : : g are also called balanced matrices; the matrices of the family fC3; C5; C7; : : : g are called totally bal- anced. It turns out that the bound on these in nite families is dependent simply on the bound for C3, i.e. Theorem 1.3.15. [2] We have forb(m;C3) = forb(m; fC3; C5; C7 : : : g) = m 2 + m 1 + m 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 nally, a set of results relating to balanced and totally balanced matrices. 121.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 de - nitions from Section 1.2. Remark 1.3.16. (Complementarity) Assume F = fF1; F2; : : : ; Ftg and F c = fF c1 ; F c 2 ; : : : ; F c t g. Then forb(m;Fi) = forb(m;F c i ) and forb(m;F) = forb(m;F c). Lemma 1.3.17. (Monotonicity) Suppose F 0; F are con gurations. If F 0 F , then forb(m;F 0) forb(m;F ). Proof. Any matrix that contains F will also contain F 0, and any matrix that avoids F 0 will also avoid F . The lemma follows. Lemma 1.3.18. (Induced lower bound) If F 0 F , then forb(m;F 0) forb(m;F). Proof. If A avoids F it will also avoid F 0, however there may be a better (larger) construction for F 0 that does not avoid the con gurations in F n F 0. Note that this lemma is super cially the exact opposite of the previous lemma. In Lemma 1.3.17, a smaller con guration 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 = fF1; F2; : : : ; Ftg, then forb(m;F) mini2[t](forb(m;Fi)). Furthermore, forb(m;F) minF 0 Ffforb(m;F 0)g. Proof. Because each F 2 F must be avoided, forb(m;F) can be no larger than the smallest forb(m;F ) for all F 2 F or the smallest forb(m;F 0) for all F 0 F . We conclude with a nal 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 = fF1; F2; : : : ; Ftg. Suppose F 0 is a family such that for each j 2 [t], there exists F 0 2 F 0 such that F 0 Fj. Then forb(m;F 0) forb(m;F). 13Proof. Let F and F 0 be as stated above. Suppose forb(m;F 0) > forb(m;F). This implies that there is a construction A of size m forb(m;F 0) that avoids F 0. For any Fi 2 F , if there is F 0 F 0, such that F 0 Fi, then Fi 6 A. However, by our hypothesis, this is true for all Fi 2 F . Thus A avoids F and forb(m;F) forb(m;F 0), a contradiction. 1.4 Basic methods 1.4.1 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 eld of forbidden con gurations. As we will use it in several results, it is worth describing in some detail here. Let A 2 Avoid(m;F), with kAk = 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]nr 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] n 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 [BrjCrjDr] is also simple. We also know that because F 6 A, F 6 [BrjCrjDr], so [BrjCrjDr] 2 Avoid(m 1;F). However kAk = kCrk+ k[BrjCrjDr]k. Thus if we can nd an upper bound for kCrk, the upper bound for kAk arises from induction on the rows of A as follows: forb(m;F) kCrk+ forb(m 1;F): (1.2) In order to establish an upper bound on kCrk, we will frequently use what we have termed inductive children, that is, sub-con gurations that must be avoided in 14Cr in order that Fi 6 [01] Cr for all Fi 2 F . Consider the following example: F = 8 >< >: 2 6 4 0 0 0 1 1 1 0 1 0 1 1 0 3 7 5 ; 2 6 4 1 1 1 1 1 1 3 7 5 9 >= >; : Inductive Children of F : " 1 0 0 0 1 0 # ; " 0 1 1 0 0 1 # ; " 1 0 1 0 1 1 # ; 2 6 4 1 1 1 3 7 5 ; " 1 1 1 1 # : If either of the last two inductive children are present in Cr, the second con guration of our forbidden family will appear in the original matrix. Similarly, if any of the rst three inductive children are present in Cr, we will have the rst con guration 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 con guration of k rows. On any k-tuple of rows we consider which k-rowed columns must be absent (missing), so that the con guration is avoided, or which k-rowed columns must have a maximum number of copies to avoid the con guration. 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 no i j " 0 0 # or i j " 1 1 # ; or one column appears ‘in short supply,’ which in this case, appears at most once, namely either 15i j 1 " 1 0 # : or the same with the roles of i; j reversed. If this is true for all pairs of rows inA then we can see that indeedA 2 Avoid(m;F ). In general for a set of rows S 2 [m] with jSj = 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 AjS. Note that here we are considering as a submatrix of AjS not as a con guration; order matters. Also when appears no times in AjS 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 kAk 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 2 [m] k , either AjS has one column absent or has two columns S; S which are in short supply, say appearing at most t times. Then kAk 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 2 S with columns and its columns in short supply. We will rst de ne a multi-linear indicator polynomial gS such that, for all columns in the matrix A, gS( ) is non-zero only when jS = or jS = . We rst de ne a 16multi-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: fS; = Y r2S (xr ( )r): 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 2 [m] k and i (a column of A) for i = 1; 2; : : : ; p such that ijSi is either or . In addition we assume that for all pairs i < j, that jjSi 6= ; and for any column of A we have that there is an i with 1 i p, such that jSi = 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 jSi = or . We recall that the highest degree terms in fSi; are Q j2Si 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) 6= 0. Thus the p polynomials gSi are linearly independent. But the polynomials lie in a space of dimension m k 1 + m k 2 + + m 0 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, jSi = or . There can be at most 2tp such columns which is O(mk 1). Our resulting matrix A0 has the property that for every S 2 [m] k , we have that A0jS has (at least) one absent column and so A0 has no Kk. Thus kA0k is O(mk 1). The number of deleted columns is also O(mk 1) and so kAk is O(mk 1). 17Chapter 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 brie y 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 speci c forbidden family and a maximal upper bound for another forbidden family. 2.1 A classi cation for families of constant bound In Section 1.2, we stated an important result of Balogh and Bollob as regarding for- bidden families, Theorem 1.3.6. This theorem states that for each k 2 N, forbidding the family F = fIk; Ick; Tkg 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 nite forbidden family. Then forb(m;F) is O(1) if and only if there exists Fi; Fj; F‘ 2 F (not necessarily distinct con gurations) such that for some value k 2 N, Fi Ik, Fj Ick, and F‘ Tk. Proof. We prove the forward direction by the contrapositive. Let F be a forbidden family, where Fi 2 F is an mi ni con guration. We choose d to be the maximum of ffmig; fnigg over i. Now suppose there is at least one matrix of I2d; Ic2d, or T2d 18(without loss of generality, we will assume I2d) where for all Fi 2 F , Fi 6 I2d. Then for all Fi 2 F , Fi 6 Im for m 2d and so there exists a linear construction A 2 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 con gurations) in our family F such that for some value k 2 N, Fi Ik, Fj Ick, and F‘ Tk. Then by Lemma 1.3.20, forb(m;F) forb(m; fIk; Ick; Tkg). But by Theorem 1.3.6 forb(m; fIk; Ick; Tkg) is O(1), so forb(m;F) is also O(1). The proof of this classi cation 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; Ick; Tk such that for all Fi 2 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 2 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 fIk; Tk; Ickg. Proposition 2.1.3. [11] We select for A all columns from the (k 1)-fold product [0k 1jTk 1] [0k 1jTk 1] [0k 1jTk 1] that have column sum at most k 1. A is a (k 1)2 2k 2 k 1 simple matrix in Avoid((k 1)2; fIk; Ick; Tkg). Proof. We readily see that Tk 6 A since A has no column with k 1’s. We also see that Ik 6 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 Ick 6 A So A 2 Avoid((k 1) 2; fIk; Ick; Tkg). We note that [0k 1jTk 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 k 1 and the columns as 19follows. 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 rst 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 + Pk 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; fIk; Tk; Ickg), 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 con gurations 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 con gurations 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 20Theorem 2.2.2. We have forb m; (" 0 0 0 0 # ; " 1 1 1 1 #)! = 8 >>>< >>>: 2 if m = 1;m 7 4 if m = 2; 5; 6 6 if m = 3; 4 : 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 K24 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 (K24) T . However, we must show that the upper bound for these rows is no greater than 4. Suppose there is a matrix of ve columns on ve or six rows that avoids our family. We analyze this matrix by rows. In the rst 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 00s 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 su ciently large. 2.3 Exact bound for blocks of 0’s and 1’s In this section, we o er a re nement 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, 21of which the family in Theorem 2.2.2 is an example. De nition 2.3.1. Let k; ‘; p; q be positive integers. We de ne 0j‘ as a k ‘ block of 0’s and Jpq as a p q block of 1’s. These two con gurations, 0j‘ and Jpq, are interesting both for for their non- monotonic bound, and for their frequent appearance in other con gurations, par- ticularly Ik; Ick and Tk. 2.3.1 Column bound Our rst theorem will establish an exact bound for forb(m; f0k‘; Jpqg) for m su - ciently large. We will rst prove a series of lemmas. Lemma 2.3.2. Let k; ‘; p; q be given. Let A 2 Avoid(m; f0k‘; Jpqg), with kAk = 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: mX r=1 ar ‘ + br q (k 1) n ‘ + (p 1) n q : (2.1) Proof. We consider the columns of A. We take all ‘ sized subsets of the columns and call them 0-buckets. Similarly, we take all q sized subsets of the columns as 1- buckets. We will have n ‘ 0-buckets and n q 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 b q 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 n q 1-buckets can have a maximum of p 1 contributions, which produces the right side of the inequality. Lemma 2.3.3. Let m; ‘; q be given with m ‘+q 2 q 1 . Let A = [Kq 1‘+q 2jj ] T , where is a column in Kq 1‘+q 2 and j = m ‘+q 2 q 1 . Then A is an m (‘+ q 2) simple matrix and A 2 Avoid(m; f01‘; J1qg). 22Proof. By de nition A is simple, with m rows and ‘+ q 2 columns. Furthermore, each row has ‘ 1 zeroes and q 1 ones, so A 2 Avoid(m; f01‘; J1qg. With these two lemmas, we can now establish an upper bound and constructive lower bound for forb(m; f0k‘; Jpqg). Theorem 2.3.4. Let k; ‘; p; q be given. Then there exists some constant ck‘pq such that for m ck‘pq, we have forb(m; f0k‘; Jpqg) = ‘+ q 2 Proof. We let d = maxfk; ‘; p; qg. We can then say 0k‘ T2d; 0k‘ I2d and Jpq T2d; Jpq Ic2d. Thus by Theorem 2.1.1, forb(m; f0k‘; Jpqg) is O(1). We wish to show that forb(m; f0k‘; Jpqg) = ‘+ 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 su ciently large m, forb(m; f0k‘; Jpqg) ‘+ q 2. It remains to show we have a construction that achieves the bound. Let A = [Kq 1‘+q 2jj ] T as described in Lemma 2.3.3. By Lemma 2.3.3 A 2 Avoid(m; f01‘; J1qg), and so we know A 2 Avoid(m; f0k‘; Jpqg). Furthermore, kAk = ‘+ q 2. Thus A is a construction that achieves the upper bound and so forb(m; f0k‘; Jpqg) = q + ‘ 2. 2.3.2 A sharp boundary We have now shown that forb(m; f0k‘; Jpqg) = ‘+q 2 for m larger than some constant ck‘pq. We can say something more speci c 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; f0k‘; Jpqg); for m ck‘pq, forb(m; f0k‘; Jpqg) > ‘ + 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, kAk = n and a+ b = n. Then the terms of the summand in (2.1) are bounded from below as follows: bn2 c ‘ + dn2 e ‘ a ‘ + b ‘ : (2.2) 23Proof. Note that if a is written as bn2 c i for some i 2 Z, then b = n a = n bn2 c+ i = d n 2 e+ i. We proceed by induction on i. Let a = bn2 c, and b = d n 2 e. Then a ‘ + b ‘ bn2 c ‘ + dn2 e ‘ is true trivially. Now assume for the inequality is true for a = bn2 c i, b = d n 2 e+ i, for some i 2 Z. We must show that bn2 c (i+ 1) ‘ + dn2 e+ (i+ 1) ‘ bn2 c ‘ + dn2 e ‘ : Using the combinatorial identity n k = n 1 k 1 + n 1 k , we can rewrite the left side of the previous expression as bn2 c i l bn2 c i 1 ‘ 1 + dn2 e+ i ‘ 1 + dn2 e+ i ‘ : By induction we know that bn2 c i l + dn2 e+i ‘ bn2 c ‘ + dn2 e ‘ and by properties of the binomial coe cient the di erence dn2 e+i ‘ 1 bn2 c i 1 ‘ 1 0. Thus bn2 c (i+ 1) ‘ + dn2 e+ (i+ 1) ‘ bn2 c ‘ + dn2 e ‘ ; as desired. Proposition 2.3.6. Let p; k be given, and l = q. Let A 2 Avoid(m; f0k‘; Jp‘g), with kAk = n. Then the number of rows m in A is subject to the following bound: m (k + p 2) n ‘ bn2 c ‘ + dn2 e ‘ (2.3) 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 bn2 c ‘ + dn2 e ‘ mX r=1 r ‘ + r q 24We 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 bn2 c ‘ + dn2 e ‘ (k 1) n ‘ + (p 1) n ‘ ; 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 2 Avoid(m; f0k‘; Jp‘g) such that kAk > 2‘ 2. If m > (k 1) 2‘ 1 ‘ + (p 1) 2‘ 1 ‘ then forb(m; f0k‘; Jpqg) = 2‘ 2. Proof. Let l = q and n = 2‘ 1. The row bound described by (2.3) is as follows: m (k + p 2) 2‘ 1 ‘ ‘ 1 ‘ + ‘ ‘ = (k + p 2) 2‘ ‘ = (k 1) 2‘ 1 ‘ + (p 1) 2‘ 1 ‘ : Let A = (k 1) K‘ 12‘ 1j(p 1) K ‘ 2‘ 1 T . Then A has (k 1) 2‘ 1 ‘ +(p 1) 2‘ 1 ‘ rows and 2‘ 1 columns. Furthermore, the con guration O1‘ will appear exactly k 1 times on any subset of ‘ columns and the con guration J1‘ will appear exactly p 1 times on any subset of ‘ columns and thus, A 2 Avoid(m; fOk‘; Jp‘g). 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 su ciently 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 2 Avoid(m; f0k‘; Jkqg) where kAk = n. Furthermore, for m > (k 1) ‘+q ‘ , forb(m; f0k‘; Jkpg) < ‘+ q. Proof. Let k = p and n = ‘ + q. Let A = [(k 1) K‘‘+q] T . By de nition, 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 q , the right hand side of (2.1) can be written as 2(k 1) ‘+q ‘ . On the left hand side of the inequality, we note that since ar + br = n = ‘+q, we have 2 ar ‘ + br q , with equality when ar = ‘ and br = q. Thus, 2m mX r=1 ar ‘ + br q 2(k 1) ‘+ q ‘ Hence for m > (k 1) ‘+q ‘ , forb(m; f0k‘; Jkpg) < ‘+ 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 2 Avoid(m; f0k‘; Jkqg) where kAk = n. Furthermore, for m > (k 1) ‘+q ‘ , forb(m; f0k‘; Jkpg) < ‘+ q 1. Proof. Let k = p and n = ‘ + q 1. Let A = [(k 1) K‘‘+q 1j(k 1) K ‘ 1 ‘+q 1] T . By de nition, 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. 26It 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 ‘ + br q , with equality when ar = ‘ or br = q. Thus, m mX r=1 ar ‘ + br q (k 1) ‘+ q ‘ Hence for m > (k 1) ‘+q ‘ , forb(m; f0k‘; Jkpg) < ‘+ q 1. 2.3.3 Other bounds and constructions We have now shown that for su ciently large m, forb(m; f0k‘; Jpqg = ‘+ 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; f0k‘; Jpqg) is for small m. The following results provide some additional insight into upper and lower bounds for forb(m; f0k‘; Jpqg). The following proposition places an absolute upper bound on forb(m; f0k‘; Jpqg) for all values of m, provided that k = p = 2 and ‘ = q. Proposition 2.3.10. Let k = 2; p = 2 and ‘ = q. For m 3, forb(m; f02‘; J2‘g) 6(‘ 1): Proof. Suppose we have a matrix A which avoids f02‘; J2‘g. 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 2 6 4 0 0 0 3 7 5 2 6 4 1 0 0 3 7 5 2 6 4 0 1 0 3 7 5 2 6 4 0 0 1 3 7 5 2 6 4 0 1 1 3 7 5 2 6 4 1 0 1 3 7 5 2 6 4 1 1 0 3 7 5 2 6 4 1 1 1 3 7 5 (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 27the 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. Proposition 2.3.11. Let k; ‘; p; q be given. Then Kpk+p 2 Avoid(m; f0k‘; Jpqg) for ‘; q > 1 Proof. Let A = Kpk+p. Consider any k-sized subset of the rows of A. Because A = Kpk+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 f0k‘; Jpqg if ‘; q > 1. This construction has k+p p columns on k+ p rows and thus shows that, for large k and p, there can be matrices with many columns in Avoid(m; fOk‘; Jpqg), even if the nal constant bound as given in Theorem 2.3.4 is small. 2.4 Constant bound for another family The previous bound for con gurations of 00s and 10s is not the rst re nement of the constant bound for families of forbidden con gurations that have a constant bound. We present the following result of Balin Fleming, taken from his research notes with his permission. Let the con gurations Fa; Fb,and Fc be de ned as follows: Fa = 1 0 0 1 t 1 1 ; Fb = 1 0 0 1 t 0 0 Fc = t 0 1 1 0 0 1 28where t is some integer constant. The con gurations Fa; Fb; Fc are contained in the matrices Ic3t; 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; fFa; Fb; Fcg) 6t 6. Proof. Let A 2 Avoid(m; fFa; Fb; Fcg). Either kAk < 6t 6 (establishing the result) or kAk > 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 A0, and the next part of the proof will take place in A0, which, by de nition, has at least 3t 2 columns. Assume for a contradiction that no row in A0 has t [01]. Assuming this, all rows in A0 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 0 0 on the row pair (j; k). Since we have this many 0 0 columns on (j; k), we cannot have an I2 on the other columns of (j; k) as this would create the con guration 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 con ned to the same columns of A0, 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 A0. 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 con ned to the same t 1 (at most) columns in A0. 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 A0. 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 kAk = 6t 6, then row ‘ has either [(3t 2) 0jt 1] or [(3t 2) 1jt 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) 0jt 1]. We obtain a similar contradiction if ‘ contains [(3t 2) 1jt 0]. Therefore kAk < 6t 6. 30Chapter 3 Families With a Linear Bound In the previous chapter, we presented a characterization of nite 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 con gurations with a quadratic bound and determine which families of these con gurations yield a linear bound. 3.1 Families of minimal quadratic con gurations In our search for families with a linear bound, we rst consider a list of minimal con- gurations 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 0 F and F 0 6= F , then forb(m;F 0) is O(m). In a sense, these are the con gurations \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 con gurations and this expectation was correct. We will focus our attention on families of size 2 from Table 3.1. By our charac- terization 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 31Con guration Bound Construction(s) Reference F1 0 0 0 0 m 2 + m 1 + m 0 Ic Ic [16] F2 1 1 1 1 m 2 + m 1 + m 0 I I [16] F3 0 0 0 1 1 1 0 1 1 0 0 1 bm 2 4 c+m+ 1 I I c [3] F4 2 4 0 0 0 3 5 m 2 + m 1 + m 0 Ic Ic [20, 21, 23] F5 2 4 1 0 0 0 1 0 0 0 1 3 5 m 2 + m 1 + m 0 I c Ic Ic T T T [19] F6 2 4 0 1 1 1 0 1 1 1 0 3 5 m 2 + m 1 + m 0 I I I T T T [19] F7 2 4 1 0 0 1 0 1 1 0 0 0 1 1 3 5 bm 2 4 c+m+ 1 T T [1] F8 2 4 1 1 1 3 5 m 2 + m 1 + m 0 I I [20, 21, 23] F9 2 6 6 4 1 0 1 0 0 1 0 1 3 7 7 5 m 2 + 2m 1 I T Ic T [15] Table 3.1: Minimal Quadratic Con gurations 32Pairs of con gurations with a con- stant bound by Theorem 2.1.1. fF1; F2g, fF1; F6g, fF1; F8g,fF2; F4g, fF2; F5g, fF4; F6g, fF5; F8g Pairs of con gurations with an (m2) construction. fF1; F4g, fF1; F5g, fF2; F6g, fF2; F8g, fF4; F6g, fF4; F8g, fF5; F6g, fF5; F7g, fF5; F9g, fF6; F7g, fF6; F8g, fF6; F9g, Pairs of con gurations known to have bound (m). fF1; F3g, fF1; F7g, fF1; F9g, fF2; F3g, fF2; F7g, fF2; F9g, fF3; F4g, fF3; F5g, fF3; F6g, fF3; F7g, fF3; F8g, fF3; F9g, fF4; F7g, fF4; F9g, fF7; F8g, fF7; F9g, fF8; F9g Table 3.2: Pairs of Minimal Quadratic Con gurations bound is also linear. See row 1 of Table 3.2. Furthermore, we note that some families of the con gurations in Table 3.1 will continue to have a quadratic bound. Any family of con gurations 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 con gurations in Table 3.1 was as follows: attempt to determine the upper bound for families which neither fall under our constant family classi cation, nor families where a quadratic product construction avoids all con gurations in the family. Such families are listed in row 3 of Table 3.2. 3.1.1 Families proved using basic methods The rst three considered families all contain the con guration F7 and have similar proofs. Proposition 3.1.1. We have forb(m; fF4; F7g) = forb(m; fF7; F8g) 2m. Proof. It su ces to show that forb(m; fF4; F7g) 2m. Let A 2 Avoid(m; fF4; F7g). In a standard decomposition of A using row r, Cr must avoid I2 and 0 0 . 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 0 0 , 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 kCrk 2, and by standard 33induction kAk 2m. A construction of Ic 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; fF1; F7g) = forb(m; fF2; F7g) 2m. Proof. It su ces to show that forb(m; fF2; F7g) 2m. Let A 2 Avoid(m; fF2; F7g). 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 kCrk 2 and thus by standard induction kAk 2m. A construction of Ic 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; fF3; F7g) 3m. Proof. Let A 2 Avoid(m; fF3; F7g). 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 kCrk 3 and by standard induction kAk 3m. Any of I; Ic 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; fF3; F4g) = forb(m; fF3; F8g) 3m+ 1. Proof. It su ces to show that forb(m; fF3; F8g) 3m+1. LetA 2 Avoid(m; fF3; F8g). 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 con guration 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 34us 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 su ces to have more than 2(m 1) edges to nd an edge not going through i; j. Thus a bound of 2m+m+ 1 = 3m+ 1 su ces for forb(m; fF3; F8g). Proposition 3.1.5. We have forb(m; fF3; F5g) and forb(m; fF3; F6g) being O(m). Proof. It su ces to show forb(m; fF3; F5g) is O(m). Let A 2 Avoid(m; fF3; F5g. Then applying our decomposition seen in (1.1), we deduce that Cr has no con gu- rations [0 0 1 1] or I3. Let R(r) denote a minimal set of rows of Cr such that CrjR(r) is simple and in particular kCrk = kCrjR(r)k. We deduce that CrjR(r) has no row of all 0’s nor a row of all 1’s nor a repeated row. Assume CrjR(r) has at least 3 rows each of row sum 1. Then we deduce that I3 CrjR(r). Thus we deduce that some row s of CrjR(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 1 0 , else A has F3. This works for every row r 2 [m]. Consider a directed graph where for each row r we have a di- rected 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 column containing aiai+1 1 0 for i = 1; 2; : : : ; t 1 and at most one column containing ak a1 1 0 . We now verify that apart from t columns, all columns of Ajfa1;a2;:::;atg are 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; fF3; F5g) t+ forb(m t+ 1; fF3; F5g). 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; fF1; F3g) = forb(m; fF2; F3g) 2m Proof. We take the case of fF1; F3g. Let A 2 Avoid(m; fF1; F3g). In order to avoid F1, on each pair of rows in A must contain at most one 0 0 while to avoid F3, each pair of rows must have no 0 0 or no 1 1 or at most 1 1 0 . In the case where all pairs of rows have no 0 0 or no 1 1 , then the result follows from Theorem 1.3.1. In the case where a pair of rows has only one 1 0 and therefore, only one of 0 0 , we have that every pair of rows has two columns in short supply. By the result of Anstee and 35Fleming (Theorem 1.4.1), we can nd 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 2 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: Ti Si Ai Bi Ci 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 1 0 : : : 0 0 1 : : : 0 ... ... . . . ... 0 0 : : : 1 1 1 : : : 1 ... ... 1 1 : : : 1 0 0 : : : 0 ... ... 0 0 : : : 0 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5 or Ai Bi Ci 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 0 1 : : : 1 1 0 : : : 1 ... ... . . . ... 1 1 : : : 0 1 1 : : : 1 ... ... 1 1 : : : 1 0 0 : : : 0 ... ... 0 0 : : : 0 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 5 (3.1) Note that for the columns of Ti, jBij = i 1 and for Si, jBij = i (jAij 1). Also kTik = jAij and kSik = jAij. We will use this structure and its properties in the proofs that follow. Proposition 3.1.7. We have forb(m; fF5; F6; F9g) 2m. Proof. Let A 2 Avoid(m; fF5; F6; F9g). 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 kAk is 2m. Proposition 3.1.8. We have forb(m; fF1; F9g) = forb(m; fF2; F9g) = 2m+ 1. 36Proof. It su ces to show forb(m; fF1; F9g) = 2m+ 1. Let A 2 Avoid(m; fF1; F9g). 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 jAm 2j = m 1, structure Sm 1 with jAm 1j = 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; fF1; F9g) = 2m+ 1. Proposition 3.1.9. We have forb(m; fF4; F9g) = forb(m; fF8; F9g) = 2m. Proof. It su ces to show that forb(m; fF4; F9g) = 2m. Let A 2 Avoid(m; fF4; F9g). 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 jAm 2j = m 1, the structure Sm 1 with jAm 1j = m and the column 1m, yielding 2m columns total. Proposition 3.1.10. We have forb(m; fF7; F9g) is O(m). Proof. Let A 2 Avoid(m; fF7; F9g). 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 kAk 2m+ kATk+ kASk, where there at most 2 columns of column sum i not in AT or AS. It su ces to show that kATk 2m; we will then know kASk 2m by taking (0; 1)-complements, as F c7 is F7 and F c 9 is F9. Note that for all i where columns of sum i are inAT , kTik is bounded by the number of rows containing the identity, or jAij. Thus, in order to show that forb(m; fF7; F9g) is O(m), it su ces to show that P jAij is O(m). If Ai \ Aj = ; for all pairs i; j then P i jAij = m and we are done. Now suppose there are i; j column sums with i > j such that Ai \ Aj 6= ;. Then jAi \ Ajj < 2. Suppose not. Then there are two rows in Ai \Aj that contain [I2jI2] on the columns of sum i and j. Furthermore, because i > j, jBij > jBjj, so there is some row b 2 Bi, b 62 Bj. Therefore b must be all 10s in the columns of column sum i and mostly 0’s in 37the columns of column sum j. Combining row b with the rows in the intersection of Ai \ Aj, we create F7, a contradiction. So jAi \ Ajj = 1. We now consider Bi; Bj where jBij > jBjj. If BjnBi 6= ; then BinBj 6= ;. We nd a copy of F7 on rows p; q; r where p = Ai \Aj, q 2 BjnBi and r 2 BinBj. 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 = fag, (a row index) and Ai \ Ak = fbg. If a 6= b, then for some c 2 BinBj, we nd 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 kATk 2m by induction on m. In particular the sets At for t of type T , have the properties that jAij 3 and jAi \ Ajj 1. They can be ordered by the index i so that if we have three indices i > j > k and Ai \ Aj = fag and Ai \ Ak = fbg, 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]n(Aina) have the same properties so we can apply induction. Thus P t jAtj = jAij+ 2(m jAij+ 1) 2m. Theorem 3.1.11. We have that forb(m; fF3; F9g) is O(m). Proof. We establish that forb(m; fF3; F9g) 12m. Let A 2 Avoid(m; fF3; F9g). 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 kAk 2m + kATk + kASk, where there at most 2 columns of column sum i not in AT or AS. We will show kATk 5m and then we deduce kASk 5m by taking (0,1)-complements (we note that F c3 is F3 and F c 9 = F9 as con gurations). This yields the bound. We have that kATk = P i jAij 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 jBinBjj 2. Else let p; q 2 BinBj. Then since jAjj 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 jBinBjj 1. Now assume P i jAij 5m. Then there is a quintuple i1 < i2 < i3 < i4 < i5 38with some row r 2 Ai1 \ Ai2 \ Ai3 \ Ai4 \ Ai5 . We will consider i1; i3; i5. We have jBi3j jBi5j 2 and so let s; t 2 Bi5nBi3 . Now jBi1j jBi3 j 2 and yet jBi1nBi3j 1. Thus without loss of generality we may assume s 62 Bi1 . We now claim that we have F3 in rows r; s. In the columns of sum i5 with r 2 Ai5 and s 2 Bi5 we nd r s " 0 0 1 1 1 1 # : Now in both the columns of sum i1 and also in columns of sum i3, we may nd r s " 0 1 0 0 # ; using the fact that i1 =2 Bi1 and i3 62 Bi3 . This yields a copy of F3 and so we may deduce P i jAij 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; fIk; Tkg) is (mk 2) From this theorem we can conclude the following. Corollary 3.2.2. We have that forb(m; fI3; T3g) is O(m). Note that Conjecture 1.3.5 states that for single con gurations, if forb(m;F ) is (mk), then there is a construction that avoids F consisting of a k-fold product of three matrices: I; Ic and T . Thus, if this conjecture were true for forbidden families, if a family of con gurations was contained in all possible two-fold products of I; Ic and T , then its bound would have to be linear. The conjecture remains unproven (and likely requires a di erent 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. 39Chapter 4 Families With a Super-linear Bound The rst section of this chapter will contain a proof that re nes a previous result, showing that a certain family of matrices de ned 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 Unexpected bound for product con gurations 4.1.1 Introduction Conjecture 1.3.5 implies that for a single forbidden con guration, 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 con gurations, 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 2 Avoid(m;13) will be a matrix with up tom+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 = jV (H)j and q = jE(H)j. Let I(H) denote the p q vertex-edge incidence matrix associated with H. 40Remark 4.1.1. forb(m; f13; I(H)g) = m+ 1 + ex(m;H). We rst 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; f13; C4g) = 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 = " 1 0 0 1 # ; T2 = " 1 1 1 0 # ; I2 I2 = 2 6 6 6 6 4 1 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 3 7 7 7 7 5 ; T2 T2 = 2 6 6 6 6 4 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 3 7 7 7 7 5 ; I2 T2 = 2 6 6 6 6 4 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 3 7 7 7 7 5 : A preliminary version of [7] contained Theorem 1.3.14, which proved that forb(m; fI2 I2; T2 T2; I2 T2g) is (m3=2). However, a closer examination of this family re- vealed that while there are (m2) constructions for the families fI2 I2; I2 T2g and fT2 T2; I2 T2g, the best construction that could be achieved for the family fI2 I2; T2 T2g 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 = fI2 I2; T2 T2; I2 T2g. 4.1.2 Theorem and proof Theorem 4.1.3. We have forb(m; fI2 I2; T2 T2g) 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 con gurations I2 I2 and T2 T2, when performing the 41standard decomposition using any row r in A, then Cr cannot contain the following inductive children: F1 = 2 6 4 1 1 1 0 1 1 3 7 5 ; F2 = 2 6 4 1 0 1 0 0 1 0 1 1 1 0 0 3 7 5 : Con guration F1 in Cr will produce T2 T2 and con guration F2 in Cr will produce I2 I2. Lemma 4.1.4. We have forb(m; fF1; F2g) 2m. Proof. Let A0 2 Avoid(m; fF1; F2g) be a simple matrix. We proceed by standard induction. In order to avoid F2, the columns of C 0 must avoid its inductive child, I2. This implies that the columns of C 0 must be pairwise comparable (recall the de nitions of Section 1.2.4), creating a tower matrix. By de nition, C 0 is simple so all the columns must be unique. If kC 0k 3, there will be an F1 contained in two of the columns. Thus kC 0k 2, and by induction A0 has at most 2m columns. It is worth nothing that in order to achieve the bound of kC 0k = 2 in the previous proof, it is necessary for the columns in C 0 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 0 is empty. De nition 4.1.5. Let A, r, be given with the decomposition (1.1). If there is a row r0 in a subset of rows S [m] such that r0 can be deleted and simplicity maintained in CrjSnr0, then we call r0 deletable. De nition 4.1.6. Let A, r, be given with the decomposition (1.1). We de ne R(r) 2 [m] to be a minimal set of rows with the property that CrjR(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 De nition 4.1.6, we have that jR(r)j kCrk=2. 42Proof. Consider the matrix CrjR(r). Note that kCrjR(r)k = kCrk. We know that CrjR(r) must avoid fF1; F2g (because Cr avoids fF1; F2g) and so by Lemma 4.1.4, kCrjR(r)k 2jR(r)j, which becomes jR(r)j kCrk=2, as desired. Lemma 4.1.8. Let A, r, be given with the decomposition (1.1). Given R(r) as described in De nition 4.1.6, we can choose a set of rows S(r) R(r) such that CrjS(r) contains IjS(r)j and jS(r)j jR(r)j=2. Proof. We choose R(r) as described for the proof of Lemma 4.1.7. Let s 2 R(r) and perform the standard decomposition of CrjR(r) using row s into Es; Gs; and Hs; see (4.1) CrjR(r) = s R(r) n s " 0 : : : 0 1 : : : 1 Es Gs Gs Hs # : (4.1) This scenario is analogous to the situation in Lemma 4.1.4, with CrjR(r) as A0, Es as B0, Gs as C 0 and Hs as D0. 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 CrjR(r), a contradiction to how we chose R(r). Thus, in the matrix CrjR(r), each row s 2 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 CrjR(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 IjS(r)j CrjS(r) and jS(r)j jR(r)j=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 de ne D to be a directed graph, where there is an directed edge from vertex s ! t if in the decomposition of CrjR(r) based on row s, Case 2 occurs. We de ne the set T as the set of all rows t 2 R(r) such that CrjR(r) has a column of column sum 1 with a 1 in row t. Let U = R(r) n T . For each edge u 2 U , there is an edge u ! v, where, by our choice of T , v 2 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 = fv 2 T : there is a u 2 U with u! vg. Finally, we de ne S(r) = U [ (T n V ). In words, we have chosen a subset of rows in R(r), where each row is associated with 43a 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 rst set (T n V ). Thus each row in S(r) is associated with a distinct column of column sum 1 and so CrjS(r) contains an IjS(r)j, potentially with some extra or repeated columns. We can con rm that jS(r)j jR(r)j=2 by noting that in fact S(r) = U [ (T n V ) = R(r) n V , so jS(r)j = jR(r)j jV j, and as jV j jU j, this gives jS(r)j jR(r)j=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; fI2 I2; I2 T2; T2 T2g) 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 which consists of p2 + p + 1 subsets each in [p2+p+1] p+1 such that for any two subsets L1; L2, we have jL1\L2j = 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 2 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 fI2 I2; I2 T2; T2 T2g, it also avoids the family of our theorem fI2 I2; T2 T2g. Thus forb(m; fI2 I2; T2 T2g) is (m3=2). It remains to show that the bound is tight, i.e., that forb(m; fI2 I2; T2 T2g) is O(m3=2). If we perform the standard decomposition on A, we would be done by induction if we could show that kCrk cm1=2 for some row r and some constant c. For this proof, we will use c = 20. We will assume kCrk 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 jS(r)j kCrk=4. Then we show that we can choose a set Q S(r) 44with jQ(r)j jS(r)j=3 such that for every choice rp; rq 2 Q we have jS(rp)\S(rq)j 5. Thus for t = 5=3m1=2 choices r1; r2; : : : ; rt 2 S(r) we show that jS(ri) \ S(rj)j < 6 and so obtain disjoint sets of rows S(r1); S(r2)nS(r1); S(r3)n(S(r1) [ S(r2)); : : : S(rt)n(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 kCrk > 20m1=2. We rst choose a set of rows R(r) [m] as described in De nition 4.1.6. By Lemma 4.1.7 we know that jR(r)j kCrk=2. We continue by choosing a set of row S(r) R(r) as described in Lemma 4.1.8; again, we know that jS(r)j jR(r)j=2, thus jS(r)j kCrk=4, and by our choice of S(r), we know that CrjS(r) contains an IjS(r)j. We now focus our attention on the matrix AjS(r). In particular, if we perform the standard decomposition on A using a row rj 2 S(r), we wish to know what happens on the columns of Crj jS(r)nrj . Let rj 2 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 jS(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) n rj). We thus have columns in Crj as follows: rj S(r) n rj r 2 6 4 0 1 a a 3 7 5 : (4.2) We now consider AjS(r) in this arrangement. We will extract two conclusions from the structure in (4.2), rst 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 [BrCr] 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 45two non-zero choices for , say 6= . We have the following situation for columns in Crj : rj S(r)nrj f r 2 6 4 0 0 1 1 0 0 0 0 3 7 5 : (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 [BrCr]jS(r). Columns 3 and 4 have 1’s in common on row rj and we deduce without loss of generality that and 6= . Now, considering columns 2; 3, and the fact that 0 6= , 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 r0 the columns of Crj must di er, yielding the following, with T2 T2 on the rst three rows plus row r0. rj S(r) n rj r0 2 6 6 6 6 6 6 4 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 1 3 7 7 7 7 7 7 5 : We prove a slightly di erent 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) n rj. Suppose there are two non-zero columns ; in Crj jS(r)nrj . rj S(r)nrj f r 2 6 4 0 1 0 1 1 1 1 1 3 7 5 : Now suppose and both have entry 1 on some row r0 2 S(r) n rj. Also, like above, because A is a simple matrix, there is some row r00 (r00 6= r; r0; rj) where the 46columns of Crj di er. The situation is then as follows: rj r0 S(r) n (rj [ r0) r00 r 2 6 6 6 6 6 6 4 0 0 1 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 1 1 3 7 7 7 7 7 7 5 : This creates a T2 T2, therefore all of our non-zero columns in Crj jS(r)nrj , 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 jS(r), where rp 2 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 CrpjS(r) must be disjoint. We now use these facts to consider what occurs in the rows of Crp jS(r)nrp (denoted X below). On the columns of Crp with a 0 in row r, we have two cases for the rows of S(r)nrj. If is of size 1 and repeated, there will be one \bad" row, say rs 2 S(r) n 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)n rp will have at most one 1. Thus for all rows in S(r) n 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) n rj will contain only one 1 each. We can now show that once we choose rp 2 S(r) for all but one rq 2 S(r) n rp, jS(rp) \ S(rq)j < 6. We decompose the matrix A based on row rp 2 S(r): Crp Crp rp S(r) n rp " 0T 1T X X # : 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 rst using rp and 47then using rq. Crp Crp Crq Crq rp rq S(rp) \ S(rq) 2 6 4 1 0 T T I I 3 7 5 ; rp rq S(rp) \ S(rq) 2 6 4 T T 1 0 I I 3 7 5 : 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 nd 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 di erent entries on rp and rq. When put together they create an I2 I2. Therefore jS(rp) \ S(rq)j 5. We nally 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 2 R(r), we say row q 2 R(r) n 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 2 (s(r) there is at most one bad row s 2 S(r). Then there is a set of rows Q S(r) such that jQj jS(r)j=3 and for any pair of rows rp; rq 2 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 jS(r)j 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 v0 2 V such that v0 has in-degree 0. Let G0 be the induced subgraph of G n v0. Directed graph G0 maintains our property of maximum out-degree 1, so we color G0 with 3 colors and then add v0 back with an appropriate color. Suppose there is no vertex v 2 V with in-degree 0. In this case all vertices 48have 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 [BrCr] 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 com- pute what is missing on any quadruple of rows in A in order to avoid I2 I2 and T2 T2. There are ve possibilities, and on any quadruple of rows in A, one must apply. Q0 = no no no 2 6 6 6 6 4 0 1 0 1 3 7 7 7 7 5 2 6 6 6 6 4 0 0 1 1 3 7 7 7 7 5 2 6 6 6 6 4 1 1 1 1 3 7 7 7 7 5 ; Q1 = no no no no no 2 6 6 6 6 4 0 1 0 1 3 7 7 7 7 5 2 6 6 6 6 4 1 1 0 1 3 7 7 7 7 5 2 6 6 6 6 4 0 0 1 1 3 7 7 7 7 5 2 6 6 6 6 4 1 0 1 1 3 7 7 7 7 5 2 6 6 6 6 4 0 1 1 1 3 7 7 7 7 5 ; Q2 = no no no no 2 6 6 6 6 4 1 1 1 0 3 7 7 7 7 5 2 6 6 6 6 4 0 1 0 1 3 7 7 7 7 5 2 6 6 6 6 4 0 0 1 1 3 7 7 7 7 5 2 6 6 6 6 4 1 0 1 1 3 7 7 7 7 5 ; Q3 = no no no no 2 6 6 6 6 4 1 1 1 0 3 7 7 7 7 5 2 6 6 6 6 4 1 0 0 1 3 7 7 7 7 5 2 6 6 6 6 4 0 1 0 1 3 7 7 7 7 5 2 6 6 6 6 4 0 0 1 1 3 7 7 7 7 5 ; Q4 = no no no no no no 2 6 6 6 6 4 1 1 0 0 3 7 7 7 7 5 2 6 6 6 6 4 1 0 1 0 3 7 7 7 7 5 2 6 6 6 6 4 0 1 1 0 3 7 7 7 7 5 2 6 6 6 6 4 1 0 0 1 3 7 7 7 7 5 2 6 6 6 6 4 0 1 0 1 3 7 7 7 7 5 2 6 6 6 6 4 0 0 1 1 3 7 7 7 7 5 : 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 nd a copy of \K2" in what is missing. That is, if on the triple i; j; k, there is a pair 49of rows i; j with all 4 columns of K2 appearing as follows: i j k no 2 6 4 0 0 a 3 7 5 no 2 6 4 0 1 b 3 7 5 no 2 6 4 1 0 c 3 7 5 no 2 6 4 1 1 d 3 7 5 where a; b; c; d 2 f0; 1g, 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 j k 2 6 4 0 0 a 3 7 5 2 6 4 0 1 b 3 7 5 2 6 4 1 0 c 3 7 5 2 6 4 1 1 d 3 7 5 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. P0 = no no no 2 6 4 1 0 1 3 7 5 2 6 4 0 1 1 3 7 5 2 6 4 1 1 1 3 7 5 or no no no 2 6 4 0 0 1 3 7 5 2 6 4 0 1 1 3 7 5 2 6 4 1 1 1 3 7 5 or no no no 2 6 4 0 1 1 3 7 5 2 6 4 0 0 1 3 7 5 2 6 4 1 1 1 3 7 5 or no no no 2 6 4 0 1 0 3 7 5 2 6 4 0 0 1 3 7 5 2 6 4 1 1 1 3 7 5 50P1 = no no no no no 2 6 4 1 0 1 3 7 5 2 6 4 1 0 1 3 7 5 2 6 4 0 1 1 3 7 5 2 6 4 0 1 1 3 7 5 2 6 4 1 1 1 3 7 5 P2 = no no no 2 6 4 1 1 0 3 7 5 2 6 4 1 0 1 3 7 5 2 6 4 0 1 1 3 7 5 or no no no 2 6 4 1 1 0 3 7 5 2 6 4 0 1 1 3 7 5 2 6 4 1 1 1 3 7 5 : These then, are the possibilities for what is missing in A, including AjS(r). Because we know that the columns of A contain an identity matrix on the rows S(r) we know that the nal three cases of P0 and the second set of case of P2 can not be what is missing on for AjS(r). Among the remaining options for what is missing (the rst 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 [BrCr] must form a laminar family. 4.2 A similar bound for larger product con gura- tions Extending the previous result, we considered another family of con gurations 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, Ic, and T . In this case, we used the following three con gurations: 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 Ic3. We then forbid all possible products of these sub-con gurations, namely the family fE1 E1; E1 E2; E1 E3; E2 E2; E2 E3; E3 E3g. If only ve of these products are forbidden, there is a product construction of size (m2) that avoids the ve 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 = fEi Ej : i; j = 1; 2; 3g we have forb(m;F) 51is (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 2 Avoid(m;F). Then using the decomposition shown in (1.1), Cr cannot contain the following inductive children of our family: F1 = 2 6 4 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 0 0 1 3 7 5 ; F2 = 2 6 4 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1 0 0 1 3 7 5 ; F3 = 2 6 4 0 0 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 3 7 5 : Similarly to the last proof, we have two lemmas relating to the inductive children and rows of A. Lemma 4.2.2. We have forb(m; fF1; F2; F3g) 2m. Proof. Let A0 2 Avoid(m; fF1; F2; F3g) be a simple matrix. We proceed by standard induction. In order to avoid fF1; F2; F3g, the columns of C 0 must avoid the sub- con gurations E1; E2 and E3. But because E1 I3, E2 T3 and E3 Ic3, by Lemma 1.3.20, kC 0k must be constant. A simple pigeonhole argument proves that kC 0k 2. Using De nition 4.1.6 as in the previous proof, we de ne R(r) 2 [m] to be a minimal set of rows with the property that CrjR(r) is simple, with no deletable rows. The result of Lemma 4.1.7 again applies to jR(r)j, so jR(r)j kCrk=2. Similarly to the previous proof, we want to show that for all r, kCrk 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 kCrk 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 jS(r)j cjR(r)j and CrjS(r) contains either a IjS(r)j; TjS(r)j; or 52IcjS(r)j. 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 2 [m], there must be at least a third of the rows in [m] such that S(r) contains IjS(r)j, a third of rows such that S(r) contains TjS(r)j; or a third of rows in S(r) contain IcjS(r)j. Thus without loss of generality, we can choose a set Q(r) [m] of size (m1=2) such that for all r 2 Q(r) CrjS(r) contains a IjS(r)j. We now consider the standard decomposition of A based on rows rp; rq 2 Q(r). Suppose jS(rp) \ S(rq)j 5. If we decompose A based on rp (and then rq), we have the following: Crp Crp rp rq S(rp) \ S(rq) 2 6 4 00 : : : : : : 00 0 : : : 0 1 : : : 1 I I 11 : : : : : : 11 0 : : : 0 1 : : : 1 I I 3 7 5 : Using our assumption about jS(rp)\ S(rq)j, and the pigeonhole principle, we can assume that one of the two following con gurations will occur in the above decom- position: rp rq S(rp) \ S(rq) 8 < : 2 6 6 6 6 6 6 4 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 3 7 7 7 7 7 7 5 or rp rq S(rp) \ S(rq) 8 < : 2 6 6 6 6 6 6 4 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 3 7 7 7 7 7 7 5 : (4.4) We now consider a decomposition again using rp and rq; however, this time the decomposition begins with rq. Crq Crq rp rq S(rp) \ S(rq) 2 6 4 0 : : : 0 1 : : : 1 00 : : : : : : 00 I I 0 : : : 0 1 : : : 1 11 : : : : : : 11 I I 3 7 5 : Note that the columns of Crq with a 1 in row rq will be disjoint from the columns 53of the rst con guration in (4.4) and the columns of Crq will be disjoint from the columns of the second con guration in (4.4). Now the columns of Crq with a 1 in row rq will be forced to contain one of the following con gurations: rp rq S(rp) \ S(rq) 8 < : 2 6 6 6 6 6 6 4 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 3 7 7 7 7 7 7 5 or rp rq S(rp) \ S(rq) 8 < : 2 6 6 6 6 6 6 4 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 3 7 7 7 7 7 7 5 : (4.5) These con gurations are both disjoint from the rst con guration in (4.4) and thus, taken together, produce either an E1 E1 in the rst 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 jS(rp) \ S(rq)j 4. Finally, we consider the following sequence of sets. We assume that jS(r)j > Km1=2 for some suitably large K. For all ri 2 S(r), we form disjoint sets S 0(ri) as follows: S 0(ri) = S(ri) n i 1X j=1 S(rj): Note that S 0(ri); S 0(rj) are disjoint for all ri; rj 2 Q(r). We then consider the size of these sets: jS 0(r1)j+ jS 0(r2)j+ jS 0(r3)j+ + jS 0(rt)j; 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. 54Chapter 5 A Case Study: Families of 2 x 2 Con gurations When rst investigating families of forbidden con gurations, we chose to take the set of all seven 2 2 con gurations (described and indexed in Table 5.1) and nd forb(m;F) for all 27 1 non-trivial families of these con gurations, with the goal of using these families as case studies for other families with larger con gurations. Con guration Bound Construction Contained in F1 0 0 0 0 m 2 + m 1 + m 0 Icm I c m I4; T4 F2 1 0 0 0 m+ 1 [Icmj1] I3; T3 F3 1 1 0 0 m+ 2 [Imj0j1] or [Icmj0j1] T3 F4 1 0 1 0 m+ 1 [Imj0] or [Icmj1] T3 F5 1 0 0 1 m+ 1 [Tmj0] I2; Ic2 F6 0 1 1 1 m+ 1 [Imj0] T2; Ic3 F7 1 1 1 1 m 2 + m 1 + m 0 Im Im T3; Ic4 Table 5.1: List of 2 x 2 Con gurations 55These 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 classi cation of families. The rst is Theorem 2.1.1, which allows us to identify families with a constant bound. For example, the family fF1; F7g has the property that F1 I4, F7 T3, and F7 Ic4 and thus by Theorem 2.1.1 forb(m; fF1; F7g) is O(1). There are many pairs of con gurations that have this property and thus a constant bound. They are as follows: fF1; F5g; fF1; F6g; fF1; F7g; fF2; F5g; fF2; F6g; fF2; F7g; fF3; F5g; fF4; F5g; fF5; F6g; fF5; F7g: (5.1) Now by Remark 1.3.19, we know that forb(m;F) must be no larger than forb(m;F 0) for all F 0 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 con gurations that have a constant bound. We will prove bounds for ten minimal families of con gurations 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; fF1; F5g) = forb(m; fF3; F5g) = forb(m; fF5; F7g) = 3. Proof. Let A 2 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 ; 2 A, or . Thus our matrix will be a selection of columns chosen from the triangular matrix [Tmj0]. If we we choose four or more columns from this matrix, on some subset of rows there will be a T4 or [T3j0], both of which contain F1; F3; and F7. Thus the bound must be less than 4. The following constructions achieve the bound 56of 3: fF1; F5g : 2 6 6 6 6 4 1 1 0 1 0 0 0 0 0 ... ... ... 3 7 7 7 7 5 fF4; F5g : 2 6 6 6 6 4 1 1 0 1 0 0 ... ... ... 1 0 0 3 7 7 7 7 5 or 2 6 6 6 6 4 1 0 0 1 1 0 ... ... ... 1 1 0 3 7 7 7 7 5 : The construction for fF5; F7g is the complement of the construction for fF1; F5g, per Remark 1.3.16. Proposition 5.1.2. We have forb(m; fF4; F5g) = forb(m; fF2; F5g) = forb(m; fF5; F6g) = 2. Proof. Let A 2 Avoid(m;F), for one of the families above. Similarly to the previ- ous proof, in order to avoid F5, A will be taken from columns of the triangular matrix [Tmj0]. But any three columns chosen from [Tmj0] will include the submatrices T3 or [T2j0], both of which contain F2; F4, and F6. Thus the bound must be less than 3. The constructions that achieve the bound of for fF4; F5g are as follows: 2 6 6 6 6 4 1 0 0 0 ... ... 0 0 3 7 7 7 7 5 or 2 6 6 6 6 4 0 1 1 1 ... ... 1 1 3 7 7 7 7 5 : The construction that achieves the bound of 2 for fF2; F5g; fF5; F6g is [1j0]. Proposition 5.1.3. Let m 7. Then forb(m; fF1; F7g) = 2. Proof. For proof of this bound, see Section 2.3 and Theorem 2.3.4. For any column , a construction of [ j c] achieves the bound. Proposition 5.1.4. We have forb(m; fF2; F6g) = 2. Proof. Let A 2 Avoid(m; fF2; F6g). Suppose our matrix A has 3 columns. Without loss of generality, we can suppose the rst 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; fF2; F6g) < 3. For any column , a construction of [ j c] achieves the bound. 57Proposition 5.1.5. We have forb(m; fF1; F6g) = forb(m; fF2; F7g) = 2. Proof. We will demonstrate the argument for forb(m; fF1; F6g; forb(m; fF2; F7g follows by Remark 1.3.16. Let A 2 Avoid(m; fF1; F6g. Suppose our matrix A has 3 columns. Suppose that the rst row has two 1s and one 0. Then A cannot avoid F6 by the same argument as the previous family. Now suppose the rst row has one 1 and two 0s. We consider the two columns and containing the 0s. After the rst row, [ j ] cannot contain [00] on any row, otherwise A will contain F1. In addition, because A is simple, on some row [ j ] must contain [01]. Therefore [ j ] can never contain [11] on a row (to avoid F6). In the row containing [10] in columns [ j ], 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 2 Avoid(m; fF1; F6g) with 3 columns is not possible and forb(m; fF1; F6g < 3. For any column , a construction of [ j c] achieves the bound. Proposition 5.1.6. For m 5, We have forb(m; fF1; F4; F6g) = forb(m; fF1; F4; F7g) = forb(m; fF2; F4; F6g) = forb(m; fF2; F4; F7g) = 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 fF1; F4; F6g, 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 con gurations 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 con gurations 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 58F2; F3; : : : F6. The only family with the potential to have a greater than linear bound would be the two con gurations with a quadratic bound, namely fF1; F7g, 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 con gurations that do not have a constant bound must have a linear bound, i.e. are (m). Carefully examining the list of pairs of con gurations that give a constant bound, we nd that the only families of 2 2 con gurations that do not contain a family from our list of constant-bounded families (5.1) are the families fF1; F2; F3; F4g or fF3; F4; F6; F7g 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 con gurations that do not yield a constant bound. These pairs are contained in the family of either fF1; F2; F3; F4g or fF3; F4; F6; F7g, or alternatively, are not contained in (5.1)). fF1; F2g; fF1; F4g; fF2; F3g; fF2; F4g; fF3; F4g (5.2) fF3; F4g; fF3; F6g; fF4; F6g; fF4; F7g; fF6; F7g (5.3) fF1; F3g; fF3; F7g (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 con guration 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 achieves the bound. In the case of families in (5.2), the matrix [Icmj1] avoids each pair of con gurations, as well as any union of them. Similarly, for families in (5.3), the matrix [Imj0] avoids each family and any union of them. Remark 5.2.2. The families in (5.4) have a bound of m+ 2. Each con guration individually has a bound of m+2, enforcing a maximum upper bound of m+2 (again by Remark 1.3.19) and the con gurations [Icmj1j0] and [Imj1j0] achieve this bound by avoiding fF1; F3g and fF3; F7g respectively. 595.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 con g- urations. Given such a family F , the rst 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) Construction Proof fF1; F4; F6g; fF1; F4; F7g; fF2; F4; F6g; fF2; F4; F7g 1 any column Proposition 5.1.6 fF1; F7g 2 [ j c] Theorem 2.3.4 fF2; F6g 2 [ j c] Proposition 5.1.4 fF1; F6g; fF2; F7g 2 [ j c] Proposition 5.1.5 fF2; F5g; fF4; F5g; fF5; F6g 2 Proposition 5.1.2 Proposition 5.1.2 fF1; F5g; fF3; F5g; fF5; F7g 3 Proposition 5.1.1 Proposition 5.1.1 fF1; F2g; fF1; F4g; fF2; F3g; fF2; F4g; fF3; F4g m+ 1 [Icj1] Remark 5.2.1 fF3; F4g; fF3; F6g; fF4; F6g; fF4; F7g; fF6; F7g m+ 1 [Ij0] Remark 5.2.1 fF1; F3g m+ 2 [Icmj0j1] Remark 5.2.2 fF3; F7g m+ 2 [Imj0j1] 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 con gurations. When forbidding a single con guration F , the con- guration may have a subcon guration F 0 F such that forb(m;F 0) = forb(m;F ). If this F 0 is minimal, that is, if for all F 00 F 0, forb(m;F 00) < forb(m;F ), F 0 is called a critical substructure of F [6]. Such a sub-con guration is called critical, because the larger con guration’s bound somehow depends on the bound of this substructure and its presence in the larger con guration. 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; Ic4; K 2 4 ; [2 03]; [2 13]. 60This 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 0 F is called a critical subfamily if forb(m;F 0) = forb(m;F) and F 0 is minimal, that is, for all F 00 F 0, forb(m;F 00) > forb(m;F). This de nition can also be seen as a further re nement 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 fF1; F2; F3; F4g has a bound of m + 1, with critical subfamilies fF2g, and fF4g, as they each also have a bound of m+ 1. Our implicit classi cation of all families of 2 2 con gurations 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; fC3; C4; C5; : : : g) and forb(m;C3) = forb(m; fC3; C5; C7; : : : g). Thus fC3g is a critical subfamily of fC3; C4; C5; : : : g and fC3; C5; C7; : : : g. 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 fF1; F7g, forb(m; fF1; F7g) is constant. However, the only subfamilies of fF1; F7g are the single con gurations fF1g and fF7g, both of which have a quadratic bound. Thus the bound in this case arises from the interaction of the two con gurations and Theorem 1.3.6, not the bound of a critical subfamily. 61Chapter 6 Conclusion 6.1 Summary of results The rst type of result in this paper is a classi cation, seen in Chapter 2 where we classify all families with a constant bound. While the classi cation theorem is based on a result not original to this paper, its conjecture and proof is a strong statement both about families of forbidden con gurations and the interaction of the three key matrices of Conjecture 1.3.5. First, the classi cation 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, that somehow the matrices Im; Icm and Tm are integral to understanding forbidden con gurations. However, the bulk of this paper has been devoted to establishing and proving both exact and asymptotic bounds for speci c families of forbidden con gurations. It is by no means an exhaustive survey, and we did not reach any other grand classi cation schemes; however, many of our results present interesting aspects of the forbidden con guration 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 con gurations. However, almost as important as the nal bounds discussed in the paper are the techniques used to prove them. Proofs in Section 2.3 used basic combinatorics, a 62bucketing 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 con guration (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 con gurations (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 re nements and extensions of previous work, as well as original results. The results will provide either tools or a jumping o point for continued research in the eld. Thus this paper could be used as a helpful starting reference for anyone seeking to continue working in the eld of forbidden con gurations, as it combines a summary of previous important results, presents an important classi cation, 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 con g- urations. The rst would be an extension of Conjecture 1.3.5 from single forbidden con gurations 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 con gurations in a forbidden family represent all the inductive children of a single forbidden con guration. 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 nding 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 induc- tion and proof by contradiction. This technique was originally used in a similar proof, 63and 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 con gurations. 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 con gurations. In return, the study of forbidden families might be of use when studying single con gurations. In particular, the use of standard induction can change the problem from avoiding a single con guration 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 con gurations. 64Bibliography [1] R.P. Anstee. A survey of forbidden con guration results. The Electronic Journal of Combinatorics, 20:DS20, 2013. (Dynamic Survey). [2] R.P Anstee and M. Farber. Characterizations of totally balanced matrices. Jour- nal of Algorithms, 5(2):215 { 230, 1984. [3] R.P Anstee, R. Ferguson, and A. Sali. Small forbidden con gurations II. Elec- tronic Journal of Combinatorics, 8(1):R4, 2001. [4] R.P. Anstee and B. Fleming. Linear algebra methods for forbidden con gura- tions. 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 con gurations: exact bounds determined by critical substructures. Electronic Journal of Combinatorics, 17, 2012. [7] R.P. Anstee, Christina Koch, Miguel Raggi, and A. Sali. Forbidden con gura- tions and product constructions. Submitted to Graphs and Combinatorics. [8] R.P Anstee and A. Sali. Small forbidden con gurations 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 con gurations. Research notes, 2003. [15] P. Frankl, Z. F uredi, and J. Pach. Bounding one-way di erences. Graphs and Combinatorics, 3:341{347, 1987. [16] H.O.F. Gronau. An extremal set theory problem. Studia Scientiarum Mathe- maticarum Hungarica, 15:29{30, 1980. [17] W. Mantel. Problem 28 solution. Wiskundige Opgavem, 10:60{61, 1907. [18] Miguel Raggi. Forbidden Con gurations. PhD thesis, University of British Columbia, 2011. [19] H.J. Ryser. A fundamental matrix equation for nite 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 in nitary languages. Paci c 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 Applica- tions, 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 | 2013 |
Date Issued | 2013-04-16 |
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 |
Collection |
Electronic Theses and Dissertations (ETDs) 2008+ |
Date Available | 2013-04-17 |
Provider | Vancouver : University of British Columbia Library |
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 |
Aggregated Source Repository | DSpace |
Download
- Media
- [if-you-see-this-DO-NOT-CLICK]
- ubc_2013_spring_koch_christina.pdf [ 488.15kB ]
- Metadata
- JSON: 1.0073659.json
- JSON-LD: 1.0073659+ld.json
- RDF/XML (Pretty): 1.0073659.xml
- RDF/JSON: 1.0073659+rdf.json
- Turtle: 1.0073659+rdf-turtle.txt
- N-Triples: 1.0073659+rdf-ntriples.txt
- Original Record: 1.0073659 +original-record.json
- Full Text
- 1.0073659.txt
- Citation
- 1.0073659.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
United States | 36 | 9 |
Canada | 24 | 1 |
Germany | 11 | 19 |
China | 6 | 1 |
Japan | 2 | 0 |
Chile | 1 | 0 |
Poland | 1 | 0 |
Taiwan | 1 | 0 |
France | 1 | 0 |
City | Views | Downloads |
---|---|---|
Vancouver | 16 | 0 |
Ashburn | 10 | 0 |
Unknown | 9 | 19 |
Burlington | 8 | 0 |
Munich | 5 | 0 |
Freudenstadt | 4 | 0 |
Beijing | 4 | 0 |
Madison | 3 | 0 |
Tucson | 3 | 0 |
New York | 3 | 0 |
Pasadena | 2 | 2 |
Tokyo | 2 | 0 |
Berlin | 2 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
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