A 0/1-polytope in \(\mathbb R^n\) is the convex hull of a subset of \(\{0,\, 1\}^n\). The graph of a polytope \(P\) is the graph whose vertices are the zero-dimensional faces of \(P\) and whose edges are the one-dimensional faces of \(P\). A conjecture of Mihail and Vazirani states that the edge expansion of the graph of every 0/1-polytope is at least one. We study a random version of the problem, where the polytope is generated by selecting vertices of \(\{0,\, 1\}^n\) independently at random with probability \(p \in (0; 1)\). Improving earlier results, we show that, for any \(p \in (0; 1)\), with high probability the edge expansion of the random 0/1-polytope is bounded from below by an absolute constant.

List-decodability of Reed-Solomon codes has re-ceived a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form$r=1-\varepsilon$for$\varepsilon$tending to zero. Our main result states that there exist Reed-Solomon codes with rate$\Omega(\varepsilon)$which are$(1-\varepsilon, O(1/\varepsilon)$-list-decodable, meaning that any Hamming ball of radius$1-\varepsilon$contains at most$O(1/\varepsilon)$codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.

In his seminal paper from 1952 Dirac showed that the complete graph on n ≥ 3 vertices remains Hamiltonian even if we allow an adversary to remove ⌊n/2⌋ edges touching each vertex. In 1960 Ghouila-Houri obtained an analogue statement for digraphs by showing that every directed graph on n ≥ 3 vertices with minimum in- and out-degree at least n/2 contains a directed Hamilton cycle. Both statements quantify the robustness of complete graphs (digraphs) with respect to the property of containing a Hamilton cycle. A natural way to generalize such results to arbitrary graphs (digraphs) is using the notion of local resilience. The local resilience of a graph (digraph) G with respect to a property is the maximum number r such that G has the property even if we allow an adversary to remove an r-fraction of (in- and out-going) edges touching each vertex. The theorems of Dirac and Ghouila-Houri state that the local resilience of the complete graph and digraph with respect to Hamiltonicity is 1/2. Recently, this statements have been generalized to random settings. Lee and Sudakov (2012) proved that the local resilience of a random graph with edge probability p = ω (log n/n) with respect to Hamiltonicity is 1/2 ± o(1). For random directed graphs, Hefetz, Steger and Sudakov (2014+) proved an analogue statement, but only for edge probability . In this paper we significantly improve their result to p = ω (log8 n/n), which is optimal up to the polylogarithmic factor.

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.