More on the Bipartite Decomposition of Random Graphs |
| |
Authors: | Noga Alon Tom Bohman Hao Huang |
| |
Affiliation: | 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 |
|
|