Gruttmuller, Martin; Hartmann, Sven; Kalinowski, Thomas; Leck, Uwe; Roberts, Ian T

Author(s)

Gruttmuller, Martin

Hartmann, Sven

Kalinowski, Thomas

Leck, Uwe

Roberts, Ian T

Publication Date

2009-05-29

Abstract

We study maximal families 𝒜 of subsets of [𝑛]={1,2, . . . , 𝑛} such that 𝒜 contains only pairs and triples and 𝐴⊈𝐵 for all {𝐴,𝐵}⊆𝒜, i.e. 𝒜 is an antichain. For any 𝑛, all such families 𝒜 of minimum size are determined. This is equivalent to finding all graphs 𝐺=(𝑉,𝐸) with |𝑉|=𝑛 and with the property that every edge is contained in some triangle and such that|𝐸|−|𝑇| is maximum, where 𝑇 denotes the set of triangles in 𝐺. The largest possible value of |𝐸|−|𝑇| turns out to be equal to ⌊(𝑛+1)²/8⌋. Furthermore, if all pairs and triples have weights 𝑤₂ and 𝑤₃, respectively, the problem of minimizing the total weight 𝑤(𝒜) of 𝒜 is considered. We show that min 𝑤(𝒜)=(2𝑤₂+𝑤₃)𝑛²/8+𝑜(𝑛²) for 3/𝑛≤𝑤₃/𝑤₂=:λ=λ(𝑛)<2. For λ≥2 our problem is equivalent to the (6,3)-problem of Ruzsa and Szemerédi, and by a result of theirs it follows that min 𝑤(𝒜)= 𝑤₂𝑛²/2+𝑜(𝑛²).

Citation

The Electronic Journal of Combinatorics, 16(1), p. 1-19

ISSN

1077-8926

Link

https://hdl.handle.net/1959.11/26802

Publisher

Electronic Journal of Combinatorics

Title

Maximal flat antichains of minimum weight

Type of document

Journal Article

Entity Type

Publication

Author(s)	Gruttmuller, Martin Hartmann, Sven Kalinowski, Thomas Leck, Uwe Roberts, Ian T
Publication Date	2009-05-29
Abstract	We study maximal families 𝒜 of subsets of [𝑛]={1,2, . . . , 𝑛} such that 𝒜 contains only pairs and triples and 𝐴⊈𝐵 for all {𝐴,𝐵}⊆𝒜, i.e. 𝒜 is an antichain. For any 𝑛, all such families 𝒜 of minimum size are determined. This is equivalent to finding all graphs 𝐺=(𝑉,𝐸) with \|𝑉\|=𝑛 and with the property that every edge is contained in some triangle and such that\|𝐸\|−\|𝑇\| is maximum, where 𝑇 denotes the set of triangles in 𝐺. The largest possible value of \|𝐸\|−\|𝑇\| turns out to be equal to ⌊(𝑛+1)²/8⌋. Furthermore, if all pairs and triples have weights 𝑤₂ and 𝑤₃, respectively, the problem of minimizing the total weight 𝑤(𝒜) of 𝒜 is considered. We show that min 𝑤(𝒜)=(2𝑤₂+𝑤₃)𝑛²/8+𝑜(𝑛²) for 3/𝑛≤𝑤₃/𝑤₂=:λ=λ(𝑛)<2. For λ≥2 our problem is equivalent to the (6,3)-problem of Ruzsa and Szemerédi, and by a result of theirs it follows that min 𝑤(𝒜)= 𝑤₂𝑛²/2+𝑜(𝑛²).
Citation	The Electronic Journal of Combinatorics, 16(1), p. 1-19
ISSN	1077-8926
Link	https://hdl.handle.net/1959.11/26802
Publisher	Electronic Journal of Combinatorics
Title	Maximal flat antichains of minimum weight
Type of document	Journal Article
Entity Type	Publication

Maximal flat antichains of minimum weight

Files: