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.

The main paradigm of smoothed analysis on graphs suggests that for any large graph $G$ in a certain class of graphs, perturbing slightly the edge set of $G$ at random (usually adding few random edges to $G$) typically results in a graph having much “nicer” properties. In this work, we study smoothed analysis on trees or, equivalently, on connected graphs. Given an $n$-vertex connected graph $G$, form a random supergraph $G^*$ of $G$ by turning every pair of vertices of $G$ into an edge with probability $\frac{\varepsilon}{n}$, where $\varepsilon$ is a small positive constant. This perturbation model has been studied previously in several contexts, including smoothed analysis, small world networks, and combinatorics. Connected graphs can be bad expanders, can have a very large diameter, and can possibly contain no long paths. In contrast, we show that if $G$ is an $n$-vertex connected graph, then typically $G^*$ has edge expansion $\Omega(\frac{1}{\log n})$, diameter $O(\log n)$, and vertex expansion $\Omega(\frac{1}{\log n})$ and contains a path of length $\Omega(n)$, where for the last two properties we additionally assume that $G$ has bounded maximum degree. Moreover, we show that if $G$ has bounded degeneracy, then typically the mixing time of the lazy random walk on $G^*$ is $O(\log^2 n)$. All these results are asymptotically tight.

The main paradigm of smoothed analysis on graphs suggests that for any large graph G in a certain class of graphs, perturbing slightly the edges of G at random (usually adding few random edges to G) typically results in a graph having much "nicer" properties. In this work we study smoothed analysis on trees or, equivalently, on connected graphs. Given an n-vertex connected graph G, form a random supergraph of G* of G by turning every pair of vertices of G into an edge with probability epsilon/n, where epsilon is a small positive constant. This perturbation model has been studied previously in several contexts, including smoothed analysis, small world networks, and combinatorics. Connected graphs can be bad expanders, can have very large diameter, and possibly contain no long paths. In contrast, we show that if G is an n-vertex connected graph then typically G* has edge expansion Omega(1/(log n)), diameter O(log n), vertex expansion Omega(1/(log n)), and contains a path of length Omega(n), where for the last two properties we additionally assume that G has bounded maximum degree. Moreover, we show that if G has bounded degeneracy, then typically the mixing time of the lazy random walk on G* is O(log^2(n)). All these results are asymptotically tight.

Given a class of graphs F, we say that a graph G is universal for F, or F-universal, if every H ∊ F is contained in G as a subgraph. The construction of sparse universal graphs for various families F has received a considerable amount of attention. One is particularly interested in tight F-universal graphs, i.e., graphs whose number of vertices is equal to the largest number of vertices in a graph from F. Arguably, the most studied case is that when F is some class of trees. Given integers n and Δ, we denote by T(n, Δ) the class of all n-vertex trees with maximum degree at most Δ. In this work, we show that every n-vertex graph satisfying certain natural expansion properties is T(n, Δ)-universal or, in other words, contains every spanning tree of maximum degree at most Δ. Our methods also apply to the case when Δ is some function of n. The result has a few very interesting implications. Most importantly, since random graphs are known to be good expanders, we obtain that the random graph G(n, p) is asymptotically almost surely (a.a.s.) universal for the class of all bounded degree spanning (that is, n-vertex) trees provided that p ≥ cn−1/3 log n where c > 0 is a constant. Moreover, a corresponding result holds for the random regular graph of degree pn. In fact, we show that if Δ satisfies log n ≤ Δ ≤ n1/3, then the random graph G(n, p) with p ≥ cΔn−1/3 log n and the random r-regular n-vertex graph with r ≥ cΔn2/3 log n are a.a.s. universal for T(n, Δ). Another interesting consequence is the existence of locally sparse n-vertex graphs that are universal for T(n, Δ). For Δ ∊ O(1), we show that one can (randomly) construct n-vertex T(n, Δ)-universal graphs with clique number at most five. This complements the construction of Bhatt, Chung, Leighton, and Rosenberg (1989), whose T(n, Δ)-universal graphs with merely O(n) edges contain large cliques of size Ω(Δ). We also derive some lower bounds and show that there exist very good expanders which are not universal for T(n, Δ). In particular, we see that there are expanders of minimum degree Ω(n/log n) which are not T(n, c√n)-universal. Finally, we show robustness of random graphs with respect to being universal for T(n, Δ) in the context of the Maker-Breaker tree-universality game.

We prove that there exists a positive constant $\varepsilon$ such that if $\log n / n \leq p \leq n^{-1+\varepsilon}$, then asymptotically almost surely the random graph $G \sim G(n,p)$ contains a collection of $\lfloor \delta(G)/2 \rfloor$ edge-disjoint Hamilton cycles.

A graph is called H-free if it contains no copy of H. Let $\mathrm{ex}(n,H)$ denote the Turán number for H, i.e., the maximum number of edges that an n-vertex H-free graph may have. An old result of Kleitman and Winston states that there are $2^{O(\mathrm{ex}(n,C_4))}$ $C_4$-free graphs on n vertices. Füredi showed that almost all $C_4$-free graphs of order n have at least $c\,\mathrm{ex}(n,C_4)$ edges for some positive constant c. We prove that there is a positive constant $\varepsilon$ such that almost all $C_4$-free graphs have at most $(1-\varepsilon)\,\mathrm{ex}(n,C_4)$ edges. This resolves a conjecture of Balogh, Bollobás, and Simonovits for the 4-cycle.