Geodesic
One-adhesive polymatroids
Kybernetika, Tome 56 (2020) no. 5, pp. 886-902
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.14736/kyb-2020-5-0886
Classification : 05B35, 52B12, 94A15
Keywords: polymatroid; amalgam; adhesive polymatroid; entropy function; polyhedral cone 
@article{10_14736_kyb_2020_5_0886,
     author = {Csirmaz, Laszlo},
     title = {One-adhesive polymatroids},
     journal = {Kybernetika},
     pages = {886--902},
     year = {2020},
     volume = {56},
     number = {5},
     doi = {10.14736/kyb-2020-5-0886},
     mrnumber = {4187778},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-5-0886/}
}
TY  - JOUR
AU  - Csirmaz, Laszlo
TI  - One-adhesive polymatroids
JO  - Kybernetika
PY  - 2020
SP  - 886
EP  - 902
VL  - 56
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-5-0886/
DO  - 10.14736/kyb-2020-5-0886
LA  - en
ID  - 10_14736_kyb_2020_5_0886
ER  - 
%0 Journal Article
%A Csirmaz, Laszlo
%T One-adhesive polymatroids
%J Kybernetika
%D 2020
%P 886-902
%V 56
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-5-0886/
%R 10.14736/kyb-2020-5-0886
%G en
%F 10_14736_kyb_2020_5_0886
Csirmaz, Laszlo. One-adhesive polymatroids. Kybernetika, Tome 56 (2020) no. 5, pp. 886-902. doi: 10.14736/kyb-2020-5-0886

[1] Ahlswede, R., Cai, N., Li, S.-Y. R., Yeung, R. W.: Network information flow. IEEE Trans. Inform. Theory 46 (2000), 1204-1216. | DOI | MR

[2] Bonin, J. E.: A note on the sticky matroid conjecture. Ann. Comb. 15 (2011), 619-624. | DOI | MR

[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 | MR

[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 | MR

[7] Fujishige, S.: Polymatroidal dependence structure of a set of random variables. Inform. Control 39 (1978), 55-72. | DOI | MR

[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

[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 | MR

[10] Matúš, F.: Probabilistic conditional independence structures and matroid theory: background. Int. J. General Syst. 22 (1994), 185-196. | DOI

[11] Matúš, F.: Adhesivity of polymatroids. Discrete Math. 307 (2007), 2464-2477. | DOI | MR

[12] Matúš, F.: Two constructions on limits of entropy functions. IEEE Trans. Inform. Theory 53 (2007), 320-330. | DOI | MR

[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 | MR

[15] Oxley, J. G.: Matroid Theory. Oxford Science Publications. The Calrendon Press, Oxford University Press, New York 1992. | MR

[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 | MR

[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

[20] Ziegler, G. M.: Lectures on polytopes. Graduate Texts in Mathematics 152 Springer, 1994. | DOI | MR

Cité par Sources :