On a conjecture of Hilton

MaRDI QIDQ2760448zbMATH OpenFDO

Authors Jiping Liu, Cheng Zhao

Publication date 2 January 2002

Published in The Australasian Journal of Combinatorics (Search for Journal in Brave)

zbMATH Keywords

collection of sets conjecture of Hilton incomparable uncomplemented collections of distinct subsets

Mathematics Subject Classification ID

Extremal set theory (05D05)

Review text

Let \({\mathcal A}_1,\dots,{\mathcal A}_k\) be collections of subsets of an \(n\)-element set. We say that the collections \({\mathcal A}_1,\dots,{\mathcal A}_k\) are incomparable if for any \(i,j= 1,\dots, k\), \(i\neq j\), and \(A'\in{\mathcal A}_i\) and \(A\in{\mathcal A}_j\) we have \(A'\not\subset A\). A collection of sets \({\mathcal A}\) is uncomplemented if \(A\in{\mathcal A}\) implies \(\overline A\not\in{\mathcal A}\), where \(\overline A\) is the complement of the set \(A\). In 1976 Hilton conjectured that the sum of the cardinalities of \(k\) incomparable uncomplemented collections of distinct subsets of an \(n\)-element set is bounded from above by \(2^{n-1}\); see \textit{A. J. W. Hilton} [Q. J. Math., Oxf. II. Ser. 27, 33-36 (1976; Zbl 0324.05004)]. He proved this conjecture for \(k=2\). The conjecture remains open for \(k\geq 3\). The paper by Liu and Zhao contains several results partially supporting this conjecture. The authors show that the conjecture holds if some additional conditions are imposed on the cardinality of one or more of the collections occurring in the conjecture of Hilton. In the case of \(k=3\) they prove an upper bound which differs form the bound anticipated by Hilton by a constant factor of \({9\over 8}\).

Recommendations

Cited in

(7)

This page was built for publication: On a conjecture of Hilton

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2760448)