Simplicial complexes and closure systems induced by indistinguishability relations

Chiaselotti, Giampiero; Gentile, Tommaso; Infusino, Federico

doi:10.1016/j.crma.2017.09.010

Topology/Computer science

Simplicial complexes and closure systems induced by indistinguishability relations
[Complexes simpliciaux et systèmes de clôture induits par les relations d'indistinguabilité]

Présenté par : Claire Voisin

Chiaselotti, Giampiero ¹ ; Gentile, Tommaso ¹ ; Infusino, Federico ¹

¹ Department of Mathematics and Informatics, University of Calabria, Via Pietro Bucci, Cubo 30B, 87036 Arcavacata di Rende (CS), Italy

Comptes Rendus. Mathématique, Tome 355 (2017) no. 9, pp. 991-1021.

Résumé
Abstract

Nous développons dans ce texte la notion d'indistinguabilité dans un contexte mathématique plus général. Cette notion a en effet été récemment étudiée en théorie des graphes, comme une relation de symétrie relativement aux sommets fixés. Le point de départ de notre analyse est de considérer un ensemble Ω de fonctions définies sur un ensemble univers U et de définir pour tout sous-ensemble $A \subset Ω$ une relation d'équivalence $\equiv_{A}$ sur U par $u \equiv u^{'}$ si $a (u) = a (u^{'})$ pour toute fonction $a \in A$ . Au moyen de cette famille de relations, nous introduisons la relation d'indistinguabilité ≈ sur l'ensemble puissance $P (Ω)$ de la façon suivante : pour $A, A^{'} \in P (Ω)$ , nous posons $A \approx A^{'}$ si les relations $\equiv_{A}$ et $\equiv_{A^{'}}$ coïncident. Nous utilisons cette relation d'indistinguabilité ≈ pour définir plusieurs familles d'ensembles sur Ω ayant d'intéressantes propriétés d'ordre, de matroïde et combinatoires. Nous appelons les familles d'ensembles ci-dessus les structures indistinguables du système de fonctions $(U, Ω)$ . De plus, nous obtenons un système de clôture et un complexe simplicial abstrait interagissant l'un l'autre au travers de trois hypergraphes, qui sont significatifs aussi bien en théorie des graphes qu'en informatique théorique. La première partie du texte est dédiée à l'étude les propriétés mathématiques élémentaires des structures d'indistinguabilité pour les systèmes de fonctions arbitraires. La seconde partie traite de quelques cas particuliers dérivés des graphes non orientés simples et de la droite euclidienne réelle usuelle.

In this paper, we develop in a more general mathematical context the notion of indistinguishability, which in graph theory has recently been investigated as a symmetry relation with respect to a fixed vertex subset. The starting point of our analysis is to consider a set Ω of functions defined on a universe set U and to define an equivalence relation $\equiv_{A}$ on U for any subset $A \subseteq Ω$ in the following way: $u \equiv_{A} u^{'}$ if $a (u) = a (u^{'})$ for any function $a \in A$ . By means of this family of relations, we introduce the indistinguishability relation ≈ on the power set $P (Ω)$ as follows: for $A, A^{'} \in P (Ω)$ , we set $A \approx A^{'}$ if the relations $\equiv_{A}$ and $\equiv_{A^{'}}$ coincide. We use then the indistinguishability relation ≈ to introduce several set families on Ω that have interesting order, matroidal and combinatorial properties. We call the above set families the indistinguishability structures of the function system $(U, Ω)$ . Furthermore, we obtain a closure system and an abstract simplicial complex interacting each other by means of three hypergraphs having relevance in both theoretical computer science and graph theory. The first part of this paper is devoted to investigate the basic mathematical properties of the indistinguishability structures for arbitrary function systems. The second part deals with some specific cases of study derived from simple undirected graphs and the usual Euclidean real line.

Reçu le : 2016-06-27
Accepté le : 2017-09-12
Publié le : 2017-09-01

DOI : 10.1016/j.crma.2017.09.010

Affiliations des auteurs :

Chiaselotti, Giampiero ¹ ; Gentile, Tommaso ¹ ; Infusino, Federico ¹

¹ Department of Mathematics and Informatics, University of Calabria, Via Pietro Bucci, Cubo 30B, 87036 Arcavacata di Rende (CS), Italy

@article{CRMATH_2017__355_9_991_0,
     author = {Chiaselotti, Giampiero and Gentile, Tommaso and Infusino, Federico},
     title = {Simplicial complexes and closure systems induced by indistinguishability relations},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {991--1021},
     publisher = {Elsevier},
     volume = {355},
     number = {9},
     year = {2017},
     doi = {10.1016/j.crma.2017.09.010},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2017.09.010/}
}

TY  - JOUR
AU  - Chiaselotti, Giampiero
AU  - Gentile, Tommaso
AU  - Infusino, Federico
TI  - Simplicial complexes and closure systems induced by indistinguishability relations
JO  - Comptes Rendus. Mathématique
PY  - 2017
SP  - 991
EP  - 1021
VL  - 355
IS  - 9
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2017.09.010/
DO  - 10.1016/j.crma.2017.09.010
LA  - en
ID  - CRMATH_2017__355_9_991_0
ER  -

%0 Journal Article
%A Chiaselotti, Giampiero
%A Gentile, Tommaso
%A Infusino, Federico
%T Simplicial complexes and closure systems induced by indistinguishability relations
%J Comptes Rendus. Mathématique
%D 2017
%P 991-1021
%V 355
%N 9
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2017.09.010/
%R 10.1016/j.crma.2017.09.010
%G en
%F CRMATH_2017__355_9_991_0

Chiaselotti, Giampiero; Gentile, Tommaso; Infusino, Federico. Simplicial complexes and closure systems induced by indistinguishability relations. Comptes Rendus. Mathématique, Tome 355 (2017) no. 9, pp. 991-1021. doi : 10.1016/j.crma.2017.09.010. http://www.numdam.org/articles/10.1016/j.crma.2017.09.010/

Bibliographie
Cité par

[1] Andrews, G.E. Euler's “De Partitio numerorum”, Bull. Amer. Math. Soc., Volume 44 (2007) no. 4, pp. 561-573

[2] Apollonio, N.; Caramia, M. Recognizing Helly edge path tree graphs and their clique graphs, Discrete Appl. Math., Volume 159 (2011), pp. 1166-1175

[3] Apollonio, N.; Simeone, B. Improved approximation of maximum vertex coverage problem on bipartite graphs, SIAM J. Discrete Math., Volume 28 (2014) no. 3, pp. 1137-1151

[4] Apollonio, N.; Simeone, B. The maximum vertex coverage problem on bipartite graphs, Discrete Appl. Math., Volume 165 (2014), pp. 37-48

[5] Apollonio, N.; Caramia, M.; Franciosa, P.G. On the Galois lattice of bipartite distance hereditary graphs, Discrete Appl. Math., Volume 190 (2015), pp. 13-23

[6] Bayley, R.A. Orthogonal partitions in designed experiments, Des. Codes Cryptogr., Volume 8 (1996) no. 3, pp. 45-77

[7] Bayley, R.A. Association Schemes: Designed Experiments, Algebra and Combinatorics, Cambridge University Press, Cambridge, UK, 2004 (387 p)

[8] Berge, C. Hypergraphs: Combinatorics of Finite Sets, Elsevier, Amsterdam, 1984

[9] Biacino, L. Generated envelopes, J. Math. Anal. Appl., Volume 172 (1993), pp. 179-190

[10] Biacino, L.; Gerla, G. An extension principle for closure operators, J. Math. Anal. Appl., Volume 198 (1996), pp. 1-24

[11] Birkhoff, G. Lattice Theory, American Mathematical Society, Providence, Rhode Island, 1967

[12] Bisi, C.; Chiaselotti, G. A class of lattices and boolean functions related to the Manickam–Miklös–Singhi conjecture, Adv. Geom., Volume 13 (2013) no. 1, pp. 1-27

[13] Bisi, C.; Chiaselotti, G.; Marino, G.; Oliverio, P.A. A natural extension of the Young partition lattice, Adv. Geom., Volume 15 (2015) no. 3, pp. 263-280

[14] Bisi, C.; Chiaselotti, G.; Ciucci, D.; Gentile, T.; Infusino, F. Micro and macro models of granular computing induced by the indiscernibility relation, Inf. Sci., Volume 388–389 (2017), pp. 247-273

[15] Bisi, C.; Chiaselotti, G.; Gentile, T.; Oliverio, P.A. Dominance order on signed partitions, Adv. Geom., Volume 17 (2017) no. 1, pp. 5-29

[16] Boykett, T. Orderly algorithm to enumerate central groupoids and their graphs, Acta Math. Sin. Engl. Ser., Volume 23 (2007) no. 2, pp. 249-264

[17] Boykett, T. Rectangular groupoids and related structures, Discrete Math., Volume 313 (2013), pp. 1409-1418

[18] Cattaneo, G.; Chiaselotti, G.; Ciucci, D.; Gentile, T. On the connection of hypergraph theory with formal concept analysis and rough set theory, Inf. Sci., Volume 330 (2016), pp. 342-357

[19] Cattaneo, G.; Chiaselotti, G.; Oliverio, P.A.; Stumbo, F. A new discrete dynamical system of signed integer partitions, Eur. J. Comb., Volume 55 (2016), pp. 119-143

[20] Chen, B.; Yan, M. Eulerian stratification of polyhedra, Adv. Appl. Math., Volume 21 (1998), pp. 22-57

[21] Chen, B.; Yan, M. The geometric cone relations for simplicial and cubical complexes, Discrete Math., Volume 183 (1998), pp. 39-46

[22] Chen, B.; Yau, S.T.; Yeh, Y.N. Graph homotopy and Graham homotopy, Discrete Math., Volume 241 (2001), pp. 153-170

[23] Chiaselotti, G.; Gentile, T. Intersection properties of maximal directed cuts in digraphs, Discrete Math., Volume 340 (2017), pp. 3171-3175

[24] Chiaselotti, G.; Infante, G.; Marino, G. New results related to a conjecture of Manickam and Singhi, Eur. J. Comb., Volume 29 (2008) no. 2, pp. 361-368

[25] Chiaselotti, G.; Gentile, T.; Oliverio, P.A. Parallel and sequential dynamics of two discrete models of signed integer partitions, Appl. Math. Comput., Volume 232 (2014), pp. 1249-1261

[26] Chiaselotti, G.; Ciucci, D.; Gentile, T. Simple graphs in granular computing, Inf. Sci., Volume 340–341 (2016), pp. 279-304

[27] Chiaselotti, G.; Gentile, T.; Infusino, F. Dependency structures for decision tables, Int. J. Approx. Reason., Volume 88 (2017), pp. 333-370

[28] Chiaselotti, G.; Gentile, T.; Infusino, F. Knowledge pairing systems in granular computing, Knowl.-Based Syst., Volume 124 (2017), pp. 144-163

[29] Chiaselotti, G.; Gentile, T.; Infusino, F.; Oliverio, P.A. The adjacency matrix of a graph as a data table. A geometric perspective, Ann. Mat. Pura Appl., Volume 196 (2017) no. 3, pp. 1073-1112

[30] G. Chiaselotti, T. Gentile, F. Infusino, P. Oliverio, Local dissymmetry on graphs and related algebraic structures, preprint.

[31] Diestel, R. Graph Theory, Grad. Texts Math., Springer, 2010

[32] Eiter, T.; Gottlob, G. Identifying the minimal transversals of a hypergraph and related problems, SIAM J. Comput., Volume 24 (1995), pp. 1278-1304

[33] Elbassioni, K. On the complexity of monotone dualization and generating minimal hypergraph transversals, Discrete Appl. Math., Volume 32 (2008) no. 2, pp. 171-187

[34] Erdös, P.; Rényi, A. Asymmetric graphs, Acta Math. Hung., Volume 14 (1963) no. 3–4, pp. 295-315

[35] Ganter, B.; Wille, R. Formal Concept Analysis. Mathematical Foundations, Springer-Verlag, 1999

[36] Guo, L.; Huang, F.; Lia, Q.; Zhang, G. Power contexts and their concept lattices, Discrete Math., Volume 311 (2011), pp. 2049-2063

[37] Gyárfás, A.; Lehel, J. Hypergraph families with bounded edge cover or transversal number, Combinatorica, Volume 3 (1983) no. 3–4, pp. 351-358

[38] Hagen, M. Lower bounds for three algorithms for transversal hypergraph generation, Discrete Appl. Math., Volume 157 (2009), pp. 1460-1469

[39] Graph Symmetry. Algebraic Methods and Applications (Hahn, G.; Sabidussi, G., eds.), NATO ASI Ser., vol. 497, Springer, 1997

[40] Harley, P.W. III Metric and symmetric spaces, Proc. Amer. Math. Soc., Volume 43 (1974) no. 2, pp. 428-430

[41] Huang, A.; Zhao, H.; Zhu, W. Nullity-based matroid of rough sets and its application to attribute reduction, Inf. Sci., Volume 263 (2014), pp. 153-165

[42] Keith, W.J. A bijective toolkit for signed partitions, Ann. Comb., Volume 15 (2011), pp. 95-117

[43] Kelarev, A.; Praeger, C.E. On transitive Cayley graphs of groups and semigroups, Eur. J. Comb., Volume 24 (2003) no. 1, pp. 59-72

[44] Kelarev, A.; Quinn, S.J. Directed graphs and combinatorial properties of semigroups, J. Algebra, Volume 251 (2002) no. 1, pp. 16-26

[45] Kelarev, A.; Ryan, J.; Yearwood, J. Cayley graphs as classifiers for data mining: the influence of asymmetries, Discrete Math., Volume 309 (2009), pp. 5360-5369

[46] Martin, H.W. Metrization of symmetric spaces and regular maps, Proc. Amer. Math. Soc., Volume 35 (1972), pp. 269-274

[47] Molnár, L. Orthogonality preserving transformations on indefinite inner product spaces: generalization of Uhlhorn's version of Wigner's theorem, J. Funct. Anal., Volume 194 (2002), pp. 248-262

[48] Pagliani, P.; Chakraborty, M.K. A Geometry of Approximation. Rough Set Theory: Logic, Algebra and Topology of Conceptual Patterns, Springer, 2008

[49] Poonen, B. Union-closed families, J. Comb. Theory, Ser. A, Volume 59 (1992), pp. 253-268

[50] Reidys, C.M. Sequential dynamical systems over words, Ann. Comb., Volume 10 (2006) no. 4, pp. 481-498

[51] Reidys, C.M. Combinatorics of sequential dynamical systems, Discrete Math., Volume 308 (2008) no. 4, pp. 514-528

[52] Tanga, J.; Shea, K.; Min, F.; Zhu, W. A matroidal approach to rough set theory, Theor. Comput. Sci., Volume 471 (2013), pp. 1-11

[53] Van den Broek, P.M. Symmetry transformations in indefinite metric spaces: a generalization of Wigner's theorem, Physica A, Volume 127 (1984) no. 3, pp. 599-612

[54] Welsh, D.J.A. Matroid Theory, Academic Press, 1976

[55] Zhu, W.; Wang, S. Rough matroids based on relations, Inf. Sci., Volume 232 (2013), pp. 241-252

Cité par Sources :