HOW MANY SUBSETS WHICH THEIR OPERATIONS WITH A FIXED SUBSET CONTAIN AT LEAST ONE ELEMENT OF A GIVEN COLLECTION?
Abstract
We pose the following problem related to binary set operations on finite sets. Given a finite set . Let a binary set operation and be a non-empty collection of non-empty subsets of . For a fixed subset of , where , how many subsets of which their operation with contains at least one element of ?. In this paper, we give the solution of this problem, especially for the subsets of size , using the inclusion-exclusion principle, Corrádi’s lemma, and Bonferroni’s inequality. In this context, the problem is related to determining the degree of nodes in certain graphs, such as graphs constructed with the adjacency rule depends on and the node set is a hypergraph.
Downloads
References
K. Dohmen, “Improved Bonferroni Inequalities via Union-Closed Set Systems,” J. Comb. Theory, Ser. A, vol. 92, pp. 61–67, 2000, doi: 10.1006/jcta.1999.3030.
K. Corrádi, “Problem at Schweitzer competition,” Mat. Lapok., vol. 20, pp. 159–162, 1969.
S. Jukna, Extremal Combinatorics With Applications in Computer Science. Berlin: Springer-Verlag Berlin Heidelberg, 2011.
X. Li, H. Broersma, and L. Wang, “Grow rates of the bipartite Erdős-Gyarfas function,” arXiv: 2111.00879 [math.CO], 2021.
C. Berge, Graphs and Hypergraphs. Amsterdam: North-Holland Publishing Company, 1973.
V. Blinovsky and C. Greenhill, “Asymptotic enumeration of sparse uniform hypergraphs with given degrees,” Eur. J. Comb., vol. 51, pp. 287–296, 2016, doi: 10.1016/j.ejc.2015.06.004.
X. Ouvrard, “Hypergraphs: an introduction and review,” arXiv: 2002.05014 [cs.DM], 2020.
M. M. Jadhav and K. F. Pawar, “On edge product number of hypergraph,” Palest. J. Math., vol. 11, no. 4, pp. 183–194, 2022.
V. Blinovsky and C. Greenhill, “Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees,” Electron. J. Comb., vol. 23, no. 3, pp. 1–17, 2016, doi: 10.37236/5512.
M. Axenovich, D. Bradač, L. Gishboliner, D. Mubayi, and L. Weber, “Large cliques or cocliques in hypergraphs with forbidden order-size pairs,” Comb. Probab. Comput., pp. 286–299, 2023, doi: 10.1017/S0963548323000433.
M. N. Huda, “Graf subset tak seragam yang berasosiasi dengan sebarang graf,” Universitas Gadjah Mada, 2024.
R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R. Wood, “Token graphs,” Graphs Comb., vol. 28, pp. 365–380, 2012, doi: 10.1007/s00373-011-1055-9.
J. Zhang, J.-X. Zhou, Y.-T. Li, and Y. S. Kwon, “The automorphisms of 2-token graphs,” Appl. Math. Comput., vol. 446, 2023, doi: 10.1016/j.amc.2023.127872.
Y. Susanti, “On the 2-token graphs of some disjoint union of graph,” Malaysian J. Math. Sci., vol. 17, no. 4, pp. 719–730, 2023, doi: 10.47836/mjms.17.4.12.
A. Lew, “Garland’s method for token graphs,” arXiv: 2305.02406 [math.CO], 2023.
J. Leaños and C. Ndjatchi, “The edge-connectivity of token graphs,” Graphs Comb., vol. 37, pp. 1013–1023, 2021, doi: 10.1007/s00373-021-02301-0.
L. E. Adame, L. M. Rivera, and A. L. Trujillo-Negrete, “Hamiltonicity of token graphs of some join graphs,” Symmetry (Basel)., vol. 13, no. 6, 2021, doi: 10.3390/sym13061076.
W. Carballosa, R. Fabila-Monroy, J. Leanos, and L. M. Rivera, “Regularity and planarity of token graphs,” Discuss. Math. Graph Theory, vol. 37, pp. 573–586, 2017, [Online]. Available: http://dx.doi.org/10.7151/dmgt.1959.
C. Dalfó, F. Duque, R. Fabila-monroy, and M. A. Fiol, “On the Laplacian spectra of token graphs ✩,” Linear Algebra Appl., vol. 625, pp. 322–348, 2021, doi: 10.1016/j.laa.2021.05.005.
S. Barik and P. Verma, “Spectral properties of token graphs,” Linear Algebra Appl., vol. 687, pp. 181–206, 2024, doi: 10.1016/j.laa.2024.02.004.
C. Bagiński and P. Grzeszczuk, “On the generic family of Cayley graphs of a finite group,” J. Comb. Theory, Ser. A, vol. 184, p. 105495, 2021, doi: 10.1016/j.jcta.2021.105495.
Y. Susanti and A. Erfanian, “Prime square order Cayley graph of cyclic groups,” Asian-European J. Math., vol. 17, no. 2, 2024, doi: 10.1142/S1793557124500037.
X. Ma, H. Wei, and L. Yang, “The coprime graph of a group,” Int. J. Gr. Theory, vol. 3, no. 3, pp. 13–23, 2014.
F. Mansoori, A. Erfanian, and B. Tolue, “Non-coprime graph of a finite group,” 2016, [Online]. Available: https://doi.org/10.1063/1.4954605.
M. N. Huda and S. Ali, “Non-coprime graph energy of dihedral and symmetric group,” 2024.
M. N. Huda, “A note on hamiltonicity conditions of the coprime and non-coprime graphs of a finite group,” J. Mat. UNAND, vol. 13, no. 3, pp. 157–162, 2024.
Copyright (c) 2024 Muhammad Nurul Huda, Veni Rizki Lestari
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
