Longueville - A Course in Topological Combinatorics

A Course in Topological Combinatorics — read online for free the complete book (whole text) full work

Below is the text of the book, divided by pages. System saving the place of the last page read, allows you to conveniently read the book "A Course in Topological Combinatorics" online for free, without having to search again every time where you left off. Put a bookmark, and you can go to the page where you finished reading at any time.

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

1234567...102

Mark de Longueville Universitext A Course in Topological Combinatorics 2013 10.1007/978-1-4419-7910-0_1 Springer Science+Business Media New York 2013

1. Fair-Division Problems

Mark de Longueville 1

(1)

Hochschule fr Technik und Wirtschaft Berlin, University of Applied Sciences, Berlin, Germany

Abstract

Almost every day, we encounter fair-division problems: in the guise of dividing a piece of cake, slicing a ham sandwich, or by dividing our time with respect to the needs and expectations of family, friends, work, etc.

Almost every day, we encounter fair-division problems: in the guise of dividing a piece of cake, slicing a ham sandwich, or by dividing our time with respect to the needs and expectations of family, friends, work, etc.

The mathematics of such fair-division problems will serve us as a first representative example for the interplay between combinatorics and topology.

In this chapter we will consider two important concepts: envy-free fair division and consensus division . These concepts lead to different topological tools that we may apply. On the one hand, there is Brouwers fixed-point theorem, and on the other hand, there is the theorem of Borsuk and Ulam. These topological results surprisingly turn out to have combinatorial analogues: the lemmas of Sperner and Tucker. Very similar in nature, they guarantee a simplex with a certain labeling in a labeled simplicial complex.

The chapter is organized in such a way that we will discuss in turn a topological result, its combinatorial analogue, and the corresponding fair-division problem.

1.1 Brouwers Fixed-Point Theorem and Sperners Lemma

Brouwers fixed-point theorem states that any continuous map from a ball of any dimension to itself has a fixed point. In two dimensions this can be illustrated as follows. Take two identical maps of Berlin or any other ball-shaped city. Now crumple one of the maps as you like and throw it on the other, flat, map as shown in Fig.. Then there exists a location in the city that on the crumpled map is exactly above the same place on the flat map.

Fig. 1.1

A city map twice

For the general formulation of Brouwers theorem, recall that the n -dimensional Euclidean ball is given by all points of distance at most 1 from the origin in n -dimensional Euclidean space, i.e.,

Theorem 1.1 (Brouwer).

Every continuous map from the n-dimensional ball to itself has a fixed point, i.e., there exists an such that f(x) = x.

The first proof that we provide for this theorem relies on a beautiful combinatorial lemma that we will discuss in the next section. There also exists a very short and simple proof using homology theory that we present on page .

Sperners Lemma

Brouwers fixed-point theorem is intimately related to a combinatorial lemma by Sperner that deals with labelings of triangulations of the simplex. Consider the standard n -simplex given as the convex hull of the standard basis vectors , see Fig.:

Fig. 1.2

The standard 2-simplex

By n we denote the (geometric) simplicial complex given by n and all its faces, i.e., . Assume that K is a subdivision of n . We may think of K as being obtained from n by adding extra vertices. For precise definitions and more details on simplicial complexes we refer to Appendix B. For any n , denote the set {1,, n } by [ n ]. In the definition of a Sperner labeling we will use labels from 1 to n +1, i.e., labels from the set [ n +1].

Definition 1.2.

A Sperner labeling is a labeling of the vertices of K satisfying

for all v vert( K ).

More intuitively, a Sperner labeling is the following. Consider the minimal face of n that contains v . Say it is given by the convex hull of . Then v is allowed to get labels only from { i 1,, i k }. In particular, the vertices e i obtain label i , while a vertex along the edge spanned by e i and e j obtains the label i or j , and so on. For an illustration see Fig..

Fig. 1.3

A Sperner-labeled triangulation of a 2-simplex

Call an n -simplex of Kfully labeled (with respect to ) if its n +1 vertices obtain distinct labels, i.e., if all possible labels from the set [ n +1] appear.

Lemma 1.3 (Sperner []).

Let : vert (K) [ n + 1] be a Sperner labeling of a triangulation K of the n-dimensional simplex. Then there exists a fully labeled n-simplex in K. More precisely, the number of fully labeled n-simplices is odd.

We will now present two inductive proofs of this amazing lemma. The first is a combinatorial construction that constructs one of the desired simplices, while the other is algebraic and uses the concept of a chain complex of a simplicial complex. The inductive proofs reveal a typical phenomenon: while we are mainly interested in the existence of a fully labeled simplex, the induction works only for the stronger statement that there is an odd number of fully labeled simplices.

A third proof, given on page of this section, proves the Sperner lemma as an application of Brouwers fixed-point theorem.

Proof (combinatorial).

The lemma is clearly valid for n =1. Now let n 2 and consider the ( n 1)-dimensional face of n given by the convex hull of e 1,, e n . Note that K restricted to is Sperner labeled with label set [ n ]. We construct a graph as follows. Let the vertex set be all n -simplices of K plus one extra vertex o . The extra vertex o is connected by an edge to all n -simplices that have an ( n 1)-simplex as a face that is labeled with all labels of [ n ] and lies within . Two n -simplices are connected by an edge if and only if they share an ( n 1)-dimensional face labeled with all of [ n ]. See Fig. for an example of the resulting graph.

Next page

1234567...102

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

Similar books «A Course in Topological Combinatorics»

Look at similar books to A Course in Topological Combinatorics. We have selected literature similar in name and meaning in the hope of providing readers with more options to find new, interesting, not yet read works.

Thomas Longueville

The Life of a Conspirator

Thomas Longueville

The First Duke and Duchess of Newcastle-upon-Tyne

Nicholas Loehr

Combinatorics, Second Edition

Edward Shuryak

Nonperturbative Topological Phenomena in QCD and Related Theories

Stanley

Algebraic Combinatorics: Walks, Trees, Tableaux, and More

Heidegger Martin

Heidegger and the thinking of place: explorations in the topology of being

Wilson

Combinatorics: A Very Short Introduction

Bóna

A Walk Through Combinatorics: An introduction to Enumeration and Graph Theory

John Wiley

Advanced Graph Theory and Combinatorics

Emil Prodan

Bulk and Boundary Invariants for Complex Topological Insulators

Shen

Topological Insulators: Dirac Equation in Condensed Matters

Martin J. Erickson

Introduction to Combinatorics

Discussion, reviews of the book A Course in Topological Combinatorics and just readers' own opinions. Leave your comments, write what you think about the work, its meaning or the main characters. Specify what exactly you liked and what you didn't like, and why you think so.