Loading...
research article
On the Size of K-Cross-Free Families
February 1, 2019
Two subsets A,B of an n-element ground set X are said to be crossing, if none of the four sets AB, A\B, B\A and X(AB) are empty. It was conjectured by Karzanov and Lomonosov forty years ago that if a family F of subsets of X does not contain k pairwise crossing elements, then |F|=O(kn). For k=2 and 3, the conjecture is true, but for larger values of k the best known upper bound, due to Lomonosov, is |F|=O(knlogn). In this paper, we improve this bound for large n by showing that |F|=O-k(nlogn) holds, where log denotes the iterated logarithm function.
Type
research article
Web of Science ID
WOS:000463671400007
Authors
Publication date
2019-02-01
Publisher
Published in
Volume
39
Issue
1
Start page
153
End page
164
Subjects
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
April 17, 2019
Use this identifier to reference this record