mycoreobjectrosdok_document_0000028035rosdok_document_0000028035rosdokdocumentrosdok_derivate_00002299352026-10-21T11:17:19.549Z2026-10-21T11:04:42.577ZMCRJANITOReditorKEpublished1rosdok_derivate_0000229935truetruederivate_types:fulltextVolltextfulltextwf_edit_epub wf_register_epubstate:publishedstate:publishedveröffentlichtpublishedrosdok_id000058981987259742Oau2026-10-212026-10-21T11:17:03ZrdaConverted from PICA to MODS using Pica2MODS XSLT Transformer 2.14-SNAPSHOT [SCM: "" "" ""] with mode 'DEFAULT'.WorkingpaperMaximal flat antichains of minimum weightWe 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).MartinGrüttmüller1970 -VerfasserInaut122522559ThomasKalinowski1980 -VerfasserInaut1284202510000-0002-8444-6848UweLeck1969 -VerfasserInaut123092418SvenHartmann1969 -VerfasserInaut118124978Ian T.RobertsVerfasserInauthttps://purl.uni-rostock.de/rosdok/id00005898urn:nbn:de:gbv:28-rosdok_id00005898-410.18453/rosdok_id00005898510 MathematikMathematisch-Naturwissenschaftliche Fakultätalle Rechte vorbehaltenRechteinhaber Universität Rostockfrei zugänglich (Open Access)Lizenz Metadaten: CC0en1 Online-Ressource (19 Seiten)2005University of Rostock, Institute of MathematicsRostockmonographic20052026Universitätsbibliothek RostockRostock2026Universitätsbibliothek Rostockhttps://purl.uni-rostock.de/rosdok/id00005898Martin Grüttmüller, Thomas Kalinowski, Uwe Leck, Sven Hartmann, Ian T. Robertsrosdok_id000058161986139832Odvhttps://purl.uni-rostock.de/rosdok/id00005816Preprints aus dem Institut für Mathematik3255797-805/30005-0003doctype:epubdoctype:epubDokumenttypDocument typedoctype:epub.workingpaperdoctype:epub.workingpaperWorkingpaperworking paperdiniPublType:workingPaper diniPublType2022:WorkingPaperinfo:eu-repo/semantics/workingPaperdocumentdiniPublType2022:WorkingPaperdiniPublType2022:WorkingPaperArbeitspapierWorking paperKDSF (Pu37)SDNB:510SDNB:510510 Mathematik510 Mathematicsinstitution:unirostockinstitution:unirostockUniversität RostockUniversity of RostockUniversität RostockUniversität RostockUni.Rostockhttp://d-nb.info/gnd/38329-6institution:unirostock.mnfinstitution:unirostock.mnfMathematisch-Naturwissenschaftliche FakultätFaculty of Mathematics and Natural SciencesUniversität Rostock. Mathematisch-Naturwissenschaftliche FakultätMathematisch-Natur-<br />wissenschaftliche FakultätUni.Rostock.Fakultaet.MNFhttp://d-nb.info/gnd/2147083-2licenseinfo:worklicenseinfo:workWerkworklicenseinfo:work.rightsreservedlicenseinfo:work.rightsreservedalle Rechte vorbehaltenall rights reserved/creativecommons/r/reserved/0.9/88x31.png[DE-28]Urheberrechtsschutz 1.0$gRights Statements$uhttp://rightsstatements.org/vocab/InC/1.0/http://rightsstatements.org/vocab/InC/1.0/http://rightsstatements.org/vocab/InC/1.0/licenseinfo:depositlicenseinfo:depositVeröffentlichungsgenehmigungpermission to storelicenseinfo:deposit.rightsunirostocklicenseinfo:deposit.rightsunirostockRechteinhaber Universität Rostockrightsholder Rostock Universityaccesscondition:openaccessaccesscondition:openaccessfrei zugänglich (Open Access)open accesshttp://purl.org/coar/access_right/c_abf2OAfreeinfo:eu-repo/semantics/openAccess[DE-28]Open Access$gControlled Vocabulary for Access Rights$uhttp://purl.org/coar/access_right/c_abf2licenseinfo:metadatalicenseinfo:metadataLizenzen für Metadatenlicenseinfo:metadata.cc0licenseinfo:metadata.cc0Lizenz Metadaten: CC0license metadata: CC0/creativecommons/p/zero/1.0/88x31.pnghttps://creativecommons.org/publicdomain/zero/1.0/rfc5646:enrfc5646:enEnglischEnglishengengMaximal flat antichains of minimum weightMaximal flat antichains of minimum weightgnd:122522559gnd:128420251orcid:0000-0002-8444-6848gnd:123092418gnd:118124978gnd:122522559gnd:128420251orcid:0000-0002-8444-6848gnd:123092418gnd:118124978rosdok_document_0000028035-d3975982e49gnd:122522559Martin GrüttmüllerMartin Grüttmüllerrosdok_document_0000028035-d3975982e63gnd:128420251orcid:0000-0002-8444-6848Thomas KalinowskiThomas Kalinowskirosdok_document_0000028035-d3975982e79gnd:123092418Uwe LeckUwe Leckrosdok_document_0000028035-d3975982e93gnd:118124978Sven HartmannSven Hartmannrosdok_document_0000028035-d3975982e107Ian T. RobertsIan T. RobertsMartin GrüttmüllerThomas KalinowskiUwe LeckSven HartmannIan T. RobertsMartin GrüttmüllerThomas KalinowskiUwe LeckSven HartmannIan T. RobertsMartin GrüttmüllerThomas KalinowskiUwe LeckSven HartmannIan T. RobertsRostockUniversity of Rostock, Institute of Mathematicsepub.workingpaperhttps://purl.uni-rostock.de/rosdok/id00005898urn:nbn:de:gbv:28-rosdok_id00005898-410.18453/rosdok_id00005898We 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).20052005Preprints aus dem Institut für Mathematikrosdok_id000058161986139832Odvhttps://purl.uni-rostock.de/rosdok/id00005816Preprints aus dem Institut für Mathematik3255797-805/30005-0003https://purl.uni-rostock.de/rosdok/id000058163255797-8Martin Grüttmüller, Thomas Kalinowski, Uwe Leck, Sven Hartmann, Ian T. Robertsepub.workingpaper1 Gruettmueller_flat_2005.pdf 227923 3b3e5e5af0023ddb76ee6733dfc59971 rosdok_id000058981987259742Oau2026-10-212026-10-21T11:17:03ZrdaConverted from PICA to MODS using Pica2MODS XSLT Transformer 2.14-SNAPSHOT [SCM: "" "" ""] with mode 'DEFAULT'.WorkingpaperMaximal flat antichains of minimum weightWe 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).MartinGrüttmüller1970 -VerfasserInaut122522559ThomasKalinowski1980 -VerfasserInaut1284202510000-0002-8444-6848UweLeck1969 -VerfasserInaut123092418SvenHartmann1969 -VerfasserInaut118124978Ian T.RobertsVerfasserInauthttps://purl.uni-rostock.de/rosdok/id00005898urn:nbn:de:gbv:28-rosdok_id00005898-410.18453/rosdok_id00005898510 MathematikMathematisch-Naturwissenschaftliche Fakultätalle Rechte vorbehaltenRechteinhaber Universität Rostockfrei zugänglich (Open Access)Lizenz Metadaten: CC0en1 Online-Ressource (19 Seiten)2005University of Rostock, Institute of MathematicsRostockmonographic20052026Universitätsbibliothek RostockRostock2026Universitätsbibliothek Rostockhttps://purl.uni-rostock.de/rosdok/id00005898Martin Grüttmüller, Thomas Kalinowski, Uwe Leck, Sven Hartmann, Ian T. Robertsrosdok_id000058161986139832Odvhttps://purl.uni-rostock.de/rosdok/id00005816Preprints aus dem Institut für Mathematik3255797-805/30005-0003 2026-10-21T11:04:42.577Z 2026-10-21T11:17:19.549Z 2026-10-31T11:17:19.562Z editorKE {"identifier":"rosdok/id00005898","type":"local_id","additional":"","service":"MCRLocalID","created":"2026-10-21T11:04:42.617Z"} {"identifier":"urn:nbn:de:gbv:28-rosdok_id00005898-4","type":"dnbUrn","additional":"","service":"RosDokURN","created":"2026-10-21T11:04:42.634Z"} {"identifier":"https://purl.uni-rostock.de/rosdok/id00005898","type":"purl","additional":"","service":"RosDokPURL","created":"2026-10-21T11:04:42.640Z","registrationStarted":"2026-10-21T11:17:18.469Z"} {"identifier":"10.18453/rosdok_id00005898","type":"doi","additional":"","service":"RosDokDOI","created":"2026-10-21T11:04:42.645Z","registrationStarted":"2026-10-21T11:17:18.228Z","registered":"2026-10-21T11:17:19.545Z"} MCRJANITORfulltextfile/rosdok_document_0000028035/rosdok_derivate_0000229935/Gruettmueller_flat_2005.pdfMaximal flat antichains of minimum weightMaximal flat antichains of minimum weightgnd:122522559gnd:128420251orcid:0000-0002-8444-6848gnd:123092418gnd:118124978gnd:122522559gnd:128420251orcid:0000-0002-8444-6848gnd:123092418gnd:118124978rosdok_document_0000028035-d3975982e49gnd:122522559Martin GrüttmüllerMartin Grüttmüllerrosdok_document_0000028035-d3975982e63gnd:128420251orcid:0000-0002-8444-6848Thomas KalinowskiThomas Kalinowskirosdok_document_0000028035-d3975982e79gnd:123092418Uwe LeckUwe Leckrosdok_document_0000028035-d3975982e93gnd:118124978Sven HartmannSven Hartmannrosdok_document_0000028035-d3975982e107Ian T. RobertsIan T. RobertsMartin GrüttmüllerThomas KalinowskiUwe LeckSven HartmannIan T. RobertsMartin GrüttmüllerThomas KalinowskiUwe LeckSven HartmannIan T. RobertsMartin GrüttmüllerThomas KalinowskiUwe LeckSven HartmannIan T. RobertsRostockUniversity of Rostock, Institute of Mathematicsepub.workingpaperhttps://purl.uni-rostock.de/rosdok/id00005898urn:nbn:de:gbv:28-rosdok_id00005898-410.18453/rosdok_id00005898We 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).20052005Preprints aus dem Institut für Mathematikrosdok_id000058161986139832Odvhttps://purl.uni-rostock.de/rosdok/id00005816Preprints aus dem Institut für Mathematik3255797-805/30005-0003https://purl.uni-rostock.de/rosdok/id000058163255797-8Martin Grüttmüller, Thomas Kalinowski, Uwe Leck, Sven Hartmann, Ian T. Roberts[xslt]Saxonrosdok_id00005898https://purl.uni-rostock.de/rosdok/id00005898198725974210.18453/rosdok_id00005898urn:nbn:de:gbv:28-rosdok_id00005898-4Martin Grüttmüller, Thomas Kalinowski, Uwe Leck, Sven Hartmann, Ian T. RobertsGrüttmüller Martin, Kalinowski Thomas, Leck Uwe, Hartmann Sven, Roberts Ian T.Maximal flat antichains of minimum weightWorkingpaperworking paperUniversity of Rostock, Institute of Mathematics, 2005We 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…rosdok_id000058160005-000305/3Martin GrüttmüllerThomas KalinowskiUwe LeckSven HartmannIan T. RobertsMaximal flat antichains of minimum weightPreprints aus dem Institut für MathematikUniversitätsbibliothek Rostockhttps://purl.uni-rostock.de/rosdok/id00005898MartinGrüttmüller1970 -VerfasserInaut122522559ThomasKalinowski1980 -VerfasserInaut1284202510000-0002-8444-6848UweLeck1969 -VerfasserInaut123092418SvenHartmann1969 -VerfasserInaut118124978Ian T.RobertsVerfasserInaut[purl]https://purl.uni-rostock.de/rosdok/id00005898[urn]urn:nbn:de:gbv:28-rosdok_id00005898-4[doi]10.18453/rosdok_id00005898open_access20052005epoch:21th_centuryrfc5646:endoctype:epub.workingpaperaccesscondition:openaccessSDNB:510institution:unirostock.mnfstate:published