THE SMALLEST BASE OF k - SETS
Main Article Content
Abstract
In information theory, such as storage model, private sharing, or encryption sometimes we want to distribute a given database into many small parts, each of which is stored by a party in such a way that when there is a cooperation of a sufficient number of parties, we are able to recover the original information. For this purpose, this paper describes the way to work on a given finite set then construct a family of uniform subsets such that there exists only one permutation that maps one-to-one each subset. Of course, the optimality of construction will be considered through its size. By evaluating the number of occurrences of each element in the subsets, it is possible to establish the lower bound for that size and using the simple undirected graph to model. The construction step is only successful with relevant data and the general case is under further study.
Keywords
base, fixed point, graph, reconstruct permutation
Article Details
References
Diatonics, P., Fulman, J., & Guralnick, R. (2008). On fixed points of permutations. J. Algebraic Combi., 28(1), 189-218.
Jung, J., Mummert, C., Niese, E., & Schroeder, M. (2018). On erasure combinatorial batch codes. Designs, Codes and Cryptography, 12(1), 49.
Ishai, Y., Kushilevitz, E., & Ostrovsky, R. (2004). Batch codes and their applications. Proceedings of STOC 2004, ACM Press, 262-271.
Paterson, M. B., Stinson, D. R., & Wei, R. (2009). Cominatorial Batch Codes. Communications in Advanced Mathematical, 3(1), 13.
Smith, R. (2006). Permutation Reconstruction. The Electronic journal of combinatorics, 13(11).
Sean, E., Kevin, F., & Ben, G. (2016). Permutations fixing a k-set. International Mathematics Research Notices, 2016(21), 6713-6731.