On "stability" in the Erd\H{o}s-Ko-Rado theorem

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.

We prove that the family of largest cuts in the binomial random graph exhibits the following stability property: If $1/n \ll p = 1-\Omega(1)$, then, with high probability, there is a set of $n - o(n)$ vertices that is partitioned in the same manner by all maximum cuts of $G_{n,p}$. Moreover, the analogous statement remains true when one replaces maximum cuts with nearly-maximum cuts. We then demonstrate how one can use this statement as a tool for showing that certain prope...

The Erd\H{o}s--Ko--Rado (EKR) theorem and its generalizations can be viewed as classifications of maximum independent sets in appropriately defined families of graphs, such as the Kneser graph $K(n,k)$. In this paper, we investigate the independence number of random spanning subraphs of two other families of graphs whose maximum independent sets satisfy an EKR-type characterization: the derangement graph on the set of permutations in $\mathrm{Sym}(n)$ and the derangement grap...

Computing the maximum size of an independent set in a graph is a famously hard combinatorial problem that has been well-studied for various classes of graphs. When it comes to random graphs, only the classical binomial random graph $G_{n,p}$ has been analysed and shown to have largest independent sets of size $\Theta(\log{n})$ w.h.p. This classical model does not capture any dependency structure between edges that can appear in real-world networks. We initiate study in this d...

Let $G$ be a graph on $n$ vertices of independence number $\alpha(G)$ such that every induced subgraph of $G$ on $n-k$ vertices has an independent set of size at least $\alpha(G) - \ell$. What is the largest possible $\alpha(G)$ in terms of $n$ for fixed $k$ and $\ell$? We show that $\alpha(G) \le n/2 + C_{k, \ell}$, which is sharp for $k-\ell \le 2$. We also use this result to determine new values of the Erd\H{o}s--Rogers function.

In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph $G$, each pair of vertices are joined by an edge with a probability $p$, where $p$ is a constant between $0$ and $1$. We show that, a maximum independent set in a random graph that contains $n$ vertices can be computed in expected computation time $2^{O(\log_{2}^{2}{n})}$. Using techniques based on enumeration, we develop an algorith...

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 ...

Given a graph G = (V,E), a vertex subset S is called t-stable (or t-dependent) if the subgraph G[S] induced on S has maximum degree at most t. The t-stability number of G is the maximum order of a t-stable set in G. We investigate the typical values that this parameter takes on a random graph on n vertices and edge probability equal to p. For any fixed 0 < p < 1 and fixed non-negative integer t, we show that, with probability tending to 1 as n grows, the t-stability number ta...

We study the weak $K_s$-saturation number of the Erd\H{o}s--R\'{e}nyi random graph $\mathbbmsl{G}(n, p)$, denoted by $\mathrm{wsat}(\mathbbmsl{G}(n, p), K_s)$, where $K_s$ is the complete graph on $s$ vertices. Kor\'{a}ndi and Sudakov in 2017 proved that the weak $K_s$-saturation number of $K_n$ is stable, in the sense that it remains the same after removing edges with constant probability. In this paper, we prove that there exists a threshold for this stability property and ...