2020/05/05 by Dhruv Rohatgi, John Urschel, Rohatgi, Dhruv +3
Mathematics · #Advanced Mathematical Identities #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2005.02529
openalex publication_date 2020/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G, let cp(G) denote the minimum number of cliques of G needed to cover the edges of G exactly once. Similarly, let bpk(G) denote the minimum number of bicliques (i.e. complete bipartite subgraphs of G) needed to cover each edge of G exactly k times. We consider two conjectures -- one regarding the maximum possible value of cp(G) + cp(G) (due to de Caen, Erdős, Pullman and Wormald) and the other regarding bpk(Kn) (due to de Caen, Gregory and Pritikin). We disprove the first, obtaining improved lower and upper bounds on maxG cp(G) + cp(G), and we prove an asymptotic version of the second, showing that bpk(Kn) = (1+o(1))n.