Please use this identifier to cite or link to this item:
https://hdl.handle.net/1959.11/26802
Title: | Maximal flat antichains of minimum weight | Contributor(s): | Gruttmuller, Martin (author); Hartmann, Sven (author); Kalinowski, Thomas (author) ; Leck, Uwe (author); Roberts, Ian T (author) | Publication Date: | 2009-05-29 | Open Access: | Yes | Handle Link: | https://hdl.handle.net/1959.11/26802 | Open Access Link: | https://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r69/pdf | 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+(²). | Publication Type: | Journal Article | Source of Publication: | The Electronic Journal of Combinatorics, 16(1), p. 1-19 | Publisher: | Electronic Journal of Combinatorics | Place of Publication: | United States of America | ISSN: | 1077-8926 | Fields of Research (FoR) 2008: | 010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics) | Socio-Economic Objective (SEO) 2008: | 970101 Expanding Knowledge in the Mathematical Sciences | Peer Reviewed: | Yes | HERDC Category Description: | C1 Refereed Article in a Scholarly Journal | Publisher/associated links: | https://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r69 |
---|---|
Appears in Collections: | Journal Article School of Science and Technology |
Files in This Item:
File | Size | Format |
---|
Page view(s)
1,542
checked on Jun 16, 2024
Download(s)
4
checked on Jun 16, 2024
Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.