×

Simplicial complexes and closure systems induced by indistinguishability relations. (Complexes simpliciaux et systèmes de clôture induits par les relations d’indistinguabilité.) (English. French summary) Zbl 1371.05327

Summary: 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 \(\Omega\) of functions defined on a universe set \(U\) and to define an equivalence relation \(\equiv_A\) on \(U\) for any subset \(A \subseteq \operatorname{\Omega}\) in the following way: \(u \equiv_A u^\prime\) if \(a(u) = a(u^\prime)\) for any function \(a \in A\). By means of this family of relations, we introduce the indistinguishability relation on the power set \(\mathcal{P}(\operatorname{\Omega})\) as follows: for \(A, A^\prime \in \mathcal{P}(\operatorname{\Omega})\), we set \(A \approx A^\prime\) if the relations \(\equiv_A\) and \(\equiv_{A^\prime}\) coincide. We use then the indistinguishability relation to introduce several set families on \(\Omega\) that have interesting order, matroidal and combinatorial properties. We call the above set families the indistinguishability structures of the function system \((U, \operatorname{\Omega})\). 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.

MSC:

05E45 Combinatorial aspects of simplicial complexes
05C10 Planar graphs; geometric and topological aspects of graph theory
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrews, G. E., Euler’s “De Partitio numerorum”, Bull. Amer. Math. Soc., 44, 4, 561-573 (2007) · Zbl 1172.11031
[2] Apollonio, N.; Caramia, M., Recognizing Helly edge path tree graphs and their clique graphs, Discrete Appl. Math., 159, 1166-1175 (2011) · Zbl 1223.05293
[3] Apollonio, N.; Simeone, B., Improved approximation of maximum vertex coverage problem on bipartite graphs, SIAM J. Discrete Math., 28, 3, 1137-1151 (2014) · Zbl 1310.90095
[4] Apollonio, N.; Simeone, B., The maximum vertex coverage problem on bipartite graphs, Discrete Appl. Math., 165, 37-48 (2014) · Zbl 1288.05201
[5] Apollonio, N.; Caramia, M.; Franciosa, P. G., On the Galois lattice of bipartite distance hereditary graphs, Discrete Appl. Math., 190, 13-23 (2015) · Zbl 1316.05033
[6] Bayley, R. A., Orthogonal partitions in designed experiments, Des. Codes Cryptogr., 8, 3, 45-77 (1996) · Zbl 0877.05006
[7] Bayley, R. A., Association Schemes: Designed Experiments, Algebra and Combinatorics (2004), Cambridge University Press: Cambridge University Press Cambridge, UK, 387 p · Zbl 1051.05001
[8] Berge, C., Hypergraphs: Combinatorics of Finite Sets (1984), Elsevier: Elsevier Amsterdam
[9] Biacino, L., Generated envelopes, J. Math. Anal. Appl., 172, 179-190 (1993) · Zbl 0777.60004
[10] Biacino, L.; Gerla, G., An extension principle for closure operators, J. Math. Anal. Appl., 198, 1-24 (1996) · Zbl 0855.54007
[11] Birkhoff, G., Lattice Theory (1967), American Mathematical Society: American Mathematical Society Providence, Rhode Island · Zbl 0126.03801
[12] Bisi, C.; Chiaselotti, G., A class of lattices and boolean functions related to the Manickam-Miklös-Singhi conjecture, Adv. Geom., 13, 1, 1-27 (2013) · Zbl 1259.05178
[13] Bisi, C.; Chiaselotti, G.; Marino, G.; Oliverio, P. A., A natural extension of the Young partition lattice, Adv. Geom., 15, 3, 263-280 (2015) · Zbl 1317.05018
[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., 388-389, 247-273 (2017)
[15] Bisi, C.; Chiaselotti, G.; Gentile, T.; Oliverio, P. A., Dominance order on signed partitions, Adv. Geom., 17, 1, 5-29 (2017) · Zbl 1383.05020
[16] Boykett, T., Orderly algorithm to enumerate central groupoids and their graphs, Acta Math. Sin. Engl. Ser., 23, 2, 249-264 (2007) · Zbl 1117.05054
[17] Boykett, T., Rectangular groupoids and related structures, Discrete Math., 313, 1409-1418 (2013) · Zbl 1283.08011
[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., 330, 342-357 (2016) · Zbl 1390.68618
[19] Cattaneo, G.; Chiaselotti, G.; Oliverio, P. A.; Stumbo, F., A new discrete dynamical system of signed integer partitions, Eur. J. Comb., 55, 119-143 (2016) · Zbl 1333.05026
[20] Chen, B.; Yan, M., Eulerian stratification of polyhedra, Adv. Appl. Math., 21, 22-57 (1998) · Zbl 0919.52014
[21] Chen, B.; Yan, M., The geometric cone relations for simplicial and cubical complexes, Discrete Math., 183, 39-46 (1998) · Zbl 0896.52020
[22] Chen, B.; Yau, S. T.; Yeh, Y. N., Graph homotopy and Graham homotopy, Discrete Math., 241, 153-170 (2001) · Zbl 0990.05120
[23] Chiaselotti, G.; Gentile, T., Intersection properties of maximal directed cuts in digraphs, Discrete Math., 340, 3171-3175 (2017) · Zbl 1347.05083
[24] Chiaselotti, G.; Infante, G.; Marino, G., New results related to a conjecture of Manickam and Singhi, Eur. J. Comb., 29, 2, 361-368 (2008) · Zbl 1131.05093
[25] Chiaselotti, G.; Gentile, T.; Oliverio, P. A., Parallel and sequential dynamics of two discrete models of signed integer partitions, Appl. Math. Comput., 232, 1249-1261 (2014) · Zbl 1410.37015
[26] Chiaselotti, G.; Ciucci, D.; Gentile, T., Simple graphs in granular computing, Inf. Sci., 340-341, 279-304 (2016) · Zbl 1395.68260
[27] Chiaselotti, G.; Gentile, T.; Infusino, F., Dependency structures for decision tables, Int. J. Approx. Reason., 88, 333-370 (2017) · Zbl 1418.68187
[28] Chiaselotti, G.; Gentile, T.; Infusino, F., Knowledge pairing systems in granular computing, Knowl.-Based Syst., 124, 144-163 (2017)
[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., 196, 3, 1073-1112 (2017) · Zbl 1366.05029
[31] Diestel, R., Graph Theory, Grad. Texts Math. (2010), Springer · Zbl 1204.05001
[32] Eiter, T.; Gottlob, G., Identifying the minimal transversals of a hypergraph and related problems, SIAM J. Comput., 24, 1278-1304 (1995) · Zbl 0842.05070
[33] Elbassioni, K., On the complexity of monotone dualization and generating minimal hypergraph transversals, Discrete Appl. Math., 32, 2, 171-187 (2008)
[34] Erdös, P.; Rényi, A., Asymmetric graphs, Acta Math. Hung., 14, 3-4, 295-315 (1963) · Zbl 0118.18901
[35] Ganter, B.; Wille, R., Formal Concept Analysis. Mathematical Foundations (1999), Springer-Verlag · Zbl 0909.06001
[36] Guo, L.; Huang, F.; Lia, Q.; Zhang, G., Power contexts and their concept lattices, Discrete Math., 311, 2049-2063 (2011) · Zbl 1233.68207
[37] Gyárfás, A.; Lehel, J., Hypergraph families with bounded edge cover or transversal number, Combinatorica, 3, 3-4, 351-358 (1983) · Zbl 0534.05052
[38] Hagen, M., Lower bounds for three algorithms for transversal hypergraph generation, Discrete Appl. Math., 157, 1460-1469 (2009) · Zbl 1177.05116
[39] (Hahn, G.; Sabidussi, G., Graph Symmetry. Algebraic Methods and Applications. Graph Symmetry. Algebraic Methods and Applications, NATO ASI Ser., vol. 497 (1997), Springer) · Zbl 0868.00039
[40] Harley, P. W., Metric and symmetric spaces, Proc. Amer. Math. Soc., 43, 2, 428-430 (1974) · Zbl 0288.54031
[41] Huang, A.; Zhao, H.; Zhu, W., Nullity-based matroid of rough sets and its application to attribute reduction, Inf. Sci., 263, 153-165 (2014) · Zbl 1328.68228
[42] Keith, W. J., A bijective toolkit for signed partitions, Ann. Comb., 15, 95-117 (2011) · Zbl 1233.05031
[43] Kelarev, A.; Praeger, C. E., On transitive Cayley graphs of groups and semigroups, Eur. J. Comb., 24, 1, 59-72 (2003) · Zbl 1011.05027
[44] Kelarev, A.; Quinn, S. J., Directed graphs and combinatorial properties of semigroups, J. Algebra, 251, 1, 16-26 (2002) · Zbl 1005.20043
[45] Kelarev, A.; Ryan, J.; Yearwood, J., Cayley graphs as classifiers for data mining: the influence of asymmetries, Discrete Math., 309, 5360-5369 (2009) · Zbl 1206.05050
[46] Martin, H. W., Metrization of symmetric spaces and regular maps, Proc. Amer. Math. Soc., 35, 269-274 (1972) · Zbl 0264.54023
[47] Molnár, L., Orthogonality preserving transformations on indefinite inner product spaces: generalization of Uhlhorn’s version of Wigner’s theorem, J. Funct. Anal., 194, 248-262 (2002) · Zbl 1010.46023
[48] Pagliani, P.; Chakraborty, M. K., A Geometry of Approximation. Rough Set Theory: Logic, Algebra and Topology of Conceptual Patterns (2008), Springer · Zbl 1213.03002
[49] Poonen, B., Union-closed families, J. Comb. Theory, Ser. A, 59, 253-268 (1992) · Zbl 0758.05096
[50] Reidys, C. M., Sequential dynamical systems over words, Ann. Comb., 10, 4, 481-498 (2006) · Zbl 1130.37334
[51] Reidys, C. M., Combinatorics of sequential dynamical systems, Discrete Math., 308, 4, 514-528 (2008) · Zbl 1128.37006
[52] Tanga, J.; Shea, K.; Min, F.; Zhu, W., A matroidal approach to rough set theory, Theor. Comput. Sci., 471, 1-11 (2013) · Zbl 1258.05022
[53] Van den Broek, P. M., Symmetry transformations in indefinite metric spaces: a generalization of Wigner’s theorem, Physica A, 127, 3, 599-612 (1984) · Zbl 0599.20072
[54] Welsh, D. J.A., Matroid Theory (1976), Academic Press · Zbl 0343.05002
[55] Zhu, W.; Wang, S., Rough matroids based on relations, Inf. Sci., 232, 241-252 (2013) · Zbl 1293.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.