Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
polymatroid; amalgam; adhesive polymatroid; entropy function; polyhedral cone
polymatroid; amalgam; adhesive polymatroid; entropy function; polyhedral cone
Summary:
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.
References:
[1] Ahlswede, R., Cai, N., Li, S.-Y. R., Yeung, R. W.: Network information flow. IEEE Trans. Inform. Theory 46 (2000), 1204-1216. DOI 10.1109/18.850663 | MR 1768542
[2] Bonin, J. E.: A note on the sticky matroid conjecture. Ann. Comb. 15 (2011), 619-624. DOI 10.1007/s00026-011-0112-7 | MR 2854783
[3] Christof, T., Loebel, A.: Porta: Polyhedron Representation Transformation Algorithm, Version 1.4.1.
[4] Csirmaz, L., Matúš, F.: Entropy region and convolution. IEEE Trans. Inf. Theory 62 (2016), 6007-6018. DOI 10.1109/tit.2016.2601598 | MR 3565097
[5] Dougherty, R., Freiling, C., Zeger, K.: Linear rank inequalities on five or more variables. Available at arXiv.org, arXiv:0910.0284, 2019.
[6] Martí-Farré, J., Padró, C.: 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 | MR 2496243
[7] Fujishige, S.: Polymatroidal dependence structure of a set of random variables. Inform. Control 39 (1978), 55-72. DOI 10.1016/s0019-9958(78)91063-x | MR 0514262
[8] Ingleton, A. W.: Representation of matroids. In: Combinatorial mathematics and its applications (D. J. A. Welsh, ed.) Academic Press, London, New York 1971, pp. 149-169. MR 0278974
[9] Lovász, L.: 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 | MR 0717403
[10] Matúš, F.: Probabilistic conditional independence structures and matroid theory: background. Int. J. General Syst. 22 (1994), 185-196. DOI 10.1080/03081079308935205
[11] Matúš, F.: Adhesivity of polymatroids. Discrete Math. 307 (2007), 2464-2477. DOI 10.1016/j.disc.2006.11.013 | MR 2359593
[12] Matúš, F.: Two constructions on limits of entropy functions. IEEE Trans. Inform. Theory 53 (2007), 320-330. DOI 10.1109/tit.2006.887090 | MR 2292891
[13] Matúš, F.: Infinitely many information inequalities. In: Proc. IEEE ISIT 2007, Nice, pp. 41-44.
[14] Matúš, F., Studený, M.: Conditional independences among four random variables I. Combin. Probab. Comput. 4 (1995), 269-278. DOI 10.1017/s0963548300001644 | MR 1356579
[15] Oxley, J. G.: Matroid Theory. Oxford Science Publications. The Calrendon Press, Oxford University Press, New York 1992. MR 1207587
[16] Padró, C.: Lecture Notes in Secret Sharing. Cryptology ePrint Archive 2012/674.
[17] Seymour, P. D.: On secret sharing matroids. J. Combin. Theory, Ser B 56 (1992), 69-73. DOI 10.1016/0095-8956(92)90007-k | MR 1182458
[18] Studeny, M., Bouckaert, R. R., Kocka, T.: Extreme Supermodular Set Functions over Five Variables. Research Report No. 1977, Institute of Information Theory and Automation, Prague 2000.
[19] Yeung, R. W.: A first course in information theory. Kluwer Academic / Plenum Publishers 2002. MR 2042182
[20] Ziegler, G. M.: Lectures on polytopes. Graduate Texts in Mathematics 152 Springer, 1994. DOI 10.1007/978-1-4613-8431-1 | MR 1311028
Search
Partner of
