A note on vertex Turán problems in the Kneser cube

Gerbner, Dániel and Patkós, Balázs (2026) A note on vertex Turán problems in the Kneser cube. GRAPHS AND COMBINATORICS, 42 (1). No. 17. ISSN 0911-0119

Preview

Text s00373-026-03013-z.pdf - Published Version Download (246kB) | Preview

Abstract

The Kneser cube Kn_n K n n has vertex set 2^{[n]} 2 [ n ] and two vertices F,F' F , F ′ are joined by an edge if and only if F\cap F'=\emptyset F ∩ F ′ = ∅ . For a fixed graph G , we are interested in the most number \textrm{vex}(n,G) vex ( n , G ) of vertices of Kn_n K n n that span a G -free subgraph in Kn_n K n n . We show that the asymptotics of \textrm{vex}(n,G) vex ( n , G ) is (1+o(1))2^{n-1} ( 1 + o ( 1 ) ) 2 n - 1 for bipartite G and (1-o(1))2^n ( 1 - o ( 1 ) ) 2 n for graphs with chromatic number at least 3. We also obtain results on the order of magnitude of 2^{n-1}-\!\textrm{vex}(n,G) 2 n - 1 - vex ( n , G ) and 2^n-\!\textrm{vex}(n,G) 2 n - vex ( n , G ) in these two cases. In the case of bipartite G , we relate this problem to instances of the forbidden subposet problem.

Actions (login required)

Edit Item