We discuss the connection between the expansion of small sets in graphs, and
the Schatten norms of their adjacency matrix. In conjunction with a variant of
the Azuma inequality for uniformly smooth normed spaces, we deduce improved
bounds on the small set isoperimetry of Abelian Alon-Roichman random Cayley
graphs.

The {\em overlap number} of a finite $(d+1)$-uniform hypergraph $H$ is
defined as the largest constant $c(H)\in (0,1]$ such that no matter how we map
the vertices of $H$ into $\R^d$, there is a point covered by at least a
$c(H)$-fraction of the simplices induced by the images of its hyperedges.
In~\cite{Gro2}, motivated by the search for an analogue of the notion of graph
expansion for higher dimensional simplicial complexes, it was asked whether or
not there exists a sequence $\{H_n\}_{n=1}^\infty$ of arbitrarily large
$(d+1)$-uniform hypergraphs with bounded degree, for which $\inf_{n\ge

We introduce a randomized iterative fragmentation procedure for finite metric
spaces, which is guaranteed to result in a polynomially large subset that is
$D$-equivalent to an ultrametric, where $D\in (2,\infty)$ is a prescribed
target distortion. Since this procedure works for $D$ arbitrarily close to the
nonlinear Dvoretzky phase transition at distortion 2, we thus obtain a much
simpler probabilistic proof of the main result of Bartel, Linial, Mendel, and
Naor, answering a question from Mendel and Naor, and yielding the best known
bounds in the nonlinear Dvoretzky theorem.

Let $(X,d,\mu)$ be a metric measure space. For $\emptyset\neq R\subseteq
(0,\infty)$ consider the Hardy-Littlewood maximal operator $$ M_R f(x)
\stackrel{\mathrm{def}}{=} \sup_{r \in R} \frac{1}{\mu(B(x,r))} \int_{B(x,r)}
|f| d\mu.$$ We show that if there is an $n>1$ such that one has the
"microdoubling condition" $ \mu(B(x,(1+\frac{1}{n})r))\lesssim \mu(B(x,r)) $
for all $x\in X$ and $r>0$, then the weak $(1,1)$ norm of $M_R$ has the
following localization property: $$ \|M_R\|_{L_1(X) \to L_{1,\infty}(X)}\asymp
\sup_{r>0} \|M_{R\cap [r,nr]}\|_{L_1(X) \to L_{1,\infty}(X)}.

Given a finite regular graph G=(V,E) and a metric space (X,d_X), let
$gamma_+(G,X) denote the smallest constant $\gamma_+>0$ such that for all
f,g:V\to X we have:

\frac{1}{|V|^2}\sum_{x,y\in V} d_X(f(x),g(y))^2\le \frac{\gamma_+}{|E|}
\sum_{xy\in E} d_X(f(x),g(y))^2.