Maximal flat antichains of minimum weight

Martin Grüttmüller; Thomas Kalinowski; Uwe Leck; Sven Hartmann; Ian T. Roberts

doi:10.18453/rosdok_id00005898

zum übergeordneten Dokument

Martin Grüttmüller Thomas Kalinowski Uwe Leck Sven Hartmann Ian T. Roberts

Maximal flat antichains of minimum weight

University of Rostock, Institute of Mathematics, 2005

https://doi.org/10.18453/rosdok_id00005898

Abstract: We study maximal families A of subsets of [n] = {1; 2; : : : ; n} such that A contains only pairs and triples and A /⊆ 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 min w(A) = (2w2 + w3)n^2/8 + o(n^2) for 0 < w3/w2 =: λ = λ(n) < 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 w(A) = w2n^2/2 + o(n^2).

Workingpaper Freier Zugang

Titel:

Maximal flat antichains of minimum weight

Schriftenreihe:

Preprints aus dem Institut für Mathematik, 05/3

Beteiligte Personen:

Martin Grüttmüller[VerfasserIn]
	122522559
Thomas Kalinowski[VerfasserIn]
	0000-0002-8444-6848
	128420251
Uwe Leck[VerfasserIn]
	123092418
Sven Hartmann[VerfasserIn]
	118124978
Ian T. Roberts[VerfasserIn]

Zusammenfassung:

We study maximal families A of subsets of [n] = {1; 2; : : : ; n} such that A contains only pairs and triples and A /⊆ 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 min w(A) = (2w2 + w3)n^2/8 + o(n^2) for 0 < w3/w2 =: λ = λ(n) < 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 w(A) = w2n^2/2 + o(n^2). [Englisch]

Dokumenttyp:

Workingpaper

Einrichtung:

Mathematisch-Naturwissenschaftliche Fakultät

Sprache:

Englisch

Sachgruppe der DNB:

510 Mathematik

Umfang:

1 Online-Ressource (19 Seiten)

Veröffentlichung /
Entstehung:

Rostock: University of Rostock, Institute of Mathematics