Kybernetika 56 no. 5, 886-902, 2020

One-adhesive polymatroids

Laszlo CsirmazDOI: 10.14736/kyb-2020-5-0886

Abstract:

Adhesive polymatroids were defined by F. Matúš motivated by entropy functions. Two polymatroids are adhesive if they can be glued together along their joint part in a modular way; and are one-adhesive, if one of them has a single point outside their intersection. It is shown that two polymatroids are one-adhesive if and only if two closely related polymatroids have joint extension. Using this result, adhesive polymatroid pairs on a five-element set are characterized.

Keywords:

polymatroid, entropy function, amalgam, adhesive polymatroid, polyhedral cone

Classification:

05B35, 94A15, 52B12

paper.pdf

References:

  1. R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung: Network information flow. IEEE Trans. Inform. Theory 46 (2000), 1204-1216.   DOI:10.1109/18.850663
  2. J. E. Bonin: A note on the sticky matroid conjecture. Ann. Comb. 15 (2011), 619-624.   DOI:10.1007/s00026-011-0112-7
  3. T. Christof and A. Loebel: Porta: Polyhedron Representation Transformation Algorithm, Version 1.4.1.    CrossRef
  4. L. Csirmaz and F. Matúš: Entropy region and convolution. IEEE Trans. Inf. Theory 62 (2016), 6007-6018.   DOI:10.1109/tit.2016.2601598
  5. R. Dougherty, C. Freiling and K. Zeger: Linear rank inequalities on five or more variables. Available at arXiv.org, arXiv:0910.0284, 2019.   CrossRef
  6. J. Martí-Farré and C. Padró: Ideal secret sharing schemes whose minimal qualified subsets have at most three participants. Des. Codes Cryptogr. 52 (2009), 1-14.   DOI:10.1007/s10623-008-9264-9
  7. S. Fujishige: Polymatroidal dependence structure of a set of random variables. Inform. Control 39 (1978), 55-72.   DOI:10.1016/s0019-9958(78)91063-x
  8. A. W. Ingleton: Representation of matroids. In: Combinatorial mathematics and its applications (D. J. A. Welsh, ed.) Academic Press, London, New York 1971, pp. 149-169.   CrossRef
  9. L. Lovász: Submodular functions and convexity. In: Mathematical Programming - The State of the Art (A. Bachem, M. Grötchel and B. Korte, eds.), Springer-Verlag, Berlin 1982, pp. 234-257.   DOI:10.1007/978-3-642-68874-4\_10
  10. F. Matúš: Probabilistic conditional independence structures and matroid theory: background. Int. J. General Syst. 22 (1994), 185-196.   DOI:10.1080/03081079308935205
  11. F. Matúš: Adhesivity of polymatroids. Discrete Math. 307 (2007), 2464-2477.   DOI:10.1016/j.disc.2006.11.013
  12. F. Matúš: Two constructions on limits of entropy functions. IEEE Trans. Inform. Theory 53 (2007), 320-330.   DOI:10.1109/tit.2006.887090
  13. F. Matúš: Infinitely many information inequalities. In: Proc. IEEE ISIT 2007, Nice, pp. 41-44.   CrossRef
  14. F. Matúš and M. Studený: Conditional independences among four random variables I. Combin. Probab. Comput. 4 (1995), 269-278.   DOI:10.1017/s0963548300001644
  15. J. G. Oxley: Matroid Theory. Oxford Science Publications. The Calrendon Press, Oxford University Press, New York 1992.   CrossRef
  16. C. Padró: Lecture Notes in Secret Sharing. Cryptology ePrint Archive 2012/674.   CrossRef
  17. P. D. Seymour: On secret sharing matroids. J. Combin. Theory, Ser B 56 (1992), 69-73.   DOI:10.1016/0095-8956(92)90007-k
  18. M. Studeny, R. R. Bouckaert and T. Kocka: Extreme Supermodular Set Functions over Five Variables. Research Report No. 1977, Institute of Information Theory and Automation, Prague 2000.   CrossRef
  19. R. W. Yeung: A first course in information theory. Kluwer Academic / Plenum Publishers 2002.   CrossRef
  20. G. M. Ziegler: Lectures on polytopes. Graduate Texts in Mathematics 152 Springer, 1994.   DOI:10.1007/978-1-4613-8431-1