Erdős-Pyber theorem for hypergraphs and secret sharing

DOI10.1007/S00373-014-1448-7zbMATH Open1321.05282arXiv1311.5027OpenAlexW1980608804MaRDI QIDQ497325FDOQ497325

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)

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.

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

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

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)

Cites Work

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

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)