### Abstract

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 language | English |
---|---|

Pages (from-to) | 1-19 |

Number of pages | 19 |

Journal | Electronic Journal of Combinatorics |

Volume | 16 |

Issue number | #R69 |

Publication status | Published - 2009 |

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

## Cite this

GRUTTMULLER, M., HARTMANN, S., Kalinowski, T., Leck, U., & Roberts, I. (2009). Maximal flat antichains of minimum weight.

*Electronic Journal of Combinatorics*,*16*(#R69), 1-19.