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.

A matching in a bipartite graph with parts X and Y is called envy-free if no unmatched vertex in X is a adjacent to a matched vertex in Y. Every perfect matching is envy-free, but envy-free matchings exist even when perfect matchings do not. We prove that every bipartite graph has a unique partition such that all envy-free matchings are contained in one of the partition sets. Using this structural theorem, we provide a polynomial-time algorithm for finding an envy-free matching of maximum cardinality. For edge-weighted bipartite graphs, we provide a polynomial-time algorithm for finding a maximum-cardinality envy-free matching of minimum total weight. We show how envy-free matchings can be used in various fair division problems with either continuous resources ("cakes") or discrete ones. In particular, we propose a symmetric algorithm for proportional cake-cutting, an algorithm for 1-out-of-(2n-2) maximin-share allocation of discrete goods, and an algorithm for 1-out-of-floor(2n/3) maximin-share allocation of discrete bads among n agents.

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.

Given a dense subset $A$ of the first $n$ positive integers, we provide a short proof showing that for $p=\omega(n^{-2/3}),$ the so-called randomly perturbed set $A \cup [n]_p$ a.a.s. has the property that any 2-coloring of it has a monochromatic Schur triple, i.e., a triple of the form $(a,b,a+b)$. This result is optimal since there are dense sets $A$, for which $A\cup [n]_p$ does not possess this property for $p=o(n^{-2/3})$.