Charles J. Colbourn

Stephen Semmes

Alessandra Carbone

Department of Mathematics and Computer Science Alessandra Carbone

This book brings into focus the contrast between explicit and implicit algorithmic descriptions of objects and presents a new geometric language for the study of combinatorial and logical problems in complexity theory. These themes are considered in a variety of settings, sometimes crossing traditional boundaries. Special emphasis is given to moderate complexity - exponential or polynomial - but objects with multi-exponential complexity also fit in. Among the items under consideration are graphs, formal proofs, languages, automata, groups, circuits, some connections with geometry of metric spaces, and complexity classes (P, NP, co-NP).

A Graphic Apology for Symmetry and Implicitness

Guy David

Stephen William Semmes

Guy Rene Pierre Pierre

This book proposes new notions of coherent geometric structure. Fractal patterns have emerged in many contexts, but what exactly is a `pattern' and what is not? How can one make precise the structures lying within objects and the relationships between them? The foundations laid herein provide a fresh approach to a familiar field. From this emerges a wide range of open problems, large and small, and a variety of examples with diverse connections to other parts ofmathematics.

Self-similar Geometry Through Metric and Measure

Fractured Fractals and Broken Dreams

Roughly speaking, a $d$-dimensional subset of $\mathbfR^n$ is minimizing if arbitrary deformations of it (in a suitable class) cannot decrease its $d$-dimensional volume. For quasiminimizing sets, one allows the mass to decrease, but only in a controlled manner. To make this precise we follow Almgren's notion of 'restricted sets' [{\textbold 2}]. Graphs of Lipschitz mappings $f\:\mathbfR^d \to \mathbfR^{n-d}$ are always quasiminimizing, and Almgren showed that quasiminimizing sets are rectifiable. Here we establish uniform rectifiability properties of quasiminimizing sets, which provide a more quantitative sense in which these sets behave like Lipschitz graphs. (Almgren also established stronger smoothness properties under tighter quasiminimality conditions.)Quasiminimizing sets can arise as minima of functionals with highly irregular 'coefficients'. For such functionals, one cannot hope in general to have much more in the way of smoothness or structure than uniform rectifiability, for reasons of bilipschitz invariance. (See also [{\textbold 9}].) One motivation for considering minimizers of functionals with irregular coefficients comes from the following type of question. Suppose that one is given a compact set $K$ with upper bounds on its $d$-dimensional Hausdorff measure, and lower bounds on its $d$-dimensional topology.What can one say about the structure of $K$? To what extent does it behave like a nice $d$-dimensional surface? A basic strategy for dealing with this issue is to first replace $K$ by a set which is minimizing for a measurement of volume that imposes a large penalty on points which lie outside of $K$. This leads to a kind of regularization of $K$, in which cusps and very scattered parts of $K$ are removed, but without adding more than a small amount from the complement of $K$. The results for quasiminimizing sets then lead to uniform rectifiability properties of this regularization of $K$. To actually produce minimizers of general functionals it is sometimes convenient to work with (finite) discrete models. A nice feature of uniform rectifiability is that it provides a way to have bounds that cooperate robustly with discrete approximations, and which survive in the limit as the discretization becomes finer and finer.

Uniform Rectifiability and Quasiminimizing Sets of Arbitrary Codimension

The notion of uniform rectifiability of sets (in a Euclidean space), which emerged only recently, can be viewed in several different ways. It can be viewed as a quantitative and scale-invariant substitute for the classical notion of rectifiability; as the answer (sometimes only conjecturally) to certain geometric questions in complex and harmonic analysis; as a condition which ensures the parametrizability of a given set, with estimates, but with some holes and self-intersections allowed; and as an achievable baseline for information about the structure of a set. This book is about understanding uniform rectifiability of a given set in terms of the approximate behavior of the set at most locations and scales. In addition to being the only general reference available on uniform rectifiability, this book also poses many open problems, some of which are quite basic.

Stephen Semmes

About

Books

Join the club