More on the Bipartite Decomposition of Random Graphs |
| |
| Authors: | Noga Alon Tom Bohman Hao Huang |
| |
| Institution: | 1. SACKLER SCHOOL OF MATHEMATICS AND BLAVATNIK SCHOOL OF COMPUTER SCIENCE, TEL AVIV UNIVERSITY, TEL AVIV, ISRAEL;2. SCHOOL OF MATHEMATICS, INSTITUTE FOR ADVANCED STUDY, PRINCETON, NJContract grant number: USA‐Israeli BSF grant;3. contract grant sponsor: ISF grant;4. contract grant sponsor: Israeli I‐Core program and by the Oswald Veblen Fund.;5. DEPARTMENT OF MATHEMATICAL SCIENCES, CARNEGIE MELLON UNIVERSITY, PITTSBURGH, PAContract grant sponsor: NSF;6. contract grant number: DMS‐1362785;7. DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE, EMORY UNIVERSITY, ATLANTA, GA |
| |
| Abstract: | For a graph  , let  denote the minimum number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to exactly one of them. It is easy to see that for every graph G ,  , where  is the maximum size of an independent set of G . Erd?s conjectured in the 80s that for almost every graph G equality holds, that is that for the random graph  ,  with high probability, that is with probability that tends to 1 as n tends to infinity. The first author showed that this is slightly false, proving that for most values of n tending to infinity and for  ,  with high probability. We prove a stronger bound: there exists an absolute constant  so that  with high probability. |
| |
| Keywords: | bipartite decomposition random graph |
|
|
