×

zbMATH — the first resource for mathematics

Antichains and completely separating systems – a catalogue and applications. (English) Zbl 1282.05207
Summary: This paper extends known results on the existence, number and structure of antichains and completely separating systems. Both these structures are classified in several ways, and both an enumeration and listing of each type of object are given in a catalogue, which is described in detail in this paper. The antichain catalogue provides a complete listing of all non-isomorphic antichains on \(m\) points for \(m\leq 7\).
MSC:
05D05 Extremal set theory
Software:
OEIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Benoumhani, M., The number of topologies on a finite set, J. Integer Seq., 9, 2, 9, (2006), Article 06.2.6 (electronic) · Zbl 1103.11007
[2] Bey, C., Polynomial LYM inequalities, Combinatorica, 25, 1, 19-38, (2005) · Zbl 1070.05076
[3] M. Böhm, Reguläre Antiketten. Diploma Thesis, Universität Rostock, 2008.
[4] Böhm, M., \((m - 1)\)-regular antichains on \([m]\), J. Combin. Math. Combin. Comput., 75, 201-207, (2010) · Zbl 1238.05265
[5] Bollobás, B., Combinatorics, (1986), Cambridge University Press Cambridge, UK
[6] Brankovic, L.; Lieby, P.; Miller, M., Flattening antichains with respect to the volume, Electron. J. Combin., 6, 12, (1999), Research paper 1 (electronic) · Zbl 0913.05092
[7] Brinkmann, G.; McKay, B. D., Counting unlabelled topologies and transitive relations, J. Integer Seq., 8, 2, 7, (2005), Article 05.2.1 (electronic) · Zbl 1064.05068
[8] Cai, M. C., On a problem of katona on minimal completely separating systems with restrictions, Discrete Math., 48, 1, 121-123, (1984) · Zbl 0498.05003
[9] Duffus, D.; Frankl, P.; Rödl, V., Maximal independent sets in bipartite graphs obtained from Boolean lattices, European J. Combin., 32, 1, 1-9, (2011) · Zbl 1203.05075
[10] Duffus, D.; Sands, B.; Winkler, P., Maximal chains and antichains in Boolean lattices, SIAM J. Discrete Math., 3, 2, 197-205, (1990) · Zbl 0704.06001
[11] Erné, M.; Stege, K., Counting finite posets and topologies, Order, 8, 3, 247-265, (1991) · Zbl 0752.05002
[12] Grüttmüller, M.; Hartmann, S.; Kalinowski, T.; Leck, U.; Roberts, I. T., Maximal flat antichains of minimum weight, Electron. J. Combin., 16, 1, 19, (2009), Research Paper 69 · Zbl 1229.05261
[13] Kisvölcsey, Á., Flattening antichains, Combinatorica, 26, 1, 65-82, (2006) · Zbl 1121.05117
[14] Kleitman, D., On dedekind’s problem: the number of monotone Boolean functions, Proc. Amer. Math. Soc., 21, 3, 677-682, (1969) · Zbl 0186.30702
[15] Lieby, P., Antichains on three levels, Electron. J. Combin., 11, 1, 32, (2004), Research paper 50 (electronic) · Zbl 1055.05148
[16] Phanalasy, O.; Miller, M.; Rylands, L. J.; Lieby, P., On a relationship between completely separating systems and antimagic labeling of regular graphs, (Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, LNCS, vol. 6460, (2011)), 238-241 · Zbl 1326.05136
[17] Ramsay, C.; Roberts, I. T., Minimal completely separating systems of sets, Australas. J. Combin., 13, 129-150, (1996) · Zbl 0847.05096
[18] Roberts, I. T., Completely separating systems of \(k\)-sets for \(7 \leq k \leq 10\), Australas. J. Combin., 33, 87-98, (2005) · Zbl 1084.05074
[19] I.T. Roberts, S. D’Arcy, D. Gronau, Completely separating systems of \(k\)-sets for \((\substack{k - 1 \\ 2}) \leq n <(\substack{k \\ 2})\) or \(11 \leq k \leq 12\). Australas. J. Combin. (Submitted for publication).
[20] Roberts, Ian T.; Rylands, Leanne J., Minimal \((n)\) and \((n, h, k)\) completely separating systems, Australas. J. Combin., 33, 57-66, (2005) · Zbl 1080.05097
[21] Roberts, I. T.; Rylands, L. J.; Montag, T.; Grüttmüller, M., On the number of minimal completely separating systems and antichains in a Boolean lattice, Australas. J. Combin., 48, 143-158, (2010) · Zbl 1231.05024
[22] N.J.A. Sloane, The on-line encyclopedia of integer sequences. http://oeis.org/classic/A003182 (accessed 18.11.2011). · Zbl 1044.11108
[23] N.J.A. Sloane, The on-line encyclopedia of integer sequences. http://oeis.org/classic/A000372 (accessed 18.11.2011). · Zbl 1044.11108
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.