On the stability of some Erd\H{o}s--Ko--Rado type results

In this paper, we study the maximum degree in non-empty induced subgraphs of the Kneser graph $KG(n,k)$. One of the main results asserts that, for $k>k_0$ and $n>64k^2$, whenever a non-empty subgraph has $m\ge k{n-2\choose k-2}$ vertices, its maximum degree is at least $\frac 12(1-\frac {k^2}n) m - {n-2\choose k-2}\ge 0.49 m$. This bound is essentially best possible. One of the intermediate steps is to obtain structural results on non-empty subgraphs with small maximum degree...

For an $r$-uniform hypergraph $H$, let $f(H)$ be the minimum number of complete $r$-partite $r$-uniform subhypergraphs of $H$ whose edge sets partition the edge set of $H$. For a graph $G$, $f(G)$ is the bipartition number of $G$ which was introduced by Graham and Pollak in 1971. In 1988, Erd\H{o}s conjectured that if $G \in G(n,1/2)$, then with high probability $f(G)=n-\alpha(G)$, where $\alpha(G)$ is the independence number of $G$. This conjecture and related problems have ...

In this note, we investigate some properties of local Kneser graphs defined in [8]. In this regard, as a generalization of the Erd${\rm \ddot{o}}$s-Ko-Rado theorem, we characterize the maximum independent sets of local Kneser graphs. Next, we present an upper bound for their chromatic number.

A family of sets is intersecting if any two sets in the family intersect. Given a graph $G$ and an integer $r\geq 1$, let $\mathcal{I}^{(r)}(G)$ denote the family of independent sets of size $r$ of $G$. For a vertex $v$ of $G$, the family of independent sets of size $r$ that contain $v$ is called an $r$-star. Then $G$ is said to be $r$-EKR if no intersecting subfamily of $ \mathcal{I}^{(r)}(G)$ is bigger than the largest $r$-star. Let $n$ be a positive integer, and let $G$ co...

A Kneser graph $KG_{n,k}$ is a graph whose vertices are in one-to-one correspondence with $k$-element subsets of $[n],$ with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to Lov\'asz states that the chromatic number of a Kneser graph $KG_{n,k}$ is equal to $n-2k+2$. In this paper we study the chromatic number of a random subgraph of a Kneser graph $KG_{n,k}$ as $n$ grows. A random subgraph $KG_{n,k}(p)$ is obtained by inclu...

The Kneser graph ${\rm KG}_{n,k}$ is a graph whose vertex set is the family of all $k$-subsets of $[n]$ and two vertices are adjacent if their corresponding subsets are disjoint. The classical Erd\H{o}s-Ko-Rado theorem determines the cardinality and structure of a maximum induced $K_2$-free subgraph in ${\rm KG}_{n,k}$. As a generalization of the Erd\H{o}s-Ko-Rado theorem, Erd\H{o}s proposed a conjecture about the maximum order of an induced $K_{s+1}$-free subgraph of ${\rm K...

For integers $n \geq k \geq 1$, the {\em Kneser graph} $K(n, k)$ is the graph with vertex-set consisting of all the $k$-element subsets of $\{1,2,\ldots,n\}$, where two $k$-element sets are adjacent in $K(n,k)$ if they are disjoint. We show that if $(n,k,s) \in \mathbb{N}^3$ with $n > 10000 k s^5$ and $\mathcal{F}$ is set of vertices of $K(n,k)$ of size larger than $\{A \subset \{1,2,\ldots,n\}:\ |A|=k,\ A \cap \{1,2,\ldots,s\} \neq \varnothing\}$, then the subgraph of $K(n,k...

Given positive integers $n\ge 2k$, the {\it Kneser graph} $KG_{n,k}$ is a graph whose vertex set is the collection of all $k$-element subsets of the set $\{1,\ldots, n\}$, with edges connecting pairs of disjoint sets. One of the classical results in combinatorics, conjectured by Kneser and proved by Lov\'asz, states that the chromatic number of $KG_{n,k}$ is equal to $n-2k+2$. In this paper, we study the chromatic number of the {\it random Kneser graph} $KG_{n,k}(p)$, that is...

Let $G = (V,E)$ be a graph on $n$ vertices and $f: V\rightarrow [1,n]$ a one to one map of $V$ onto the integers $1$ through $n$. Let $dilation(f) =$ max$\{ |f(v) - f(w)|: vw\in E \}$. Define the {\it bandwidth} $B(G)$ of $G$ to be the minimum possible value of $dilation(f)$ over all such one to one maps $f$. Next define the {\it Kneser Graph} $K(n,r)$ to be the graph with vertex set $\binom{[n]}{r}$, the collection of $r$-subsets of an $n$ element set, and edge set $E = \{ v...

Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph Kneser(n,k) is the graph with vertex set $\binom{[n]}{k}$, such that two vertices are adjacent if they are disjoint. We determine, for large values of n with respect to k, the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erd\H{o}s-Ko-Rado Theorem (for large n with respect to k) when a number of disjoint pai...