The toughness conjecture for Kneser graphs
Statement
Let and be natural numbers with . The vertex set of the Kneser graph is , with two vertices adjacent exactly when they are disjoint. For a connected graph , define its toughness by
where the minimum is over vertex cuts and is the number of remaining components. A maximum independent set is an independent set of largest possible size.
The toughness conjecture for Kneser graphs. If and , then
Moreover, if a vertex subset satisfies
then is the complement of a maximum independent set in .
The result is known for for all , and for when is sufficiently large as a function of . The conjecture asks for the remaining range and .
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.