Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
union-closed sets; Frankl’s conjecture; lattice; semimodularity; planar lattice
union-closed sets; Frankl’s conjecture; lattice; semimodularity; planar lattice
Summary:
A lattice $L$ is said to satisfy (the lattice theoretic version of) Frankl’s conjecture if there is a join-irreducible element $f\in L$ such that at most half of the elements $x$ of $L$ satisfy $f\le x$. Frankl’s conjecture, also called as union-closed sets conjecture, is well-known in combinatorics, and it is equivalent to the statement that every finite lattice satisfies Frankl’s conjecture. Let $m$ denote the number of nonzero join-irreducible elements of $L$. It is well-known that $L$ consists of at most $2^m$ elements. Let us say that $L$ is large if it has more than $5\cdot 2^{m-3}$ elements. It is shown that every large semimodular lattice satisfies Frankl’s conjecture. The second result states that every finite semimodular planar lattice $L$ satisfies Frankl’s conjecture. If, in addition, $L$ has at least four elements and its largest element is join-reducible then there are at least two choices for the above-mentioned $f$.
References:
[1] Tetsuya, A: Excess of a lattice. Graphs and Combinatorics 18 (2002), 395–402. MR 1939063 | Zbl 1023.06002
[2] Tetsuya, A: Strong semimodular lattices and Frankl’s conjecture. Algebra Universalis 44 (2000), 379–382. MR 1816032 | Zbl 1013.06008
[3] Tetsuya A., Bumpei N.: Frankl’s conjecture is true for modular lattices, Graphs and Combinatorics. 14 (1998), 305–311. MR 1658869
[4] Tetsuya A., Bumpei N.: Lower semimodular types of lattices: Frankl’s conjecture holds for lower quasi-semimodular lattices. Graphs Combin. 16, 1 (2000), 1–16. MR 1750462 | Zbl 0948.06006
[5] Burris S., Sankappanavar H. P.: A Course in Universal Algebra. Graduate Texts in Mathematics, 78. Springer-Verlag, New York–Berlin, 1981; The Millennium Edition, http://www.math.uwaterloo.ca/$\sim $snburris/htdocs/ualg.html. MR 0648287 | Zbl 0478.08001
[6] Czédli G.: On averaging Frankl’s conjecture for large union-closed sets. Journal of Combinatorial Theory - Series A, to appear. Zbl 1206.05099
[7] Czédli G., Schmidt E. T.: How to derive finite semimodular lattices from distributive lattices?. Acta Mathematica Hungarica, to appear. MR 2452806 | Zbl 1199.06028
[8] Czédli G., Maróti, M, Schmidt E. T.: On the scope of averaging for Frankl’s conjecture. Order, submitted. Zbl 1229.05259
[9] Frankl P.: Extremal set systems. Handbook of combinatorics. Vol. 1, 2, 1293–1329, Elsevier, Amsterdam, 1995. MR 1373680
[10] Weidong G.,Hongquan Y.: Note on the union-closed sets conjecture. Ars Combin. 49 (1998), 280–288. MR 1633064 | Zbl 0963.05129
[11] Grätzer G.: General Lattice Theory. : Birkhäuser Verlag, Basel–Stuttgart. 1978, sec. edi. 1998. MR 0504338
[12] Grätzer G., Knapp E.: A note on planar semimodular lattices. Algebra Universalis 58 (2008), 497-499. MR 2443218 | Zbl 1223.06006
[13] Herrmann C., Langsdorf R.: Frankl’s conjecture for lower semimodular lattices. http://www.mathematik.tu-darmstadt.de:8080/$\sim $herrmann/recherche/
[14] Poonen B.: Union-closed families. J. Combinatorial Theory A 59 (1992), 253–268. MR 1149898 | Zbl 0758.05096
[15] Reinhold J.: Frankl’s conjecture is true for lower semimodular lattices. Graphs and Combinatorics 16 (2000), 115–116. MR 1750455 | Zbl 0948.06007
[16] Roberts I.: Tech. Rep. No. 2/92. : School Math. Stat., Curtin Univ. Tech., Perth. 1992.
[17] Stanley R. P.: Enumerative Combinatorics, Vol. I. : Wadsworth & Brooks/Coole, Belmont, CA. 1986. MR 0847717
Search
Partner of
