TAILIEUCHUNG - Báo cáo toán học: "Threshold Functions for the Bipartite Tur´n Property a"

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í toán học quốc tế đề tài: Threshold Functions for the Bipartite Tur´n Property a. | Threshold Functions for the Bipartite Turán Property Anant P. Godbole Department of Mathematical Sciences Michigan Technological University Houghton MI 49931-1295 . anant@ Ben Lamorte Engineering and Economic Systems Department Stanford University Stanford CA 93405-4025 . lamorte@ Erik Jonathan Sandquist Department of Mathematics Cornell University Ithaca NY 14853-7901 . ejs9@ Submitted May 20 1997 Accepted August 20 1997 MR Subject Numbers 05C50 05C80 05C35 05B30 ABSTRACT Let G2 n denote a bipartite graph with n vertices in each color class and let z n t be the bipartite Turan number representing the maximum possible number of edges in G2 n if it does not contain a copy of the complete bipartite subgraph K t t . It is then clear that n t n2 z n t denotes the minimum number of zeros in an n X n zero-one matrix that does not contain a t X t submatrix consisting of all ones. We are interested in the behaviour of z n t when both t and n go to infinity. The case 2 t n1 5 has been treated in 9 here we use a different method to consider the overlapping case log n t n1 3. Fill an n X n matrix randomly with z ones and n2 z zeros. Then we prove that the asymptotic probability that there are no t X t submatrices with all ones is zero or one according as z t ne 2 exp an t2 or z t ne 2G exp log t bn t2 where an tends to infinity at a specified rate and bn 1 is arbitrary. The proof employs the extended Janson exponential inequalities 1 . 1 the electronic journal of combinatorics 4 1997 R18 2 1. INTRODUCTION AND STATEMENT OF RESULTS Given a graph F what is the maximum number of edges in a graph on n vertices that does not contain F as a subgraph In the bipartite case we let z n t denote the diagonal bipartite Turán number which represents the maximum number of edges in a bipartite graph with n vertices in each color class that does not contain a complete bipartite graph K t t of order t. An equivalent formulation of this .

• Báo cáo khoa học
• 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
• các bài toán hay
• trình bày báo cáo
• báo cáo ngành văn học
• báo cáo tiếng anh
• nghiên cứu văn thơ
• giọng điệu trào phúng
• nghiên cứu khoa học
• báo cáo khoa học
• thơ lục bát
• chính sách phát triển
• gia đình việt nam
• nghiên cứu xã hội