2013/11/20 by László Csirmaz, Csirmaz, László, Péter Ligeti +3 · 1 citation
Computer Science · Engineering · Mathematics · #05C65 #05C99 #05D40 #94A60 #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #cs.CR #graph theory and CDMA systems #math.CO #msc:05C65 #msc:05C99 #msc:05D40 #msc:94A60
paper · pdf · doi:10.48550/arxiv.1311.5027
arxiv created 2013/11/20 · openalex publication_date 2013/11/20 · arxiv updated 2013/11/21 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
A new, constructive proof with a small explicit constant is given to the Erdős-Pyber theorem which says that the edges of a graph on n vertices can be partitioned into complete bipartite subgraphs so that every vertex is covered at most O(n/log n) times. The theorem is generalized to uniform hypergraphs. Similar bounds with smaller constant value is provided for fractional partitioning both for graphs and for uniform hypergraphs. We show that these latter constants cannot be improved by more than a factor of 1.89 even for fractional covering by arbitrary complete multipartite subgraphs or subhypergraphs. In the case every vertex of the graph is connected to at least n-m other vertices, we prove the existence of a fractional covering of the edges by complete bipartite graphs such that every vertex is covered at most O(m/log m) times, with only a slightly worse explicit constant. This result also generalizes to uniform hypergraphs. Our results give new improved bounds on the complexity of graph and uniform hypergraph based secret sharing schemes, and show the limits of the method at the same time.