I. Moore Type Graphs. II. Properties of (0,1)-Matrices with Forbidden Configurations. III. Properties of (0,1)-Matrices with Prescribed Row and Column Sums

Author: Anstee, Richard Paul

Year: 1980

Degree: Dissertation (Ph.D.)

Advisor: Ryser, Herbert J.

Committee Member: Unknown, Unknown

Option: Mathematics

DOI: 10.7907/s4k2-y035

Abstract

NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document.

The thesis consists of three chapters. The first chapter starts by discussing the class C(S) of all (0,1)-matrices A which have the off diagonal entries of AAT the same as S. This leads to a consideration of the properties of remainder matrices which correspond to graphs without triangles. Our main result concerns special remainder matrices S of order n which satisfy the matrix equation S + S2 = k I + J - L, where I is the identity matrix, J is the matrix of all l's, and L is the direct sum of n/l, matrices of all l's of order l. We call such graphs Moore type graphs because for l = l we obtain Moore graphs and for l = k we obtain Moore graphs stripped of some vertices. We obtain a new graph with k = 6, l = 4, n = 40 as well as an additional possible parameter set k = 20, l = 10, n = 410.

The second chapter considers configurations defined as equivalence classes of matrices, where two matrices represent the same configuration if one is a row and column permutation of the other. A matrix A is said to contain a configuration if a submatrix of A represents that configuration. For certain lists, a (0,1)-matrix A, with no configurations in some list and AAT > 0, is forced to have a column of l 1s. We then derive results about row intersections of a matrix. The row intersection of row i and j (i ≠ j) is the vector with a l in a column if both row i and j do and a O otherwise. For matrices with column sums at least 2 satisfying some condition on forbidden configurations, we find that the number of linearly independent row intersections is equal to the number of distinct columns. One possible condition is 11contains no triangles", where a triangle is a configuration of order 3 with row and column sums 2. We study the extremal matrices of size m by (m2) with distinct columns and the above properties. In the case of no triangles, we find that there are m - l + 1 columns of column sum l and they form an (l-1)-tree. Such matrices have a fascinating inductive buildup. Other conditions are also considered.

The third chapter explores a number of properties of the class [...] (R,S). Let R = (r1, r2, ...,rm) and S = (s1, s2, ...,sn). We define [...](R,S) to be all (0,1)-matrices of size m by n with ith row sum ri and jth column sum sj. We obtain a generalization of the Gale- Riser theorem by finding simple conditions which determine when there exists a matrix A ∈ [...](R,S) with A ≥ P for some (0,1 )-matrix P with column sums at most 1. Our second main result extends a theorem of Brualdi and Ross. Consider vectors R', S' with r'i = ri - k or ri - k - 1 and S ≥ S'. If [...](R,S) and [...](R', S') are nonempty, then there exists an A ∈ [...](R,S) and a B ∈ [...](R', S') with A ≥ B. Our third main result gives that under simple conditions, ([...](R,S) nonempty, R,S ordered, ri ≤ n - i + 1, si ≤ n - i + for all i) there is a matrix A ∈ (R,S) with 0's in the (i,j) entry for j > n - i + 1 i.e. A is in triangular form.

Files