# Striking existence theorems with mild conditions, and simple to state: more recent examples?

I would like to write an article about powerful existence theorems that assert, under mild and simple conditions, that some basic pattern or regularity exist. See some examples below. By mild conditions I mean short, easy, general. By simple conditions I mean that they should be accessible to undergraduate mathematics/science students.

I am especially interested in "low-dimensional" examples which allow an easy graphical representation.

I had some obvious examples in mind (given below), but many of them are rather classical results established until around 1970, roughly speaking.

I would be interested in more recent results. Thanks to the users that added great examples in the comments!

(1) Cantor Set, and existence of cardinalities $$>|\mathbb N |$$

(2) Lemma of Sperner, and Brouwer Fixed Point Theorem

(3) Lemma of Tucker, and Borsuk-Ulam Theorem

(4) Ramsey's Theorem

(5) Wallpaper Groups: There exist exactly 17 plane symmetry groups

(7) Wagner's Theorem about Planar Graphs

(8) Monsky's Theorem

(9) Four Color Theorem

(10) Penrose Tiling

(11) Max-Flow Min-Cut Theorem from graph theory

(12) Tverberg's Theorem about intersecting convex hulls

(13) Van der Waerden's Theorem

(14) Szemerédi's Regularity Lemma from extremal graph theory

(15) Recent results about Existence of Designs (Keevash 2014, Glock et al. 2016)

• On the topic of Ramsey's theorem, you might be interested in van der Waerden's Theorem about arithmetic progressions. – Carl-Fredrik Nyberg Brodda May 17 at 11:07
• The Max-flow Min-cut theorem was proved by Ford and Fulkerson in 1956, which is slightly later than 1950. – Sam Hopkins May 17 at 13:14
• I’m not sure what you mean by minimum regular pattern, but probably the existence of designs fits the bill (recent result of Keevash and of Glock et al). – user36212 May 17 at 16:37
• Tverberg's theorem might be suitable, and its topological version also. – gyashfe May 18 at 9:52
• Maybe: Infinite Ramsey theorem (from which the finite version follows). Also Szemerédi's regularity lemma. – LeechLattice May 18 at 10:46

Alexandrov's gluing theorem: If one glues polygons together along their boundaries to form a closed surface homeomorphic to a sphere, such that no point has more than $$2\pi$$ incident surface angle, then the result is isometric to a convex polyhedron, uniquely determined up to rigid motions.

There is as yet no effective procedure to actually construct the polyhedron guaranteed to exist.

A.D. Alexandrov. Convex Polyhedra. Springer-Verlag, Berlin, 2005. Monographs in Mathematics. Translation of the 1950 Russian ed. by N. S. Dairbekov, S.S. Kutateladze, and A.B. Sossinsky. p.100.

The result also holds for a single polygon, whose perimeter is glued closed by identifications:

Snapshots from a video by Erik Demaine, Martin Demaine, Anna Lubiw, J.O'Rourke, Irena Pashchenko.

• I think you want to say "then the result is isometric to a convex polyhedron". Consider the cube on $(\pm1,\pm1,\pm1)$, with the top face replaced by four triangles going to $(0,0,1/2)$. Those instructions for gluing do not result in a convex polyhedron, but the result is isometric to the cube with the top face replaced by four triangles going to $(0,0,3/2)$, and that is a convex shape. – Matt F. May 18 at 16:53
• @Joseph O'Rourke, thanks a lot, this is a great example of what I am looking for – Claus May 18 at 17:00
• @MattF. Thanks for the correction. Among the class of convex polyhedra, the result is unique. Your phrasing is clearer, and I've changed it. – Joseph O'Rourke May 18 at 17:18

There are a number of easily stated problems in elementary computational geometry that have been solved only relatively recently, e.g.,

• the origami existence theorem that a single rectangular sheet of paper can be folded into the shape of any connected polygonal region, even if it has holes;

• the fold-and-cut theorem that any shape with straight sides can be cut from a single sheet of paper by folding it flat and making a single straight complete cut;

• the carpenter's rule problem of moving a simple planar polygon continuously to a position where all its vertices are in convex position, without ever crossing itself (below is an example from Erik Demaine's website);

• the existence of hinged dissections; i.e., the existence of a common hinged dissection of any finite collection of polygons of equal area (below is an example due to Greg Frederickson).

• thanks a lot for these examples. I followed the link, they are great! Very powerful. Thanks again – Claus yesterday

1) The set of continuous everywhere but differentiable nowhere functions on the unit interval is a meagre set of measure 1.

2) The existence of a space filling curve, or more generally surjective continuous maps $$S^m \to S^n$$ for $$n>m$$ (and then the fact that however any such map is homotopic to a map that misses a point).

• thanks a lot! Two good examples – Claus yesterday

These are a few of the existence-type results that may be of interest to you.

1. $$\text{Green, Tao (2006)}$$: There are arbitrarily long arithmetic progressions in primes. The proof they provided is based on extending Szemerédi's Theorem [1975, Endre Szemerédi] which, in itself, is an existence-type result, stating that any subset of $$\mathbb{Z}$$ with positive upper density, has arbitrarily long A.P.s. To understand the statement, one needs to only understand the definition of natural density and in particular, upper density. There are also results around this one (like the Weak Arithmetic Regularity Lemma) that also are existence-type results.
2. $$\text{Dirichlet's Theorem on Primes in A.P.s (1837)}$$: This is a classical (and old) result, and is not a pure existence-result, as in, it not only shows existence of a prime, but shows that infinitely many such primes exist. I know you were looking for recent results, but this is a standard and nice example, that I added here because it fits your ask for a result that is completely accessible at the undergraduate level. The result is as follows: $$\forall a, b \in \mathbb{N}: [[gcd(a,b) = 1] \rightarrow [\#(\{a + bk: k \in \mathbb{N}\} \cap \mathbb{P}) = \infty]]$$
3. $$\text{Tao, Zhang, Maynard, Polymath (2013-2014)}$$: A lot of work was done in 2013 and 2014 in the last decade about small prime-gaps, which, like the Dirichlet's theorem, not only show existence, but also, infinitude of such existence. Checking out Tao's wordpress site may be useful here. Incidentally, a lot of work was also done in this time on large prime-gaps, but showing the existence of arbitrarily large prime-gaps is quite trivial, and the questions that were focused on by the researchers were not 'existential'.

Extra Note: The Mean-Value Theorem, The Hahn-Banach Theorem and the Intermediate Value Theorem: I add these elementary results in Real Analysis and the Hahn-Banach Theorem from Functional Analysis (Rudin, 1991) since, for graphical representation, they are perhaps three of the most nicely presentable results.

• thanks for great examples. I will look up the Polymath results to learn more about it – Claus yesterday

adding other great examples, many of them provided in the comments section

(16) Kakeya needle problem and Besicovitch sets: You want to rotate a needle of unit length by $$360°$$. What is the region with smallest area to do that? It turns out there is no lower bound > 0 for the area of such a region, i.e. you can find arbitrarily small such regions. (https://en.wikipedia.org/wiki/Kakeya_set)

(17) A more recent one, Brenier’s Theorem on the existence of optimal transport maps between probability measures. (https://en.wikipedia.org/wiki/Transportation_theory_(mathematics))

(18) Recent results about bounded gaps between primes (e.g. Zhang)

(Adding these examples as an answer because the list of examples in my original question is getting too long)

• @MattF., this is a fair comment and thank you for making it. I added it because of its extreme simplicity, and because it establishes what I would call a regularity: You can obviously divide it into an even number (=existence). But that's the only possible case and all other cases fail. I feel it draws a powerful and insightful line between existence and non-existence. – Claus May 18 at 17:56