Publication

On the Size of K-Cross-Free Families

János Pach, Andrei Kupavskii, Istvan Tomon
2019
Journal Articles

Résumé

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.

Source officielle

https://infoscience.epfl.ch/entities/publication/c653e1b1-313e-42f8-b57d-b09f5bf845ec

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

On the Size of K-Cross-Free Families

Chattez avec Graph Search

Additive and geometric transversality of fractal sets in the integers

Acceleration of graph pattern mining and applications to financial crime

Chung-type law of the iterated logarithm and exact moduli of continuity for a class of anisotropic Gaussian random fields