Maximal flat antichains of minimum weight

M GRUTTMULLER, S HARTMANN, Thomas Kalinowski, Uwe Leck, Ian Roberts

    Research output: Contribution to journalArticlepeer-review


    We study maximal families A of subsets of [n] = {1, 2, . . . , n} such that A contains only pairs and triples and A 6? B for all {A,B} ? A, i.e. A is an antichain. For any n, all such families A of minimum size are determined. This is equivalent to finding all graphs G = (V,E) with V = n and with the property that every edge is contained in some triangle and such that E-T is maximum, where T denotes the set of triangles in G. The largest possible value of E - T turns out to be equal to ?(n+1)2/8?. Furthermore, if all pairs and triples have weights w2 and w3, respectively, the problem of minimizing the total weight w(A) of A is considered. We show that minw(A) = (2w2+w3)n2/8+o(n2) for 3/n ? w3/w2 =: - = -(n) < 2. For- ? 2 our problem is equivalent to the (6,3)-problem of Ruzsa and Szemer'edi, and by a result of theirs it follows that minw(A) = w2n2/2 + o(n2).
    Original languageEnglish
    Pages (from-to)1-19
    Number of pages19
    JournalElectronic Journal of Combinatorics
    Issue number#R69
    Publication statusPublished - 2009


    Dive into the research topics of 'Maximal flat antichains of minimum weight'. Together they form a unique fingerprint.

    Cite this