tailieunhanh - Báo cáo toán học: "Asymptotics for incidence matrix classes"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Asymptotics for incidence matrix classes. | Asymptotics for incidence matrix classes Peter Cameron Thomas Prellberg and Dudley Stark School of Mathematical Sciences Queen Mary University of London Mile End Road London E1 4NS . Submitted Apr 4 2006 Accepted Oct 2 2006 Published Oct 12 2006 Mathematics Subject Classifications 05A16 05C65 Abstract We define incidence matrices to be zero-one matrices with no zero rows or columns. We are interested in counting incidence matrices with a given number of ones irrespective of the number of rows or columns. A classihcation of incidence matrices is considered for which conditions of symmetry by transposition having no repeated rows columns or identihcation by permutation of rows columns are imposed. We hnd asymptotics and relationships for the number of matrices with n ones in some of these classes as n 1. 1 Introduction In this paper we address the problem How many zero-one matrices are there with exactly n ones Note that we do not specify in advance the number of rows or columns of the matrices. In order to make the answer finite we assume that no row or column of such a matrix consists entirely of zeros. We call such a matrix an incidence matrix. Rather than a single problem there are many different problems here depending on what symmetries and constraints are permitted. In general we define Fijkl n to be the number of zero-one matrices with n ones and no zero rows or columns subject to the conditions i 0 if matrices differing only by a row permutation are identified and i 1 if not j 0 if matrices with two equal rows are forbidden and j 1 if not k 0 if matrices differing only by a column permutation are identified and k 1 if not l 0 if matrices with two equal columns are forbidden and l 1 if not. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R85 1 The notation is chosen so that Fijkl n is a monotonic increasing function of each of the arguments i j k l. By transposition it is clear that Fklij n Fijkl n for all i j