Diagonal Forms, Linear Algebraic Methods and Ramsey-Type Problems Citation Wong, Wing Hong Tony (2013) Diagonal Forms, Linear Algebraic Methods and Ramsey-Type Problems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/5B5A-Q252. https://resolver.caltech.edu/CaltechTHESIS:05312013-153531964 Abstract This thesis focuses mainly on linear algebraic aspects of combinatorics. Let N_t(H) be an incidence matrix with edges versus all subhypergraphs of a complete hypergraph that are isomorphic to H. Richard M. Wilson and the author find the general formula for the Smith normal form or diagonal form of N_t(H) for all simple graphs H and for a very general class of t-uniform hypergraphs H. As a continuation, the author determines the formula for diagonal forms of integer matrices obtained from other combinatorial structures, including incidence matrices for subgraphs of a complete bipartite graph and inclusion matrices for multisets. One major application of diagonal forms is in zero-sum Ramsey theory. For instance, Caro's results in zero-sum Ramsey numbers for graphs and Caro and Yuster's results in zero-sum bipartite Ramsey numbers can be reproduced. These results are further generalized to t-uniform hypergraphs. Other applications include signed bipartite graph designs. Research results on some other problems are also included in this thesis, such as a Ramsey-type problem on equipartitions, Hartman's conjecture on large sets of designs and a matroid theory problem proposed by Welsh. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: Combinatorics, Diagonal Forms, Linear Algebraic Methods, Ramsey Theory Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Wilson, Richard M. Thesis Committee: Wilson, Richard M. (chair) Omar, Mohamed Ramakrishnan, Dinakar Wales, David B. Defense Date: 28 May 2013 Non-Caltech Author Email: tonywhwong (AT) yahoo.com.hk Funders: Funding Agency Grant Number Sir Edward Youde Memorial Fund UNSPECIFIED Record Number: CaltechTHESIS:05312013-153531964 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:05312013-153531964 DOI: 10.7907/5B5A-Q252 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 7801 Collection: CaltechTHESIS Deposited By: Wing Hong Tony Wong Deposited On: 03 Jun 2013 22:46 Last Modified: 04 Oct 2019 00:01 Thesis Files Preview PDF - Final Version See Usage Policy. 742kB Repository Staff Only: item control page

Diagonal Forms, Linear Algebraic Methods and Ramsey-Type Problems Thesis by Wing Hong Tony Wong In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 2013 (Defended May 28, 2013) ii c 2013 Wing Hong Tony Wong All Rights Reserved iii To my wife, Jane, who offers me unconditional love, care and support throughout the course of this thesis. iv Acknowledgements First and foremost, I would like to express my deepest gratitude to my advisor, Prof. Richard M. Wilson, for his guidance, teaching, patience and support. His extensive knowledge in combinatorics and unparalleled skills in teaching inspire and sparkle me tremendously. I am very fortunate to be able to work closely with him for four years on numerous projects, and our collaboration work lays down the most important foundation for my thesis and beyond. I would also like to thank my friends and collaborators, Mr. Edward S. C. Fan, with whom I always enjoy discussing about mathematics, and Mr. Michel van Garrel, who is always giving me useful advices and supportive comments. A very special thank goes to Dr. Cheng Yeaw Ku, my mentor in the Summer Undergraduate Research Fellowship at California Institute of Technology in 2006, when I was a sophomore in the Chinese University of Hong Kong. He is the one who introduces me to frontier research in combinatorics. Another special thank goes to the Sir Edward Youde Memorial Fund for providing a three-year Overseas Fellowship to support my graduate studies. Lastly, I would like to thank my parents, for their constant care and love, as well as being the perfect role models and moral exemplars for me, and my elder brother, the very first mathematics teacher in my life. v Abstract This thesis focuses mainly on linear algebraic aspects of combinatorics. Let Nt (H) be an incidence matrix with edges versus all subhypergraphs of a complete hypergraph that are isomorphic to H. Richard M. Wilson and the author find the general formula for the Smith normal form or diagonal form of Nt (H) for all simple graphs H and for a very general class of t-uniform hypergraphs H. As a continuation, the author determines the formula for diagonal forms of integer matrices obtained from other combinatorial structures, including incidence matrices for subgraphs of a complete bipartite graph and inclusion matrices for multisets. One major application of diagonal forms is in zero-sum Ramsey theory. For instance, Caro’s results in zero-sum Ramsey numbers for graphs and Caro and Yuster’s results in zerosum bipartite Ramsey numbers can be reproduced. These results are further generalized to t-uniform hypergraphs. Other applications include signed bipartite graph designs. Research results on some other problems are also included in this thesis, such as a Ramseytype problem on equipartitions, Hartman’s conjecture on large sets of designs and a matroid theory problem proposed by Welsh. vi Contents Acknowledgements iv Abstract v 1 Introduction 1 1.1 Integer matrices and Smith normal form . . . . . . . . . . . . . . . . . . . . 1 1.2 Incidence matrices for hypergraphs . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Matrices for bipartite graphs and multisets . . . . . . . . . . . . . . . . . . . 3 1.4 Ramsey-type problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Some problems in design theory . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.6 Number of bases in a matroid of fixed size and rank . . . . . . . . . . . . . . 6 2 Diagonal forms of incidence matrices arising from subhypergraphs of complete t-uniform hypergraphs 7 2.1 Diagonal forms of integer matrices . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Inclusion matrices for hypergraphs and primitivity . . . . . . . . . . . . . . . 9 2.3 Shadows and fronts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 Primitivity of random hypergraphs . . . . . . . . . . . . . . . . . . . . . . . 17 2.5 Fronts and diagonal forms for primitive 2-vectors and graphs . . . . . . . . . 19 2.6 Fronts and diagonal forms for nonprimitive simple graphs . . . . . . . . . . . 23 3 Diagonal forms of incidence matrices arising from subgraphs of complete bipartite graphs 38 vii 3.1 Diagonal forms of U · N (G) . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2 Primitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3 The nonprimitive case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4 Inclusion matrices arising from multisets 59 4.1 v Inclusion matrix Ctk for multisets . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Row, column and null module . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3 v . . . . . . . . . . . . . . . . . . . Integer solutions and diagonal forms of Ctk 63 5 Ramsey-type problems 66 5.1 Zero-sum (mod 2) Ramsey numbers for hypergraphs . . . . . . . . . . . . . . 66 5.2 When is 1 ∈ rowZp (N2 (G)) for graphs G? . . . . . . . . . . . . . . . . . . . . 68 5.3 Zero-sum (mod 2) bipartite Ramsey numbers . . . . . . . . . . . . . . . . . . 73 5.4 Ramsey problem on hypergraphs induced by equipartitions . . . . . . . . . . 79 6 Problems in design theory 83 6.1 Hartman’s conjecture on large sets of designs of size 2 . . . . . . . . . . . . . 83 6.2 Signed bipartite graph designs . . . . . . . . . . . . . . . . . . . . . . . . . . 85 7 A problem in matroid theory by Dominic Welsh 7.1 7.2 A brief introduction to matroids . . . . . . . . . . . . . . . . . . . . . . . . .
The case 1 ≤ b ≤ r+2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . r Bibliography 87 87 88 93 1 Chapter 1 Introduction 1.1 Integer matrices and Smith normal form Understanding integer matrices is essential in the studies of many combinatorial problems. For instance, it was the study of a hypothetical self-dual binary code arising from a putative projective plane of order 10 that led to the proof of the nonexistence of such a plane [16], while the p-rank for primes p of the inclusion matrices was used to prove the Frankl-Wilson inequalities [10] that have geometric consequences. To understand the p-rank of an integer matrix or the structure of its row module over Z, one of the most important techniques is to find the Smith normal form or a diagonal form of that matrix. This thesis is partly motivated by Wilson [27] and Brouwer and Van Eijl [5]. Both works determine the diagonal forms and Smith normal forms of matrices arising from special graphs and hypergraphs. For any integer matrix A, there always exist two square integer matrices E and F , each with determinant ±1, such that EAF = D is a diagonal matrix. D is called a diagonal form of A, and E and F are called a front and a back of A respectively. If D has diagonal entries di dividing di+1 for all i, then D is called the Smith normal form, or Smith form, of A. There are numerous applications of Smith forms in combinatorics. In design theory, for example, Smith forms help with distinguishing nonisomorphic designs. In particular, Brouwer and Van Eijl [5] used Smith forms to identify nonisomorphic strongly regular graphs with the same parameters, and Chandler and Xiang [8] showed that certain difference sets 2 (the HKM and Lin difference sets) and their associated designs are nonisomorphic by computing the Smith forms of their incidence matrices. While it is easy to convert between the Smith form and a diagonal form of an integer matrix, the expression of a diagonal form is often much cleaner. Besides, a diagonal form is sometimes more natural to obtain by constructing a front explicitly. With a front, not only can we determine the corresponding diagonal form, the front also helps with determining whether a particular vector is in the row module of A. This technique is essential in the research on zero-sum Ramsey problems, discussed in chapter 5. 1.2 Incidence matrices for hypergraphs Let X be a set of size v, and T be the set of all t-subsets of X, with 0 ≤ t ≤ v. By a t-vector
based on X, we refer to an integer vector h whose vt coordinates are indexed by T . Given a column t-vector h, for each permutation σ in the symmetric group Sv , let σ(h) be the t-vector such that for each T ∈ T , σ(h)(T ) = h(σ −1 (T )). Let Nt (h) be the matrix whose columns are all the images of h under the symmetric group Sv , i.e., Nt (h) = [σ(h)]σ∈Sv . In particular, if h is a zero-one vector, then we can view h as a characteristic vector of a simple t-uniform hypergraph H, and the corresponding incidence matrix can be written as Nt (H). The matrix Nt (h) is a generalization of many integer matrices arising from set systems. Examples include integer matrices in the association algebras of Johnson schemes J(n, t), as well as the inclusion matrices Wtkv introduced in section 2.2. Let h(T ) denote the entry of h at coordinate T ∈ T . x ∈ X is an “isolated vertex” of h if h(T ) = 0 for all T containing x. Wilson [27] described a diagonal form for Nt (h) when h has at least t isolated vertices. In chapter 2, this result is extended to a very general class of h, namely all “primitive” h whose “shadows” are primitive or “multiples of primitive vectors”, defined in section 2.3 (see theorem 2.3.3). It is further shown in section 2.4 that most t-vectors h satisfies this property, including those h with t isolated vertices. Diagonal forms for N2 (G), where G is a simple graph, are studied in greater details. The family of primitive graphs is treated in section 2.5, while the remaining nonprimitive 3 graphs are tackled one by one in section 2.6. This work generalizes the results by some mathematicians interested in Smith forms. For example, N2 (K2,k−2 ) is the adjacency matrix of the complement of the line graph of Kn , whose Smith form was given by Brouwer and Van Eijl [5]. 1.3 Matrices for bipartite graphs and multisets In the previous project, simple t-uniform hypergraphs, or simple graphs in particular, are embedded into a complete one. As a continuation, the author considers embeddings of simple bipartite graphs into complete bipartite ones. Let G be a nonempty spanning subgraph of the complete bipartite graph Kn,n , i.e., G has 2n vertices, some of which may be isolated. As an analogue of the setting in chapter 2, let h be the characteristic vector of G. This means that h is a column vector indexed by the edge set of Kn,n such that for each edge E in Kn,n , h(E) = 1 if E is an edge of G and 0 otherwise. Let P be the graph automorphism group on Kn,n , and let N = N (G) be the matrix whose columns are all the images of h under the action of P. The main results in chapter 3 are the expressions for a diagonal form of N (G) for every nonempty spanning subgraph G in Kn,n (see theorems 3.2.2 and 3.3.2). This work on bipartite cases again leads to applications in zero-sum Ramsey theory, and Caro and Yuster’s results on zero-sum bipartite Ramsey numbers [7] can be deduced as a corollary (see section 5.3). Besides, it gives the necessary and sufficient conditions for the existence of a signed bipartite graph design, which are previously unknown (see section 6.2). Another direction is to consider a multiset system. Motivated by Ray-Chaudhuri and Singhi’s ideas on studying designs via multisets [19], the author derives the diagonal forms and discover other properties for the inclusion matrices of multisets (see chapter 4). 4 1.4 Ramsey-type problems The Ramsey problem is a classical graph coloring problem. One version of the Ramsey problem for hypergraphs can be stated as follows: Given a t-uniform hypergraph H and m colors, determine the minimum integer Rm (H) such that for all v ≥ Rm (H), for all edge(t) coloring of Kv (t) (t) with m colors, there exists a monochromatic H in Kv . Note that Kv denotes the complete t-uniform hypergraph on v vertices. The classical Ramsey problem is notoriously difficult. In fact, R2 (K5 ) is still unknown. Besides, the classical Ramsey numbers Rm (H) grows exponentially with k in general, where k is the number of vertices of H. Many mathematicians thus start to look for variations of the Ramsey problem and try to make progress on those problems. Zero-sum Ramsey problems are first studied by Bialostocki and Dierker [4] and Alon and Caro [3] in the 1990s. Let H be a t-uniform hypergraph with e edges and let Zm be the set of colors such that m | e. The objective of the zero-sum Ramsey problem is to determine the minimum integer ZRm (H) such that for all v ≥ ZRm (H), for all edge-coloring (t) (t) c : E(Kv ) → Zm , there exists a subgraph H 0 in Kv , H 0 isomorphic to H, such that the sum of the colors on E(H 0 ) is 0 in Zm . Using the notation in chapter 2, the zero-sum Ramsey problem is looking for the minimum integer ZRm (H) such that for all v ≥ ZRm (H), the row module of Nt (H ↑v ) over Zm does not contain a nowhere-zero vector. Here, H ↑v denotes the hypergraph obtained by adjoining isolated vertices to H so that the total number of vertices is v. Note that ZRm (H) is welldefined since Rm (H) exists by classical Ramsey theorem. In particular, if p = 2, then the zero-sum Ramsey number ZR2 (H) is the smallest integer such that for all v ≥ ZR2 (H), the binary code generated by Nt (H ↑v ) does not contain the vector 1 of all 1’s. Based on the formula for the diagonal forms and fronts of Nt (H) given in theorem 2.3.3, it is shown in section 5.1 that vector 1 does not lie in the row module of Nt (H) over Zm if H is primitive and all its shadows are multiples of primitive. Together with the result in section 2.4, we conclude that ZR2 (H) = k for almost all H, where k is the number of vertices of H (see theorem 5.1.4). This extends earlier results by Wilson [29], which gives ZR2 (H) ≤ k + t 5 for all t-uniform hypergraph H. As an analogue to the zero-sum Ramsey number, for each simple bipartite graph G, we define the zero-sum bipartite Ramsey number ZBm (G) as the smallest integer such that for all n ≥ ZBm (G), for all edge-coloring c : E(Kn,n ) → Zm , there exists a subgraph G0 in Kn,n , G0 isomorphic to G, such that the sum of the colors on E(G0 ) is 0 in Zm . A complete characterization of ZR2 (G) and ZB2 (G) are given in [6] and [7] respectively, and these results are reproduced through the studies of the diagonal forms (see sections 5.2 and 5.3). Another Ramsey-type problem that the author has studied is on hypergraphs induced by equipartitions on sets. Given a set X of v elements, consider the set V of all s-equipartitions, and the set E of all t-equipartitions, where s | t | v. Consider the hypergraph H = H(s, t, v) with V as its vertex set, and an edge E of H is the set of s-equipartitions in V that has a common t-equipartition in E as a refinement. It is conjectured that the Ramsey property holds for these hypergraphs on equipartitions, i.e., there exists v0 such that for all v ≥ v0 , for all 2-colorings of the vertices in H(v, s, t), there exists a monochromatic edge in H. This conjecture is proved to be true for s = 2 and t = 4 (see section 5.4). 1.5 Some problems in design theory Apart from the zero-sum Ramsey theory, the studies of incidence matrices have applications in design theory as well. In chapter 6, two of such applications are introduced. One of them is Hartman’s conjecture about large sets of t-designs. Hartman’s conjecture is one of the most important problems in design theory. Translating back to the language of inclusion matrix, this conjecture is related to the existence of a vector consisting of only 1’s and −1’s in the null space of Wtkv . This conjecture is solved in [1] for t = 2 as well as for some other cases (see [15] for more details). The author solved the case independently for t = 2 and k = 3, using some results from his studies of the inclusion matrix Wtkv . Another application is on signed graph design. This is a generalization of graph decom- 6 position, studied by Wilson [25], Ushio [22] and many others. In section 6.2, the necessary and sufficient conditions for the existence of a signed bipartite graph design are given. 1.6 Number of bases in a matroid of fixed size and rank One of the problems in matroid theory that Dominic Welsh [24] proposed is to determine all
triples of integers (n, r, b), 0 < r ≤ n and 1 ≤ b ≤ nr , for which there exists a matroid of rank r on n elements with exactly b bases. Mayhew and Royle [17] conjectured that there exists such a matroid for all triples except the case where (n, r, b) = (6, 3, 11). Sivaraman [21] used computer program SAGE to verify the conjecture up to n = 12. Given an r × n matrix A with full row rank over a field, the set of columns of A will form a linear matroid or column matroid with n elements and rank r, and a basis of this matroid is given by an invertible r × r submatrix. Edward S. T. Fan and the author [9] prove the
conjecture for 1 ≤ b ≤ r+2 by constructing these matrices explicitly (see chapter 7). r 7 Chapter 2 Diagonal forms of incidence matrices arising from subhypergraphs of complete t-uniform hypergraphs 2.1 Diagonal forms of integer matrices Two integer matrices A and B of the same size are Z-equivalent if B can be obtained from A by a sequence of integral row and column operations (adding an integer multiple of one row or column to another row or column, or multiplying a row or column by −1). Alternatively, A and B are Z-equivalent if there exist integer square matrices E and F with determinants ±1 such that EAF = B. If integer matrix A is Z-equivalent to a diagonal matrix D, then D is called a diagonal form of A, and the list of diagonal entries of D are called a list of diagonal factors of A. Here, diagonal means that the (i, j)-entry of D is nonzero only if i = j. In the Z-equivalence relation, if EAF = D where E and F are integer square matrices with determinants ±1, we call E a front and F a back of A. One remark is that for a fixed A and a diagonal form D, the choice of E and F is not unique. Given A, if a list of diagonal factors d1 , d2 , . . . of A are nonnegative such that di | di+1 for all i, then D is the Smith normal form of A, and this list of diagonal factors is called the invariant factors or the elementary divisors of A. Note that the Smith normal form is unique for each A, while diagonal forms are not. Readers are referred to [18] for more 8 background on Smith normal form. It is clear that the rank of an integer matrix A is the number of nonzero entries in any list of diagonal factors. As an extension, for any prime p, the p-rank, or pα -rank with α ∈ N, is the number of entries in any list of diagonal factors that are indivisible by pα . The number of diagonal factors of an r × s matrix A is the minimum of r and s, but sometimes it will be convenient to speak of diagonal factors d1 , d2 , . . . , dr of an r × s matrix even when r > s, in which case it is to be understood that di = 0 for s < i ≤ r, as if we have appended r − s columns of all 0’s to A. Notice that diagonal factors of A are also diagonal factors for A> , if we consider min{r, s} as the number of diagonal factors. Integers d1 , d2 , . . . , dr are diagonal factors for an r × s matrix A if and only if Zr /colZ (A) ∼ = Zd1 ⊕ Zd2 ⊕ · · · ⊕ Zdr , (2.1) where colZ (A) is the Z-module (abelian group) generated by the columns of A. Here, we take the convention that Z1 = {0} and Z0 = Z. As we mentioned above, it is to be understood that di = 0 for s < i ≤ r. The group in (2.1) may be called the (column) Smith group S(A) of A. The dimension of S(A) as a finitely generated abelian group is the number of diagonal factors d1 , . . . , dr that are equal to 0 and this is r − rank(A). We use τ (A) to denote the order of the torsion subgroup of S(A), which is simply the product of the nonzero diagonal factors. An integer matrix A is said to be unimodular if A is of square size and is Z-equivalent to an identity matrix. In fact, it is easy to see that A is unimodular if and only if its determinant is ±1. If A is rectangular of dimension r × s and has a unimodular submatrix of size r, then A is said to be row-unimodular. Equivalently, A is row-unimodular if a list of diagonal factors of A has r 1’s, or if the Smith group S(A) is trivial. A significant property of a row-unimodular matrix is that all its rows are linearly independent over any field. Besides, every row-unimodular A has unimodular extensions, i.e., there are unimodular matrices B whose row set contains that of A. We remark that if A0 has the same size and the same row module over Z as A, then any unimodular extension of 9 A will also give a unimodular extension of A0 by appending the same rows. 2.2 Inclusion matrices for hypergraphs and primitivity Let X be a set of size v, T be the set of all t-subsets of X and S the set of all k-subsets, with 0 ≤ t ≤ k ≤ t + k ≤ v. Let Wtkv , or simply Wtk if the underlying set X is understood,

be the vt × kv inclusion matrix, rows indexed by T and columns by S, such that for each T ∈ T and S ∈ S,   1 if T ⊆ S, v Wtk (T, S) =  0 otherwise. A diagonal form of this matrix is given by [26]. Let nullR (A) denote the null module to the row module of A over the ring R. Integer vectors in the null space nullQ (Wtk ) are called null t-designs or trades. A survey and comparison of explicit constructions of Z-bases for nullZ (Wtk ) may be found in [14]. The elements of all Z-bases in nullZ (Wtk ) are of a certain type that were called (t, k)-pods by Graver and Jurkat [12], cross-polytopes by Graham, Li, and Li in [11], and minimal trades in [14]. For our purpose, we only need to know a generating set for nullZ (Wt−1,t ), and we restrict our attention to this case. We use the term t-pods for what are called (t − 1, t)-pods in [12]. Let P be a pairing, a set of t disjoint ordered pairs {(a1 , b1 ), (a2 , b2 ), . . . , (at , bt )} of elements of X. To each pairing P , we associate a row t-vector f P , indexed by T ∈ T such that for each T = {c1 , c2 , . . . , ct } ∈ T , f P (T ) is the coefficient of the monomial c1 c2 · · · ct in the expansion of the polynomial (a1 − b1 )(a2 − b2 ) · · · (at − bt ). Thus f P (T ) = 0 unless T is transverse to P , i.e., contains exactly one member of each pair {ai , bi }, in which case 10 f P (T ) = (−1)|T ∩{b1 ,b2 ,...,bt }| . These f P are called t-pods, and the following theorem 2.2.1 about t-pods is proved in [11] and [12]. v ) and every integer t-vector in the null space Theorem 2.2.1. Every t-pod is in nullQ (Wt−1,t nullQ (Wtkv ) is an integer linear combination of the t-pods. We remark that there are no t-pods if v < 2t, but in that case, nullQ (Wt−1,t ) is trivial, see, e.g., [12], so the theorem remains valid. Let h be a t-vector based on X, a set of size v ≥ 2t. We say that h is primitive if the GCD of hf , hi over all integer t-vectors f ∈ nullQ (Wt−1,t ) is equal to 1. Equivalently, h is primitive if the GCD of the entries in f P Nt (h) is 1 for any t-pod f P . This is because of theorem 2.2.1 and the fact that {σ(f P )}σ∈Sv , the set of images of f P under the symmetric group Sv , is the collection of all t-pods. In general, we say that the GCD γ of the entries in f P Nt (h) is the index of primitivity of h. In the sequel, when we speak of a “multiple of a primitive vector”, we refer to a nonzero integer multiple of a primitive vector. Lemma 2.2.2. Let h be a t-vector based on a set X of size v ≥ 2t with the index of primitivity γ, and let c be the GCD of the entries of h. Then h is a multiple of a primitive vector if and only if γ = c. Proof. If h = cp is a multiple of primitive vector p, then f P Nt (h) = cf P Nt (p) whose GCD is c · 1, so c is the index of primitivity of h. On the other hand, if γ = c, we write h = ch0 . Then f P Nt (h0 ) = f P Nt ((1/c)h) = (1/γ)f P Nt (h) which has GCD 1. Proposition 2.2.3. Let h be a t-vector based on a set X of size v ≥ 2t such that h has at least t isolated vertices. Then h is a multiple of a primitive vector. We recall that x is an isolated vertex of h if h(T ) = 0 for all T containing x. Proof. Let b1 , . . . , bt be t isolated vertices of h. For each T ∈ T , if T ∩{b1 , . . . , bt } is nonempty, then h(T ) = 0. Otherwise, let T = {a1 , . . . , at }, and let P = {(a1 , b1 ), . . . , (at , bt )} be a 11 pairing. Now, hf P , hi = h(T ), implying that the index of primitivity γ divides the GCD of h. Since the GCD of h always divides γ, we are done by lemma 2.2.2. Proposition 2.2.4. Let h be a t-vector with t − 1 isolated vertices b1 , . . . , bt−1 , and let γ be the index of primitivity of h. Then h(T ) is constant modulo γ for all t-subsets T ⊂ X\{b1 , . . . , bt−1 }. Proof. Consider two t-subsets T1 = {a1 , . . . , at−1 , c} and T2 = {a1 , . . . , at−1 , d}, both disjoint from B = {b1 , . . . , bt−1 }. Let P be the pairing {(a1 , b1 ), . . . , (at−1 , bt−1 ), (c, d)}. Then γ divides hf P , hi = h(T1 ) − h(T2 ), i.e., h(T1 ) ≡ h(T2 ) (mod γ). Given any two t-subsets T, T 0 disjoint from B, there exists a sequence T = T1 , T2 , . . . , Tm = T 0 of t-subsets disjoint from B such that |Ti ∩ Ti+1 | = t − 1, so h(T ) ≡ h(T 0 ) (mod γ). Theorem 2.2.5. Let h be a t-vector with the index of primitivity γ. Then colZ (Nt (h)) contains γf for every integer vector f in the nullQ (Wt−1,t ). Proof. It suffices to show that for each pairing P = {(a1 , b1 ), . . . , (at , bt )}, γf P is contained in colZ (Nt (h)). For a subset I ⊆ {1, 2, . . . , t}, let σI be the product of the transpositions (ai , bi ), i ∈ I. Let h0 be a column in Nt (h). We claim that for each T ∈ T , X sign(σI ) · σI (h0 )(T ) = hf P , h0 i · f P (T ). (2.2) I⊆{1,2,...,t} If T is not transverse to the pairing P , then the R.H.S. of (2.2) is 0, while there exists i ∈ {1, 2, . . . , t} such that σI (h0 )(T ) = ((ai , bi )σI )(h0 )(T ) for all I ⊆ {1, 2, . . . , t}, meaning that the terms on the L.H.S of (2.2) can be paired up with terms of the opposite signs but the same magnitude, yielding 0 when we take the sum. If T is transverse to the pairing P , then there is a bijection between subsets I ⊆ {1, 2, . . . , t} and transversals TI to P such that σI (T ) = TI , and sign(σI ) · σI (h0 )(T ) = (−1)|T ∩B| (−1)|TI ∩B| · h0 (TI ) = f P (T )f P (TI )h0 (TI ), 12 where B = {b1 , b2 , . . . , bt }. Summing over I ⊆ {1, 2, . . . , t}, we get (2.2). Now, hf p , h0 i · f P is in colZ (Nt (h)) for every column h0 in Nt (h), then so is γf P . 2.3 Shadows and fronts Let X be a fixed v set. We are going to define a family of matrices, written as Yitv . Let



v Y0tv = W0tv , a 1 × vt matrix of all 1’s. For i = 1, 2, . . . , t, let Yitv be the vi − i−1 by vt matrix obtained from Witv by deleting those rows corresponding to an (i − 1, i)-basis on X. Here, an (i − 1, i)-basis on X is a set of i-subsets of X such that the corresponding columns v v ). Such bases exist by proposition 1 of [27] and here form a Z-basis for colZ (Wi−1,i of Wi−1,i we choose and fix one for each i. If A and B are two matrices with the same number of columns, let A t B denote the matrix obtained by placing A on top of B. The following lemma is proved in [27] for v ≥ 2t but is easily extended to v ≥ t + i; see [28]. Lemma 2.3.1. Let i ≤ t ≤ v − i. (a) The matrix Y0tv Y1tv Y2tv j G Yitv = .. . i=0 Yjtv is a v j
× v t
row-unimodular matrix whose rows form a Z-basis for the integer vectors in

t rowQ (Wjtv ). In particular, if v ≥ 2t, then t Yitv is a vt × vt unimodular matrix. i=0 13 (b) For each j = 0, 1, 2, . . . , t, the module rowZ (Wjtv ) is equal to that generated by the rows of  j  G t−i i=0 j−i Yitv . A fundamental relation for inclusion matrices Witv is given by Wijv Wjtv =   t−i Witv , j−i (2.3) and when we delete the rows corresponding to an (i − 1, i)-basis from both sides of (2.3), we obtain Yijv Wjtv =   t−i Yitv . j−i (2.4) Theorem 2.3.2. Let h be a t-vector based on a v-set X, and let γ be the primitivity of h. v be an integer matrix whose rows form a Z-basis for the module of integer vectors Let Ut−1,t v in rowQ (Wt−1,t ). (a) If γ 6= 0, then

v Nt (h) + rank Nt (h) = rank Ut−1,t v t


v − t−1 , and
τ Nt (h) divides
v v v γ ( t )−(t−1) τ Ut−1,t Nt (h) . (2.5) (b) If h is a multiple of a primitive t-vector, then equality holds in (2.5). Moreover, a front v v for Nt (h) can be any unimodular extension of EUt−1,t , where E is a front of Ut−1,t Nt (h),

v and the corresponding list of diagonal factors of Nt (h) is obtained by adjoining vt − t−1 v Nt (h). copies of γ to the list of diagonal factors of Ut−1,t Proof. (a) By theorem 2.2.5, colZ (Nt (h)) contains γf for any t-pod f , so the column module 14 colZ (Nt (h)) is equal to the column module of the matrix Nt (h) = v is a where Mt−1,t v t
− v t−1
by v )> , γ(Mt−1,t Nt (h) v t
matrix whose rows are selected t-pods f such that the v v ). Let form a Z-basis for the integer vectors in nullQ (Wt−1,t rows of Mt−1,t v Ut−1,t U= V v . Then be a unimodular extension of Ut−1,t v Ut−1,t v U (Mt−1,t )> = V O v )> = (Mt−1,t , B v v v v ). So ) = rowQ (Wt−1,t ) while all the rows in Mt−1,t are in nullQ (Wt−1,t since rowQ (Ut−1,t U Nt (h) = v Ut−1,t Nt (h) O V Nt (h) γB . (2.6) v As Mt−1,t is row-unimodular, B is unimodular and det(B) = ±1. It is now clear that the

v v rank of Nt (h) is the rank of Ut−1,t Nt (h) plus vt − t−1 .
v v For any square submatrix A of Ut−1,t Nt (h) of order equal to rank Ut−1,t Nt (h) , the 15 determinant of the square submatrix A O C γB v v of U Nt (h) is a multiple of τ (U N t (h)) = τ (Nt (h)), i.e., γ ( t )−(t−1) det(A) is a multiple of τ (Nt (h)), which implies (2.5). (b) As h is a multiple of a primitive vector, by lemma 2.2.2, the GCD of the entries of h is γ. In this case, column operations can be used to transform the matrix U Nt (h) in (2.6) to U N t (h)U 0 = v Nt (h) Ut−1,t O O γI , v Nt (h) with D and F where U 0 is an appropriate unimodular matrix. If E is a front for Ut−1,t v the corresponding diagonal form and back such that EUt−1,t Nt (h)F = D, then v EUt−1,t V F O Nt (h)U 0 D O O γI = O . I v v As EUt−1,t and Ut−1,t have the same size and the same row module over Z, appending V to v v EUt−1,t is also a unimodular extension. Hence, EUt−1,t t V is a front for Nt (h) or Nt (h). t−1 v Remarks. One choice for the matrix Ut−1,t in the above theorem is t Yitv , and in the proof, i=0 16 v one may take V = Yttv regardless of the choice of Ut−1,t . For an integer j, 0 ≤ j ≤ t, the j-th shadow h(j) of a t-vector h is the (t − j)-vector v Wt−j,t h. For example, if g is the characteristic 2-vector of a multigraph G, then the first shadow g(1) is the 1-vector whose coordinates give the degrees of the vertices of G, and the second shadow g(2) is the scalar e, the number of edges of G. Note that by (2.3), a shadow of a shadow is an integer multiple of a shadow. For instance, the first shadow of g(1) is the scalar 2e. Theorem 2.3.3. If a t-vector h and all of its shadows are primitive or multiples of primitive vectors, then a front for Nt (h) is given by t E = t Yitv , i=0 and the corresponding list of diagonal factors are v v v (g0 )1 , (g1 )v−1 , (g2 )(2)−v , . . . , (gt )( t )−(t−1) , where gi is the GCD of all entries of Witv h. Here, the exponents denote the multiplicities. Proof. We proceed by induction on t. When t = 0, a 0-vector h is a scalar. Then a front for N0 (h) can be Y00v = 1, and the corresponding diagonal form is h, which is equal to g0 , the v GCD of the entries of W00 h. Now fix t ≥ 1. v v Given h, let h0 = Wt−1,t h be the first shadow of h. Then Nt−1 (h0 ) = Wt−1,t Nt (h). Let gi0 v be the GCD of the entries of Wi,t−1 h0 for i = 0, 1, . . . , t − 1. By (2.3), gi0 = (t − i)gi , i = 0, 1, . . . , t − 1. (2.7) t−1 v Applying the induction hypothesis to h0 , t Yi,t−1 is a front for Nt−1 (h0 ), and the correspondi=0 ing diagonal form is
v v D = diag (gi0 )( i )−(i−1) , i = 0, 1, . . . , t − 1 . (2.8) 17 By (2.4),

t−1 t (t − i)Yitv Nt (h) = D0 t Yitv Nt (h), t−1 t−1 i=0 i=0
v v Wt−1,t Nt (h) = t Yi,t−1 i=0 where D0 is the square diagonal matrix with diagonal entries v v (t − i)( i )−(i−1) , i = 0, 1, . . . , t − 1. By (2.7), (2.8) and (2.9), a diagonal form for (2.9) t−1
t Yitv Nt (h) is i=0
v v diag (gi )( i )−(i−1) , i = 0, 1, . . . , t − 1 . The index of primitivity γ of h is the GCD of the entries of h, and this is gt . By theorem t 2.3.2(b), t Yitv is a front for Nt (h) with the corresponding diagonal form i=0
v v diag (gi )( i )−(i−1) , i = 0, 1, . . . , t . 2.4 Primitivity of random hypergraphs We consider the following model for a random t-uniform multihypergraph on k vertices. Let (t) XT be i.i.d random variables associated with each edge T of Kk , uniformly distributed on {0, 1, . . . , M − 1} for some M ≥ 2. Let H be the “random multihypergraph” where the multiplicity of each edge T is given by XT . Let P = {(a1 , b1 ), (a2 , b2 ), . . . , (at , bt )} be a pairing and σI the product of the transpositions (ai , bi ), i ∈ I ⊆ {1, 2, . . . , t}. Let T = {a1 , a2 , . . . , at }. By definition, H is primitive if and only if the GCD of X (−1)|I| XσI (T ) I⊆{1,2,...,t} 18 with P running over all pairings in the k-set is 1. Note that if we fix a pairing P , for any prime p,  P  X t−1 2 X (−1)|I| XσI (T ) ≡p 0 = P XTi − i=1 I⊆{1,2,...,t} (M −1)2t−1 = t−1 t−1 X P r=−(M −1)(2t−1 −1) 2 X t−1 XTi − i=1 2 X ! XTi0 = r i=2 2 X ! XTi0 ≡p 0 i=1 1 · P XT10 ≡p r ≤ M
  M , p j k l m
since P XT10 ≡p r = M1 Mp or M1 Mp for all r ∈ Z. If we form bk/2tc disjoint subsets of 2t vertices out of the set of k vertices, and from each subset of 2t vertices we choose a pairing, then  X P(H is nonprimitive) ≤ p prime≤(M −1)2t−1 t−1 ≤ (M − 1)2 1 M  M p bk/2tc  bk/2tc 2 k→∞ −−−→ 0, 3 which proves the following theorem. Theorem 2.4.1. A random t-uniform multihypergraph H on k vertices is almost surely primitive as k → ∞. We remark that the i-th shadow of a random t-uniform hypergraph is not necessarily a random (t − i)-uniform hypergraph, yet we show that it, too, is almost surely primitive. Consider the i-th shadow H (i) of H. For each edge R = {a1 , . . . , at−i } in H (i) , let P ZR = T ∈E(H) s.t. R⊂T XT , which represents the multiplicity of each edge R in H (i) . Then H (i) is primitive if and only if the GCD of ω(P (i) ) := X (−1)|I| ZσI ({a1 ,a2 ...,at−i }) I⊆{1,2,...,t−i} with P (i) = {(a1 , b1 ), (a2 , b2 ), . . . , (at−i , bt−i )} running over all pairings in the k-set is 1. We form bk/2(t − i)c disjoint subsets of 2(t − i) vertices out of the set of k vertices, and 19 (i) (i) (i) from each subset of 2(t − i) vertices we choose a pairing, labeled by P1 , P2 , . . . , Pbk/2(t−i)c . (i) For each pairing Pj , since k → ∞, there always exists at least one t-subset T such that XT (i) (i) occurs only once in ω(Pj ) but not in any other ω(P` ). Hence, the independence of the XT ’s gives P(H (i) is nonprimitive) ≤  X p prime≤(M −1)2t−i−1 k−2(t−i) i ( ) 1 M  M p bk/2(t−i)c , which also goes to 0 when k → ∞, and so we obtain the following theorem. Theorem 2.4.2. The i-th shadow H (i) of a random multihypergraph H on k vertices is almost surely primitive as k → ∞. In fact, both theorems hold for any distribution of i.i.d. random variables XT as long as P(XT ≡p r) < 1 for all primes p and r ∈ Z. Finally, note that when M = 2, our original setting coincides with one of the most classical definition of random simple hypergraph. 2.5 Fronts and diagonal forms for primitive 2-vectors and graphs For a column 1-vector a = [a1 , . . . , av ]> , the columns of N1 (a) are simply all the permutations of a. Let B = B(b; a1 , . . . , av ) be the matrix derived from N1 (a) by replacing the top row with the row vector b1v! for some integer b. Here, and throughout this thesis, we use 1i and 0i to denote row vectors of all 1’s and all 0’s respectively of length i, and Oi×j the matrix of all 0’s of size i by j, unless otherwise specified. Before we proceed, we will prove the following lemma in elementary number theory. Lemma 2.5.1. For any x, y ∈ Z, there exists a, b ∈ Z such that GCD{a, x, y} = 1 and ax + by = GCD{x, y}. Proof. Let GCD{x, y} = d, x = x0 d and y = y 0 d. Let a0 , b0 ∈ Z be such that a0 x0 + b0 y 0 = 1. Note that GCD{a0 , y 0 } = 1. Our goal is to find a such that a ≡ a0 (mod y 0 ) and 20 GCD{a, d} = 1. Without loss of generality, we can assume that all prime factors of d are of degree 1. Let d = d1 d2 such that d1 | y 0 and GCD{d2 , y 0 } = 1. As GCD{a0 , y 0 } = 1, it suffices to find a such that a ≡ a0 (mod y 0 ) and a ≡ 1 (mod d2 ), which is possible by the Chinese remainder theorem. Theorem 2.5.2. Given integers a1 , . . . , av and b, not all zero, let h = GCD{a1 , . . . , av , b} g = GCD{ai − aj : 1 ≤ i, j ≤ v}. and A front for B(b; a1 , . . . , av ) can be given by the matrix (a1 , g)/h `b/h α β O2×(v−2) E= , 0> v−2 −1> v−2 I(v−2)×(v−2) and the corresponding list of diagonal factors is (bg/h)1 , (h)1 , (g)v−2 . Here, ` is any nonzero integer such that GCD{`, a1 , g} = 1 and (a1 , g) + `a1 ≡ 0 (mod g), which exists by lemma 2.5.1, and α, β are chosen to satisfy  det  (a1 , g)/h `b/h α β   = 1. Proof. For each 2 ≤ r ≤ v and 1 ≤ i, j ≤ v, there are two columns of B that are identical except the r-th coordinate, where one contains ai and the other aj . For example, if i = 1, 21 j = 2, r = 3, the columns could be [b, a3 , a1 , a4 , a5 , . . . , av ]> and [b, a3 , a2 , a4 , a5 , . . . , av ]> . By taking the difference between these two vectors, we show that colZ (B) contains the vector (ai − aj )er , where er is the r-th standard basis vector. As this is true for every pair of i and j, colZ (B) has to contain the vector ger for each r ≥ 2. It is now obvious that the matrix C= b 0v−1 a1 1> v−1 gI(v−1)×(v−1) shares the same column module as B, thus the same fronts and diagonal factors as well. For the rest of the proof, we will try to show that E is a front for C. The matrix E is defined such that it has determinant 1, so it is unimodular. It then suffices to find a unimodular matrix F such that EC = DF , where D is the diagonal form in the statement of the theorem. Now, let `0 ` (αb + βa1 )/h βg/h O2×(v−2) F = , 0> v−2 −1> v−2 I(v−2)×(v−2) where `0 is an integer defined such that (a1 , g) + `a1 = `0 g. By the definition of α and β,
(a1 , g)β − `αb /h = 1, or (a1 , g)β − `αb = h. From these two equations, we get `(αb + βa1 ) = `0 βg − h. As GCD{`, a1 , g} = 1, we have ` and h are relatively prime. Hence, αb + βa1 = (`0 βg − h)/` is divisible by h, and we have shown that F is an integer matrix. The determinant of F is `0 βg/h − `(αb + βa1 )/h = `0 βg/h − (`0 βg − h)/h which is 1, 22 meaning that F is unimodular. Finally, it is routine to check that EC = DF . Corollary 2.5.3. For any nonzero a, a list of diagonal factors of N1 (a) is (bg/h)1 , (h)1 , (g)v−2 , where b = a1 + a2 + · · · + av , h = GCD{a1 , . . . , av } and g = GCD{ai − aj : 1 ≤ i, j ≤ v}. Proof. This is a direct application of theorem 2.5.2, since B(b; a1 , . . . , av ) is obtained by adding all the other rows to the top row of N1 (a). We now describe a front and the corresponding list of diagonal factors for N2 (h) for any primitive 2-vector h. Theorem 2.5.4. Let h be a primitive 2-vector based on a v-set with the first shadow a = [a1 , . . . , av ]> . Let b = (a1 + · · · + av )/2 and let g, h, E be described as in the statement of theorem 2.5.2. Then a front for N2 (h) can be (E(Y02 t Y12 )) t Y22 , and the corresponding list of diagonal factors is v (bg/h)1 , (h)1 , (g)v−2 , (1)(2)−v . Proof. Note that W02 N2 (h) = b1v! and W12 N2 (h) = N1 (a), so if we take U12 = Y02 t Y12 , where Y12 is W12 with the top row deleted, we will have U12 N2 (h) = B(b; a1 , . . . , av ). As E is a front for U12 N2 (h) by theorem 2.5.2, we can apply theorem 2.3.2(b), which says any unimodular extension of EU12 is a front for N2 (h), and the list of corresponding diagonal
factors is obtained by adjoining v2 − v copies of 1’s to (bg/h)1 , (h)1 , (g)v−2 . We finish by noticing that EU12 t Y22 is a unimodular extension of EU12 , since U12 and EU12 have the same row module over Z, and Y22 is a unimodular extension of U12 by lemma 2.3.1. Remarks. If h is the characteristic 2-vector of a multigraph G (graphs with multiple edges but no loops), then the shadow a = W12 h is the degree sequence and b the number of edges of G. Theorem 2.5.4 gives a list of diagonal factors of N2 (G) if G is primitive, determined only by the degree sequence of G. As simple examples, if G is the Petersen graph, then a list of diagonal factors of N2 (G) is (3)1 , (0)9 , (1)35 (g = 0 since G is a regular graph), while 23 for the graph G0 consisting of the Petersen graph plus an isolated vertex, a list of diagonal factors for N2 (G0 ) is (15)1 , (3)10 , (1)44 . This is because both graphs G and G0 (and almost all simple graphs) are primitive by theorem 2.6.1 in the next section. 2.6 Fronts and diagonal forms for nonprimitive simple graphs Let X be a set of size k. We use 1{x,y} to denote a row 2-vector of length k 2
, indexed by the 2-subsets of X, such that the entry corresponding to {x, y} is 1 and 0 elsewhere. Then the 2-pod corresponding to the pairing P = {(a1 , b1 ), (a2 , b2 )} can be written as f P = 1{a1 ,a2 } + 1{b1 ,b2 } − 1{a1 ,b2 } − 1{a2 ,b1 } . If G is a simple graph with characteristic 2-vector g, i.e., g({x, y}) = 1 if {x, y} is an edge of G and 0 otherwise, then hf P , gi = g({a1 , a2 }) + g({b1 , b2 }) − g({a1 , b2 }) − g({a2 , b1 }). In particular, we always have hf p , gi ∈ {−2, −1, 0, 1, 2}. Theorem 2.6.1. A simple graph G with at least four vertices is primitive unless G is isomorphic to a complete graph, an empty graph, a complete bipartite graph, or a disjoint union of two cliques. Proof. It is easy to check which simple graphs on four vertices are primitive, since there are only three possible 2-pods, up to signs, on four vertices. Up to isomorphism, here are all the primitive simple graphs on four vertices. a c a c a c a c a c b d b d b d b d b d (2.10) 24 As a result, a simple graph G is nonprimitive if and only if every subgraph induced by any four vertices of G is isomorphic to one of the following. a c a c a c a c a c a c b d b d b d b d b d b d Note that a simple graph is primitive if and only if its complement is primitive. Let G be a nonprimitive simple graph. If G is neither a complete graph nor an empty graph, then there exist three vertices a, b, c such that the subgraph they induce is isomorphic to a Case (i ) c a or Case (ii ) b b c . Case (i ). For every vertex x 6= a, b, c in G, the induced subgraph on {a, b, c, x} is isomorphic to a c b u or a c b v . Let U and V be, respectively, the sets of vertices other than a, b, c that are adjacent to a, and are adjacent to b and c. Observe that two vertices u1 , u2 ∈ U cannot be adjacent in G, or else the subgraph induced by {a, b, u1 , u2 } is on the list (2.10); two vertices v1 , v2 ∈ V cannot be adjacent in G, or else the subgraph induced by {a, b, v1 , v2 } is on the list (2.10); and vertices u ∈ U , v ∈ V must be adjacent in G, or else the subgraph induced by {a, b, u, v} is on the list (2.10). Therefore, G is a complete bipartite graph with partite sets {b, c} ∪ U and {a} ∪ V . Case (ii ). We simply take the complement of the graph G and it will return to case (i ). Hence, G is a disjoint union of two cliques. Theorem 2.6.2. Let G be a simple nonprimitive graph with k vertices, k ≥ 4. Then diagonal forms of G can be given by the following table. 25 G (a) Kk a list of diagonal factors of N2 (G) k (1)1 , (0)(2)−1 (b) empty k (0)(2) (c) K1,k−1 (d ) ˙ k−1 K1 ∪K (e) (f ) k (2)1 , (1)k−1 , (0)(2)−k k (k − 2)1 , (1)k−1 , (0)(2)−k
eg 1 , h Kr,k−r 2 ≤ r ≤ k2 ˙ k−r Kr ∪K 2 ≤ r ≤ k2 k (h)1 , (2g)k−2 , (2)(2)−(2k−2) , (1)k−2 e = r(k − r), g = k − 2r, h = GCD{r, k}
k 2eg 1 , (h)1 , (2g)k−2 , (2)(2)−(2k−1) , (1)k−1 h

e = 2r + k−r , g = k − 2r, 2 h = GCD{r − 1, g, e},  = GCD{k, 2} Parts (a) and (b) are trivial, so we will omit the proof. k 2 Proof of (c). Let X = {v1 , v2 , . . . , vk } be the vertex set of G. Let E be the

× k2 matrix given in (2.11) below. By elementary row operations, we can clear the two −1’s in the top row of E without changing its determinant, and the resultant matrix is lower-triangular with only 1’s on the diagonal, so E is unimodular.
Note that the bottom k2 −k rows of E are 2-pods, so we get 0’s for these rows of EN2 (G) k > since all the columns in N2 (G) are columns in (W12 ) . The top k rows of EN2 (G) are given by 1 0> k−1 −1 0k−3 −1 · 1> k−1 I(k−1)×(k−1) ··· 1> k−1 I(k−1)×(k−1) I(k−1)×(k−1) 0 1 1 0k−3 0 1 1 0k−3 = 26 2 0k−1 · 0> k−1 I(k−1)×(k−1) 0 0 1> k−2 0> k−2 0 1 −1 0k−3 I(k−2)×(k−2) 1 ··· 0k−3 −1 0 0 1> k−2 0> k−2 0 1 0k−3 I(k−2)×(k−2) . 1 0k−3 It is easy to see that the last matrix is row-unimodular, and can be extended to a unimodular
k matrix F such that EN (G) = DF , where D = diag (2)1 , (1)k−1 , (0)(2)−k . 2 1 0> k−1 −1 0k−3 −1 Ok×((k)−k) 2 I(k−1)×(k−1) 1{v1 ,v3 } + 1{v2 ,x} − 1{v1 ,x} − 1{v2 ,v3 } , x ∈ {v4 , . . . , vk } 1{v1 ,v2 } + 1{x,y} − 1{v1 ,y} − 1{v2 ,x} , {x, y} ⊆ {v3 , . . . , vk }                                                      k rows k − 3 rows (2.11) k−2 2
rows                       Proof of (d ). Let E be the same k 2
are replaced by the matrix in (2.12).
× k2 matrix given in (2.11) except that the first k rows 27 1 0> k−1 1k−2 0 (2.12) Ok×((k)−k) I(k−1)×(k−1) 2 By elementary row operations, we can clear the vector 1k−2 in the top row of E without changing its determinant, and the resultant matrix is lower-triangular with only 1’s on the diagonal, so E is unimodular. k > ) , where J denotes the Note that all the columns in N2 (G) are columns in J − (W12 matrix of all 1’s. Since a 2-pod is orthogonal to a vector of all 1’s, it is orthogonal to all the
k > ) . As a result, the bottom k2 − k rows of EN2 (G) are again all 0’s. columns in J − (W12 The top k rows of EN2 (G) are given by 1 0> k−1 1k−2 0 · 0> k−1 (J − I)(k−1)×(k−1) ··· 0> k−1 (J − I)(k−1)×(k−1) = I(k−1)×(k−1) 1 k−2 0k−1 0> k−1 I(k−1)×(k−1) · 0 0 1k−3 1 0 1 1k−2 0> k−2 1> k−2 (J − I)k−2 . 1 0 0 1 1k−2 0> k−2 1> k−2 (J − I)k−2 1 0 0 1k−3 ··· 0 0 1k−3 0 1k−3 It is easy to see that the last matrix is row-unimodular, and can be extended to a unimodular
k matrix F such that EN (G) = DF , where D = diag (k − 2)1 , (1)k−1 , (0)(2)−k . 2 To prove theorem 2.6.2(e) and (f ), we need the following two lemmas. Lemma 2.6.3. Let A be an r × s integer matrix, r ≤ s, and D a square diagonal integer matrix of order r. If both A and D are of rank r, then τ (DA) = det(D)τ (A). Proof. As DA is of rank r, τ (DA) is simply the product of its invariant factors. On the other hand, from the notion of determinantal divisors (see [23] for details), the product of 28  the invariant factors of DA is GCD det((DA)L ) : L ⊆ {1, . . . , s}, |L| = r , where (DA)L denotes the submatrix of DA by picking columns in L. Since det((DA)L ) = det(D) det(AL ),  we have τ (DA) = det(D) · GCD det(AL ) : L ⊆ {1, . . . , s}, |L| = r , which is det(D)τ (A). Lemma 2.6.4. Let A be an r × s integer matrix, r ≤ s, and E a unimodular matrix with rows E1 , . . . , Er . Suppose di | Ei A for all i = 1, 2, . . . r. Let D be a diagonal matrix of size r × s with diagonal entries di ’s. If rank(A) = rank(D) and τ (A) | τ (D), then E is a front and D a diagonal form of A. Proof. Let ` = rank(D). Without loss of generality, assume that d`+1 = · · · = dr = 0. Let B be a square integer matrix of order s such that EA = DB. Let D0 be the submatrix of D by taking the first ` rows and first ` columns, and let B 0 be the submatrix of B by taking the first ` rows. Note that DB = D0 B 0 t O(r−`)×s , and hence τ (DB) = τ (D0 B 0 ) = det(D0 )τ (B 0 ), where the last equality is due to lemma 2.6.3. Now, since A and EA share the same row module over Z, we have τ (A) = τ (EA) = τ (DB) = det(D0 )τ (B 0 ). On the other hand, it is given that τ (A) | τ (D) = det(D0 ), which forces τ (A) = det(D0 ) and τ (B 0 ) = 1, i.e., B 0 is row-unimodular. Hence, there is a unimodular extension of B 0 to F 0 . By letting F = (F 0 )−1 , we get EAF = D, where both E and F are unimodular. k Proof of (e). Let U12 = Y02k t Y12k , where Yitk are defined in section 2.3. Then by the notation k of theorem 2.5.2, U12 N2 (G) = B(e; (r)k−r , (k − r)r ), where e = r(k − r). By theorem 2.5.2, a k list of diagonal factors of U12 N2 (G) is (eg/h)1 , (h)1 , (g)k−2 , where g = k −2r, h = GCD{r, k}. k k If k 6= 2r, then rank(U12 N2 (G)) = k and τ (U12 N2 (G)) = eg k−1 . Since the index of
primitivity of Kr,k−r is 2 when 2 ≤ r ≤ k − 2, by theorem 2.3.2(a), rank(N2 (G)) = k2 and k τ (N (G)) | 2(2)−k eg k−1 . 2 Let
k D = diag ( eg )1 , (h)1 , (2g)k−2 , (2)(2)−(2k−2) , (1)k−2 . h 29 If we can find a unimodular matrix E such that EN2 (G) = DB for some integer matrix B,
k then we are done by lemma 2.6.4 since rank(D) = k2 and τ (D) = 2(2)−k eg k−1 .

Let E be the k2 × k2 matrix k 1(k) + `e/h × second row of W12 o 1 row k second row of W12 o 1 row 2 k−3 X i=1

  1{wi ,x} − 1{wi ,y} − (k − 2r − 1) 1{x,z} − 1{y,z} ,          x y z       v2 vk−1 vk v3 .. . vk−1 .. . vk .. . vk−2 vk−1 vk vk−2 vk vk−1 and {wi }k−3 i=1 = X\{x, y, z} 1{x,y} + 1{x,vk } + 1{y,vk } , {x, y} ⊆ {v2 , . . . , vk−1 } except {x, y} = {v2 , v3 } 1{x,vk } , x ∈ {v2 , . . . , vk−1 }                                                 k − 2 rows , k−2 2
− 1 rows k − 2 rows     where ` is an integer such that 1 + `r/h ≡ 0 (mod g/h). Here, we assume the edges that index the columns of E are ordered lexicographically.

The bottom left k2 − k ×k submatrix of E is a zero matrix. By a suitable permutation




of the bottom k2 − k rows, the bottom right k2 − k × k2 − k submatrix will become upper-trianglar with only 1’s on the diagonal. The top left k × k submatrix is 30 1 + `e/h 1(k)−2 2 1 + `e/h 1 1 1 1 0(k)−4 . −1>k −3 (2) I((k)−3)×((k)−3) 2 2 1 0 −1 2 By some elementary row operations, we can see that this matrix has determinant ±1. Hence, E is unimodular, and it remains to show that EN2 (G) gives the correct factors. Let Ei denote the i-th row of E. Then
k N2 (G) E1 N2 (G) = 1(k) + `e/h × second row of W12 2 = e1k! + `e/h × vector with entries r or k − r = e × vector with entries 1 + `r/h or 1 + `(k − r)/h which are all divisible by eg/h by the definition of `.
k E2 N2 (G) = second row of W12 × N2 (G) = vector with entries r or k − r which are all divisible by h. For 3 ≤ i ≤ k, note that each column of N2 (G) corresponds to a G0 ∼ = Kr,k−r . Let P1 and P2 be the two partite sets of G0 with |P1 | = r and |P2 | = k − r. If x, y ∈ P1 or x, y ∈ P2 , then the product of Ei with this column is 0. If x ∈ P1 and y ∈ P2 , then if z ∈ P1 , the product of Ei with this column is 1 × |P2 \{y}| + (−1) × |P1 \{x, z}| + (k − 2r − 1) = (k − r − 1) − (r − 2) + (k − 2r − 1) = 2(k − 2r) = 2g; if z ∈ P2 , the product of Ei with this column is 1 × |P2 \{y, z}| + (−1) × |P1 \{x}| − (k − 2r − 1) = 0. Similar results hold if x ∈ P2 and y ∈ P1 . Hence, all the entries in Ei N2 (G) are divisible by 2g.
For k + 1 ≤ i ≤ k2 − (k − 2), any triangle has 2 or 0 edges incident with any complete bipartite graph. Hence, all the entries in Ei N2 (G) are divisible by 2. 31 If k = 2r, then by deleting repeated columns from N2 (G), we get the matrix k−1 k−1 k−1 W21 W1,r−1 − 2W2,r−1 , Ṅ = k−1 J − W1,r−1 where J is the matrix of all 1’s. This is because there is a bijection between graphs G0 isomorphic to Kr,r and r − 1 subsets R not containing v1 , and for each edge {x, y}, we can easily check that N2 (G)({x, y}, G0 ) = Ṅ ({x, y}, R). k−1 Multiplying the bottom layer of Ṅ by W21 and adding this to the top layer yield k−1 2J − 2W2,r−1 N̈ = . k−1 J − W1,r−1 2 1 i=0 i=0 By lemma 2.3.1(a), t Yi2k−1 and t Yi1k−1 are unimodular matrices of order k−1 2
and k − 1 respectively, so if we multiply them to the top and bottom layers respectively, the new matrix ... N shares the same row module as N̈ .

k−1 r−1 2 k−1 J − 2 Y0,r−1 2 2
k−1 r−2 2(k − 2)J − 2 1 Y1,r−1 ... N= k−1 2J − 2Y2,r−1
k−1 (k − 1)J − r−1 Y0,r−1 1 k−1 J − Y1,r−1 3r(r − 1)1 k−1 2(k − 2)J − 2(r − 2)Y1,r−1 = k−1 2J − 2Y2,r−1 r1 k−1 J − Y1,r−1 . 32 ... By doing simple row operations, we can clear the top two layers of N to get 0 O(k−2)×(k−1) r−1 k−1 2J − 2Y2,r−1 e= N . r1 k−1 J − Y1,r−1
−(k−1) b be the bottom three layers of N e, D b = diag (2)(k−1 2 ) , (r)1 , (1)k−2 and B an Let N b = DB. b b ) = det(D)τ b (B) = integer matrix such that N Lemma 2.6.3 then implies that τ (N 2 k−1 r2( 2 )−(k−1) since τ (B) = 1 because B has the same row module as t Y k−1 which is rowi=0 i,r−1 unimodular. Now, if we let
k D = diag ( eg )1 , (h)1 , (2g)k−2 , (2)(2)−(2k−2) , (1)k−2 , h k 2 then rank(D) =
b ) = rank(N2 (G)) since g = 0, and τ (D) = τ (N b) = − (k − 1) = rank(N τ (N2 (G)). By lemma 2.6.4, E is a front and D the corresponding diagonal form of N2 (G). k Proof of (f ). Similar to the proof of (e), U12 N2 (G) = B(e; (r − 1)r , (k − r − 1)k−r ), where

k e = 2r + k−r since h = r. By theorem 2.5.2, a list of diagonal factors of U12 N2 (G) is 2 (eg/h)1 , (h)1 , (g)k−2 , where g = k − 2r, h = GCD{r − 1, g, e}. If k 6= 2r, since the index of primitivity of Kr ∪˙ Kk−r is 2 when 2 ≤ r ≤ k − 2, by theorem
k 2.3.2(a), rank(N (G)) = k and τ (N (G)) | 2(2)−k eg k−1 . Let 2 2 2 1 1 k−2 (k2)−(2k−1) , (1)k−1
, ) , (h) , (2g) , (2) D = diag ( 2eg h where  = GCD{k, 2}. It suffices to determine a unimodular E such that EN2 (G) = DB for some integer matrix B. When k is odd, let E be the k 2

× k2 matrix 33 k 1(k) + `e/h × second row of W12 2 +eg/h × [0(k)−3 , 1, 1, 1] 2 k second row of W12 k−3 X i=1    o

  1{wi ,x} − 1{wi ,y} − (k − 2r − 1) 1{x,z} − 1{y,z} ,          x y z       v2 vk−1 vk v3 .. . vk−1 .. . vk .. . vk−2 vk−1 vk vk−2 vk vk−1 and {wi }k−3 i=1 = X\{x, y, z} 1{w,x} + 1{w,y} + 1{x,z} + 1{y,z} , w x y z v2 .. . v4 .. . vk−1 .. . vk .. . v2 vk−2 vk−1 vk v2 vk−1 vk v3 v3 .. . v4 .. . vk−1 .. . vk .. . v3 vk−2 vk−1 vk v3 .. . vk−1 .. . vk .. . v4 .. . vk−4 vk−3 vk−1 vk vk−4 vk−2 vk−1 vk vk−4 vk−1 vk vk−3 vk−3 vk−2 vk−1 vk vk−3 vk−1 vk vk−2 1{x,y} ,                                                                                                        {x, y} = {v2 , vk }, {v3 , vk }, . . . , {vk−1 , vk }, {vk−2 , vk−1 }    1 row 1 row k − 2 rows , k−2 2
− 2 rows k − 1 rows 34 where ` is an even integer such that 1 + `(r − 1)/h ≡ 0 (mod g/h). This is possible since g = k − 2r is odd. Here, we assume the edges that index the columns of E are ordered lexicographically. By the exact same argument as in (e), this matrix E is unimodular. To show that EN2 (G) gives the correct factors, let Ei be the i-th row of E. As ` is even, we have 1 + `(r − 1)/h ≡ 1 + `(k − r − 1)/h ≡ g/h (mod 2g/h). So
k E1 N2 (G) = 1(k) + `e/h × second row of W12 + eg/h × [0(k)−3 , 1, 1, 1] N2 (G) 2 2 = e1k! + `e/h × vector with entries r − 1 or k − r − 1 +eg/h × vector with entries 1 or 3 = e × vector with entries 1 + `(r − 1)/h or 1 + `(k − r − 1)/h +eg/h × vector with entries 1 or 3 ≡ (eg/h)1k! + (eg/h)1k! ≡ 0k! (mod 2eg/h).
k E2 N2 (G) = second row of W12 × N2 (G) = vector with entries r − 1 or k − r − 1 which are all divisible by h. For 3 ≤ i ≤ k, note that each column of N2 (G) corresponds to a G0 ∼ = Kr ∪˙ Kk−r . If x and y are in the same clique of G0 , then the product of Ei with this column is 0. If x ∈ Kr and y ∈ Kk−r , then if z ∈ Kr , the product of Ei with this column is 1 × (r − 2) + (−1) × (k − r − 1) − (k − 2r − 1) = −2(k − 2r) = −2g; if z ∈ Kk−r , the product of Ei with this column is 1 × (r − 1) + (−1) × (k − r − 2) + (k − 2r − 1) = 0. Similar results hold if x ∈ Kk−r and y ∈ Kr . Hence, all the entries in Ei N2 (G) are divisible by 2g.
For k + 1 ≤ i ≤ k2 − (k − 2), any 4-cycle has 4, 2 or 0 edges incident with Kr ∪˙ Kk−r . Hence, all the entries in Ei N2 (G) are divisible by 2. When k is even and r − 1 ≡ λ (mod 2h), where λ = 0 or h, we use the matrix E almost the same as in the case when k is odd, except that the first two rows are replaced by o k 1(k) + `e/h × second row of W12 1 row 2 o k second row of W12 + λ × [0(k)−3 , 1, 1, 1] 1 row 2 where ` is an integer, not necessarily even, such that 1 + `(r − 1)/h ≡ 0 (mod g/h). This change does not affect the unimodularity of E, and we only need to verify whether the 35 product of these two rows with N2 (G) gives the correct factors. Let E1 and E2 be the first and second row respectively. Then
k N2 (G) E1 N2 (G) = 1(k) + `e/h × second row of W12 2 = e1k! + `e/h × vector with entries r − 1 or k − r − 1 = e × vector with entries 1 + `(r − 1)/h or 1 + `(k − r − 1)/h which are all divisible by eg/h by the definition of `. Before we work on E2 N2 (G), we claim that k−r−1 ≡ r−1 (mod 2h). If r−1 is odd, then k −r −1 is also odd since k is even and we are done. If r −1 is even, then r and k −r are both odd. Since h | e = r(r−1)/2+(k−r)(k−r−1)/2, i.e., r(r−1)+(k−r)(k−r−1) ≡ 0 (mod 2h), we have r − 1 ≡ r(r − 1) ≡ −(k − r)(k − r − 1) ≡ k − r − 1 (mod 2h). Now,
k + λ × [0(k)−3 , 1, 1, 1] N2 (G) E2 N2 (G) = second row of W12 2 = vector with entries r − 1 or k − r − 1 + λ × vector with entries 1 or 3 ≡ λ1k! + λ1k! ≡ 0k! (mod 2h). If k = 2r, we proceed in a similar manner as in (e). First, by taking the complement of the matrix in (e), we get the matrix k−1 k−1 k−1 J − W21 W1,r−1 + 2W2,r−1 Ṅ = k−1 W1,r−1 which has the same column module as N2 (G). 36 k−1 Multiplying the bottom layer of Ṅ by W21 and adding this to the top layer yield k−1 J + 2W2,r−1 . N̈ = k−1 W1,r−1 2 1 By multiplying t Yi2k−1 and t Yi1k−1 to the top and bottom layers respectively, the new i=0 i=0 ... matrix N becomes k−1 k−1 J + 2 r−1 Y0,r−1 2 2
k−1 (k − 2)J + 2 r−2 Y1,r−1 1
... N=
k−1 J + 2Y2,r−1
k−1 r−1 Y0,r−1 1 3(r − 1)2 1 k−1 (k − 2)J + 2(r − 2)Y1,r−1 k−1 J + 2Y2,r−1 = . (r − 1)1 k−1 Y1,r−1 k−1 Y1,r−1 ... By doing simple row operations, we can clear the top two layers of N to get 0 O(k−2)×(k−1) r−1 e= N k−1 J + 2Y2,r−1 . (r − 1)1 k−1 Y1,r−1
−(k−1) b be the bottom three layers of N e, D b = diag (1)(k−1 2 ) , (r − 1)1 , (1)k−2 and B Let N b = DB. b b ) = det(D)τ b (B) = an integer matrix such that N Lemma 2.6.3 then implies that τ (N k−1 k−1 (r − 1)2( 2 )−(k−1) since τ (B) = 2( 2 )−(k−1) because B has the same row module as Y k−1 t 0,r−1 k−1 k−1 Y1,r−1 t 2Y2,r−1 . 37 Now, if we let
k D = diag ( 2eg )1 , (h)1 , (2g)k−2 , (2)(2)−(2k−1) , (1)k−1 , h where  = GCD{k, 2}. However, since k = 2r, we automatically have k being even, so  = 2
b ) = rank(N2 (G)) since g = 0, and in this situation. So rank(D) = k2 − (k − 1) = rank(N k b ) = τ (N (G)) since h = r − 1. By lemma 2.6.4, E is a front and τ (D) = h2(2)−(2k−1) = τ (N 2 D the corresponding diagonal form of N2 (G). 38 Chapter 3 Diagonal forms of incidence matrices arising from subgraphs of complete bipartite graphs 3.1 Diagonal forms of U · N (G) In this chapter, we let W be a 2n × n2 incidence matrix of Kn,n with vertices against edges, and let U be a (2n − 1) × n2 matrix obtained from W with the first row replaced by 1, the vector of all ones, and the last row deleted. The matrix U is row-unimodular since U has a submatrix 1n−1 1 1n−1 O(n−1)×(n−1) 0> n−1 I(n−1)×(n−1) , 1n−1 I(n−1)×(n−1) 0> n−1 O(n−2)×(n−1) which is Z-equivalent to I(2n−1)×(2n−1) . Once again, 1i and 0i denote row vectors of all ones and all zeros respectively of length i, and Oi×j denotes a zero matrix of dimensions i by j. 39 Let G be a nonempty subgraph of the complete bipartite graph Kn,n with degrees a1 , . . . , an , b1 , . . . , bn , where ai ’s are the degrees of the vertices in one partite set and bi ’s in the other one, and some of these are possibly zeroes. Let h be the characteristic vector of G, i.e., h is a column vector of length n2 indexed by the edges of Kn,n , with 1 if the edge is in G and 0 otherwise. Let P ∼ = Sn o{a,b} S2 be the permutation group on the vertices of Kn,n which can permute vertices within each partite set and interchange the two partite sets. Let N = N (G) be the matrix with 2(n!)2 columns, each column representing an image of h under the action of P on the vertices. In the following, we try to find a diagonal form for U · N (G). We proceed in a similar manner as in the proof of theorem 2.5.2. In U ·N (G), each column is either [e, ai2 , ai3 . . . , ain , bj2 , bj3 , . . . , bjn ]> or [e, bi2 , bi3 . . . , bin , aj2 , aj3 , . . . , ajn ]> , where e is the number of edges of G and {i1 , i2 , . . . , in } = {j1 , j2 , . . . , jn } = {1, 2, . . . , n}. Pick two columns in U N that are identical except one entry, e.g. [e, a1 , a3 . . . , an , b1 , . . . , bn−1 ]> and [e, a2 , a3 , . . . , an , b1 , . . . , bn−1 ]> . Taking the difference of these two columns, we get [0, a1 −a2 , 0, . . . , 0]> in the column module of U N over Z. Hence, the column module of U N contains ge> k , k = 2, . . . , 2n − 1, where g = GCD{ai − aj , bi − bj } over 1 ≤ i, j ≤ n and ek denotes the k-th standard unit vector of length 2n − 1. So the matrix e e a1 1 > n−1 b1 1> n−1 02n−2 gI(2n−2)×(2n−2) b1 1 > n−1 a1 1> n−1 has the same column module as U N . After some integral row and column operations, we can see that the matrix 40 e 0 02n−3 a1 g̃ 02n−3 0> n−2 0> n−2 (3.1) gI(2n−3)×(2n−3) (a1 + b1 )1> n−1 0> n−1 has the same diagonal form as U N , where g̃ = GCD{ai − bj , ai − aj , bi − bj } = GCD{a1 − b1 , g}. By computing the determinantal divisors (see [23] for details), we have the following theorem. Theorem 3.1.1. A list of diagonal factors of U N is eg 1 ( hc ) , (g̃c)1 , (h)1 , (g)2n−4 ,  1 g where h = GCD{ai , bj } = GCD{a1 , g̃} and c = GCD he , a1 +b , g̃ . (Note that h 6= 0 since G h is nonempty. Note also that g̃ = 0 if and only if g = 0, and in this case, we define gg̃ = 1.) Proof. The GCD of the determinants of 1 × 1 submatrices in (3.1) is GCD{a1 , g̃} = h. The GCD of the determinants of i × i submatrices in (3.1), 2 ≤ i ≤ 2n − 2, is GCD{eg̃g i−2 , g̃g i−1 , a1 g i−1 , g̃g i−2 (a1 + b1 )} = g̃g i−2 hc. The determinant of the full matrix in (3.1) is eg̃g 2n−3 .  1 g Theorem 3.1.2. By lemma 2.5.1, let α, σ ∈ Z be such that GCD α, a1 +b , g̃ = 1 and h   a1 +b1 g g a1 +b1 g `0 0 1 −α a1 +b + σ = GCD , . Then there exist `, ` ∈ Z such that GCD , g̃ − h g̃ h g̃ c h 0 e `α hc = 1. Let β, τ ∈ Z be such that −βa1 + τ g̃ = h. Let `00 = β `e+` (ah 1 +b1 ) . A front E of U N is 41 eg e α hc + σβ hcg̃ 0n−2 e α hc 0n−2 ` `0 + `00 0n−2 `0 0n−2 0 1 0n−2 0 0n−2 0> n−2 −1> n−2 I(n−2)×(n−2) 0> n−2 O(n−2)×(n−2) 0> n−2 0> n−2 O(n−2)×(n−2) −1> n−2 I(n−2)×(n−2) 1 GCD c  a +b 1 1 h , gg̃ , eg where the first three rows correspond to the diagonal factors hc , g̃c and h respectively, and the other rows correspond to the diagonal factors g.  1 g Proof. We first show that E is unimodular. Given that GCD α, a1 +b , g̃ = 1, we have h  e 1  a +b g  e a +b g = 1. Hence, there exist `, `0 ∈ Z, GCD α h , 1 h 1 , g̃ = c, or GCD α hc , c GCD 1 h 1 , g̃  0 e 1 g GCD{`, `0 } = 1, such that `c GCD a1 +b , g̃ − `α hc = 1. So the submatrix h 1 GCD c  a1 +b1 g , g̃ h eg e α hc + σβ hcg̃ e α hc ` `0 + `00 `0 0 1 0 has determinant −1, thus E is unimodular. From (3.1), we note that the column module of U N is the same as that of e 0 02n−3 02n−3 a1 1 > n−1 g̃1> n−1 . M= gI(2n−3)×(2n−3) b1 1 > n−1 −g̃1> n−1 42 Let Ei denote the i-th row of E. The product of the E1 with the first column of M is 
e
e 1g 1g 1 g 1 1 1 GCD a1 +b = c − α a1 +b , g̃ + α a1 +b + σβ ahg̃ + σ g̃g + α a1 +b + σβ ahg̃ c h h h h eg eg eg = σ hcg̃ (h + βa1 ) = σ hcg̃ (−βa1 + τ g̃ + βa1 ) = στ hc . eg The product of E1 with the second column of M is σβ hc , and the product of E1 with eg the (n + 1)-th column of M is α hc . From the definition, it is clear that GCD{β, τ } = eg . GCD{α, σ} = 1, so GCD{στ, σβ, α} = 1. Hence, the GCD of the entries in E1 (U N ) is hc The product of E2 with the first column of M is 0 0 1 +b1 ) `e + `0 (a1 + b1 ) + `00 a1 = `e+` (ah 1 +b1 ) (h + βa1 ) = `e+` (a τ gc. e hc 0 1 +b1 ) The product of E2 with the second column of M is `00 g̃ = β `e+` (a g̃c, and the product of hc g E2 with the (n + 1)-th column of M is `0 g = `0 g̃c g̃c. Recall that GCD{τ, β} = 1. Note that  `e+`0 (a1 +b1 ) 0 g GCD , ` g̃ divides h
 1 g 1 + σ g̃g = −`α he + `0 GCD a1 +b , g̃ = c, −`α he + `0 − α a1 +b h h  0 0 g 1 +b1 ) 1 +b1 ) so GCD τ `e+` (a , β `e+` (a , `0 g̃c hc hc = 1. Hence, the GCD of the entries in E2 (U N ) is g̃c. Finally, it is obvious that the GCD of the entries in E3 (U N ) is h, and the GCD of Ei (U N ) is g for all i ≥ 4. Since the factors of each row in E(U N ) agree with the list of diagonal factors given in theorem 3.1.1, E is a front for U N . 3.2 Primitivity Let u, u0 , v, v 0 be four distinct vertices of Kn,n such that u and u0 are in the same partite set while v and v 0 are in the other one. Let 1{u,v} be a row vector of length n2 , indexed by the edges of Kn,n , such that the entry corresponding to the edge {u, v} is 1 and all other entries are 0. Let f u,u0 ,v,v0 = 1{u,v} + 1{u0 ,v0 } − 1{u,v0 } − 1{u0 ,v} . Such a vector is called a 2-pod over the tuple (u, u0 , v, v 0 ), which is an analogue of the t-pods in section 2.2. If h is a characteristic vector of a nonempty subgraph G of Kn,n , then we say G or h is primitive if GCD(f N (G)) = 1, where f is any 2-pod. 43 Proposition 3.2.1. The collection of 2-pods f u,u0 ,v,v0 over all tuples (u, u0 , v, v 0 ) spans over Z all the integer vectors in nullQ (U ), the null space of U . Proof. Let {u1 , . . . , un } and {v1 , . . . , vn } be the two partite sets of Kn,n . Let g be an integer row vector indexed by {ui , vj }. As nullQ (U ) = nullQ (W ), g is in nullQ (U ) if and only if n n P P g({ui , vj }) = 0 for all ui and g({ui , vj }) = 0 for all vj , so all 2-pods are contained in j=1 i=1 nullQ (U ). We say that ui is an isolated vertex of g if g({ui , vj }) = 0 for all j = 1, . . . , n. Let g be an integer vector in nullQ (U ). If i is the maximum such that ui is not an isolated n P vertex of g and i ≥ 2, then consider g0 = g − g({ui , vj })f u1 ,ui ,v1 ,vj , which is in nullQ (U ) j=2 since it is a linear combination of vectors inside nullQ (U ). Note then that ui is an isolated vertex of g0 since g0 ({ui , vj }) = 0 for all j = 2, . . . , n, and g0 being inside nullQ (U ) means n P that g0 ({ui , vj }) = 0, implying that g0 ({ui , v1 }) = 0. j=1 In this way, we have expressed g as a linear combination of g0 and 2-pods, and if i0 is the maximum such that ui0 is not an isolated vertex of g0 , we have i0 < i. By iterating this e and 2-pods, where g e is in nullQ (U ), process, we can express g as a linear combination of g e satisfies ei ≤ 1. However, g e and the maximum ei such that uei is not an isolated vertex of g e, meaning that g e is a vector being in nullQ (U ) implies that u1 is also an isolated vertex of g of all 0’s. Hence, g is a linear combination of 2-pods. Theorem 3.2.2. If h is primitive, a list of diagonal factors of N is 2 eg 1 ( hc ) , (g̃c)1 , (h)1 , (g)2n−4 , (1)(n−1) , e of EU , where E is defined in and a corresponding front can be any unimodular extension E theorem 3.1.2. We proceed to prove theorem 3.2.2 by first introducing a number of lemmas. The proofs of lemmas 3.2.3 and 3.2.4 can be found in [27] and [20] respectively. Lemma 3.2.3. Let A be an r×s integer matrix. Suppose EA = DA0 for some unimodular E, diagonal D and integer matrix A0 . Let Ei be the i-th row of E and di the i-th diagonal entry of D. If the conditions Ei b ≡ 0 (mod di ) for i = 1, . . . , r are sufficient for the existence of an 44 integer vector solution x of Ax = b, then D is a diagonal form for A and E a corresponding front. Lemma 3.2.4. Given a rational matrix A and a column vector b, the system Ax = b has an integer vector solution x if and only if for every rational row vector y, yA ≡ 0 (mod 1) implies yb ≡ 0 (mod 1). Lemma 3.2.5. If h is primitive, then any rational row vector y such that yN ≡ 0 (mod 1) implies y ≡ zU (mod 1) for some rational vector z. Proof. Let f = f u,u0 ,v,v0 be a 2-pod. Let h(u,v) , h(u0 ,v0 ) and h(u,v)(u0 ,v0 ) be the image of h under the permutations (u, v), (u0 , v 0 ) and (u, v)(u0 , v 0 ) respectively. By direct computation, hf , hi f > = h+h(u,v)(u0 ,v0 ) −h(u,v) −h(u0 ,v0 ) . As h is primitive, f > will be in the column module of N over Z. Now, f y> = yf > ≡ 0 (mod 1) since yN ≡ 0 (mod 1). Note that f can run through all 2-pods, so Fy> ≡ 0 (mod 1), where F is a matrix whose rows are all the 2-pods f . We claim that there is an integer vector solution x to Fx = Fy> . For every rational row vector w such that wF ≡ 0 (mod 1), wF is an integer vector in the null space of U . By proposition 3.2.1, wF = w0 F for some integer vector w0 , so wFy> = (w0 F)y> ≡ w0 (Fy> ) ≡ 0 (mod 1). Our claim then follows from lemma 3.2.4. Let x be our integer vector solution to Fx = Fy> , or F(y> − x) = 0. This implies that y − x> is in the row space of U , so y = zU + x> for some rational vector z, i.e., y ≡ zU (mod 1). Lemma 3.2.6. If h is primitive, N x = b has an integer vector solution x if and only if U N x0 = U b has an integer vector solution x0 . Proof. The direction “only if” is trivial. Assume that x0 is an integer vector solution of U N x0 = U b. Let y be a rational row vector such that yN ≡ 0 (mod 1). By lemma 3.2.5, y ≡ zU (mod 1) for some rational z. Then yb ≡ zU b = zU N x0 ≡ yN x0 ≡ 0 (mod 1). By lemma 3.2.4, we are done. 45 eg , d2 = g̃c, d3 = h and di = g for i = 4, 5, . . . , 2n − 1. Proof of theorem 3.2.2. Let d1 = hc As E is a front of U N , there exists a back F such that EU N F = D where D is a diagonal matrix with diagonal entries di ’s. e be a unimodular extension of EU with rows E ei , i = 1, . . . , n2 . Suppose E ei b ≡ Let E ei b ≡ 0 (mod 1) for i = 2n . . . , n2 . Note that the 0 (mod di ) for i = 1, . . . , 2n − 1 and E first 2n − 1 congruences are equivalent to Ei U b ≡ 0 (mod di ) for i = 1, . . . , 2n − 1, which implies EU b = Dx00 = EU N F x00 for some integer vector x00 . Hence, U N x0 = U b has an integer vector solution x0 = F x00 . By lemma 3.2.6, N x = b has an integer vector solution e is a front of N and d1 , . . . , d2n−1 , (1)(n−1)2 is the corresponding list of x. By lemma 3.2.3, E diagonal factors. 3.3 The nonprimitive case Proposition 3.3.1. Let G be a nonempty subgraph of the complete bipartite graph Kn,n with 2n vertices. Then G is nonprimitive if and only if G is Kn,n , Ks,n ∪˙ {n − s isolated vertices} or Ks,t ∪˙ Kn−s,n−t for some 1 ≤ s, t ≤ n − 1. Proof. Let {u1 , . . . , un } and {v1 , . . . , vn } be the two partite sets of G. Let u ↔ v represent that {u, v} is an edge in G while u = v represent that {u, v} is not. If G is Kn,n , then it is obviously nonprimitive. If G is nonprimitive but not Kn,n , then without loss of generality, u1 , u2 , v1 , v2 satisfy one of the following two cases: (i ) u1 ↔ v1 and u1 ↔ v2 , while u2 = v1 and u2 = v2 ; (ii ) u1 ↔ v1 and u2 ↔ v2 , while u1 = v2 and u2 = v1 . Case (i ). For any u 6= u1 , u2 , either u ↔ vi for both i ∈ {1, 2} or u = vi for both i ∈ {1, 2}, so Γ(v1 ) = Γ(v2 ), where Γ(x) denotes all the neighbors of vertex x. Now, for any v 6= v1 , v2 , either v ↔ u for all u ∈ Γ(v1 ) and v = u0 for all u0 ∈ / Γ(v1 ), or v = u for all u ∈ Γ(v1 ) and v ↔ u0 for all u0 ∈ / Γ(v1 ). Hence, G is either Ks,n ∪˙ {n−s isolated vertices} or Ks,t ∪˙ Kn−s,n−t for some 1 ≤ s, t ≤ n. Case (ii ). For any u 6= u1 , u2 , exactly one of u ↔ v1 and u ↔ v2 occurs. Note that Γ(v1 ) 46 and Γ(v2 ) form a partition of {u1 , . . . , un }. Now, for any v 6= v1 , v2 , either v ↔ u for all u ∈ Γ(v1 ) and v = u0 for all u0 ∈ Γ(v2 ), or v = u for all u ∈ Γ(v1 ) and v ↔ u0 for all u0 ∈ Γ(v2 ). Hence, G is Ks,t ∪˙ Kn−s,n−t for some 1 ≤ s, t ≤ n. Theorem 3.3.2. If G is nonprimitive, then diagonal forms of N (G) can be given by the following. (a) (b) G a list of diagonal factors of N (G) Kn,n (1)1 , (0)n −1 Ks,n ∪˙ {n − s isolated vertices} (s)1 , (h)1 , (1)2n−3 , (0)(n−1) 2 2 1≤s≤n−1 h = GCD{n, s} 2((n−s)(n−t)+st)g̃
1 (c) Ks,t ∪˙ Kn−s,n−t 1≤s≤t≤n−1 hδ 2 , (h)1 , (δg̃)1 , (2g̃)2n−4 , (2)(n−2) , (1)2n−3 g̃ = GCD{n − 2s, t − s}, h = GCD{n, s, t}, δ = GCD{ n−t+s h , 2} (a) is trivial, so we will omit its proof. Proof of (b). By dropping the repetitive columns and applying integral elementary column operations on N , the matrix becomes 47 A B A C1 − C2 .. . .. . 1 1n−1 1> s−1 A C1 − Cs , where A = , −I(n−1)×(n−1) 0> n−s A −Cs+1 .. . .. . A −Cn B is an n × n matrix of all 1’s, and Ci is an n × n matrix with 1’s in the i-th column and 0’s elsewhere. Take the sum of the second to the s-th column and add it to the first column, and take the sum of the (n + 2)-th to the (n + s)-th column and add it to the (n + 1)-th column. After that, in each section of n rows, subtract the last row from each of the other rows. Then add each of the in-th row, 2 ≤ i ≤ n, to the n-th row. Finally, take the sum of the (n + 2)-th to the 2n-th column and add it to the n-th column. The resultant matrix will have the first to the (n − 1)-th row occurring once in every section of n rows. By deleting the repeated rows, the matrix becomes 48 s 1n−2 2 −I(n−2)×(n−2) 1> n−2 . −n s −I(n−1)×(n−1) Take the sum of the second to the (n − 1)-th row and add it to the first row. Then take the sum of the second to the (n − 1)-th column and add it to the n-th column. By rearranging the rows and columns, we have s n 0 0 −n s O2×(2n−3) . O(2n−3)×3 −I(2n−3)×(2n−3) Adding the second row to the first row, subtracting the third column from the first column, and applying the Euclidean algorithm to −n and s, we obtain the desired diagonal form. Proof of (c). We will separate the proof into two cases: Case (i ) s = t and Case (ii ) s < t. Case (i ). In this case, diagonal factors of N (G) can be simplified as 2 2((n−s)2 +s2 )(n−2s)
1 , (h)1 , (δ(n − 2s))1 , (2(n − 2s))2n−4 , (2)(n−2) , (1)2n−3 , hδ where h = GCD{n, s} and δ = GCD{ nh , 2}. By dropping the repetitive columns and applying integral elementary column operations on N , the matrix becomes 49 A1 + · · · + An − (B2 + · · · + Bn ) C 2C A1 − A2 + B2 C −2C .. . .. . A1 − As + Bs C B1 − As+1 + Bs+1 −C .. . .. . B1 − An + Bn −C ··· .. 2C 2C ··· 2C . , −2C −2C ... −2C > where Ai is an n × n matrix with the i-th column 1t 0n−t and 0’s elsewhere, Bi is an > n × n matrix with the i-th column 0t 1n−t and 0’s elsewhere, and 1n−1 C= . −I(n−1)×(n−1) In each section of n rows, take the sum of the second to the n-th row and add it to the first row. For each 1 ≤ i ≤ n, add the (i + (n − 1)n)-th row to the (i + jn)-th row for each 0 ≤ j ≤ s − 1, and subtract the (i + (n − 1)n)-th row from the (i + jn)-th row for each s ≤ j ≤ n − 1. At this moment, from the (n + 1)-th column to the (2n − 1)-th column, 50 there is only one 1 in each of them, and we can use them to clear all other entries in their corresponding (2 + (n − 1)n)-th row to the last row. This gives (1)n−1 in a diagonal form of N. Dropping the (n + 1)-th column to the (2n − 1)-th column and the (2 + (n − 1)n)-th row to the last row, the matrix becomes 0 ) A0 − (B20 + · · · + Bn−1 −C 0 A0 + B20 + Bn0 C0 .. . ··· −C 0 −C 0 .. . ... C0 C0 0 − Bn0 Bs+1 C0 .. . .. . . C0 n − 2t −C 0 0(n−1)2 where A0 is an n × n matrix with the first column n > 1n−1 and 0’s elsewhere, Bi0 is an > n × n matrix with the i-th column n − 2t , −C 0 .. 0 Bn−1 − Bn0 0n−2 −C 0 C0 A0 + Bs0 + Bn0 n−t ··· −1s−1 1n−s and 0’s elsewhere, and 51 0n−1 C0 = . 2I(n−1)×(n−1) In each section of n rows, subtract n − 2t times the last row from the first row, add the last row to each of the second to the t-th row, and subtract the last row from each of the (t + 1)-th to the (n − 1)-th row. Subtract twice the n-th column from the last column. Take the sum of the second to the s-th column and subtract it from the n-th column, and take the sum of the (s + 1)-th to the (n − 1)-th column and add it to the n-th column. For each 2 ≤ i ≤ n − 1, subtract twice the i-th column from the n + (i − 1)(n − 1)-th column. For each 2 ≤ i ≤ n − 1, add the in-th row to the n-th row. At this moment, from the second column to the n-th column, there is only one 1 in each of them, and and we can use them to clear all other entries in their corresponding rows. This gives another (1)n−2 in a diagonal form of N . Dropping the second to the n-th column and the corresponding rows, the matrix becomes 52 A00 s −B 00 ··· −B 00 −B 00 −(n − 2s) A00 ··· −B 00 0(n−1)2 B 00 .. . B 00 .. A00 .. . . B 00 B 00 B 00 −B 00 .. .. . . B 00 n−t n − 2t , 0(n−1)(n−2) −B 00 0n−2 −2(n − 2t) where 0n−2 2t 21> t−1 A00 = −2(n − 2t) 21> t−1 , B 00 = 0> n−1 , 2I(n−2)×(n−2) 0> n−t−1 and there are s sections of A00 above the thick horizontal line. −21> n−t−1 53 For each 1 ≤ i ≤ n − 2, for each 1 ≤ j ≤ n − 1, add the (1 + i(n − 1) + j)-th row to the j-th row. At this moment, from the third column to the (2 + (n − 2)(n − 1))-th column, except the (2 + in)-th column for 1 ≤ i ≤ n − 2, there is only one 2 in each of them, and we 2 can use them to clear all other entries in their corresponding rows. This gives (2)(n−2) in a diagonal form of N . Dropping the third to the (2 + (n − 2)(n − 1))-th column, except the (2 + in)-th column for 1 ≤ i ≤ n − 2 and the corresponding rows, the matrix becomes N 0 = 2st 0n−2 2s1> t−1 −2(n − 2s)1> t−1 0> n−1 O(n−1)×(n−2) −2(n − 2s)I(n−2)×(n−2) 0> n−t−1 s 2(n − 2s)1> n−t−1 −(n − 2s) . 02n−3 2t1> s−1 −2(n − 2t)1> s−1 0> n−2 −2(n − 2t)I(n−2)×(n−2) 0> n−s−1 n−t 2(n − 2s)(n − 2t) O(n−2)×(n−2) 2(n − 2t)1> n−s−1 n − 2t 02n−4 −2(n − 2t) For each 2 ≤ i ≤ t, subtract twice the n-th row from the i-th row. For each 2 ≤ i ≤ s, subtract twice the n-th row from the (n + i − 1)-th row. At this moment, from the third to the (2 + 2(n − 2))-th column, there is only one −2(n − 2s) in each of them, and we can use them to clear all other entries in their corresponding rows. This gives (2(n − 2s))2n−4 in a diagonal form of N . Dropping the third to the (2 + 2(n − 2))-th column and the corresponding rows, the 54 matrix becomes   2(n − 2s)(n − 2t)      s . −(n − 2s) 0   n−t n − 2t −2(n − 2t) 2st 0 Let θ, φ ∈ Z be such that φ is odd and θn + φs = h = GCD{n, s}. This is possible since if one choice of φ is even, then nh is odd, and we can pick φ − nh as our new φ. Using s = t, and applying a series of integral elementary row and column operations to this matrix, we get   2s2 0 2(n − 2s)2         ∼   ∼  s  s −(n − 2s) 0 −(n − 2s) 0     n 0 −2(n − 2s) n−s n − 2s −2(n − 2s)     (n − s)2 + s2 0 0 (n − s)2 + s2 0 0           ∼  − φ−1  ∼ s −(n − 2s) 0 n + φs −(n − 2s) 0 2     n 0 −2(n − 2s) n 0 −2(n − 2s)     2 2 2 2 (n − s) + s 0 0 (n − s) + s 0 0          ∼  θn + φs h −(n − 2s) 0 −(n − 2s) −(2θ + φ − 1)(n − 2s) ∼      n 0 −2(n − 2s) n 0 −2(n − 2s)     2 2 )(n−2s) ((n−s)2 +s2 )(n−2s) 0 ((n−s) +s 0 0 0 h h         ∼ h h  . −(n − 2s) 0 0 0     n(n−2s) n(n−2s) 0 −2(n − 2s) 0 −2(n − 2s) h h  2s2 0 2(n − 2s)2  If nh is even, then the last matrix is equivalent to   2 2 0 ((n−s) +sh )(n−2s) 0     h . 0 0   0 0 −2(n − 2s) If nh is odd, then the last matrix is equivalent to    ((n−s)2 +s2 )(n−2s) 0 0 0 0 h       h  ∼ h 0 0 0    0 n − 2s −2(n − 2s) 0 n − 2s  2((n−s)2 +s2 )(n−2s) h  0 0  .  55 Case (ii ). In a manner similar to case (i ), by dropping the repetitive columns and applying integral elementary column operations on N , the first n2 columns of the matrix are identical to those in case (i ). However, there are an additional 2n − 1 columns, which are p> r> p> −r> .. . ··· r> r> ··· r> r> ··· 2(t − s)C ... p> −r> p> −r> .. . , .. p> . −r> q> −r> .. . ... q> where p = r> −r> 1s 0n−s , q = 0s 1n−s , r = 2(t − s) 0n−1 , 56 1n−1 C= , −I(n−1)×(n−1) and there are s sections above the first thick horizontal line, t − s sections between the two thick horizontal lines and n − t sections below the second thick horizontal lines. Now, together with the first n2 columns, apply the same row and column operations as in case (i ) to get rid of the last n−1 rows, the n-th row in each of the i-th section, 2 ≤ i ≤ n−1, as well as the j-th row, 2 ≤ j ≤ n − 1, in each of the i-th section, 2 ≤ i ≤ n − 1. The remaining rows in these extra 2n − 1 columns are N 00 = 2st − 2(t − s)2 2(t − s)(n − 2s) 2(t − s)(n − 2t) 0n−2 2s1> s−1 2(2s − t)1> t−s −2(t − s)1> s−1 On×(n−2) 0> n−1 −2(t − s)I(n−2)×(n−2) 0> n−t−1 2(t − s)1> s−1 2s − t . −2(t − s)1> s−1 −2(t − s)I(n−2)×(n−2) 0> n−t−1 n−s −2(t − s) 0n−2 2t1> s−1 −2(t − s)1> t−s −2(t − s)1> t−s 2(t − s)1> t−s O(n−1)×(n−1) 2(t − s)1> n−t−1 0n−2 −2(t − s) Take the first column in N 0 in case (i ) and subtract it from the first column in N 00 . For 57 each 2 ≤ i ≤ t, subtract twice the n-th row from the i-th row. For each 2 ≤ i ≤ s, subtract twice the n-th row from the (n + i − 1)-th row. At this moment, from the third to the (2 + 2(n − 2))-th column in N 0 , there is only one −2(n − 2s) or −2(n − 2t) in each of them, and from the second to the (n − 1)-th column and from the (n + 1)-th to the (2n − 2)-th column in N 00 , there is only one −2(t − s) in each of them. We can use them to clear all other entries in their corresponding rows. This gives (2GCD{n − 2s, t − s})2n−4 in a diagonal form of N . Dropping the second to the (n − 1)-th row and the (n + 1)-th to the (2n − 2)-th row and the corresponding columns in both N 0 and N 00 , the combined matrix becomes   2st 0 2(n − 2s)(n − 2t) −2(t − s)2 2(t − s)(n − 2s) 2(t − s)(n − 2t)      s −(n − 2s) 0 −(t − s) 0 −2(t − s)  .   n−t n − 2t −2(n − 2t) t−s −2(t − s) 0 Note that adding twice the fourth column with the fifth column gives the last, so we can eliminate the last column. Add n − 2t times the second row and n − 2s times the last row to the first row. Add the second row to the last row. Subtract the fifth column from the second column. Then the matrix becomes   (n − s)(n − t) + st 0 0 0 0      , s −(n − 2s) 0 −(t − s) 0   n−t+s 0 −2(n − 2t) 0 −2(t − s) which is equivalent to      (n − s)(n − t) + st 0 s n−t+s 0    g̃ 0  ,  0 2g̃ where g̃ = GCD{n − 2s, t − s}. Let θ, φ, ξ ∈ Z be such that θn+φs+ξt = h = GCD{n, s, t}. Applying a series of integral elementary row and column operations to this matrix, we get 58  (n − s)(n − t) + st 0    (n − s)(n − t) + st 0 0       2θ+φ+3ξ−1  ∼ s g̃ 0  ∼ s + −φ−ξ+1 (n − 2s) + (t − s) g̃ 0 2 2    n−t+s 0 2g̃ n−t+s 0 2g̃     (n − s)(n − t) + st 0 0 (n − s)(n − t) + st 0 0          θn + φs + ξt g̃ (2θ + φ + ξ − 1)g̃  ∼  h −g̃ 0  ∼     n−t+s 0 2g̃ n−t+s 0 2g̃     ((n−s)(n−t)+st)g̃ ((n−s)(n−t)+st)g̃ 0 0 0 0 h h         h −g̃ 0  ∼ h 0 0.     (n−t+s)g̃ (n−t+s)g̃ 0 0 2g̃ 2g̃ h h 0     If n−t+s is even, then the last matrix is equivalent to h   ((n−s)(n−t)+st)g̃ 0 0 h     h 0 0.   0 0 2g̃ If n−t+s is odd, then the last matrix is equivalent to h    ((n−s)(n−t)+st)g̃ 0 0 0 0 h       h 0 0  ∼ h 0    0 g̃ −2g̃ 0 g̃  2((n−s)(n−t)+st)g̃ h  0 0  .  59 Chapter 4 Inclusion matrices arising from multisets 4.1 v for multisets Inclusion matrix Ctk Let X = {x1 , x2 , . . . , xv } be a set of size v, and let S = [a1 , a2 , . . . , ak ] be a submultiset of X of size k, where every ai is from X and they are not necessarily distinct. Also, the order of the elements does not matter. For example, [1, 1, 1, 2, 2] is a submultiset of {1, 2, 3} of size 5, and [1, 1, 1, 2, 2] = [2, 1, 1, 2, 1]. For each element xi ∈ X, let si denote the number of occurences of xi in S, and we (s ) (s ) (s ) write S = [x1 1 , x2 2 , . . . , xv v ]. Hence, each submultiset S of size k corresponds to a tuple P (s1 , . . . , sv ) of nonnegative integers such that si = k. We denote it as S ∼ (si )vi=1 . Let 0 ≤ t ≤ k. Denote the set of k-submultisets of X by S and the set of t-submultisets

v+k−1 v × matrix with rows indexed by T ∈ T and columns by by T. Let Ctk be a v+t−1 t k Q si
v S ∈ S such that for each T ∼ (ti )vi=1 and S ∼ (si )vi=1 , Ctk (T, S) = , which calculates ti v the number of ways to extract T from S. It is worth noting that Wtkv is a submatrix of Ctk v when v ≥ t + k, since if both S and T are sets, then Ctk (T, S) = 1 if T ⊆ S and 0 otherwise. v A fundamental relation for inclusion matrices Ctk is given by the following lemma. v Lemma 4.1.1 ( [19]). For 0 ≤ i ≤ t ≤ k, Citv Ctk = k−i v Cik . t−i
v This chapter is going to study the row, column and null module of Ctk , and give the v diagonal forms of Ctk for all parameters t, k and v. 60 4.2 Row, column and null module v Let cS denote the column of Ctk corresponding to S ∈ S. For each T = [a1 , . . . , at ] ∈ T, let (k−t) ST = [x1 , a1 , . . . , at ] ∈ S be an extension of T , the k-submultiset containing T and k − t v be the square extra copies of x1 . So if T ∼ (ti )vi=1 , then ST ∼ (t1 + k − t, t2 , . . . , tv ). Let Dtk v submatrix of Ctk consisting of all the columns S0 := {cST }T ∈T . Let A = (a1 , a2 , . . . , at , b1 , b2 , . . . , bt ) ∈ X 2t be an ordered 2t-tuple. Let PA = Q (ai − bi ) ∈ Z[X] be a polynomial, and pA be a column vector indexed by T such that pA (T ) denotes the coefficient of T in the expansion of PA , so (−1)|{θi :θi =bi }| . P pA (T ) = Q (θ1 ,...,θt )∈ {ai ,bi }: T =[θ1 ,...,θt ] This is analogous to the t-pods in chapter 2 and 2-pods in chapter 3. In fact, it is proved v in [19] that {pA }A∈X 2t spans over Z all the integer vectors in nullQ (Ct−1,t ). v Lemma 4.2.1. Dtk pA = pA . Proof. Fix A = (a1 , . . . , at , b1 , . . . , bt ) ∈ X 2t . We will show that for each T ∈ T, P T 0 ∈T v Dtk (T, ST 0 )pA (T 0 ) = pA (T ). v (T, ST 0 )pA (T 0 ) 6= 0 only if T 0 = [θ1 , θ2 , . . . , θt ] for some Fix T ∼ (ti )vi=1 . Each term Dtk Q (k−t) Θ = (θ1 , . . . , θt ) ∈ {ai , bi } and T can be extracted from ST 0 = [x1 , θ1 , θ2 , . . . , θt ]. For each 0 ≤ r ≤ t1 , let ΓΘ,r be the set of (t − r)-subsets {i1 , i2 , . . . , it−r } of {1, 2, . . . , t} such (r) v that T can be written as [x1 , θi1 , θi2 , . . . , θit−r ]. As Dtk (T, ST 0 ) calculates the number of ways to extract T from ST 0 , we split the term in the following way: for each Θ, r and (r) {i1 , . . . , it−r } ∈ ΓΘ,r , we extract x1 (k−t) in T from x1 in ST 0 and θi1 , . . . , θit−r in T from θi1 , . . . , θit−r in ST 0 . Then the summation becomes P v P v Dtk (T, ST 0 )pA (T 0 ) = Dtk (T, ST 0 )(−1)|{θi :θi =bi }| T 0 ∈T T 0 =[θ1 ,...,θ Q t ]: (θ1 ,...,θt )∈ {ai ,bi } = P P P Q 0≤r≤t1 Θ∈ {ai ,bi } {i1 ,...,it−r }∈ΓΘ,r k−t (−1)|{θi :θi =bi }| . r
61 In this summation, for each r > 0, for each {i1 , . . . , it−r } ∈ ΓΘ,r , if we fix (θi1 , . . . , θit−r ), then there are 2r choices of {θ1 , . . . , θt }\{θi1 , . . . , θit−r } to extend it to Θ. Among all these choices, exactly half of the extensions have |{θi : θi = bi }| being an odd number and the other half even, so these terms will cancel in the summation. This leaves the terms corresponding
to r = 0. In this case, T = T 0 , and k−t = 1, so the summation is simply 0 (−1)|{θi :θi =bi }| = pA (T ). P Q (θ1 ,...,θt )∈ {ai ,bi }: T =[θ1 ,...,θt ] Using the same notation introduced in section 2.3, we use tMi to denote the matrix composed by stacking the rows of the matrices Mi . v v consisting of the rows corresponding to those be the submatrix of Cjt Lemma 4.2.2. Let Ejt
v j-submultisets containing no x1 . Then if i ≤ t, the row module of t t−j Ejt over Z is the i−j 0≤j≤i same as that of Citv . Proof. As t−j i−j
v v v Cit , = Eji Ejt t−j 0≤j≤i i−j t
v v Cit . It suffices to show that Ei = t Eji
v Ejt = 0≤j≤i v has determinant 1. t Eji 0≤j≤i Assume that the rows and columns of Ei are arranged in lexicographical order. Let Jm denote the submultiset corresponding to the m-th row and Hn the i-submultiset corresponding to the n-th column of Ei . If Jm ∼ (0, j2 , . . . , jv ) is of size j, then Hm ∼ (i − j, j2 , . . . , jv ), so Ei (Jm , Hm ) = 1. If n < m, then Hn ∼ (h1 , h2 , . . . , hv ) has h1 ≥ i − j, so there is one `, 2 ≤ ` ≤ v, such that h` < j` , and Ei (Jm , Hn ) = 0. Therefore, Ei is upper-triangular with only 1’s on the diagonal. v v Theorem 4.2.3. The columns of Dtk form a basis in the column module of Ctk over Z. Proof. Let S = [a1 , . . . , ak ] ∈ S. We start by assuming that a1 , . . . , ak ∈ X\{x1 } are distinct, i.e., we also assume v ≥ k + 1. It suffices to show that cS = P ri 0≤i≤t P c[x(k−t+i) ,a ,...,a δ⊆{1,...,k} |δ|=t−i 1 δ1 δt−i ] 62 for some integers ri , i = 0, . . . , t. Take r0 = 1. Then the entries corresponding to [aδ1 , . . . , aδt ], δ ⊆ {1, . . . , k} and |δ| = t, (j) are 1’s on both sides. In summand i, the entries corresponding to [x1 , aδ1 , . . . , aδt−j ] is



(j) (k−t+i) k−t+i k−t+j , since there are k−t+i ways to extract x1 from x1 and k−t+j choices j j−i j j−i
for δt−j+1 , . . . , δt−i . As k−t+j = 0 when i > j, in order to choose integers ri such that all the j−i (j) entries corresponding to [x1 , aδ1 , . . . , aδt−j ] are cancelled for j > 0, we only need to check
k−t+j



k−t+j k−t+i k−t+j that k−t+i is divisible by for all i < j, which is true since = j j−i j j j−i

k−t k−t+j . j−i j P Next, we remove all assumptions on S, but realize that cS = 1[aδ1 ,...,aδt ] , where δ⊆{1,...,k} |δ|=t 1T is the characteristic column vector of length v+t−1 with 1 at the entry corresponding to t
T and 0 elsewhere. Hence, our proof above works for all S ∈ S. The next theorem is motivated by the work in [2], which attempts to study Hartman’s conjecture on large sets of t-designs [13, 15] through understanding the row module of the inclusion matrix Wtkv for sets. More details will be introduced in section 6.1. A conjecture in [2] is that the signs are constant in each row of the reduced row echelon form of Wtkv . They believe that there are certain relationships between this property and the property that there is a vector of 1’s and −1’s in the null space of Wtkv . Although the author cannot v prove this sign property for Wtkv , he manages to prove it for Ctk instead. v ev be Theorem 4.2.4. Let the columns of Ctk be arranged in lexicographical order, and let C tk v ev are integers, and the signs of the reduced row echelon form of Ctk . Then all entries of C tk each row are constant, i.e., either all entries are nonnegative or all entries are nonpositive except the leading 1. ev are integers follows from theorem 4.2.3 since Dv are Proof. The fact that all entries of C tk tk v the leading columns of Ctk . We will finish by showing that when {cS : S ∈ S} are expressed as a linear combination of {cST : T ∈ T}, the signs of the coefficients of cST always stay unchanged. To do that, we first determine rj ’s in theorem 4.2.3.
Claim. rj = (−1)j k−t+j−1 . j 63 Proof of claim. The claim holds for j = 0. When j > 0, there is a recurrence relation for j−1 j−1

P k−t
P i k−t k−t+i−1 rj , namely rj = − r . By induction, we have r = − (−1) , so we i j j−i j−i i i=0 i=0 would like to show that j P (−1)

i k−t k−t+i−1 j−i i=0 j

P k−t −(k−t) the identity becomes j−i i=0
x+y . j i i
= 0. Note that (−1)i k−t+i−1 = i = 0, which is true as a special case of j P i=0 −(k−t) , so i
x j−i
y
i = This claim shows that if S = [a1 , . . . , ak ] has a1 , . . . , ak ∈ X\{x1 } all distinct, then when cS is expressed as a linear combination of {cST : T ∈ T}, the sign of the coefficient of cST is always (−1)j if T ∼ (j, t2 , . . . , tv ). Next, notice if a1 , . . . , a` = x1 , ` < k − t, and a`+1 , . . . , ak ∈ X\{x1 } are all disj j

−(k−t)

P P ` ` `−(k−t) tinct, then the coefficient of c[x(k−t+j) ,a ,...,a ] is r = = = i j−i j−i i j δ1 δt−i 1 i=0 i=0
(−1)j k−t−`+j−1 , so the sign is still (−1)j . j Finally, if a`+1 , . . . , ak ∈ X\{x1 } are not distinct, then the coefficient of cST , T ∼
. Hence, the sign of the (j, t2 , . . . , tv ), is a positive integral multiple of (−1)j k−t−`+j−1 j coefficient of cST is always (−1)j . 4.3 v Integer solutions and diagonal forms of Ctk v Theorem 4.3.1. There exists an integer vector solution xfor Ctk x = a if and only if Citv a ≡ 0 (mod k−i ) for i = 0, 1, . . . , t. t−i
(4.1) v Proof. The “only if” statement is trivial since Ctk x = a for some integer vector x implies
v Citv a = Citv Ctk x ≡ 0 (mod k−i ) for i = 0, 1, . . . , t by lemma 4.1.1. t−i v To prove the “if” statement, we proceed by induction on t. When t = 0, Ctk is a row
v ), i.e., a is an integer, then there always exists vector of all 1’s, so if C00 a ≡ 0 (mod k−0 0−0 v an integer vector x such that Ctk x = a. When t > 0, by lemma 3.2.4, it suffices to show v that if condition (4.1) holds, then for any rational vector y, yCtk is an integer vector implies ya ∈ Z. 64 v Let a0 = Ct−1,t a. For i = 0, 1, . . . , t − 1, by lemma 4.1.1,
v v v ), a = (t − i)Citv a ≡ 0 (mod (t − i) k−i Ct−1,t a0 = Ci,t−1 Ci,t−1 t−i 1 v so Ci,t−1 ( k−t+1 a0 ) ≡ 0 (mod k−i ). t−1−i
Claim. There exists an integer vector z indexed by t-submultisets and a rational vector y0 v indexed by (t − 1)-submultisets such that y = z + y0 Ct−1,t . If the claim holds, v v v v v , − zCtk = yCtk Ctk = y0 Ct−1,t ((k − t + 1)y0 )Ct−1,k 1 which is an integer vector. By induction hypothesis, (k − t + 1)y0 ( k−t+1 a0 ) = y0 a0 ∈ Z. As a result, ya = za + y0 a0 ∈ Z and we are done. v Proof of claim. By lemma 4.2.1, pA is in the column module of Ctk over Z, so y · pA v is an integer since yCtk is an integer vector. If P denotes the matrix with all pA as its columns, then yP is an integer vector. As {pA }A∈X 2t spans over Z all the integer vectors v in the null space to the row space of Ct−1,t over Q, we can select columns of P to obtain a unimodular matrix. Then P is row-unimodular by definition, so there exists an integer vector z such that yP = zP . This implies y − z is in the null space to the column space of v P , or equivalently, it is in the row space of Ct−1,t . Hence, there exists a rational vector y0 v such that y − z = y0 Ct−1,t . v Theorem 4.3.2. A diagonal form for Ctk is given by diagonal entries

v+i−1 − v+i−2 , i = 0, 1, . . . , t. i i−1 Proof. Let D be a diagonal matrix with entries k−i t−i
k−i t−i
of multiplicities with multiplicities v+i−1 i
− v+i−2 , i−1
i = 0, 1, . . . , t. From the proof in lemma 4.2.2, Et = t Eitv is a unimodular matrix, and 0≤i≤t
k−i v v v 0 Eit Ctk ≡ O (mod t−i ), so Et Ctk = DA for some integral matrix A0 .
Assume that Eitv a ≡ 0 (mod k−i ) for i = 0, 1, . . . , t. By lemma 4.2.2, there exists a t−i
v
unimodular matrix Ui such that Citv = Ui t t−j Ejt . Then i−j 0≤j≤i Citv a = Ui t 0≤j≤i t−j i−j
v
Ejt a ≡ 0 (mod k−i ), t−i
65 since t−j i−j
k−j
t−j = k−j i−j
k−i
t−i ≡ 0 (mod k−i ). t−i
By theorem 4.3.1, there exists an integer v v vector solution x for Ctk x = a, and by lemma 3.2.3, D is a diagonal form of Ctk . 66 Chapter 5 Ramsey-type problems 5.1 Zero-sum (mod 2) Ramsey numbers for hypergraphs Let H be a given t-uniform hypergraph on k vertices with e edges, and let m be a positive (t) integer which divides e. Let Kv denote the complete t-uniform hypergraph on v vertices, (t) and let T denote the set of all edges of Kv . In the zero-sum Ramsey problem, we want to determine the smallest integer v ≥ k, called ZRm (H), such that for any coloring c : T → Zm , (t) there exists an isomorphic copy of H in Kv so that the sum of the colors on its edges is 0 in Zm . The zero-sum (mod 2) Ramsey numbers for graphs are completely characterized by Caro [6], and a bound on the ZR2 (H) for t-uniform hypergraphs is given by Wilson [29]. In this section, we will show that ZR2 (H) = k for almost all H, and reproduce Caro’s results on ZR2 (G) in the next section. (t) Let c : T → Zm be a coloring of Kv and let c be the t-vector over Zm such that c(T ) = c(T ). Let H ↑v be the hypergraph obtained by adjoining isolated vertices to H so that the total number of vertices is v. If h is the characteristic vector of a spanning subgraph (t) H 0 of Kv which is isomorphic to H ↑v , then hc, hi gives the sum of the colors on the edges of H 0 . Hence, ZRm (H) is the smallest integer v ≥ k such that rowZm (Nt (H ↑v )) does not contain a nowhere zero vector. In particular, if m = 2, then ZRm (H) is the smallest integer v ≥ k such that the vector 1 of all ones is not in rowZm (Nt (H ↑v )). 67 Lemma 5.1.1. Let A be an r × s integer matrix, D, E and F be its diagonal form, front and back respectively, i.e., EAF = D. Let d1 , d2 , . . . , ds be the diagonal entries of D, with the understanding that di = 0 if r < i ≤ s. Let s be an integer row vector of length s. Then s is in rowZm (A) if and only if the i-th entry of sF is divisible by GCD{di , m} for i = 1, 2, . . . , s. Proof. The vector s is in rowZm (A) if and only if there exists an integer vector x such that xA ≡ s (mod m), which is equivalent to (xE −1 )EA ≡ s (mod m). This equation has an integer vector solution x if and only if yD ≡ sF (mod m) has an integer vector solution y, and the necessary and sufficient conditions for the existence of an integer vector solution y are those given in the statement of the lemma. Theorem 5.1.2. Let h be a t-vector based on a k-set X, k ≥ 2t, and suppose that h and all of its shadows are multiples of primitive vectors. Let e be the sum of all entries of h. Then 1 ∈ rowZm (Nt (h)) if and only if GCD{e, m} = 1. Proof. Let E and D be defined as in the statement of theorem 2.3.3, and let F be the corresponding back such that such that ENt F = D. The first row of E is 1(k) , so the first row of ENt is e1k! . As the first row of D is [e, 0k!−1 ], 2 we have e1k! F = [e, 0k!−1 ], or 1k! F = [1, 0k!−1 ]. By lemma 5.1.1, 1 ∈ rowZm (Nt (h)) if and only if 1 is divisible by GCD{e, m}, or equivalently, GCD{e, m} = 1. By taking m = 2, we obtain the following theorems as corollaries. Theorem 5.1.3. If H is a simple t-uniform hypergraph on k ≥ 2t vertices with even number of edges such that H and all of its shadows are primitive, then ZR2 (H) = k. A slightly weaker but probably more remarkable version is stated in the following theorem. Theorem 5.1.4. Let H be a simple random t-uniform hypergraph on k vertices with even number of edges. Then ZR2 (H) = k almost surely as k → ∞. Proof. This follows from theorems 2.4.1, 2.4.2, and 5.1.3. The following theorem gives sharp upper bounds on ZR2 (H). 68 Theorem 5.1.5. Let H be a simple t-uniform hypergraph on k ≥ 2t vertices with even number of edges. Then (a) ZR2 (H) ≤ k + t; (b) if H is neither empty nor complete, then ZR2 (H) ≤ k + t − 1. Proof. (a) When v ≥ k + t, the hypergraph H ↑v and all of its shadows have at least t isolated vertices. By proposition 2.2.3, H ↑v and all of its shadows are primitive, so the result follows from theorem 5.1.3. (b) When v ≥ k + t − 1, H ↑v has at least t − 1 isolated vertices. By proposition 2.2.4, if the primitivity γ of H ↑v is greater than 1, then either all edges of H are present or all are absent. In other words, if H is neither empty nor complete, then γ = 1, or H is primitive. The j-th shadow of H ↑v , j ≥ 1, has at least t − 1 isolated vertices, so they are all primitive by proposition 2.2.3. Theorem 5.1.3 completes the proof. (t) We remark that Caro [6] proves the special case of theorem 5.1.5(a) for H = Kk , while Wilson [29] proves the full statement of theorem 5.1.5(a). Also, it is proved in [29] that if
(t) H = Kk and kt is even, then ZR2 (H) = k + 2q , where 2q is the smallest power of 2 that appears in the base 2 representation of t but not in the base 2 representation of k. So even when H is complete, ZR2 (H) ≤ k + t − 1 holds except when t is a power of 2, in which case ZR2 (H) = k + t. 5.2 When is 1 ∈ rowZp (N2(G)) for graphs G? The following theorem on zero-sum (mod 2) Ramsey numbers for graphs is from [6]. Theorem 5.2.1 (Y. Caro). Let G be a simple graph on k vertices with even number of edges. Then 69     k+2    ZR2 (G) = k + 1      k if G = Kk , if G = Kr ∪˙ Kk−r or G 6= Kk has all vertices of odd degree, otherwise. This theorem is a corollary of theorem 5.2.2 below. Caro’s proof of theorem 5.2.1 is significantly shorter than that obtained from our viewpoint, but our theorem makes assertions for all primes p. It is interesting to note that p = 2 is often a special case in the statement of theorem 5.2.2. In theorem 5.2.2, we opt to restrict our results for primes p rather than general m, because the statements become more complex in the general case. Theorem 5.2.2. Let G be a simple graph with k ≥ 4 vertices with e edges and let p be a prime divisor of e. Let δ1 , . . . , δk be the degree sequence of G, g = GCD1≤i,j≤v (δi − δj ), and h = GCD{δ1 , . . . , δk , e}. Then 1 ∈ rowZp (N2 (G)) if and only if one of the following holds: (i ) G is primitive with p | g but p - h, (ii ) G = Kk , (iii ) G = K1,k−1 and p > 2, (iv ) G = K1 ∪˙ Kk−1 and (p = 2 or p - k − 2), (v ) G = Kr ∪˙ Kk−r , 2 ≤ r ≤ k − 2, and (p = 2 or (p | g but p - h)). Proof of theorem 5.2.2 implying theorem 5.2.1. A graph G which satisfies condition (i ) is a graph which is not complete but all the degrees are odd, so for this type of G, ZR2 (G) ≥ k+1. However, the graph G↑k+1 does not satisfy any of the above five conditions, since it has an isolated vertex whose degree is even. Hence, ZR2 (G↑k+1 ) = k + 1, implying ZR2 (G) = k + 1. If G = Kk , then ZR2 (G) ≥ k + 1 by (ii ). However, G↑k+1 = K1 ∪˙ Kk−1 , so ZR2 (G↑k+1 ) ≥ k + 2 by (iv ). As ZR2 (G) ≤ k + 2 by theorem 5.1.5(a), we have ZR2 (G) = k + 2. If G = Kr ∪˙ Kk−r , 1 ≤ r ≤ k − 1, then (iv ) and (v ) implies that ZR2 (G) ≥ k + 1. Therefore, ZR2 (G) = k + 1 since ZR2 (G) ≤ k + 1 by theorem 5.1.5(b). 70 To prove theorem 5.2.2, we restate lemma 5.1.1 for primes. Lemma 5.2.3. Let A be an r × s integer matrix, D, E and F be its diagonal form, front and back respectively, i.e., EAF = D. Let d1 , d2 , . . . , ds be the diagonal entries of D, with the understanding that di = 0 if r < i ≤ s. Let s be an integer row vector of length s. If p is a prime, then s is in rowZp (A) if and only if p | di implies p divides the i-th entry of sF for i = 1, 2, . . . , s. Proof of theorem 5.2.2 when G is primitive. Recall from theorem 2.5.4 that the front E can be taken as (a1 ,g) h ` he α β Y02 O2×(k−2) Ok×((k)−k) 2 0> k−2 −1> k−2 I(k−2)×(k−2) O((k)−k)×k 2 Y12 · I((k)−k)×((k)−k) 2 2 , O((k)−k)×k 2 I((k)−k)×((k)−k) 2 2
k and the corresponding diagonal form is D = diag (eg/h)1 , (h)1 , (g)k−2 , (1)(2)−k . If we multiply the vector [β, −`e/h, 0(k)−2 ] to both sides of EN2 F = D, then L.H.S. = 2 Y02 N2 F = e1n! F , and R.H.S. = [βeg/h, −`e, 0k!−2 ], so we get 1F = [βg/h, −`, 0k!−2 ]. If p - g, then p - h and p - β since β(a1 , g)/h − α`e/h = 1 by the definition of α and β, so 1 ∈ / rowZp (N2 ) since p | eg/h but p - βg/h. If p | h, then p - ` since GCD{`, a1 , g} = 1 by definition, while h | (a1 , g), so we also have 1 ∈ / rowZp (N2 ). Finally, if p | g but p - h, then p | eg/h and p | βg/h, so 1 ∈ rowZp (N2 ). 71 If G is nonprimitive, we study case by case, following theorem 2.6.2. It is trivial that 1 ∈ rowZp (N2 (G)) if G = Kk and 1 ∈ / rowZp (N2 ) if G is empty. Proof of theorem 5.2.2 when G = K1,k−1 . Note that N2 and EN2 share the same row module, so 1 ∈ rowZp (N2 ) if and only if 1 ∈ rowZp (EN2 ). Recall from the proof of theorem 2.6.2(c)
that the bottom k2 − k rows of EN2 are 0’s, and the top k rows can be given by 2 0k−1 0> k−1 · I(k−1)×(k−1) 0 0 1> k−2 0> k−2 0 1 −1 0k−3 I(k−2)×(k−2) 1 ··· 0 0 1> k−2 0> k−2 0 1 0k−3 −1 0k−3 I(k−2)×(k−2) . 1 0k−3 Let us denote the first matrix in this product as D0 and the second as F 0 . If we multiply the vector [−(k − 4), −(k − 4), 1k−2 ] to F 0 , we get 1k! . As F 0 is row-unimodular, this is the unique way to obtain 1 in rowZp (F 0 ) for all primes p. Hence, 1 ∈ rowZp (EN2 ) if and only if [−(k − 4), −(k − 4), 1k−2 ] ∈ rowZp (D0 ), which obviously holds true if p > 2, and fails if p = 2 since 2 = p | e = k − 1 implies k is odd, meaning that k − 4 is also odd. Proof of theorem 5.2.2 when G = K1 ∪˙ Kk−1 . Similar to the above proof for the case G =
K1,k−1 , we recall from the proof of theorem 2.6.2(d ) that the bottom k2 − k rows of EN2 are 0’s, and the top k rows can be given by k−2 0> k−1 0k−1 · I(k−1)×(k−1) 0 1 1k−2 0> k−2 1> k−2 (J − I)k−2 1 0 0 1k−3 ··· 0 1 1k−2 0> k−2 1> k−2 (J − I)k−2 . 1 0 0 1k−3 Again, we denote the first matrix in the product as D0 and the second as F 0 . Multiplying [−(k − 4), 0, 1k−2 ] to F 0 , we get 1k! . As F 0 is row-unimodular, 1 ∈ rowZp (EN2 ) if and only if [−(k − 4), 0, 1k−2 ] ∈ rowZp (D0 ). This obviously holds true if and only if p - k − 2, or p | k − 2 and p | k − 4, which forces p = 2. 72 Proof of theorem 5.2.2 when G = Kr,k−r , 2 ≤ r ≤ k − 2. Recall from theorem 2.6.2(e) that
k a diagonal form of N is D = diag (eg/h)1 , (h)1 , (2g)k−2 , (2)(2)−(2k−2) , (1)k−2 , and a corre2 sponding front E is given in the proof of theorem 2.6.2(e). If we multiply [1, −`e/h, 0(k)−k ] 2 to both sides of EN2 F = D, then L.H.S. = Y02 N2 F = e1F , and R.H.S. = [eg/h, −`e, 0k!−2 ], so we get 1F = [g/h, −`, 0k!−2 ]. If p - g, then by lemma 5.2.3, 1 ∈ / rowZp (N2 ); if p | g = k − 2r, then together with p | e = r(k − r), we have p | h = GCD{r, k}. However, g/h and ` cannot be 0 in Zp simultaneously, otherwise we have 1F = 0 in Zp , contradicting that the rows of F are linearly independent over all fields. Hence, 1 ∈ / rowZp (N2 ). Proof of theorem 5.2.2 when G = Kr ∪˙ Kk−r , 2 ≤ r ≤ k − 2. Recall from theorem 2.6.2(f ) that
k a diagonal form of N is D = (2eg/h)1 , (h)1 , (2g)k−2 , (2)(2)−(2k−1) , (1)k−1 , where  = 2 GCD{k, 2}. When k is odd, if E is the corresponding front such that EN2 F = D, we multiply the vector [1, −`e/h, 0(k)−5 , −eg/h, −eg/h, −eg/h] to both sides of the equation. Then L.H.S. = 2 e1F , and R.H.S = [2eg/h, −`e, 0(k)−5 , −eg/h, −eg/h, −eg/h, 0k!−(k) ], so we get 2 2 1F = [2g/h, −`, 0(k)−5 , −g/h, −g/h, −g/h, 0k!−(k) ]. 2 2 Note that 1 ∈ rowZp (N2 ) only if p | 2g/h. If p | 2, i.e., p = 2, then since ` is defined to be even, we have 1 ∈ rowZp (N2 ) by lemma 5.2.3. If p | g/h, then since 1 + `(r − 1)/h ≡ 0 (mod g/h) by definition of `, p - `, so 1 ∈ rowZp (N2 ) if and only if p - h. When k is even and r − 1 ≡ h (mod 2h), if E is the corresponding front, we multiply the vector [1, −`e/h, 0(k)−5 , `e, `e, `e] to both sides of EN2 F = D. Then L.H.S. = e1F , and 2 R.H.S. = [eg/h, −2`e, 0(k)−5 , `e, `e, `e, 0k!−(k) ], so we get 2 2 1F = [g/h, −2`, 0(k)−5 , `, `, `, 0k!−(k) ]. 2 2 73 Note that 1 ∈ rowZp (N2 ) only if p | g/h. Recall from the proof of theorem 2.6.2(f ) that k − r − 1 ≡ r − 1 (mod 2h), so g = k − 2r ≡ 0 (mod 2h), implying that g/h is even. Hence, if p = 2, 1 ∈ rowZp (N2 ). If p | g/h, we again have p - ` for the same reason above, so 1 ∈ rowZp (N2 ) if and only if p - h. Finally, when k is even and r − 1 ≡ 0 (mod 2h), if E is the corresponding front, we multiply the vector [1, −`/h, 0(k)−2 ] to both sides of EN2 F = D. Then we have 2 1F = [g/h, −2`, 0k!−2 ], and the rest of the proof is the same as the case when r − 1 ≡ h (mod 2h). 5.3 Zero-sum (mod 2) bipartite Ramsey numbers In sections 5.1 and 5.2, we use results from chapter 2. In this section, however, we use results from chapter 3. Let G be a nonempty subgraph of the complete bipartite graph Kn,n , and let h be its characteristic vector. Let e be the number of edges in G, and let p be a prime that divides e. Let N = N (G) be the matrix whose columns are all the images of h under the automorphism group on Kn,n . The objective of this section is to investigate when 1 ∈ rowZp (N ), and reproduce Caro and Yuster’s results [7] on zero-sum bipartite Ramsey numbers. Theorem 5.3.1. If h is primitive and p is a prime such that p | e, where e is the number of edges in G, then 1 is in rowZp (N ) if and only if either of the following holds: (i ) p - h and p | g̃, (ii ) p = 2, p - g̃ and p | g, (iii ) p 6= 2, p - g̃, p | g and p - a1 + b1 .
e F = D, where D = diag ( eg )1 , (g̃c)1 , (h)1 , (g)2n−4 , (1)(n−1)2 is the diagonal Proof. Let EN hc e is the corresponding front given in theorem 3.2.2. If we multiply the vector form of N and E eg e e e F = D, then L.H.S. = [1, 0n2 −1 ]U N F = [`0 , −α hc , `00 α hc −`0 σβ hcg̃ , 0n2 −3 ] to both sides of EN 74 eg eg , −α eg̃ , `00 α ec − `0 σβ eg , 0n2 −3 ] = [`0 hc , −α eg̃ , −βe, 0n2 −3 ] 1n2 N F = e1F , and R.H.S. = [`0 hc h g̃c h

0 1 g since `00 α ec − `0 σβ eg = β ec `e+` (ah 1 +b1 ) α − `0 σ gg̃ = β ec `α he − `0 GCD a1 +b , g̃ = −βe. Thereg̃c h fore, we have g 1F = [`0 hc , −α hg̃ , −β, 0n2 −3 ]. To determine whether 1 ∈ rowZp (N ), we will apply lemma 5.2.3 and do the following analysis. If p | h, then by lemma 2.5.1, β can be chosen in theorem 3.1.2 such that GCD{β, h} = 1, g g so 1 ∈ / rowZp (N ). If p - h but p | g̃, then since hg̃ = h (g/g̃) which divides hc , we have p divides g both `0 hc and −α hg̃ , implying that 1 ∈ rowZp (N ). If p - g̃ but p | g, then since g̃ = GCD{a1 − b1 , g}, we have p - a1 − b1 . If p = 2, then p - a1 + b1 , implying that p - c, so 1 ∈ rowZp (N ). If p 6= 2 and p - a1 + b1 , then 1 ∈ rowZp (N )  1 g by the same argument. If p | a1 + b1 , then p | c. However, p - α since GCD α, a1 +b , g̃ = 1, h so 1 ∈ / rowZp (N ).  1 g Lastly, if p - g, then p - c, and `0 GCD a1 +b , g̃ h − `α he = c implies p - `0 , so 1 ∈ / rowZp (N ). Theorem 5.3.2. If h is nonprimitive and p is a prime such that p | e, 1 is in rowZp (N ) if and only if either of the following holds: (i ) G is Kn,n , (ii ) G is Ks,n t {n − s isolated vertices} with p - s, (iii ) G is Ks,t t Kn−s,n−t with p - h and p | 2g̃ , where h = GCD{n, s, t}, g̃ = GCD{n − 2s, t − δ  n−t+s s}, δ = GCD ,2 h Proof. (i ) Every row of N is 1, so 1 is in rowZp (N ). 2 (ii ) The list of diagonal factors of N given in theorem 3.3.2(b) is (s)1 , (h)1 , (1)2n−3 , (0)(n−1) . By keeping track of the row operations in the proof of theorem 3.3.2(b), the corresponding front E of N is 75 P Q R S ··· Q , .. . .. . R S where 1 P = 0> n−2 0 R= 1n−2 −(n − 2) I(n−2)×(n−2) −1> n−2 0n−2 1 −I(n−1)×(n−1) 1> n−1 0n−1 0 ,S= 1 ,Q= , 0> n−2 On×(n−1) 1 I(n−1)×(n−1) −1> n−1 0n−1 1 , and there are n horizontal sections. The first row of E corresponds to the diagonal factor s, the n-th row corresponds to the diagonal factor h, the second to the (n − 1)-th row and the (in)-th row, 2 ≤ i ≤ n, correspond to the diagonal factor 1, and the rest corresponds to 0. Let EN F = D. From the structure of Ks,n , we see that the first row of EN is s1, so s1F = [s, 02(n!)2 −1 ], the first row of D. Hence, 1F = [1, 02(n!)2 −1 ], 76 and 1 ∈ rowZp (N ) if and only if p - s. )1 , (h)1 , (iii ) The list of diagonal factors of N given in theorem 3.3.2(c) is ( 2((n−s)(n−t)+st)g̃ hδ 2 (δg̃)1 , (2g̃)2n−4 , (2)(n−2) , (1)2n−3 , and a corresponding front E of N is P0 P0 ··· P0 R0 Q0 S0 .. . ... T0 T0 ··· R0 S0 T0 U0 , where 1 P 0 = 0> n−2 1n−2 ω1 I(n−2)×(n−2) , −1> n−2 0n−2 1+µ 0 ω2 Q 0 = 0> n−2 µ ω2 1n−2 ω3 (1 − (n − 2s))I(n−2)×(n−2) , ((n − 2s) − 1)1> n−2 µ1n−2 ω4 77 1n−2 1 − (n − 2s) I(n−2)×(n−2) 1> n−2 0 0n−2 1 −1 −1n−2 (n − 2s) − 1 I(n−2)×(n−2) 1> n−2 0n−2 1 1 R 0 = 0> n−2 S 0 = 0> n−2 0 1 − hν (1 + µ) T0 = On×(n−1) 0> n−1 , U0 = , , 1 − hν µ (1 − hν µ)1n−2 ω5 0> n−2 I(n−2)×(n−2) 1> n−2 0 0n−2 1 
 e ν , ν = n − t + s, ω = 1 − and e = (n − s)(n − t) + st, µ = 2θ+φ+ξ−1 1 + 1 − (1 + µ) , 1 2 h h 

ω2 = 1 − he 1 + 1 − hν µ , ω3 = 1 − he ω4 + ω5 , ω4 = 1 − (n − 2s) + (2 − (n − 2s))µ, ω5 = 2 − (n − 2s) − hν ω4 . The first row of E corresponds to the diagonal factor 2eg̃ , the n-th hδ row corresponds to the diagonal factor h, the (n(n−1)+1)-th row corresponds to the diagonal factor δg̃, the second to the (n − 1)-th row and the (1 + in)-th row, 1 ≤ i ≤ n − 2, correspond to the diagonal factor 2g̃, the (i + jn)-th row, 2 ≤ i ≤ n − 1, 1 ≤ j ≤ n − 2, correspond to the diagonal factor 2, while the (in)-th row, 2 ≤ i ≤ n − 1, and the ((n − 1)n + 2)-th to the last row correspond to the diagonal factor 1. This matrix works as a front since the first, n-th and (n(n − 1) + 1)-th rows come from the row operations in the proof of theorem 3.3.2(c). As for the other rows, we can multiply to N directly to check. 78 Now, if we multiply [1, 0n−2 , he , 0n(n−1) , he , 0n−1 ] to both sides of EN F = D, then L.H.S. = e1F , and R.H.S. = [ 2eg̃ , 0n−2 , e, 0n(n−1) , he δg̃, 0n−1 ], so we have hδ 2g̃ 1F = [ hδ , 0n−2 , 1, 0n(n−1) , δg̃ , 0n−1 ]. h If p | h, then 1 ∈ / rowZp (N ) by lemma 5.2.3. If p - h and p - 2g̃ , then 1 ∈ / rowZp (N ) either. δ , then regardless whether p | δg̃, we still have 1 ∈ rowZp (N ). If p - h but p | 2g̃ δ Next, we apply these results to the zero-sum bipartite Ramsey problem. Let G be a simple nonempty bipartite graph with e edges. A p-coloring on the edges of G is a function P c : E(G) → Zp . If T ∈E(G) c(T ) = 0 over Zp , then we say that G is a zero-sum (mod p) graph with respect to c. If p | e, then the zero-sum bipartite Ramsey number ZBp (G) is the smallest integer n such that for every p-coloring of Kn,n , there exists a zero-sum (mod p) copy of G in Kn,n . The zero-sum (mod 2) bipartite Ramsey numbers are fully characterized by Caro and Yuster [7] in the following theorem, and we are going to provide our own proof here. Theorem 5.3.3 (Y. Caro and R. Yuster). Let G be a simple nonempty bipartite graph with even number of edges. Let n be the minimum number such that the vertices of G can be divided into two partite sets, each of size not exceeding n. Then isolated vertices are added to G if necessary to make each partite set of G have size n, and by abuse of notation, we call this new graph G instead. Let ZB2 (G) denote the zero-sum bipartite Ramsey number of G modulo 2. Then ZB2 (G) = n + 1 if and only if one of the following holds: (i ) G is primitive with all degrees odd, (ii ) G is primitive such that for any partition of the vertices of G into two partite sets, each of size n, all degrees in one partite set are odd and all degrees in the other partite set even, (iii ) G = Kn,n , (iv ) G = Ks,n t {n − s isolated vertices} with s odd, (v ) G = Ks,t t Kn−s,n−t with n even and at least one of s and t is odd. Otherwise, ZB2 (G) = n. 79 Proof. Let p = 2. It is easy to see that theorems 5.3.1(i ), 5.3.1(ii ), 5.3.2(i ) and 5.3.2(ii ) are respectively equivalent to (i ), (ii ), (iii ) and (iv ) of this theorem. This leaves the only unobvious case, which is theorem 5.3.2(iii ) is equivalent to (v ) of this theorem. If n is odd, then g̃ is also odd. As p - h and p | 2g̃ , we must have δ = 1, implying s and t δ are of the same parity, which contradicts that p divides e = st + (n − s)(n − t). If n is even, then p always divides e. Since p - h, at least one of s and t is odd. If s and t are of opposite parity, then δ is odd and p | 2g̃ . If both s and t are odd, then g̃ is even and again p | 2g̃ . δ δ ZB2 (G) ≥ n + 1 if and only if there exists a 2-coloring on the edges of Kn,n such that all isomorphic copies of G in Kn,n have color sum equal to 1 (mod 2). In other words, 1 is in rowZ2 (N ), which happens if and only if one of the conditions in theorems 5.3.1 and 5.3.2 hold. Note that when two more isolated vertices are added to G so that G is embedded in Kn+1,n+1 , none of these conditions are satisfied, so we always have ZB2 (G) ≤ n + 1. Combining these two directions, this theorem is proved. 5.4 Ramsey problem on hypergraphs induced by equipartitions Let s, t, v be positive integers such that s | t | v. Let X be a set of size v. An s-equipartition or t-equipartition of X is a partition of X into s or t equal parts. Let V and E be the set of s-equipartitions and t-equipartitions of X respectively. Let H = H(s, t, v) be a hypergraph induced by the equipartitions of X, where the vertex set of H is V, and an edge of H is the collection of all s-equipartitions that share a common refinement E ∈ E. Conjecture 5.4.1. For all s, t ∈ N, there exists v0 ∈ N such that for all v ≥ v0 , if s | t | v, then for all 2-colorings of the vertices of H = H(s, t, v), there exists a monochromatic edge, i.e., all the vertices in that edge have the same color. (t) (t) Unlike the classical Ramsey problem, where Kv0 is a subgraph of Kv for all v ≥ v0 , it is not true that H(s, t, v0 ) is always a subgraph of H(s, t, v) for v ≥ v0 , t | v. Hence, 80 it is more difficult to show that hypergraphs H(s, t, v) arising from equipartitions has the Ramsey property. This conjecture originates as a problem from the logician point of view, but the author attempts to solve it from the combinatorial perspective, and is able to verify the conjecture for the case s = 2 and t = 4 by explicit constructions. Lemma 5.4.2. If s = 2, t = 4 and 8 | v, then for all 2-colorings of the vertices of H(s, t, v), there exists a monochromatic edge. Proof. Let {X1 , X2 , . . . , X8 } be an 8-equipartition of a v-set X. Label some 2-equipartitions of X as follows: a : {X1 ∪ X2 ∪ X3 ∪ X4 , X5 ∪ X6 ∪ X7 ∪ X8 }, b : {X1 ∪ X2 ∪ X7 ∪ X8 , X3 ∪ X4 ∪ X5 ∪ X6 }, c : {X1 ∪ X2 ∪ X5 ∪ X6 , X3 ∪ X4 ∪ X7 ∪ X8 }, d : {X2 ∪ X3 ∪ X5 ∪ X8 , X1 ∪ X4 ∪ X6 ∪ X7 }, e : {X2 ∪ X3 ∪ X6 ∪ X7 , X1 ∪ X4 ∪ X5 ∪ X8 }, f : {X2 ∪ X4 ∪ X6 ∪ X8 , X1 ∪ X3 ∪ X5 ∪ X7 }, g : {X2 ∪ X4 ∪ X5 ∪ X7 , X1 ∪ X3 ∪ X6 ∪ X8 }. Then {a, b, c}, {a, d, e}, {a, f, g}, {b, d, f }, {b, e, g}, {c, d, g}, {c, e, f } are edges in H. In fact, these seven edges form a subhypergraph isomorphic to the Fano plane, which is not 2-vertex-colorable, i.e., for all 2-vertex-colorings of H, there always exists a monochromatic edge in H. Lemma 5.4.3. If s = 2, t = 4 and 12 | v, then for all 2-colorings of the vertices of H(s, t, v), there exists a monochromatic edge. Proof. Let {X1 , X2 , . . . , X12 } be a 12-equipartition of a v-set X. Label some 2-equipartitions of X as follows: 81 A : {X1 ∪ X2 ∪ X3 ∪ X4 ∪ X5 ∪ X6 , X7 ∪ X8 ∪ X9 ∪ X10 ∪ X11 ∪ X12 }, B : {X1 ∪ X2 ∪ X3 ∪ X10 ∪ X11 ∪ X12 , X4 ∪ X5 ∪ X6 ∪ X7 ∪ X8 ∪ X9 }, C : {X1 ∪ X2 ∪ X3 ∪ X7 ∪ X8 ∪ X9 , X4 ∪ X5 ∪ X6 ∪ X10 ∪ X11 ∪ X12 }, D : {X1 ∪ X3 ∪ X5 ∪ X7 ∪ X9 ∪ X11 , X2 ∪ X4 ∪ X6 ∪ X8 ∪ X10 ∪ X12 }, E : {X1 ∪ X3 ∪ X5 ∪ X8 ∪ X10 ∪ X12 , X2 ∪ X4 ∪ X6 ∪ X7 ∪ X9 ∪ X11 }, F : {X1 ∪ X3 ∪ X4 ∪ X6 ∪ X8 ∪ X11 , X2 ∪ X5 ∪ X7 ∪ X9 ∪ X10 ∪ X12 }, G : {X1 ∪ X2 ∪ X6 ∪ X7 ∪ X9 ∪ X10 , X3 ∪ X4 ∪ X5 ∪ X8 ∪ X11 ∪ X12 }, H : {X1 ∪ X2 ∪ X6 ∪ X8 ∪ X11 ∪ X12 , X3 ∪ X4 ∪ X5 ∪ X7 ∪ X9 ∪ X10 }, I: {X1 ∪ X2 ∪ X4 ∪ X5 ∪ X8 ∪ X10 , X3 ∪ X6 ∪ X7 ∪ X9 ∪ X11 ∪ X12 }, J: {X1 ∪ X4 ∪ X7 ∪ X8 ∪ X9 ∪ X12 , X2 ∪ X3 ∪ X5 ∪ X6 ∪ X10 ∪ X11 }, K : {X2 ∪ X3 ∪ X5 ∪ X8 ∪ X9 ∪ X10 , X1 ∪ X4 ∪ X6 ∪ X7 ∪ X11 ∪ X12 }, L: {X2 ∪ X3 ∪ X5 ∪ X7 ∪ X11 ∪ X12 , X1 ∪ X4 ∪ X6 ∪ X8 ∪ X9 ∪ X10 }, M : {X2 ∪ X3 ∪ X4 ∪ X6 ∪ X7 ∪ X10 , X1 ∪ X5 ∪ X8 ∪ X9 ∪ X11 ∪ X12 }, N : {X3 ∪ X4 ∪ X5 ∪ X6 ∪ X9 ∪ X12 , X1 ∪ X2 ∪ X7 ∪ X8 ∪ X10 ∪ X11 }, O : {X2 ∪ X4 ∪ X9 ∪ X10 ∪ X11 ∪ X12 , X1 ∪ X3 ∪ X5 ∪ X6 ∪ X7 ∪ X8 }. Then {A, B, C}, {A, D, E}, {B, D, F }, {C, E, F }, {A, G, H}, {B, G, I}, {D, G, J}, {C, H, I}, {E, H, J}, {F, I, J}, {A, K, L}, {B, K, M }, {D, K, N }, {G, K, O}, {C, L, M }, {E, L, N }, {H, L, O}, {F, M, N }, {I, M, O}, {J, N, O} are edges in H. The subgraph of H on these fifteen vertices with these twenty edges is not 2-vertex-colorable by some checking on Mathematica. Theorem 5.4.4. If s = 2 and t = 4, then for all v ≥ 8 such that 4 | v, for all 2-colorings of the vertices of H = H(s, t, v), there exists a monochromatic edge. In other words, conjecture 5.4.1 is true for the case s = 2 and t = 4, with v0 = 8. Proof. If 8 | v or 12 | v, then it is done by lemmas 5.4.2 and 5.4.3. For all v = 4k with k ≥ 2 such that 8 - v and 12 - v, there exists α, β ∈ N such that 8α + 12β = v. Partition X 82 into X 0 ∪ X 00 such that |X 0 | = 8α and |X 00 | = 12β. Let aA denote the 2-equipartition of X such that the 2-equipartition on X 0 is a in lemma 5.4.2 and the 2-equipartition on X 00 is A in lemma 5.4.3. We define other 2-equipartitions of X in the similar manner. Consider the following fifteen 2-equiparitions of X: aA, bB, cC, dD, eE, f F , f G, gH, dI, bJ, eK, dL, gM , aN , cO, which are some of the vertices of H. By lemmas 5.4.2 and 5.4.3, {aA, bB, cC}, {aA, dD, eE}, {bB, dD, f F }, {cC, eE, f F }, {aA, f G, gH}, {bB, f G, dI}, {dD, f G, bJ}, {cC, gH, dI}, {eE, gH, bJ}, {f F, dI, bJ}, {aA, eK, dL}, {bB, eK, gM }, {dD, eK, aN }, {f G, eK, cO}, {cC, dL, gM }, {eE, dL, aN }, {gH, dL, cO}, {f F, gM, aN }, {dI, gM, cO}, {bJ, aN, cO} are edges in H. This subgraph of H is isomorphic to the one in lemma 5.4.3, so it is not 2-vertex-colorable. 83 Chapter 6 Problems in design theory 6.1 Hartman’s conjecture on large sets of designs of size 2 A t-(v, k, λ) design is a collection B of k-subsets (often referred to as blocks) of a v-set X, such that every t-subset of X is contained in exactly λ blocks in B. A large set of t-(v, k, λ) designs of size N , denoted by LS[N ](t, k, v), is a partition of the set of all k-subsets of X into
v−t N disjoint t-(v, k, λ) designs, where N = k−t /λ. A set of trivial necessary conditions for
v−i the existence of a LS[N ](t, k, v) is that N | k−i for i = 0, 1, . . . , t. Hartman [13] conjectured that the trivial necessary conditions are sufficient for the existence of large sets of size N = 2. When N = 2, the existence of a large set of t designs is equivalent to the existence of a vector of all 1’s and −1’s in nullQ (Wtkv ). Hartman’s conjecture is proved in [1] to be true for t = 2 as well as for some other cases (see [15] for more details). Here, we will give an explicit construction for t = 2 and k = 3, which is independent of the results from the literature.
v−1

v−2 and being even, which is The set of trivial necessary conditions are v−0 , 3−0 3−1 3−2 equivalent to v ≡ 2 (mod 4), so v = 2(2w + 1) for some w ∈ N. Let the v vertices be {a1 , . . . , a2w+1 , b1 , . . . , b2w+1 }. Let   aσ 1 b σ 1     aσ2 bσ2    aσ 3 b σ 3 84 denote the 3-pod 1{aσ1 ,aσ2 ,aσ3 } + 1{aσ1 ,bσ2 ,bσ3 } + 1{bσ1 ,aσ2 ,bσ3 } + 1{bσ1 ,bσ2 ,aσ3 } − 1{aσ1 ,aσ2 ,bσ3 } +
1{aσ1 ,bσ2 ,aσ3 } + 1{aσ1 ,aσ2 ,bσ3 } + 1{bσ1 ,bσ2 ,bσ3 } in the nullQ (W23v ). If v = 6, then  a  1   a2  a3      b1 a b a b   1 2  1 3      b2  + a2 b3  − a2 b1       b3 a3 b 1 a3 b 2 is a vector of all ±1’s. In general, if v = 2(2w + 1), consider the vector       aσ1 bσ1 aσ1 bσ2 aσ1 bσ3       X       f= + − aσ2 bσ2  aσ2 bσ3  aσ2 bσ1  × (−1)σ1 +σ2 +σ3 .       {σ1 ,σ2 ,σ3 }⊆[2w+1] σ1 <σ2 <σ3 aσ3 bσ3 aσ3 bσ1 aσ3 bσ2 (6.1) Here, [2w + 1] = {1, 2, . . . , 2w + 1}. We are going to show that f is a vector of ±10 s. For all σ1 < σ2 < σ3 , each of 1{aσ1 ,aσ2 ,bσ3 } , 1{aσ1 ,bσ2 ,aσ3 } , 1{bσ1 ,aσ2 ,aσ3 } , 1{aσ1 ,bσ2 ,bσ3 } , 1{bσ1 ,aσ2 ,bσ3 } , 1{bσ1 ,bσ2 ,aσ3 } only occurs once in the summation, so f has ±1’s in those entries. As for 1{aσ1 ,aσ2 ,aσ3 } and 1{bσ1 ,bσ2 ,bσ3 } , the coefficients are ±(1 + 1 − 1)(−1)σ1 +σ2 +σ3 = ±1. It remains to determine the coefficients of 1{aσi ,aσj ,bσi } and 1{aσi ,bσi ,bσj } , where {i, j, k} = {1, 2, 3}. We will calculate the coefficient of 1{aσi ,aσj ,bσi } for the case where σi < σj , and the computation for the other terms is similar. We see that 1{aσi ,aσj ,bσi } occurs 2w − 1 times in the summation in (6.1), falling into one of the following three categories.   a  σk  (1)  aσi  aσj  a  σi  (2) aσk  aσj bσ i   bσj  × 1 × (−1)σi +σj +σk for 1 ≤ σk < σi ,  bσk  bσj   bσi  × (−1) × (−1)σi +σj +σk for σi < σk < σj ,  bσk 85   a b  σi σj    (3) aσj bσk  × 1 × (−1)σi +σj +σk for σj < σk ≤ 2w + 1.   aσk bσi If σi and σj are odd, the coefficient from (1) is 0, the coefficient from (2) is 1 and the coefficient from (3) is 0, so the total is 1; if σi is odd and σj is even, the coefficient from (1) is 0, the coefficient from (2) is 0, and the coefficient from (3) is −1, so the total is −1; if σi is even and σj is odd, the coefficient from (1) is −1, the coefficient from (2) is 0, and the coefficient from (3) is 0, so the total is −1; if σi and σj are even, the coefficient from (1) is 1, the coefficient from (2) is −1, and the coefficient from (3) is 1, so the total is 1. In any case, the coefficient of 1{aσi ,aσj ,bσi } for σi < σj is always ±1. 6.2 Signed bipartite graph designs Let G be a nonempty proper subgraph of the complete bipartite graph Kn,n with 2n vertices, some of which are possibly isolated. Let G be the collection of subgraphs G0 of Kn,n which are isomorphic to G. We say that there exists a (n, G, λ)-signed bipartite graph design if there exists z : G → Z such that for each edge e ∈ E(Kn,n ), P z(G0 ) = λ. G0 ∈G: E(G0 )3e If λ = 1 and z : G → {0, 1}, then such a design becomes a graph decomposition, which is studied by Wilson [25] and many others. Ushio [22] gives the necessary and sufficient conditions for a complete bipartite graph to be decomposed into smaller complete bipartite graphs. Here, the necessary and sufficient conditions for the existence of a (n, G, λ)-signed bipartite graph design are given. Theorem 6.2.1. Let G be a nonempty proper spanning subgraph of the complete bipartite graph Kn,n . If G has only one connected component of size greater than 1, then there exists a (n, G, λ)-signed bipartite graph design if and only if all the following three conditions hold: (i ) h | λn, 86 (ii ) g̃c | λn(`n + 2`0 + `00 ), eg 1 g | λn(nGCD{ a1 +b , g̃ } + α 2e + σβ hg̃ ), (iii ) eg h h h where g, g̃, h, are defined in section 3.1, and α, β, σ, `, `0 and `00 are defined in theorem 3.1.2. Proof. Note that there exists a (n, G, λ)-signed bipartite graph design if and only if there exists an integer vector solution z to N (G)z = λ1> . If G is primitive, then by theorem 3.2.2, e F = D for some unimodular matrix F , where D contains the list of diagonal factors given EN e −1 DF −1 z = λ1> , or Dz0 = λE1 e > for some integer vector solution z0 , in theorem 3.2.2. So E which exists if and only if di | λEi U 1> for i = 1, 2, . . . , 2n − 1, where Ei is the i-th row of E given in theorem 3.1.2. By definition, U 1> = (n2 , n, . . . , n)> , so λEi U 1> = 0 which is divisible by di for i ≥ 4. When i = 3, 2 and 1, they correspond to the conditions (i ), (ii ) and (iii ) respectively. If G is nonprimitive, then G = Ks,n ∪˙ {n−s isolated vertices}. The conditions (i ) to (iii ) combine to be hs | λ, which is equivalent to s | λn since h = GCD{n, s}. Let E be the front given in the proof of theorem 5.3.2(ii ), and let D be the corresponding diagonal form, given in theorem 3.3.2. Again, there exists a (n, G, λ)-signed bipartite graph design if and only if there exists an integer vector solution to Dz0 = λE1. Note that λE1> is a vector with λn in the first and the n-th entries, λ’s in the in-th entries, 2 ≤ i ≤ n, and 0’s elsewhere. As a result, Dz0 = λE1> has an integer vector solution if and only if s | λn, since other congruent conditions are trivial. Corollary 6.2.2. If G = Ks,t , 1 ≤ s ≤ t ≤ n, then there exists a (n, G, λ)-signed bipartite graph design if and only if st | λn2 . 87 Chapter 7 A problem in matroid theory by Dominic Welsh 7.1 A brief introduction to matroids A matroid M = (X, I) is a combinatorial structure defined on a finite ground set X of n elements, together with a family I of subsets of X called independent sets, satisfying the following three properties: 1. ∅ ∈ I, or I is nonempty. 2. If I ∈ I and J ⊆ I, then J ∈ I. This is sometimes known as hereditary property. 3. If I, J ∈ I and |J| < |I|, then there exists x ∈ I\J such that J ∪ {x} ∈ I. This is known as augmentation property or exchange property. A maximal independent set is called a basis of the matroid. A direct consequence of the augmentation property is that all bases have the same cardinality, and this cardinality is defined as the rank of M. One of the most important examples of matroids is a linear matroid. A linear matroid is defined from a matrix A over a field F, where X is the set of columns of A, and an independent set I ∈ I is a collection of columns which is linearly independent over F. For a linear matroid, the rank is exactly the rank of the matrix A. Since the elements of a linear matroid are the columns of a matrix, it is also called a column matroid. 88 Given a triple of integers (n, r, b), 0 < r ≤ n and 1 ≤ b ≤ n , r
Welsh [24] asked if there exists a matroid of n elements, rank r, and has exactly b bases. It was conjectured that a matroid exists for every such triple, until Mayhew and Royle [17] found the lone counterexample to date, namely (n, r, b) = (6, 3, 11). However, they suggested that this is the only triple where the conjecture fails. In this chapter, we will show that if 1 ≤ b ≤ r+2 , there always exists a matroid satisfying r
the given parameters (n, r, b). We proceed by constructing the matrix, or the linear matroid,
explicitly for all triples (n, r, b) such that n ≤ r + 2. Then if 1 ≤ b ≤ r+2 and n > r + 2, r we simply put zeros in the last n − (r + 2) columns. 7.2 The case 1 ≤ b ≤ r+2 r
Let A be an r × n matrix over Q of rank r, and let b be the number of invertible r × r submatrices of A. Note that b is an invariant if we perform row operations or permute the columns of A, so we can always assume that A = (Ir |M ), where M is an r × (n − r) matrix. Proposition 7.2.1. The number of invertible square submatrices of M is b − 1, and the number of invertible (n − r) × (n − r) submatrices of (In−r |M > ) is b. Proof. Let S be the set of all invertible r × r submatrices of A except the identity matrix in the first r columns, and let T be the set of all invertible square submatrices of M . Let S be a matrix in S with columns i1 , i2 , . . . , ir , where i1 , . . . , ij ≤ r and ij+1 , . . . , ir > r. Then there is a bijection between S and T which sends S to the square submatrix of M with rows {1, 2, . . . , r}\{i1 , i2 , . . . , ij } and columns ij+1 , ij+2 , . . . , ir . Hence, the number of invertible square submatrices of M is b − 1. It is obvious then that the number of invertible square submatrices of M > is b − 1, which implies that the number of invertible (n − r) × (n − r) submatrices of (In−r |M > ) is b. In view of this proposition, it suffices to consider only n ≤ 2r when we study this Welsh’s problem for matrices, since if r < n − r, then we can construct matrices of dimension 89 (n − r) × n instead. In theorem 7.2.3, we prove the conjecture for n ≤ r + 2, so what remains unknown is when r + 3 ≤ n ≤ 2r. The following lemma in number theory will help us to show the existence of matrices satisfying the parameters (n, r, b). Lemma 7.2.2. Let s ≥ 5 be a positive integer, and let k be a nonnegative integer such that 2 k ≤ s −5s . Then there exist nonnegative integers a1 , a2 , . . . , as such that a1 + a2 + · · · + as = s 4 and a21 + a22 + · · · + a2s = s + 2k. Proof. For 5 ≤ s ≤ 32, we verified the lemma by Mathematica; for s ≥ 33, we will use strong induction on s. Suppose the statement is true for all integers u such that 5 ≤ u < s for some s ≥ 33, i.e., 2 , there exist nonnegative integers a1 , . . . , au such that for all nonnegative integers k 0 ≤ u −5u 4 a1 + · · · + au = u and a21 + · · · + a2u = u + 2k 0 . 2 Let t and k be integers such that 0 < t ≤ s − 5 and 0 ≤ k − t 2−t ≤ (s−t) −5(s−t) . Then 4 2 2 2 u := s − t falls in the range 5 ≤ u < s, and k 0 := k − t 2−t ≤ u −5u . By the induction 4 hypothesis, there are nonnegative integers a1 , . . . , as−t such that a1 + · · · + as−t = s − t and
2 a21 +· · ·+a2s−t = s−t+2 k− t 2−t = s+2k−t2 . If we set as−t+1 = t and as−t+2 = · · · = as = 0, then a1 + · · · + as = s and a21 + · · · + a2s = s + 2k, implying that the statement holds true for 2 −5s k satisfying 0 ≤ k − t 2−t ≤ (s−t) −5(s−t) , or equivalently, t 2−t ≤ k ≤ 3t −2st+3t+s . 4 4 i h2 t −t 3t2 −2st+3t+s2 −5s for It now suffices to show that the union of the intervals I(t) := 2 , 4 h 2 i 2 2 2 −5s 0 < t ≤ s − 5 covers 0, s −5s when s ≥ 33. Let α(t) = t 2−t and β(t) = 3t −2st+3t+s . 4 4 2 2 2 2 2 Claim 1. s −5s ≤ β(t) if and only if t ≥ 23 s − 1, which is attainable for some t in the range 4 0 < t ≤ s − 5 if s ≥ 12. Proof of claim 1. This inequality holds if and only if 3t2 − 2st + 3t ≥ 0, which is equivalent to t ≥ 23 s − 1 since t is positive. We finish by noticing that when s ≥ 12, s − 5 ≥ 23 s − 1. Claim 2. α(t − 1) ≤ α(t) ≤ β(t). Proof of claim 2. The first inequality holds since α(t) is an increasing function for t ≥ 1, 90 > 0 when t ≥ 1, considering α as a continuous function on R. The second since α0 (t) = 2t−1 2 inequality holds if and only if 5(s − t) ≤ (s − t)2 , which is always true since t ≤ s − 5. √ Claim 3. α(t) ≤ β(t − 1) if and only if t ≤ 2s+1−2 16s+1 . Proof of claim 3. This inequality holds if and only if t2 − (2s + 1)t + s2 − 3s ≥ 0, which √ √ √ occurs if and only if t ≤ 2s+1−2 16s+1 or t ≥ 2s+1+2 16s+1 . However, t ≥ 2s+1+2 16s+1 is rejected since t < s. √ By claims 2 and 3, if t ≤ 2s+1−2 16s+1 , then I(1) ∪ · · · ∪ I(t − 1) ∪ I(t) forms one closed s−1e h 2 i d 32 S 2  2s+1−√16s+1 s −5s interval. If 3 s − 1 ≤ ⊆ , then claim 1 implies that 0, 4 I(t). 2 t=1 √  2s+1−√16s+1 2 2s+1− 16s+1 2 , we look for integers s satisfying s ≤ , or To obtain 3 s − 1 ≤ 2 3 2 √ equivalently, 3 16s + 1 ≤ 2s + 3. This inequality holds if 33s ≤ s2 , or s ≥ 33. Theorem 7.2.3. If n ≤ r + 2, then for all b such that 1 ≤ b ≤ n , there exists a matrix r
A = (Ir |M ) over Q such that the number of invertible r × r submatrices of A is exactly b. Proof. It is trivial for n = r. If n = r + 1, then A = (Ir |M ) where M is a column vector with the first b − 1 entries 1’s and the rest 0’s. If n = r + 2, let the first column of M have the first s entries 1’s, the second column have the first s entries nonzero, and the rest be all 0’s. Furthermore, assume that there are ai i’s in the second column, 1 ≤ i ≤ s, where a1 + a2 + · · · + as = s. Then the number of invertible r × r submatrices of A is P P P 1 + 2s + i<j ai aj = 1 + 2s + 12 ( i ai )2 − 21 ( i a2i ) P = 1 + 2s + 21 s2 − 12 ( i a2i ),
P 2 and we would like to set it to be b, which gives s + 2( s+2 − b) = i ai . 2
2 2 2 By lemma 7.2.2, if 0 ≤ s+2 − b ≤ s −5s , or equivalently s +11s+4 ≤ b ≤ s +3s+2 , there is 2 4 4 2 2 2 a solution for ai ’s. It is easy to check that the intervals [ s +11s+4 , s +3s+2 ] cover all integers 4 2 b ≥ 39, and the only missing integers are in [1, 20] ∪ [22, 26] ∪ [29, 32] ∪ [37, 38]. Here, we finish the proof by constructing M explicitly for each of these b’s. 91 In the following table, 0 represents a column vector of all 0’s (possibly of length 0), which fills up the column so that M has r rows. b= M= 1 2 1 0 0 9 1 M= 1 1 0 1 4 0 0 10 1 2 0 0 1 1 1 0 5 6 7 1 0 1 1 1 1 0 1 1 0 1 2 0 0 0 0 0 0 1 0 0 b= 3 0 11 12 13 8 1 1 1 1 1 0 1 1 1 0 1 0 0 0 0 0 14 15 16 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 2 1 0 1 0 1 2 1 3 1 3 1 0 1 0 1 0 1 0 1 4 0 0 0 0 0 0 0 0 0 0 1 2 3 0 1 1 1 1 1 0 1 0 0 1 0 0 92 b= M= 17 18 19 20 22 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 2 1 3 1 2 1 3 1 0 1 0 1 3 1 4 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 b= 26 1 1 1 M= 1 1 1 0 29 30 23 24 25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 2 1 3 1 2 1 2 1 3 1 4 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 31 32 37 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 3 1 2 1 2 1 3 1 4 1 2 1 3 1 0 1 0 1 3 1 4 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 2 3 4 0 0 38 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 3 1 3 1 4 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 93 Bibliography [1] S. Ajoodani-Namini, All block designs with b = v k
/2 exist, Disc. Math. 179 (1998), 27–35. [2] M. H. Ahmadi, N. Akhlaghinia, G. B. Khosrovshahi, Ch. Maysoori, On the inclusion matrix W23 (v), preprint. [3] N. Alon and Y. Caro, On three zero-sum Ramsey-type problems, J. Graph Thy. 17 (1993), 177–192. [4] A. Bialostocki and P. Dierker, Zero-sum Ramsey theorems, Congressus Numerantium 70 (1990), 119–130. [5] A. E. Brouwer and C. A. van Eijl, On the p-rank of the adjacency matrices of strongly regular graphs, J. Alg. Combinatorics 1 (1992), 329–346. [6] Y. Caro, A complete characterization of the zero-sum (mod 2) Ramsey numbers, J. Combinatorial Thy. Ser. A 68 (1994), 205–211. [7] Y. Caro and R. Yuster, The characterization of zero-sum (mod 2) bipartite Ramsey numbers, J. Graph Thy. 29 (1998), 151–166. [8] D. B. Chandler and Q. Xiang, The invariant factors of some cyclic difference sets, J. Combinatorial Thy. Ser. A 101 (2003) 131–146. [9] E. S. T. Fan and T. W. H. Wong, Welsh’s problem on the number of bases of matroids, in preparation. 94 [10] P. Frankl and R. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), 357–368. [11] R. L. Graham, S.-Y. R. Li, and W.-C. W. Li, On the structure of t-designs, SIAM J. Alg. Disc. Math. 1 (1980), 8–14. [12] J. E. Graver and W. B. Jurkat, The module structure of integral designs, J. Combinatorial Thy. 15 (1973), 75–90. [13] A. Hartman, Halving the complete design, Ann. Disc. Math. 34 (1987), 207–224. [14] G. B. Khosrovshahi and Ch. Maysoori, On the bases for trades, Lin. Alg. and its Appl. 226–228 (1995), 731–748. [15] G. B. Khosrovshahi, B. Tayfeh-Rezaie, Large sets of t-designs through partitionable sets, a Review, Disc. Math. 306 (2006), 2993–3004. [16] C. W. H. Lam, The search for a finite projective plane of order 10, Amer. Math. Monthly 98 (1991), 305–318. [17] D. Mayhew and G. F. Royle, Matroids with nine elements, J. Combinatorial Thy. Ser. B 98 (2008), 415–431. [18] M. Newman, The Smith normal form, Proceedings of the Fifth Conference of the International Linear Algebra Society (Atlanta, GA, 1995), Lin. Alg. and its Appl. 254 (1997), 367–381. [19] D. K. Ray-Chaudhuri, N. Singhi, Studying designs via multisets, Des. Codes Cryptogr. 65 (2012), 365–381. [20] A. Schrijver, Theory of Linear and Integer Programming, Wiley, New York, 1986. [21] V. Sivaraman, On a conjecture of Welsh, preprint. [22] K. Ushio, Bipartite decomposition of complete multipartite graphs, Hiroshima Math. J. 11 (1981), 321–345. 95 [23] B. L. van der Waerden, Algebra, Vol. 2, Springer, 2003. [24] D. Welsh, Combinatorial problems in matroid theory, Combinatorial Math. and its Appl. (Proc. Conf. Oxford 1969), Academic Press, London, 1971. [25] R. M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Proc. 5th Brit. Combinatorial Conf. (1975), 647–659. [26] R. M. Wilson, A diagonal form for the incidence matrices of t-subsets vs. ksubsets, Europ. J. Combinatorics 11 (1990), 609–615. [27] R. M. Wilson, Signed hypergraph designs and diagonal forms for some incidence matrices, Des. Codes Cryptogr. 17 (1999), 289–297. [28] R. M. Wilson, On set systems with restricted intersections modulo p and p-ary t-designs, Disc. Math. 309 (2009), 606–612. [29] R. M. Wilson, Some applications of incidence matrices of t-subsets and hypergraphs, Proceedings of the Third Shanghai Conference on Combinatorics, Disc. Math., to appear. [30] R. M. Wilson and T. W. H. Wong, Diagonal forms of incidence matrices associated with t-uniform hypergraphs, accepted by Europ. J. Combinatorics. [31] T. W. H. Wong, Diagonal forms and zero-sum (mod 2) bipartite Ramsey numbers, submitted to J. Combinatorial Thy. Ser. A. [32] T. W. H. Wong, Inclusion matrices of multisets, in preparation.