TAILIEUCHUNG - Báo cáo toán học: "Thin Lehman Matrices and Their Graphs"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Thin Lehman Matrices and Their Graphs. | Thin Lehman Matrices and Their Graphs Jonathan Wang Department of Mathematics Harvard University Cambridge MA 02138 USA jpwang@ Submitted Apr 24 2010 Accepted Nov 22 2010 Published XXDec 3 2010 Mathematics Subject Classification 05B20 Abstract Two square 0 1 matrices A B are a pair of Lehman matrices if ABT J di where J is the matrix of all 1s and d is a positive integer. It is known that there are infinitely many such matrices when d 1 and these matrices are called thin Lehman matrices. An induced subgraph of the Johnson graph may be defined given any Lehman matrix where the vertices of the graph correspond to rows of the matrix. These graphs are used to study thin Lehman matrices. We show that any connected component of such a graph determines the corresponding rows of the matrix up to permutations of the columns. We also provide a sharp bound on the maximum clique size of such graphs and give a complete classification of Lehman matrices whose graphs have at most two connected components. Some constraints on when a circulant matrix can be Lehman are also provided. Many general classes of thin Lehman matrices are constructed in the paper. 1 Introduction Lehman matrices were defined by Lutolf and Margot 7 to aid in the classification of minimally nonideal matrices which are a key tool for understanding when the set covering problem can be solved using linear programming we refer the reader to 2 for more information on minimally nonideal matrices . Lehman matrices lie at the heart of Lehman s central theorem on minimally nonideal matrices 5 6 . He showed that for m n almost every m X n minimally nonideal matrix contains a unique n X n Lehman matrix. Bridges and Ryser 1 showed that every Lehman matrix is r-regular for some integer r 2 . each row and column sums to r. Two infinite families of Lehman matrices are known the point-line incidence matrices of finite nondegenerate projective planes a widely studied topic 4 and thin Lehman matrices. Thin .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học