PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
February 2, 2026Graphs and Combinatorics0 citationsOpen Access

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

View Full Paper
DGDániel GerbnerBPBalázs Patkós

Key Points

  • The aim is to determine the maximum number of vertices in the Kneser cube that span a G-free subgraph.
  • Analyzed the structure of Kneser cubes and their vertex set.
  • Calculated asymptotic behavior of vex(n,G) for various types of graphs.
  • Considered bipartite graphs and their chromatic number.
  • For bipartite G, vex(n,G) asymptotically equals (1+o(1))2^(n-1).
  • For graphs with chromatic number at least 3, vex(n,G) asymptotically equals (1-o(1))2^n.
  • Determined the order of magnitude of 2^(n-1) - vex(n,G).

Abstract

Abstract The Kneser cube Knₙ 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 F'= F ∩ F ′ = ∅. For a fixed graph G, we are interested in the most number vex (n, G) vex (n, G) of vertices of Knₙ K n n that span a G -free subgraph in Knₙ K n n. We show that the asymptotics of 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ⁿ (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-\!vex (n, G) 2 n - 1 - vex (n, <mm

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Gerbner et al. (2026) studied this question.

synapsesocial.com/papers/6980feeac1c9540dea811657https://doi.org/10.1007/s00373-026-03013-z
Ask AI
Helpful
Bookmark
Share
View Full Paper