2013/11/20 by László Csirmaz, Csirmaz, László, Péter Ligeti +3 · 1 citation
Computer Science · Engineering · #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 #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1311.5027
openalex publication_date 2013/11/20 · 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\nErd Hos-Pyber theorem which says that the edges of a graph on n vertices\ncan be partitioned into complete bipartite subgraphs so that every vertex is\ncovered at most O(n/\log n) times. The theorem is generalized to uniform\nhypergraphs. Similar bounds with smaller constant value is provided for\nfractional partitioning both for graphs and for uniform hypergraphs. We show\nthat these latter constants cannot be improved by more than a factor of 1.89\neven for fractional covering by arbitrary complete multipartite subgraphs or\nsubhypergraphs. In the case every vertex of the graph is connected to at least\nn-m other vertices, we prove the existence of a fractional covering of the\nedges by complete bipartite graphs such that every vertex is covered at most\nO(m/\log m) times, with only a slightly worse explicit constant. This result\nalso generalizes to uniform hypergraphs. Our results give new improved bounds\non the complexity of graph and uniform hypergraph based secret sharing schemes,\nand show the limits of the method at the same time.\n