A note on vertex Turán problems in the Kneser cube
Open Access
- 30 January 2026
- journal article
- research article
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 42 (1) , 17
Abstract
The Kneser cube $$Kn_n$$ has vertex set $$2^{[n]}$$ and two vertices $$F,F'$$ are joined by an edge if and only if $$F\cap F'=\emptyset $$ . For a fixed graph G , we are interested in the most number $$\textrm{vex}(n,G)$$ of vertices of $$Kn_n$$ that span a G -free subgraph in $$Kn_n$$ . We show that the asymptotics of $$\textrm{vex}(n,G)$$ is $$(1+o(1))2^{n-1}$$ for bipartite G and $$(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)$$ and $$2^n-\!\textrm{vex}(n,G)$$ in these two cases. In the case of bipartite G , we relate this problem to instances of the forbidden subposet problem.
Keywords
All Related Versions
Funding Information
- Nemzeti Kutatási és Technológiai Hivatal (FK132060)
- Nemzeti Kutatási és Technológiai Hivatal (KKP-133819)
This publication has 25 references indexed in Scilit:
- On a Generalization of a Result of KleitmanAnnals of Combinatorics, 2025
- The vertex Turán density in 3-ary n-cubesDiscrete Applied Mathematics, 2022
- Families of sets with no matchings of sizes 3 and 4European Journal of Combinatorics, 2019
- New inequalities for families without k pairwise disjoint membersJournal of Combinatorial Theory, Series A, 2018
- Progress on poset-free families of subsets2016
- Union-Intersecting Set SystemsGraphs and Combinatorics, 2014
- On crown-free families of subsetsJournal of Combinatorial Theory, Series A, 2014
- The History of Degenerate (Bipartite) Extremal Graph Problems2013
- Vertex Turán problems in the hypercubeJournal of Combinatorial Theory, Series A, 2010
- A simple proof of the Erdös-Chao Ko-Rado theoremJournal of Combinatorial Theory, Series B, 1972