On Erd\H{o}s-Ko-Rado for random hypergraphs II

For a hypergraph $H$, let $q(H)$ denote the expected number of monochromatic edges when the color of each vertex in $H$ is sampled uniformly at random from the set of size 2. Let $s_{\min}(H)$ denote the minimum size of an edge in $H$. Erd\H{o}s asked in 1963 whether there exists an unbounded function $g(k)$ such that any hypergraph $H$ with $s_{\min}(H) \geq k$ and $q(H) \leq g(k)$ is two colorable. Beck in 1978 answered this question in the affirmative for a function $g(k) ...

The upper tail problem in a random graph asks to estimate the probability that the number of copies of some fixed subgraph in an Erd\H{o}s--R\'enyi random graph exceeds its expectation by some constant factor. There has been much exciting recent progress on this problem. We study the corresponding problem for hypergraphs, for which less is known about the large deviation rate. We present new phenomena in upper tail large deviations for sparse random hypergraphs that are not...

We study the algorithmic task of finding large independent sets in Erdos-Renyi $r$-uniform hypergraphs on $n$ vertices having average degree $d$. Krivelevich and Sudakov showed that the maximum independent set has density $\left(\frac{r\log d}{(r-1)d}\right)^{1/(r-1)}$. We show that the class of low-degree polynomial algorithms can find independent sets of density $\left(\frac{\log d}{(r-1)d}\right)^{1/(r-1)}$ but no larger. This extends and generalizes earlier results of Gam...

Answering in a strong form a question posed by Bollob\'as and Scott, in this paper we determine the discrepancy between two random k-uniform hypergraphs, up to a constant factor depending solely on k.

In 1961 Erd\H{o}s and Hajnal introduced the quantity $m(n)$ as the minimum number of edges in an $n$-uniform hypergraph with chromatic number at least 3. The best known lower and upper bounds for $ m(n) $ are $ c_1 \sqrt{\frac{n}{\ln n}} 2^n$ and $c_2 n^2 2^n$ respectively. The lower bound is due to Radhakrishnan and Srinivasan (see \cite{RS}). A natural generalization for $ m(n) $ is the quantity $ m(n,r) $, which is the minimum number of edges in an $n$-uniform hypergraph w...

We use an algebraic method to prove a degree version of the celebrated Erd\H os-Ko-Rado theorem: given $n>2k$, every intersecting $k$-uniform hypergraph $H$ on $n$ vertices contains a vertex that lies on at most $\binom{n-2}{k-2}$ edges. This result can be viewed as a special case of the degree version of a well-known conjecture of Erd\H{o}s on hypergraph matchings. Improving the work of Bollob\'as, Daykin, and Erd\H os from 1976, we show that given integers $n, k, s$ with $n...

A 2-coloring of a hypergraph is a mapping from its vertices to a set of two colors such that no edge is monochromatic. Let $H_k(n,m)$ be a random $k$-uniform hypergraph on $n$ vertices formed by picking $m$ edges uniformly, independently and with replacement. It is easy to show that if $r \geq r_c = 2^{k-1} \ln 2 - (\ln 2) /2$, then with high probability $H_k(n,m=rn)$ is not 2-colorable. We complement this observation by proving that if $r \leq r_c - 1$ then with high probabi...

The work deals with the threshold probablity for r-colorability in the binomial model H(n,k,p) of a random k-uniform hypergraph. We prove a lower bound for this threshold which improves the previously known results in the wide range of the parameters r=r(n) and k=k(n).

For all integers $n \geq k > d \geq 1$, let $m_{d}(k,n)$ be the minimum integer $D \geq 0$ such that every $k$-uniform $n$-vertex hypergraph $\mathcal H$ with minimum $d$-degree $\delta_{d}(\mathcal H)$ at least $D$ has an optimal matching. For every fixed integer $k \geq 3$, we show that for $n \in k \mathbb{N}$ and $p = \Omega(n^{-k+1} \log n)$, if $\mathcal H$ is an $n$-vertex $k$-uniform hypergraph with $\delta_{k-1}(\mathcal H) \geq m_{k-1}(k,n)$, then a.a.s.\ its $p$-ra...

Let $K^r_n$ be the complete $r$-uniform hypergraph on $n$ vertices, that is, the hypergraph whose vertex set is $[n]:=\{1,2,...,n\}$ and whose edge set is $\binom{[n]}{r}$. We form $G^r(n,p)$ by retaining each edge of $K^r_n$ independently with probability $p$. An $r$-uniform hypergraph $H\subseteq G$ is $F$-saturated if $H$ does not contain any copy of $F$, but any missing edge of $H$ in $G$ creates a copy of $F$. Furthermore, we say that $H$ is weakly $F$-saturated in $G$...