We initiate a statistical study of Kalai’s exterior algebraic shifting, focusing on concentration phenomena for random triangulations of a fixed space. First, for a uniform n-vertex refinement of any given graph G, we show that asymptotically almost-surely (a.a.s.) its exterior algebraic shifting is an explicit shifted graph depending only on n and the Betti numbers of G. Next, for any given compact connected Riemannian surface S, sample n points independently at random according to the volume measure, and consider the resulted a.a.s. unique Delaunay triangulation. We prove that a.a.s. its exterior algebraic shifting is an explicit shifted complex depending only on n and the Euler genus of S, and in particular is area-rigid. In both results the expected shifted complex is a homology lex-segment complex, a notion we define combinatorially and characterize numerically à la Björner-Kalai. As a tool to prove the result on surfaces, we prove a universality result on edge contractions: for every fixed surface triangulation K, every dense enough point set in the surface yields a Delaunay triangulation that edge contracts to K.

A layout of a graph G is an injective function f : V(G) → ℤ, and the bandwidth of a layout f is (G,f) = maxuv ∈ E(G) |f(u) − f(v)|. The bandwidth (G) of G is the minimum bandwidth of a layout of G. Computing the bandwidth of a graph is a notoriously hard problem: assuming P ≠ NP there is no polynomial time algorithm, even on very restricted classes of trees [Monien, SIAM Journal on Algebraic Discrete Methods, 1986], and no constant factor approximation, even on trees [Dubey et al., JCSS 2011]. Assuming the Exponential Time Hypothesis there is no algorithm with running time f(k)no(k) to determine whether an input graph has bandwidth at most k, even on very restricted classes of trees [Dregi and Lokshtanov, ICALP 2014].

We present some enumerative and structural results for flag homology spheres. For a flag homology sphere $\Delta$, we show that its $\gamma$-vector $\gamma^\Delta{\,=\,}(1,\gamma_1,\gamma_2,\ldots)$ satisfies: $\gamma_j{\,=\,}0$ for all $j>\gamma_1$, $\gamma_2\leq\binom{\gamma_1}{2}$, $\gamma_{\gamma_1}\in\{0,1\}$, and $\gamma_{\gamma_1-1}\in\{0,1,2,\gamma_1\}$, supporting a conjecture of Nevo and Petersen. Further we characterize the possible structures for $\Delta$ in extremal cases. As an application, the techniques used produce infinitely many $f$-vectors of flag balanced simplicial complexes that are not $\gamma$-vectors of flag homology spheres (of any dimension); these are the first examples of this kind. In addition, we prove a flag analog of Perles' 1970 theorem on $k$-skeleta of polytopes with “few” vertices, specifically, the number of combinatorial types of $k$-skeleta of flag homology spheres with $\gamma_1\leq b$ of any given dimension, is bounded independently of the dimension.

A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if the closed Jordan region that it bounds does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of n pseudo-circles with the property that any two curves intersect precisely twice. We use this bound to show that any collection of n x -monotone pseudo-circles can be cut into O ( n 8/5 ) arcs so that any two intersect at most once; this improves a previous bound of O ( n 5/3 ) due to Tamaki and Tokuyama. If, in addition, the given collection admits an algebraic representation by three real parameters that satisfies some simple conditions, then the number of cuts can be further reduced to O ( n 3/2 (log n ) O (α( s ( n )) ), where α( n ) is the inverse Ackermann function, and s is a constant that depends on the the representation of the pseudo-circles. For arbitrary collections of pseudo-circles, any two of which intersect exactly twice, the number of necessary cuts reduces still further to O ( n 4/3 ). As applications, we obtain improved bounds for the number of incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, of pairwise intersecting pseudo-circles, of arbitrary x -monotone pseudo-circles, of parabolas, and of homothetic copies of any fixed simply shaped convex curve. We also obtain a variant of the Gallai--Sylvester theorem for arrangements of pairwise intersecting pseudo-circles, and a new lower bound on the number of distinct distances under any well-behaved norm.

(MATH) A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if it does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of n pseudo-circles with the property that any two curves intersect precisely twice. Enhancing this bound in several ways, and combining it with the technique of Tamaki and Tokuyama [16], we show that any collection of n pseudo-circles can be cut into $\bx$ arcs so that any two intersect at most once, provided that the given pseudo-circles are x-monotone and admit an algebraic representation by three real parameters; here $\alpha(n)$ is the inverse Ackermann function, and s is a constant that depends on the algebraic degree of the representation of the pseudo-circles (s=2 for circles and parabolas). For arbitrary collections of pseudo-circles, any two of which intersect twice, the number of necessary cuts reduces to O(n 4/3). As applications, we obtain improved bounds for the number of point-curve incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, pairwise intersecting pseudo-circles, parabolas, and families of homothetic copies of a fixed convex curve. We also obtain a variant of the Gallai-Sylvester theorem for arrangements of pairwise intersecting pseudo-circles, and a new lower bound for the number of distinct distances among n points in the plane under any simply-defined norm or convex distance function.