Arbitrary matricesM∈ Rm×n, randomly perturbed in an additive manner using a random matrixR∈ Rm×n, are shown to asymptotically almost surely satisfy the so-calledrobust null space property. Whilst insisting on an asymptotically optimal order of magnitude formrequired to attainunique reconstructionvia ℓ1-minimisation algorithms, our results track the level of arbitrariness allowed for the fixed seed matrixMas well as the degree of distributional irregularity allowed for the entries of the perturbing matrixR. Starting with sub-gaussian entries forR, our results culminate with these allowed to have substantially heavier tails than sub-exponential ones. Throughout this trajectory, two measures control the arbitrariness allowed forM; the first is ∥M∥∞ and the second is a localised notion of the Frobenius norm ofM(which depends on the sparsity of the signal being reconstructed). A key tool driving our proofs isMendelson’s small-ball method (Learning without concentration, J. ACM, Vol. 62, 2015).

We study Ramsey properties of randomly perturbed $3$-uniform hypergraphs. For~$t\geq 2$, write $\tilde K^{(3)}_t$ to denote the $3$-uniform {\it expanded} clique hypergraph obtained from the complete graph $K_t$ by expanding each of the edges of the latter with a new additional vertex. For an even integer $t\geq 4$, let~$M$ denote the asymmetric maximal density of the pair $(\tilde K^{(3)}_t,\tilde K^{(3)}_{t/2})$. We prove that adding a set~$F$ of random hyperedges satisfying $|F|\gg n^{3-1/M}$ to a given $n$-vertex $3$-uniform hypergraph~$H$ with non-vanishing edge density asymptotically almost surely results in a perturbed hypergraph enjoying the Ramsey property for $\tilde K^{(3)}_t$ and two colours. We conjecture that this result is asymptotically best possible with respect to the size of $F$ whenever $t\geq 6$ is even. The key tools of our proof are a new variant of the hypergraph regularity lemma accompanied with a \emph{tuple lemma} providing appropriate control over joint link graphs. Our variant combines the so called strong and the weak hypergraph regularity lemmata.

For two graphs $G$ and $H$, write $G \stackrel{\mathrm{rbw}}{\longrightarrow} H$ if $G$ has the property that every proper coloring of its edges yields a rainbow copy of $H$. We study the thresholds for such so-called anti-Ramsey properties in randomly perturbed dense graphs, which are unions of the form $G \cup \mathbb{G}(n,p)$, where $G$ is an $n$-vertex graph with edge-density at least $d$, and $d$ is a constant that does not depend on $n$. Our results in this paper, combined with our results in a companion paper, determine the threshold for the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} K_s$ for every $s$. In this paper, we show that for $s \geq 9$ the threshold is $n^{-1/m_2(K_{\left\lceil s/2 \right\rceil})}$; in fact, our $1$-statement is a supersaturation result. This turns out to (almost) be the threshold for $s=8$ as well, but for every $4 \leq s \leq 7$, the threshold is lower; see our companion paper for more details. Also in this paper, we determine that the threshold for the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} C_{2\ell - 1}$ is $n^{-2}$ for every $\ell \geq 2$; in particular, the threshold does not depend on the length of the cycle $C_{2\ell - 1}$. For even cycles, and in fact any fixed bipartite graph, no random edges are needed at all; that is, $G \stackrel{\mathrm{rbw}}{\longrightarrow} H$ always holds, whenever $G$ is as above and $H$ is bipartite.

Given an $n$-vertex graph $H$ with minimum degree at least $d n$ for some fixed $d > 0$, the distribution $H \cup \mathbb{G}(n,p)$ over the supergraphs of $H$ is referred to as a (random) perturbation of $H$. We consider the distribution of edge-colored graphs arising from assigning each edge of the random perturbation $H \cup \mathbb{G}(n,p)$ a color, chosen independently and uniformly at random from a set of colors of size $r := r(n)$. We prove that edge-colored graphs which are generated in this manner asymptotically almost surely admit rainbow Hamilton cycles whenever the edge-density of the random perturbation satisfies $p := p(n) \geq C/n$ for some fixed $C > 0$ and $r = (1 + o(1))n$. The number of colors used is clearly asymptotically best possible. In particular, this improves on a recent result of Anastos and Frieze [ J. Graph Theory, 92 (2019), pp. 405--414] in this regard. As an intermediate result, which may be of independent interest, we prove that randomly edge-colored sparse pseudorandom graphs asymptotically almost surely admit an almost spanning rainbow path.

We introduce and study a game variant of the classical spanning-tree problem. Our spanning-tree game is played between two players, min and max, who alternate turns in jointly constructing a spanning tree of a given connected weighted graph G. Starting with the empty graph, in each turn a player chooses an edge that does not close a cycle in the forest that has been generated so far and adds it to that forest. The game ends when the chosen edges form a spanning tree in G. The goal of min is to minimize the weight of the resulting spanning tree and the goal of max is to maximize it. A strategy for a player is a function that maps each forest in G to an edge that is not yet in the forest and does not close a cycle. We show that while in the classical setting a greedy approach is optimal, the game setting is more complicated: greedy strategies, namely ones that choose in each turn the lightest (min) or heaviest (max) legal edge, are not necessarily optimal, and calculating their values is NP-hard. We study the approximation ratio of greedy strategies. We show that while a greedy strategy for min guarantees nothing, the performance of a greedy strategy for max is satisfactory: it guarantees that the weight of the generated spanning tree is at least w(MST(G))/2, where w(MST(G)) is the weight of a maximum spanning tree in G, and its approximation ratio with respect to an optimal strategy for max is 1.5+1/w(MST(G)), assuming weights in [0,1]. We also show that these bounds are tight. Moreover, in a stochastic setting, where weights for the complete graph K_n are chosen at random from [0,1], the expected performance of greedy strategies is asymptotically optimal. Finally, we study some variants of the game and study an extension of our results to games on general matroids.

For a tree $T$ on $n$ vertices, we study the Maker-Breaker game, played on the edge set of the complete graph on $n$ vertices, which Maker wins as soon as the graph she builds contains a copy of $T$. We prove that if $T$ has bounded maximum degree and $n$ is sufficiently large, then Maker can win this game within $n+1$ moves. Moreover, we prove that Maker can build almost every tree on $n$ vertices in $n-1$ moves and provide nontrivial examples of families of trees which Maker cannot build in $n-1$ moves.

We analyze classical Maker-Breaker games played on the edge set of a randomly generated graph G.We consider the random graph process and analyze, for each of the properties "being spanning k-vertex-connected" , "admitting a perfect matching", and "being Hamiltonian", the first time when Maker starts having a winning strategy for building a graph possessing the target property (the so called hitting time).We prove that typically it happens precisely at the time the random graph process first reaches minimum degree 2k, 2 and 4, respectively, which is clearly optimal.The latter two statements settle conjectures of Stojaković and Szabó.We also consider a general-purpose game, the expander game, which is a main ingredient of our proofs and might be of an independent interest.

Let m and b be positive integers, and let F be a hypergraph. In an $(m,b)$ Maker-Breaker game F two players, called Maker and Breaker, take turns selecting previously unclaimed vertices of F. Maker selects m vertices per move, and Breaker selects b vertices per move. The game ends when every vertex has been claimed by one of the players. Maker wins if he claims all of the vertices of some hyperedge of F; otherwise Breaker wins. An $(m,b)$ Avoider-Enforcer game F is played in a similar way. The only difference is in the determination of the winner: Avoider loses if he claims all of the vertices of some hyperedge of F; otherwise Enforcer loses. In this paper we consider the Maker-Breaker and Avoider-Enforcer versions of the planarity game, the k-colorability game, and the $K_t$-minor game.