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

Two families $\mathcal{A}$ and $\mathcal{B}$, of $k$-subsets of an $n$-set, are {\em cross $t$-intersecting} if for every choice of subsets $A \in \mathcal{A}$ and $B \in \mathcal{B}$ we have $|A \cap B| \geq t$. We address the following conjectured cross $t$-intersecting version of the Erd\H os--Ko--Rado Theorem: For all $n \geq (t+1)(k-t+1)$ the maximum value of $|\mathcal{A}||\mathcal{B}|$ for two cross $t$-intersecting families $\mathcal{A}, \mathcal{B} \subset\binom{[n]}...

Fix integers $n \ge r \ge 2$. A clique partition of ${[n] \choose r}$ is a collection of proper subsets $A_1, A_2, \ldots, A_t \subset [n]$ such that $\bigcup_i{A_i \choose r}$ is a partition of ${[n] \choose r}$. Let $\cp(n,r)$ denote the minimum size of a clique partition of ${[n] \choose r}$. A classical theorem of de Bruijn and Erd\H os states that $\cp(n, 2) = n$. In this paper we study $\cp(n,r)$, and show in general that for each fixed $r \geq 3$, \[ \cp(n,r) \ge...

The generalized Kneser graph $K(n,k,t)$ for integers $k>t>0$ and $n>2k-t$ is the graph whose vertices are the $k$-subsets of $\{1,\dots,n\}$ with two vertices adjacent if and only if they share less than $t$ elements. We determine the treewidth of the generalized Kneser graphs $K(n,k,t)$ when $t\ge 2$ and $n$ is sufficiently large compared to $k$. The imposed bound on $n$ is a significant improvement of a previously known bound. One consequence of our result is the following....

Let $n,k,r$ be positive integers with $n \geq rk$ and $r \geq 2$. Consider a circle $C$ with~$n$ points~$1,\ldots,n$ in clockwise order. The $r$-stable \emph{interlacing graph} $\text{IG}_{n,k}^{(r)}$ is the graph with vertices corresponding to $k$-subsets $S$ of $\{1,...,n\}$ such that any two distinct points in~$S$ have distance at least~$r$ around the circle, and edges between~$k$-subsets $P$ and $Q$ if they \emph{interlace}: after removing the points in~$P$ from $C$, the ...

We prove that for a large family of product graphs, and for Kneser graphs $K(n,\alpha n)$ with fixed $\alpha <1/2$, the following holds. Any set of vertices that spans a small proportion of the edges in the graph can be made independent by removing a small proportion of the vertices of the graph. This allows us to strengthen the results of [DinurFR06] and [DinurF09], and show that any independent set in these graphs is almost contained in an independent set which depends on f...

Let r be a fixed constant and let H be an r-uniform, D-regular hypergraph on N vertices. Assume further that D > N^\epsilon for some \epsilon>0. Consider the random greedy algorithm for forming an independent set in H. An independent set is chosen at random by iteratively choosing vertices at random to be in the independent set. At each step we choose a vertex uniformly at random from the collection of vertices that could be added to the independent set (i.e. the collection o...

In this paper, we prove a generalization of a conjecture of Erd\"{o}s, about the chromatic number of certain Kneser-type hypergraphs. For integers $n,k,r,s$ with $n\ge rk$ and $2\le s\le r$, the $r$-uniform general Kneser hypergraph $\mbox{KG}^r_s(n,k)$, has all $k$-subsets of $\{1,\dots,n\}$ as the vertex set and all multi-sets $\{A_1,\dots, A_r\}$ of $k$-subsets with $s$-wise empty intersections as the edge set. The case $r=s=2$, was considers by Kneser \cite{K} in 1955, wh...

In a graph $G$, a geodesic between two vertices $x$ and $y$ is a shortest path connecting $x$ to $y$. A subset $S$ of the vertices of $G$ is in general position if no vertex of $S$ lies on any geodesic between two other vertices of $S$. The size of a largest set of vertices in general position is the general position number that we denote by $gp(G)$. Recently, Ghorbani et al, proved that for any $k$ if $n\ge k^3-k^2+2k-2$, then $gp(Kn_{n,k})=\binom{n-1}{k-1}$, where $Kn_{n,k}...

Two years ago, Conlon and Gowers, and Schacht proved general theorems that allow one to transfer a large class of extremal combinatorial results from the deterministic to the probabilistic setting. Even though the two papers solve the same set of long-standing open problems in probabilistic combinatorics, the methods used in them vary significantly and therefore yield results that are not comparable in certain aspects. The theorem of Schacht can be applied in a more general s...

We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In this survey we discuss some of them.