Erdős-Pyber theorem for hypergraphs and secret sharing

DOI10.1007/S00373-014-1448-7MaRDI QIDQ497325zbMATH OpenOpenAlexFDO

Authors László Csirmaz, Péter Ligeti, Gábor Tardos

Publication date 24 September 2015

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.5027

zbMATH Keywords

bipartite graphgraph coveringuniform hypergraphsecret sharingpartition cover number

Mathematics Subject Classification ID

Cryptography (94A60) Hypergraphs (05C65) Graph theory (05C99) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: A new, constructive proof with a small explicit constant is given to the ErdH{o}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/logn)$ 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/logm)$ 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.

Recommendations

• Multicovering hypergraphs
• Bounds for the Graham-Pollak theorem for hypergraphs
• Near perfect coverings in graphs and hypergraphs
• On judicious partitions of uniform hypergraphs
• Judicious partitions of uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 3238444 (Why is no real title available?)
• Biclique covers and partitions
• Bipartite dimensions and bipartite degrees of graphs
• Covering a graph by complete bipartite graphs
• Covering graphs by the minimum number of equivalence relations
• Decomposition constructions for secret-sharing schemes
• Fractional biclique covers and partitions of graphs
• How to share a secret
• On biclique coverings
• On set intersection representations of graphs
• On the decomposition of graphs into complete bipartite graphs
• Secret sharing schemes for very dense graphs
• Tight bounds on the information rate of secret sharing schemes

Cited in

(5)

• On difference graphs and the local dimension of posets
• Exact information ratios for secret sharing on small graphs with girth at least 5
• Secret-sharing schemes for very dense graphs
• Secret sharing on large girth graphs
• Secret sharing schemes for ports of matroids of rank 3.

This page was built for publication: Erdős-Pyber theorem for hypergraphs and secret sharing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q497325)