Publication

Forbidden induced subposets of given height

Istvan Tomon
2019
Article
Résumé

Let P be a partially ordered set. The function La* (n, P) denotes the size of the largest family F subset of 2([n]) that does not contain an induced copy of P. It was proved by Methuku and Palvolgyi that there exists a constant C-P (depending only on P) such that La*(n,P) < C-P(left perpendicular n/2 right perpendicular n). However, the order of the constant C-P following from their proof is typically exponential in vertical bar P vertical bar. Here, we show that if the height of the poset is constant, this can be improved. We show that for every positive integer h there exists a constant c(h) such that if P has height at most h, then La* (n, P) = 2 vertical bar P vertical bar, then vertical bar F vertical bar

À 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.