Explains how the maximum bisection value of sparse Erdos-Renyi graphs with asymptotically large average degree is related to the SK model from spin glasses.
The Matrix-Tree theorem connects the number of spanning trees in a graph to the eigenvalues of the graph Laplacian. Combined with the theory of local convergence of graphs this allows us to enumerate, up to exponential order terms, the number of spanning trees in various sequences of large graphs. We can computer, for example, the number of spanning trees in typical regular graphs.
The Hausdorff-Young inequality states that for 1 < p < 2, the Fourier transform of an L^p function lies in L^q where q is the Holder dual of p. How small is the image of L^p in L^q under the Fourier transform? Motivated by these questions the Tomas- Stein restriction theorem states that for p in a certain range, the Fourier transform of an L^p function in R^n lies in L^2 of the (n-1)-sphere. This note contains a proof of this theorem along with an application to Schrodinger's equation and discussion on the connection between restriction problems and the Kakeya conjecture.
Klaus Roth proved in the 1950s that any sufficiently large subset of the the first N natural numbers contains a three term arithmetic progression. Since then arithmetic problems of this nature have seen remarkable progress with important tools developed through combinatorics, ergodic theory, harmonic analysis and number theory. This note provides Roth's Fourier analytic proof of the theorem.
Sub-optimality of local algorithms for some combinatorial optimization problems on basic models of sparese random graphs.