×

Well-graded families and the union-closed sets conjecture. (English) Zbl 1507.05096

Summary: The union-closed sets conjecture states that if a finite family of sets \(\mathcal{F}\) is union-closed, then there must be some element contained in at least half of the sets of \(\mathcal{F} \). In this work we study the relationship between the union-closed sets conjecture and union-closed families that have the property of being well-graded. In doing so, we show how the density and other properties are affected by the extra structure contained in well-graded families, and we also give several conditions under which well-graded families satisfy the union-closed sets conjecture.

MSC:

05D05 Extremal set theory
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] A. Abdollahi, R. Woodroofe, and G. Zaimi. Frankl’s conjecture for subgroup lattices. The Electronic Journal of Combinatorics, 24(3), 2017. · Zbl 1369.06001
[2] I. Balla. Minimum density of union-closed families.arXiv:1106.0369, 2011.
[3] I. Balla, B. Bollobas, and T. Eccles. Union-closed families of sets.Journal of Combinatorial Theory (Series A), 120:531-544, 2013. · Zbl 1259.05177
[4] H. Bruhn and O. Schaudt. The journey of the union-closed sets conjecture.Graphs and Combinatorics, 31:2043-2074, 2015. · Zbl 1327.05249
[5] J.-P. Doignon and J.-C. Falmagne. Spaces for the assessment of knowledge.International Journal of Man-Machine Studies, 23:175-196, 1985. · Zbl 0581.68066
[6] J.-P. Doignon and J.-C. Falmagne. Well-graded families of relations.Discrete Mathematics, 173:35-44, 1997. · Zbl 0877.06002
[7] D. Duffus and B. Sands. An inequality for the sizes of prime filters of finite distributive lattices.Discrete Mathematics, 201:89-99, 04 1999. · Zbl 0937.06004
[8] T. Eccles. A stability result for the union-closed size problem.Combinatorics, Probability and Computing, 25(3):399-418, 2016. · Zbl 1372.05016
[9] D. Eppstein, J.-C. Falmagne, and H. Uzun. On verifying and engineering the wellgradedness of a union-closed family.Journal of Mathematical Psychology, 53(1): 34-39, 2009. · Zbl 1176.91136
[10] J.-C. Falmagne and J.-P. Doignon.Learning Spaces. Springer-Verlag, Heidelberg, 2011.
[11] J.-C. Falmagne, E. Cosyn, J.-P. Doignon, and N. Thi´ery. The assessment of knowledge, in theory and in practice. In R. Missaoui and J. Schmidt, editors,Formal Concept Analysis: Foundations and Applications, pages 61-79. Spring-Verlag, 2006. · Zbl 1177.68206
[12] J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, editors.Knowledge Spaces: Applications in Education. Springer-Verlag, Heidelberg, 2013. · Zbl 1276.68015
[13] I. Karpas. Two results on union-closed families.arXiv:1708.01434, 2017.
[14] M. Koppen. On alternative representations for knowledge spaces.Mathematical Social Sciences, 36(2):127-143, 1998. · Zbl 0923.92039
[15] J. Matayoshi. On the properties of well-graded union-closed families.Journal of Mathematical Psychology, 80:15-21, 2017. · Zbl 1397.91540
[16] B. Poonen. Union-closed families.Journal of Combinatorial Theory, Series A, 59: 253-268, 1992. · Zbl 0758.05096
[17] J. Pulaj, A. Raymond, and D. Theis. New conjectures for union-closed families.The Electronic Journal of Combinatorics, 23(3) #P3.23, 2016. · Zbl 1412.05193
[18] A. Raz. Note on the union-closed sets conjecture.The Electronic Journal of Combithe electronic journal of combinatorics27(1)(2020), #P1.6417 natorics, 24(3) #P3.53, 2017. · Zbl 1369.05198
[19] D. Reimer. An average set size theorem.Combinatorics, Probability and Computing, 12:89-93, 2003. · Zbl 1013.05083
[20] I. Rival, editor.Graphs and order, volume 147. Springer Netherlands, 1985.
[21] D. Sarvate and J.-C. Renaud. On the union-closed sets conjecture.Ars Combinatorica, 27:149-154, 1989. · Zbl 0686.05001
[22] P.
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.