Semi-random processes involve an adaptive decision-maker, whose goal is to achieve some predetermined objective in an online randomized environment. In this paper, we consider a recently proposed semi-random graph process, defined as follows: we start with an empty graph on $n$ vertices, and in each round, the decision-maker, called Builder, receives a uniformly random vertex $v$, and must immediately (in an online manner) choose another vertex $u$, adding the edge $\{u,v\}$ to the graph. Builder's end goal is to make the constructed graph satisfy some predetermined monotone graph property. There are also natural offline and non-adaptive variants of this setting.

It was asked by $N$. Alon whether for every bounded-degree (spanning) graph $H$, Builder can construct a copy of $H$ with high probability in $O(n)$ rounds. We answer this question positively in a strong sense, showing that any graph with maximum degree $\Delta$ can be constructed with high probability in $(3\Delta/2+o(\Delta))n$ rounds, where the $o(\Delta)$ term tends to zero as $\Delta$ tends to infinity. This is tight (even for the offline case) up to a multiplicative factor of $3+o_{\Delta}(1)$. Furthermore, for the special case where $H$ is a forest of maximum degree $\Delta$, we show that $H$ can be constructed with high probability in $O(\log\Delta)n$ rounds. This is tight up to a multiplicative constant, even for the offline setting. Finally, we show a separation between adaptive and non-adaptive strategies, proving a lower bound of $\Omega(n\sqrt{\log n})$ on the number of rounds necessary to eliminate all isolated vertices w.h.p. using a non-adaptive strategy. This bound is tight, and in fact there are non-adaptive strategies for constructing a Hamilton cycle or a $K_r$-factor, which are successful w.h.p. within $O(n\sqrt{\log n})$ rounds.

Let $[n]:=\{1,\ldots,n\}$. The following conjecture was made by Aharoni and Howard [1]:

Conjecture. Let $n\ge s$ and $k$ be positive integers. If $\mathcal F_1,\ldots,\mathcal F_s\subset [n]^k$ satisfy $\min_{i}|\mathcal F_i|>(s-1)n^{k-1}$ then there exist $F_1\in\mathcal F_1,\ldots, F_s\in \mathcal F_s,$ such that $F_i\cap F_j = \emptyset$ for any $1\le i < j\le s$.

In their paper, Aharoni and Howard proved this conjecture for $k=2,3$. Then, Lu and Yu [3] proved it for $n>3(s-1)(k-1).$

Our main result is the proof of the conjecture for all $s>s_0.$ The proof relies on the idea that intersection of any family with a random matching is highly concentrated around its expectation. This idea was introduced by the second author in the paper [2] in the context of the Erdős Matching Conjecture.

[1] R. Aharoni and D. Howard, A Rainbow $r$-Partite Version of the Erdős—Ko—Rado Theorem, Comb. Probab. Comput. 26 (2017), N3, 321—337.

[2] P. Frankl, A. Kupavskii, The Erdős os Matching Conjecture and Concentration Inequalities, arXiv:1806.08855.

[3] H. Lu and X. Yu, On rainbow matchings for hypergraphs, SIAM J. Disrete Math. 32 (2018), N1, 382—393.

Various notions of dimension are important in many area of mathematics, and for graphs the Prague dimension was introduced in the late 1970s Nesetril, Pultr and Rodl.

We show that the Prague dimension of the binomial random graph $G(n,p)$ is typically of order $n/\log n$ for constant edge-probabilities $p$; this proves a conjecture of Furedi and Kantor.

One key ingredient of our proof is a randomized greedy edge-coloring algorithm, that allows us to bound the chromatic index of random subhypergraphs with large edge-uniformities.

For positive integers $d < k$ and $n$ divisible by $k$, let $m_{d}(k,n)$ be the minimum $d$-degree ensuring the existence of a perfect matching in a $k$-uniform hypergraph. In the graph case (where $k=2$), a classical theorem of Dirac says that $m_{1}(2,n)=\lceil n/2\rceil$. However, in general, our understanding of the values of $m_{d}(k,n)$ is still very limited, and it is an active topic of research to determine or approximate these values. In the first part of this talk, we discuss a new "transference" theorem for Dirac-type results relative to random hypergraphs. Specifically, we prove that a random $k$-uniform hypergraph $G$ with $n$ vertices and "not too small" edge probability $p$ typically has the property that every spanning subgraph with minimum $d$-degree at least $(1+\varepsilon)m_{d}(k,n)p$ has a perfect matching. One interesting aspect of our proof is a "non-constructive" application of the absorbing method, which allows us to prove a bound in terms of $m_{d}(k,n)$ without actually knowing its value.

The ideas in our work are quite powerful and can be applied to other problems: in the second part of this talk we highlight a recent application of these ideas to random designs, proving that a random Steiner triple system typically admits a decomposition of almost all its triples into perfect matchings (that is to say, it is almost resolvable).

Recall that for an integer $j$, a $j$-independent set in a hypergraph $H=(V,E)$ is a subset $W\subset V$ such that for every edge $e\in E: |e\cap W| \leqslant j$. A $j$-proper coloring of $H=(V,E)$ is a partition of the vertex set $V$ of $H$ into disjoint union of $j$-independent sets, so called colors. The $j$-chromatic number $\chi_j(H)$ of $H$ is the minimal number of colors needed for a $j$-proper coloring of $H$.

We will talk about our latest results on colorings of the k-uniform random hypergraph $H(n,k,p)$. We are interested in asymptotic properties of $H(n,k,p)$ to have its $j$-chromatic number equal to some fixed number $r$. By asymptotic properties of $H(n,k,p)$ we consider $n$ as tending to infinity, while $k$ and $r$ are kept constant.

It can be shown that the previously mentioned property of random hypergraph has a sharp threshold. For the classic case of $(k-1)$-chromatic number, upper and lower bounds for that threshold were investigated by different researchers. It should be also mentioned that the gap between these bounds in terms of the parameter $c=p{n\choose k}/n$ has a bounded order $O_k(1)$.

We are going to present the results from our last series of works where we found very tight bounds for the case of arbitrary $r$ and $1 < k-j=o(k^{1/4})$.

How many edges do we need in order to construct a $k$-uniform hypergraph which is not two-colorable? This number, denoted by $m(k)$, has been intensively studied since its introduction by Erd\H{o}s and Hajnal in 1961. As a result, the lower bounds have been improved a number of times and nowadays we know that $m(k)=\Omega(\sqrt{k/\log(k)}\;2^k)$ (Radhakrishnan and Srinivasan 2000). The story of the upper bounds is much shorter. Bound $m(k)= O(k^2 \;2^k)$, obtained by Erdős in 1964, has not been improved since.

We are going to discuss what insights can be gained from considering analogous problem for non-uniform hypergraphs. We focus on an interesting class of bi-uniform hypergraphs, i.e. hypergraphs in which there are only two allowed sizes of edges. On the other hand, having only two sizes of edges eliminates a lot of technical difficulties.