Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Maximal flat antichains of minimum weight. | Maximal flat antichains of minimum weight Martin Gruttmiiller Hochschule fur Technik Wirtschaft und Kultur Leipzig Fakultat Informatik Mathematik und Naturwissenschaften Gustav-Freytag-Str. 42 a 04277 Leipzig Germany gruettmueller@ Sven Hartmann Technische Universitat Clausthal Institut fuur Informatik Julius-Albert-Str. 4 38678 Clausthal-Zellerfeld Germany Thomas Kalinowski Universitat Rostock Institut fuur Mathematik Universitatsplatz 1 18051 Rostock Germany Uwe Leck University of Wisconsin-Superior Dept. of Mathematics and Computer Science Belknap Catlin POB 2000 Superior WI 54880 USA Ian T. Roberts Charles Darwin University School of Engineering and IT Darwin 0909 Australia Submitted Jun 25 2005 Accepted May 22 2009 Published May 29 2009 Mathematics Subject Classification 05D05 06A07 Abstract We study maximal families A of subsets of n 1 2 . n such that A contains only pairs and triples and A c B for all A B c A . 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 ws n2 8 o n2 for 3 n w3 w2 A A n 2. For A 2 our problem is equivalent to the 6 3 -problem of Ruzsa and Szemeredi and by a result of theirs it follows that min w A w2n2 2 o n2 . THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R69 1 1 Introduction Let n 2 be an integer and n 1 2 . n . By 2 n we denote the family of all subsets of n and by n the family of all k-subsets of n . A family A 2 n is an antichain if A B for all A
