Abstract
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.
Similar content being viewed by others
Notes
Note that \(\log \) denotes base \(2\) logarithm.
References
Alon, N.: Covering graphs by the minimum number of equivalence relations. Combinatorica 2(3), 201–206 (1986)
Beimel, A., Ferràs, O., Mintz, Y.: Secret Sharing Schemes for Very Dense Graphs, Lecture Notes in Computer Science, vol. 7417 (Advances in Cryptology—CRYPTO 2012), pp. 144–161, ISSN: 0302–9743 (2012)
Bezrukov, S., Fronček, D., Rosenberg, S.J., Kovár, P.: On biclicque coverings. Discret. Math. 208, 319–323 (2008)
Blakley, G.R.: Safeguarding cryptographic keys. In: Merwin, R.E., Zanca, J.T., Smith, M. (eds.) Proceedings of the 1979 IFIPS National Computer Conference, vol. 48, pp. 313–317 (1979)
Blundo, C., De Santis, A., De Simone, R., Vaccaro, U.: Tight bounds on the information rate of secret sharing schemes. Des. Codes Cryptogr. 11, 107–122 (1997)
Dong, J., Liu, Y.: On the decomposition of graphs into complete bipartite graphs. Graph. Combin. 23, 255–262 (2007)
Erdős, P., Pyber, L.: Covering a graph by complete bipartite graphs. Discret. Math. 170(1–3), 249–251 (1997)
Fishburn, P.C., Hammer, P.L.: Bipartite dimensions and bipartite degrees of graphs. Discret. Math. 160, 127–148 (1996)
Hajuabolhassan, H., Moazami, F.: Some New Bounds for Cover-Free Families Through Biclique Cover, arXiv:1008.3691 (2011), Accessed Nov 2013
Jukna, S.: On set intersection representation of graphs. J. Graph. Theor. 61, 55–75 (2009)
Katona, G., Szemerédi, E.: On a problem of graph theory. Studia Math. Hung. 2, 23–28 (1967)
Kanuer, K., Ueckerdt, T.: Three Ways to Cover a Graph arXiv:1205.1627 (2012), Accessed Nov 2013
Padro, C.: Lecture Notes in Secret Sharing IACR preprint http://eprint.iacr.org/2012/674 (2012) Accessed Nov 2013
Pinto, T.: Biclique Covers and Partitions, arXiv:1307.6363 (2013), Accessed Nov 2013
Shamir, A.: How to share a secret. Commun. ACM 22, 612–613 (1979)
Stinson, D.R.: Decomposition construction for secret sharing schemes. IEEE Trans. Inf. Theory 40, 118–125 (1994)
Watts, V.L.: Fractional biclique covers and partitions of graphs. Electron. J. Combin. 13, R74 (2006)
Acknowledgments
This research has been partially supported by the Cryptography Lendület program of the Hungarian Academy of Sciences. The first author also acknowledges the support from the grant TAMOP-4.2.2.C-11/1/KONV-2012-0001. The second author was supported by the OTKA grant PD100712. The last author also acknowledges the support of the grant OTKA NN-102029 and the NSERC Discovery grant.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Csirmaz, L., Ligeti, P. & Tardos, G. Erdős–Pyber Theorem for Hypergraphs and Secret Sharing. Graphs and Combinatorics 31, 1335–1346 (2015). https://doi.org/10.1007/s00373-014-1448-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-014-1448-7