Given a
k
-uniform hypergraph ℋ and sufficiently large
m
≫
m
0
(ℋ), we show that an m-element set
I
⊆
V
(ℋ), chosen uniformly at random, with probability 1 −
e−
ω
(
m
)
is either not independent or ...is contained in an almost-independent set in ℋ which, crucially, can be constructed from carefully chosen
o
(
m
) vertices of
I
. As a corollary, this implies that if the largest almost-independent set in ℋ is of size
o
(
v
(ℋ)) then
I
itself is an independent set with probability
e
−ω
(
m
)
. More generally,
I
is very likely to inherit structural properties of almost-independent sets in ℋ.
The value
m
0
(ℋ) coincides with that for which Janson’s inequality gives that
I
is independent with probability at most
e
−
Θ
(
m
0
)
. On the one hand, our result is a significant strengthening of Janson’s inequality in the range
m
≫
m
0
. On the other hand, it can be seen as a probabilistic variant of hypergraph container theorems, developed by Balogh, Morris and Samotij and, independently, by Saxton and Thomason. While being strictly weaker than the original container theorems in the sense that it does not apply to all independent sets of size
m
, it is nonetheless sufficient for many applications and admits a short proof using probabilistic ideas.
We consider the following matching-based routing problem. Initially, each vertex
v
of a connected graph
G
is occupied by a pebble which has a unique destination
π
(
v
)
. In each round the pebbles ...across the edges of a selected matching in
G
are swapped, and the goal is to route each pebble to its destination vertex in as few rounds as possible. We show that if
G
is a sufficiently strong
d
-regular spectral expander then any permutation
π
can be achieved in
O
(
log
n
)
rounds. This is optimal for constant
d
and resolves a problem of Alon et al. (SIAM J Discret Math 7:516–530, 1994).
Estimating the probability that the Erdős-Rényi random graph Gn,m is H-free, for a fixed graph H, is one of the fundamental problems in random graph theory. If H is non-bipartite and m is such that ...each edge of Gn,m belongs to a copy of H′ for every H′⊆H, in expectation, then it is known that Gn,m is H-free with probability exp(−Θ(m)). The KŁR conjecture, slightly rephrased, states that if we further condition on uniform edge distribution, the archetypal property of random graphs, the probability of being H-free becomes superexponentially small in the number of edges. While being interesting on its own, the conjecture has received significant attention due to its connection with the sparse regularity lemma, and the many results in random graphs that follow. It was proven by Balogh, Morris, and Samotij and, independently, by Saxton and Thomason, as one of the first applications of the hypergraph containers method. We give a new direct proof using induction.
Triangle‐factors in pseudorandom graphs Nenadov, Rajko
The Bulletin of the London Mathematical Society,
June 2019, 2019-06-00, Letnik:
51, Številka:
3
Journal Article
Recenzirano
We show that if the second eigenvalue λ of a d‐regular graph G on n∈3Z vertices is at most εd2/(nlogn), for a small constant ε>0, then G contains a triangle‐factor. The bound on λ is at most an ...O(logn) factor away from the best possible one: Krivelevich, Sudakov and Szabó, extending a construction of Alon, showed that for every function d=d(n) such that Ω(n2/3)⩽d⩽n and infinitely many n∈N, there exists a d‐regular triangle‐free graph G with Θ(n) vertices and λ=Ω(d2/n).
We prove that every graph of minimum degree d contains a spanning forest in which every component is a star of size at least d−O˜(d1/4). This improves a result of Alon and Wormald and is optimal up ...to the lower order term.
In this paper we give a short proof of the Random Ramsey Theorem of Rödl and Ruciński: for any graph F which contains a cycle and r ≥ 2, there exist constants c, C > 0 such that
$$
\begin{equation*}
...\PrG_{n,p} \rightarrow (F)_r^e =
\begin{cases}
1-o(1) &p\ge Cn^{-1/m_2(F)},\\
o(1) &p\le cn^{-1/m_2(F)},
\end{cases}
\end{equation*}
$$
where
$$
\begin{equation*}
m_2(F) = \max_{J\subseteq F, v_J\ge 2} \frac{e_J-1}{v_J-2}.
\end{equation*}
$$
The proof of the 1-statement is based on the recent beautiful hypergraph container theorems by Saxton and Thomason, and Balogh, Morris and Samotij. The proof of the 0-statement is elementary.
Abstract
We show that if $G$ is a graph on $n$ vertices, with all degrees comparable to some $d = d(n)$, and without a sparse cut, for a suitably chosen notion of sparseness, then it contains a ...complete minor of order $$\begin{equation*} \Omega\left( \sqrt{\frac{n d}{\log d}} \right). \end{equation*}$$As a corollary we determine the order of a largest complete minor one can guarantee in $d$-regular graphs for which the 2nd largest eigenvalue is bounded away from $d/2$, in $(d/n, o(d))$-jumbled graphs, and in random $d$-regular graphs, for almost all $d = d(n)$.
Let r≥4 be an integer and consider the following game on the complete graph Kn for n∈rZ: Two players, Maker and Breaker, alternately claim previously unclaimed edges of Kn such that in each turn ...Maker claims one and Breaker claims b∈N edges. Maker wins if her graph contains a Kr-factor, that is a collection of n/r vertex-disjoint copies of Kr, and Breaker wins otherwise. In other words, we consider a b-biased Kr-factor Maker–Breaker game. We show that the threshold bias for this game is of order n2/(r+2). This makes a step towards determining the threshold bias for making bounded-degree spanning graphs and extends a result of Allen et al. who resolved the case r∈{3,4} up to a logarithmic factor.
A celebrated result of Rödl and Ruciński states that for every graph
$F$
, which is not a forest of stars and paths of length 3, and fixed number of colours
$r\geqslant 2$
there exist positive ...constants
$c,C$
such that for
$p\leqslant cn^{-1/m_{2}(F)}$
the probability that every colouring of the edges of the random graph
$G(n,p)$
contains a monochromatic copy of
$F$
is
$o(1)$
(the ‘0-statement’), while for
$p\geqslant Cn^{-1/m_{2}(F)}$
it is
$1-o(1)$
(the ‘1-statement’). Here
$m_{2}(F)$
denotes the 2-density of
$F$
. On the other hand, the case where
$F$
is a forest of stars has a coarse threshold which is determined by the appearance of a certain small subgraph in
$G(n,p)$
. Recently, the natural extension of the 1-statement of this theorem to
$k$
-uniform hypergraphs was proved by Conlon and Gowers and, independently, by Friedgut, Rödl and Schacht. In particular, they showed an upper bound of order
$n^{-1/m_{k}(F)}$
for the 1-statement, where
$m_{k}(F)$
denotes the
$k$
-density of
$F$
. Similarly as in the graph case, it is known that the threshold for star-like hypergraphs is given by the appearance of small subgraphs. In this paper we show that another type of threshold exists if
$k\geqslant 4$
: there are
$k$
-uniform hypergraphs for which the threshold is determined by the asymmetric Ramsey problem in which a different hypergraph has to be avoided in each colour class. Along the way we obtain a general bound on the 1-statement for asymmetric Ramsey properties in random hypergraphs. This extends the work of Kohayakawa and Kreuter, and of Kohayakawa, Schacht and Spöhel who showed a similar result in the graph case. We prove the corresponding 0-statement for hypergraphs satisfying certain balancedness conditions.
PDF
