34
34

Sep 19, 2013
09/13

by
Günter M. Ziegler

texts

######
eye 34

######
favorite 0

######
comment 0

In this paper, we discuss f- and flag-vectors of 4-dimensional convex polytopes and cellular 3-spheres. We put forward two crucial parameters of fatness and complexity: Fatness F(P) := (f_1+f_2-20)/(f_0+f_3-10) is large if there are many more edges and 2-faces than there are vertices and facets, while complexity C(P) := (f_{03}-20)/(f_0+f_3-10) is large if every facet has many vertices, and every vertex is in many facets. Recent results suggest that these parameters might allow one to...

Source: http://arxiv.org/abs/math/0208073v2

54
54

Sep 23, 2013
09/13

by
Günter M. Ziegler

texts

######
eye 54

######
favorite 0

######
comment 0

These lectures on the combinatorics and geometry of 0/1-polytopes are meant as an \emph{introduction} and \emph{invitation}. Rather than heading for an extensive survey on 0/1-polytopes I present some interesting aspects of these objects; all of them are related to some quite recent work and progress. 0/1-polytopes have a very simple definition and explicit descriptions; we can enumerate and analyze small examples explicitly in the computer (e.g. using {\tt polymake}). However, any intuition...

Source: http://arxiv.org/abs/math/9909177v1

43
43

Sep 19, 2013
09/13

by
Günter M. Ziegler

texts

######
eye 43

######
favorite 0

######
comment 0

Let $B$ be an arrangement of linear complex hyperplanes in $C^d$. Then a classical result by Orlik \& Solomon asserts that the cohomology algebra of the complement can be constructed from the combinatorial data that are given by the intersection lattice. If $B'$ is, more generally, a $2$-arrangement in $R^{2d}$ (an arrangement of real subspaces of codimension $2$ with even-dimensional intersections), then the intersection lattice still determines the cohomology {\it groups} of the...

Source: http://arxiv.org/abs/alg-geom/9202005v1

44
44

Sep 23, 2013
09/13

by
Günter M. Ziegler

texts

######
eye 44

######
favorite 0

######
comment 0

It is an amazing and a bit counter-intuitive discovery by Micha Perles from the sixties that there are ``non-rational polytopes'': combinatorial types of convex polytopes that cannot be realized with rational vertex coordinates. We describe a simple construction of non-rational polytopes that does not need duality (Perles' ``Gale diagrams''): It starts from a non-rational point configuration in the plane, and proceeds with so-called Lawrence extensions. We also show that there are non-rational...

Source: http://arxiv.org/abs/0710.4453v2

30
30

Sep 21, 2013
09/13

by
Günter M. Ziegler

texts

######
eye 30

######
favorite 0

######
comment 0

We construct a 2-parameter family of 4-dimensional polytopes with extreme combinatorial structure: In this family, the ``fatness'' of the f-vector gets arbitrarily close to 9, the ``complexity'' (given by the flag vector) gets arbitrarily close to 16. The polytopes are obtained from suitable deformed products of even polygons by a projection to four-space.

Source: http://arxiv.org/abs/math/0407042v1

42
42

Sep 24, 2013
09/13

by
Günter M. Ziegler

texts

######
eye 42

######
favorite 0

######
comment 0

The construction of the COMBINATORIAL data for a surface with n vertices of maximal genus is a classical problem: The maximal genus g=[(n-3)(n-4)/12] was achieved in the famous ``Map Color Theorem'' by Ringel et al. (1968). We present the nicest one of Ringel's constructions, for the case when n is congruent to 7 mod 12, but also an alternative construction, essentially due to Heffter (1898), which easily and explicitly yields surfaces of genus g ~ 1/16 n^2. For GEOMETRIC (polyhedral) surfaces...

Source: http://arxiv.org/abs/math/0412093v1

35
35

Sep 24, 2013
09/13

by
Günter M. Ziegler

texts

######
eye 35

######
favorite 0

######
comment 0

The Kneser conjecture (1955) was proved by Lov\'asz (1978) using the Borsuk-Ulam theorem; all subsequent proofs, extensions and generalizations also relied on Algebraic Topology results, namely the Borsuk-Ulam theorem and its extensions. Only in 2000, Matou\v{s}ek provided the first combinatorial proof of the Kneser conjecture. Here we provide a hypergraph coloring theorem, with a combinatorial proof, which has as special cases the Kneser conjecture as well as its extensions and generalization...

Source: http://arxiv.org/abs/math/0103146v1

48
48

Sep 23, 2013
09/13

by
Günter M. Ziegler

texts

######
eye 48

######
favorite 0

######
comment 0

These lecture notes treat some current aspects of two closely interrelated topics from the theory of convex polytopes: the shapes of f-vectors, and extremal constructions. The first lecture treats 3-dimensional polytopes; it includes a complete proof of the Koebe--Andreev--Thurston theorem, using the variational principle by Bobenko & Springborn (2004). In Lecture 2 we look at f-vector shapes of very high-dimensional polytopes. The third lecture explains a surprisingly simple construction...

Source: http://arxiv.org/abs/math/0411400v2

30
30

Sep 22, 2013
09/13

by
Thilo Rörig; Günter M. Ziegler

texts

######
eye 30

######
favorite 0

######
comment 0

We introduce the wedge product of two polytopes. The wedge product is described in terms of inequality systems, in terms of vertex coordinates as well as purely combinatorially, from the corresponding data of its constituents. The wedge product construction can be described as an iterated ``subdirect product'' as introduced by McMullen (1976); it is dual to the ``wreath product'' construction of Joswig and Lutz (2005). One particular instance of the wedge product construction turns out to be...

Source: http://arxiv.org/abs/0908.3159v1

4
4.0

Jun 28, 2018
06/18

by
Lauri Loiskekoski; Günter M. Ziegler

texts

######
eye 4

######
favorite 0

######
comment 0

We show that by cutting off the vertices and then the edges of neighborly cubical polytopes, one obtains simple 4-dimensional polytopes with n vertices such that all separators of the graph have size at least $\Omega(n/\log^{3/2}n)$. This disproves a conjecture by Kalai from 1991/2004.

Topics: Combinatorics, Metric Geometry, Mathematics

Source: http://arxiv.org/abs/1510.00511

2
2.0

Jun 28, 2018
06/18

by
Emerson León; Günter M. Ziegler

texts

######
eye 2

######
favorite 0

######
comment 0

We construct and study the space C(\R^d,n) of all partitions of \R^d into n non-empty open convex regions (n-partitions). A representation on the upper hemisphere of an n-sphere is used to obtain a metric and thus a topology on this space. We show that the space of partitions into possibly empty regions C(\R^d,\le n) yields a compactification with respect to this metric. We also describe faces and face lattices, combinatorial types, and adjacency graphs for $n$-partitions, and use these...

Topics: Metric Geometry, Mathematics

Source: http://arxiv.org/abs/1511.02904

113
113

Sep 22, 2013
09/13

by
Benjamin Nill; Günter M. Ziegler

texts

######
eye 113

######
favorite 0

######
comment 0

We show that up to unimodular equivalence there are only finitely many d-dimensional lattice polytopes without interior lattice points that do not admit a lattice projection onto a (d-1)-dimensional lattice polytope without interior lattice points. This was conjectured by Treutlein. As an immediate corollary, we get a short proof of a recent result of Averkov, Wagner and Weismantel, namely the finiteness of the number of maximal lattice polytopes without interior lattice points. Moreover, we...

Source: http://arxiv.org/abs/1101.4292v2

46
46

Sep 23, 2013
09/13

by
Cesar Ceballos; Günter M. Ziegler

texts

######
eye 46

######
favorite 0

######
comment 0

We review three realizations of the associahedron that arise as secondary polytopes, from cluster algebras, and as Minkowski sums of simplices, and show that under any choice of parameters, the resulting associahedra are affinely non-equivalent.

Source: http://arxiv.org/abs/1006.3487v2

4
4.0

Jun 28, 2018
06/18

by
Philip Brinkmann; Günter M. Ziegler

texts

######
eye 4

######
favorite 0

######
comment 0

We present a first example of a flag vector of a polyhedral sphere that is not the flag vector of any polytope. Namely, there is a unique 3-sphere with the parameters $(f_0,f_1,f_2,f_3;f_{02})=(12,40,40,12;120)$, but this sphere is not realizable by a convex 4-polytope. The 3-sphere, which is 2-simple and 2-simplicial, was found by Werner (2009); we present results of a computer enumeration which imply that the sphere with these parameters is unique. We prove that it is non-polytopal in two...

Topics: Metric Geometry, Combinatorics, Mathematics

Source: http://arxiv.org/abs/1506.08148

2
2.0

Jun 29, 2018
06/18

by
Philip Brinkmann; Günter M. Ziegler

texts

######
eye 2

######
favorite 0

######
comment 0

We present a new algorithmic approach that can be used to determine whether a given quadruple $(f_0,f_1,f_2,f_3)$ is the f-vector of any convex 4-dimensional polytope. By implementing this approach, we classify the f-vectors of 4-polytopes in the range $f_0+f_3\le22$. In particular, we thus prove that there are f-vectors of cellular 3-spheres with the intersection property that are not f-vectors of any convex 4-polytopes, thus answering a question that may be traced back to the works of...

Topics: Metric Geometry, Combinatorics, Mathematics

Source: http://arxiv.org/abs/1610.01028

43
43

Sep 19, 2013
09/13

by
Andreas Paffenholz; Günter M. Ziegler

texts

######
eye 43

######
favorite 0

######
comment 0

We describe and analyze a new construction that produces new Eulerian lattices from old ones. It specializes to a construction that produces new strongly regular cellular spheres (whose face lattices are Eulerian). The construction does not always specialize to convex polytopes; however, in a number of cases where we can realize it, it produces interesting classes of polytopes. Thus we produce an infinite family of rational 2-simplicial 2-simple 4-polytopes, as requested by Eppstein, Kuperberg...

Source: http://arxiv.org/abs/math/0304492v2

44
44

Sep 18, 2013
09/13

by
Julian Pfeifle; Günter M. Ziegler

texts

######
eye 44

######
favorite 0

######
comment 0

We construct 2^{\Omega(n^{5/4})} combinatorial types of triangulated 3-spheres on n vertices. Since by a result of Goodman and Pollack (1986) there are no more than 2^{O(n log n)} combinatorial types of simplicial 4-polytopes, this proves that asymptotically, there are far more combinatorial types of triangulated 3-spheres than of simplicial 4-polytopes on n vertices. This complements results of Kalai (1988), who had proved a similar statement about d-spheres and (d+1)-polytopes for fixed d...

Source: http://arxiv.org/abs/math/0212004v2

39
39

Sep 20, 2013
09/13

by
Michael Joswig; Günter M. Ziegler

texts

######
eye 39

######
favorite 0

######
comment 0

We give a simple formula for the signature of a foldable triangulation of a lattice polygon in terms of its boundary. This yields lower bounds on the number of real roots of certain of systems of polynomial equations known as "Wronski systems".

Source: http://arxiv.org/abs/1207.6865v2

35
35

Sep 23, 2013
09/13

by
Cesar Ceballos; Günter M. Ziegler

texts

######
eye 35

######
favorite 0

######
comment 0

There are many open problems and some mysteries connected to the realizations of the associahedra as convex polytopes. In this note, we describe three -- concerning special realizations with the vertices on a sphere, the space of all possible realizations, and possible realizations of the multiassociahedron.

Source: http://arxiv.org/abs/1110.4059v1

95
95

Sep 23, 2013
09/13

by
Bernd Gonska; Günter M. Ziegler

texts

######
eye 95

######
favorite 0

######
comment 0

We characterize the combinatorial types of stacked d-polytopes that are inscribable. Equivalently, we identify the triangulations of a simplex by stellar subdivisions that can be realized as Delaunay triangulations.

Source: http://arxiv.org/abs/1111.5322v1

39
39

Sep 22, 2013
09/13

by
Torsten Schöneborn; Günter M. Ziegler

texts

######
eye 39

######
favorite 0

######
comment 0

The Topological Tverberg Theorem claims that any continuous map of a (q-1)(d+1)-simplex to \R^d identifies points from q disjoint faces. (This has been proved for affine maps, for d=1, and if q is a prime power, but not yet in general.) The Topological Tverberg Theorem can be restricted to maps of the d-skeleton of the simplex. We further show that it is equivalent to a ``Winding Number Conjecture'' that concerns only maps of the (d-1)-skeleton of a (q-1)(d+1)-simplex to \R^d. ``Many Tverberg...

Source: http://arxiv.org/abs/math/0409081v2

35
35

Sep 23, 2013
09/13

by
Raman Sanyal; Günter M. Ziegler

texts

######
eye 35

######
favorite 0

######
comment 0

We introduce a deformed product construction for simple polytopes in terms of lower-triangular block matrix representations. We further show how Gale duality can be employed for the construction and for the analysis of deformed products such that specified faces (e.g. all the k-faces) are ``strictly preserved'' under projection. Thus, starting from an arbitrary neighborly simplicial (d-2)-polytope Q on n-1 vertices we construct a deformed n-cube, whose projection to the last dcoordinates yields...

Source: http://arxiv.org/abs/0710.2162v1

48
48

Sep 22, 2013
09/13

by
Thomas Voigt; Günter M. Ziegler

texts

######
eye 48

######
favorite 0

######
comment 0

Let $P(d)$ be the probability that a random 0/1-matrix of size $d \times d$ is singular, and let $E(d)$ be the expected number of 0/1-vectors in the linear subspace spanned by d-1 random independent 0/1-vectors. (So $E(d)$ is the expected number of cube vertices on a random affine hyperplane spanned by vertices of the cube.) We prove that bounds on $P(d)$ are equivalent to bounds on $E(d)$: \[ P(d) = (2^{-d} E(d) + \frac{d^2}{2^{d+1}}) (1 + o(1)). \] We also report about computational...

Source: http://arxiv.org/abs/math/0308050v3

76
76

Sep 21, 2013
09/13

by
Bruno Benedetti; Günter M. Ziegler

texts

######
eye 76

######
favorite 0

######
comment 0

Durhuus and Jonsson (1995) introduced the class of "locally constructible" (LC) 3-spheres and showed that there are only exponentially-many combinatorial types of simplicial LC 3-spheres. Such upper bounds are crucial for the convergence of models for 3D quantum gravity. We characterize the LC property for d-spheres ("the sphere minus a facet collapses to a (d-2)-complex") and for d-balls. In particular, we link it to the classical notions of collapsibility, shellability and...

Source: http://arxiv.org/abs/0902.0436v4

1,282
1.3K

Jul 29, 2017
07/17

by
Martin Aigner, Günter M. Ziegler

texts

######
eye 1,282

######
favorite 2

######
comment 0

Book Proofs from THE BOOK, 5th edition. The one that says "-PRINT" has extra blank pages for printing.

Topics: math, proofs, demonstrations

3
3.0

Jun 28, 2018
06/18

by
Arnau Padrol; Günter M. Ziegler

texts

######
eye 3

######
favorite 0

######
comment 0

Inscribability of polytopes is a classic subject but also a lively research area nowadays. We illustrate this with a selection of well-known results and recent developments on six particular topics related to inscribable polytopes. Along the way we collect a list of (new and old) open questions.

Topics: Metric Geometry, Mathematics

Source: http://arxiv.org/abs/1511.03458

57
57

Sep 22, 2013
09/13

by
Christian Haase; Günter M. Ziegler

texts

######
eye 57

######
favorite 0

######
comment 0

The combinatorial structure of a d-dimensional simple convex polytope can be reconstructed from its abstract graph [Blind & Mani 1987, Kalai 1988]. However, no polynomial/efficient algorithm is known for this task, although a polynomially checkable certificate for the correct reconstruction was found by [Joswig, Kaibel & Koerner 2000]. A much stronger certificate would be given by the following characterization of the facet subgraphs, conjectured by M. Perles: ``The facet subgraphs of...

Source: http://arxiv.org/abs/math/0011170v2

34
34

Sep 19, 2013
09/13

by
Jiri Matousek; Günter M. Ziegler

texts

######
eye 34

######
favorite 0

######
comment 0

This paper is a study of ``topological'' lower bounds for the chromatic number of a graph. Such a lower bound was first introduced by Lov\'asz in 1978, in his famous proof of the \emph{Kneser conjecture} via Algebraic Topology. This conjecture stated that the \emph{Kneser graph} $\KG_{m,n}$, the graph with all $k$-element subsets of $\{1,2,...,n\}$ as vertices and all pairs of disjoint sets as edges, has chromatic number $n-2k+2$. Several other proofs have since been published (by B\'ar\'any,...

Source: http://arxiv.org/abs/math/0208072v3

77
77

Sep 22, 2013
09/13

by
Julian Pfeifle; Günter M. Ziegler

texts

######
eye 77

######
favorite 0

######
comment 0

The Monotone Upper Bound Problem asks for the maximal number M(d,n) of vertices on a strictly-increasing edge-path on a simple d-polytope with n facets. More specifically, it asks whether the upper bound M(d,n)

Source: http://arxiv.org/abs/math/0308186v1

128
128

Jul 20, 2013
07/13

by
Francisco Santos; Günter M. Ziegler

texts

######
eye 128

######
favorite 0

######
comment 0

A seminal result in the theory of toric varieties, due to Knudsen, Mumford and Waterman (1973), asserts that for every lattice polytope $P$ there is a positive integer $k$ such that the dilated polytope $kP$ has a unimodular triangulation. In dimension 3, Kantor and Sarkaria (2003) have shown that $k=4$ works for every polytope. But this does not imply that every $k>4$ works as well. We here study the values of $k$ for which the result holds showing that: 1. It contains all composite...

Source: http://arxiv.org/abs/1304.7296v1

31
31

Sep 23, 2013
09/13

by
Karim A. Adiprasito; Günter M. Ziegler

texts

######
eye 31

######
favorite 0

######
comment 0

We construct an infinite family of 4-polytopes whose realization spaces have dimension smaller or equal to 96. This in particular settles a problem going back to Legendre and Steinitz: whether and how the dimension of the realization space of a polytope is determined/bounded by its f-vector. From this, we derive an infinite family of combinatorially distinct 69-dimensional polytopes whose realization is unique up to projective transformation. This answers a problem posed by Perles and Shephard...

Source: http://arxiv.org/abs/1212.5812v2

42
42

Sep 18, 2013
09/13

by
Jürgen Richter-Gebert; Günter M. Ziegler

texts

######
eye 42

######
favorite 0

######
comment 0

Let $P\subset\R^d$ be a $d$-dimensional polytope. The {\em realization space} of~$P$ is the space of all polytopes $P'\subset\R^d$ that are combinatorially equivalent to~$P$, modulo affine transformations. We report on work by the first author, which shows that realization spaces of \mbox{4-dimensional} polytopes can be ``arbitrarily bad'': namely, for every primary semialgebraic set~$V$ defined over~$\Z$, there is a $4$-polytope $P(V)$ whose realization space is ``stably equivalent'' to~$V$....

Source: http://arxiv.org/abs/math/9510217v1

39
39

Sep 22, 2013
09/13

by
Ronald F. Wotzlaw; Günter M. Ziegler

texts

######
eye 39

######
favorite 0

######
comment 0

In a Note added in proof to a 1984 paper, Daniel A. Marcus claimed to have a counterexample to his conjecture that a minimal positively k-spanning vector configuration in R^m has size at most 2km. However, the counterexample was never published, and seems to be lost. Independently, ten years earlier, Peter Mani in 1974 solved a problem by Hadwiger, disproving that every ``illuminated'' d-dimensional polytope must have at least 2d vertices. These two studies are related by Gale duality, an...

Source: http://arxiv.org/abs/0908.1698v1

51
51

Sep 23, 2013
09/13

by
Cesar Ceballos; Francisco Santos; Günter M. Ziegler

texts

######
eye 51

######
favorite 0

######
comment 0

Hohlweg and Lange (2007) and Santos (2004, unpublished) have found two different ways of constructing exponential families of realizations of the n-dimensional associahedron with normal vectors in {0,1,-1}^n, generalizing the constructions of Loday (2004) and Chapoton-Fomin-Zelevinsky (2002). We classify the associahedra obtained by these constructions modulo linear equivalence of their normal fans and show, in particular, that the only realization that can be obtained with both methods is the...

Source: http://arxiv.org/abs/1109.5544v2

59
59

Sep 23, 2013
09/13

by
Thilo Rörig; Nikolaus Witte; Günter M. Ziegler

texts

######
eye 59

######
favorite 0

######
comment 0

There are d-dimensional zonotopes with n zones for which a 2-dimensional central section has \Omega(n^{d-1}) vertices. For d=3 this was known, with examples provided by the "Ukrainian easter eggs'' by Eppstein et al. Our result is asymptotically optimal for all fixed d>=2.

Source: http://arxiv.org/abs/0710.3116v3

156
156

Sep 24, 2013
09/13

by
Pavle V. M. Blagojević; Günter M. Ziegler

texts

######
eye 156

######
favorite 0

######
comment 0

We describe a regular cell complex model for the configuration space F(\R^d,n). Based on this, we use Equivariant Obstruction Theory to prove the prime power case of the conjecture by Nandakumar and Ramana Rao that every polygon can be partitioned into n convex parts of equal area and perimeter.

Source: http://arxiv.org/abs/1202.5504v3

54
54

Sep 19, 2013
09/13

by
Raman Sanyal; Axel Werner; Günter M. Ziegler

texts

######
eye 54

######
favorite 0

######
comment 0

In 1989 Kalai stated the three conjectures A, B, C of increasing strength concerning face numbers of centrally symmetric convex polytopes. The weakest conjecture, A, became known as the ``$3^d$-conjecture''. It is well-known that the three conjectures hold in dimensions d \leq 3. We show that in dimension 4 only conjectures A and B are valid, while conjecture C fails. Furthermore, we show that both conjectures B and C fail in all dimensions d \geq 5.

Source: http://arxiv.org/abs/0708.3661v2

43
43

Sep 20, 2013
09/13

by
David Eppstein; Greg Kuperberg; Günter M. Ziegler

texts

######
eye 43

######
favorite 0

######
comment 0

We introduce the fatness parameter of a 4-dimensional polytope P, defined as \phi(P)=(f_1+f_2)/(f_0+f_3). It arises in an important open problem in 4-dimensional combinatorial geometry: Is the fatness of convex 4-polytopes bounded? We describe and analyze a hyperbolic geometry construction that produces 4-polytopes with fatness \phi(P)>5.048, as well as the first infinite family of 2-simple, 2-simplicial 4-polytopes. Moreover, using a construction via finite covering spaces of surfaces, we...

Source: http://arxiv.org/abs/math/0204007v3

30
30

Sep 18, 2013
09/13

by
Pavle V. M. Blagojević; Günter M. Ziegler

texts

######
eye 30

######
favorite 0

######
comment 0

We compute the complete Fadell-Husseini index of the 8 element dihedral group D_8 acting on S^d \times S^d, both for F_2 and for integer coefficients. This establishes the complete goup cohomology lower bounds for the two hyperplane case of Gr"unbaum's 1960 mass partition problem: For which d and j can any j arbitrary measures be cut into four equal parts each by two suitably-chosen hyperplanes in R^d? In both cases, we find that the ideal bounds are not stronger than previously...

Source: http://arxiv.org/abs/0704.1943v4

8
8.0

Jun 30, 2018
06/18

by
Anders Björner; Jiří Matoušek; Günter M. Ziegler

texts

######
eye 8

######
favorite 0

######
comment 0

Brouwer's fixed point theorem from 1911 is a basic result in topology - with a wealth of combinatorial and geometric consequences. In these lecture notes we present some of them, related to the game of HEX and to the piercing of multiple intervals. We also sketch stronger theorems, due to Oliver and others, and explain their applications to the fascinating (and still not fully solved) evasiveness problem.

Topics: Mathematics, Combinatorics, Algebraic Topology

Source: http://arxiv.org/abs/1409.7890

40
40

Sep 21, 2013
09/13

by
Pavle V. M. Blagojevic; Günter M. Ziegler

texts

######
eye 40

######
favorite 0

######
comment 0

We show that for every injective continuous map f: S^2 --> R^3 there are four distinct points in the image of f such that the convex hull is a tetrahedron with the property that two opposite edges have the same length and the other four edges are also of equal length. This result represents a partial result for the topological Borsuk problem for R^3. Our proof of the geometrical claim, via Fadell-Husseini index theory, provides an instance where arguments based on group cohomology with...

Source: http://arxiv.org/abs/0808.3841v1

3
3.0

Jun 30, 2018
06/18

by
Pavle V. M. Blagojević; Florian Frick; Günter M. Ziegler

texts

######
eye 3

######
favorite 0

######
comment 0

We give a short and simple proof of a recent result of Dobbins that any point in an $nd$-polytope is the barycenter of $n$ points in the $d$-skeleton. This new proof builds on the constraint method that we recently introduced to prove Tverberg-type results.

Topics: Mathematics, Metric Geometry, Combinatorics

Source: http://arxiv.org/abs/1411.4417

2
2.0

Jun 28, 2018
06/18

by
Pavle V. M. Blagojević; Florian Frick; Günter M. Ziegler

texts

######
eye 2

######
favorite 0

######
comment 0

Using the authors' 2014 "constraints method," we give a short proof for a 2015 result of Dobbins on representations of a point in a polytope as the barycenter of points in a skeleton, and show that the "r-fold Whitney trick" of Mabillard and Wagner (2014/2015) implies that the Topological Tverberg Conjecture for r-fold intersections fails dramatically for all r that are not prime powers.

Topics: Combinatorics, Algebraic Topology, Mathematics, Metric Geometry

Source: http://arxiv.org/abs/1510.07984

35
35

Jul 20, 2013
07/13

by
Pavle V. M. Blagojević; Benjamin Matschke; Günter M. Ziegler

texts

######
eye 35

######
favorite 0

######
comment 0

We prove that any continuous map of an N-dimensional simplex Delta_N with colored vertices to a d-dimensional manifold M must map r points from disjoint rainbow faces of Delta_N to the same point in M: For this we have to assume that N \geq (r-1)(d+1), no r vertices of Delta_N get the same color, and our proof needs that r is a prime. A face of Delta_N is a rainbow face if all vertices have different colors. This result is an extension of our recent "new colored Tverberg theorem", the...

Source: http://arxiv.org/abs/1107.1904v1

45
45

Sep 20, 2013
09/13

by
Pavle V. M. Blagojević; Wolfgang Lück; Günter M. Ziegler

texts

######
eye 45

######
favorite 0

######
comment 0

We study the Fadell-Husseini index of the configuration space F(R^d,n) with respect to different subgroups of the symmetric group S_n. For p prime and d>0, we completely determine Index_{Z/p}(F(R^d,p);F_p) and partially describe Index{(Z/p)^k}(F(R^d,p^k);F_p). In this process we obtain results of independent interest, including: (1) an extended equivariant Goresky-MacPherson formula, (2) a complete description of the top homology of the partition lattice Pi_p as an F_p[Z_p]-module, and (3) a...

Source: http://arxiv.org/abs/1207.2852v2

35
35

Sep 20, 2013
09/13

by
Volker Kaibel; Raphael Mechtel; Micha Sharir; Günter M. Ziegler

texts

######
eye 35

######
favorite 0

######
comment 0

The worst-case expected length f(n) of the path taken by the simplex algorithm with the Random Edge pivot rule on a 3-dimensional linear program with n constraints is shown to be bounded by 1.3445 n

Source: http://arxiv.org/abs/math/0301076v1

36
36

Sep 19, 2013
09/13

by
Pavle V. M. Blagojević; Benjamin Matschke; Günter M. Ziegler

texts

######
eye 36

######
favorite 0

######
comment 0

We prove a "Tverberg type" multiple intersection theorem. It strengthens the prime case of the original Tverberg theorem from 1966, as well as the topological Tverberg theorem of Barany et al. (1980), by adding color constraints. It also provides an improved bound for the (topological) colored Tverberg problem of Barany & Larman (1992) that is tight in the prime case and asymptotically optimal in the general case. The proof is based on relative equivariant obstruction theory.

Source: http://arxiv.org/abs/0910.4987v2

38
38

Sep 21, 2013
09/13

by
Anders Björner; Andreas Paffenholz; Jonas Sjöstrand; Günter M. Ziegler

texts

######
eye 38

######
favorite 0

######
comment 0

In 1992 Thomas Bier presented a strikingly simple method to produce a huge number of simplicial (n-2)-spheres on 2n vertices as deleted joins of a simplicial complex on n vertices with its combinatorial Alexander dual. Here we interpret his construction as giving the poset of all the intervals in a boolean algebra that "cut across an ideal." Thus we arrive at a substantial generalization of Bier's construction: the Bier posets Bier(P,I) of an arbitrary bounded poset P of finite...

Source: http://arxiv.org/abs/math/0311356v2

30
30

Sep 23, 2013
09/13

by
Bernhard Hanke; Raman Sanyal; Carsten Schultz; Günter M. Ziegler

texts

######
eye 30

######
favorite 0

######
comment 0

We describe an explicit chain map from the standard resolution to the minimal resolution for the finite cyclic group Z_k of order k. We then demonstrate how such a chain map induces a "Z_k-combinatorial Stokes theorem", which in turn implies "Dold's theorem" that there is no equivariant map from an n-connected to an n-dimensional free Z_k-complex. Thus we build a combinatorial access road to problems in combinatorics and discrete geometry that have previously been treated...

Source: http://arxiv.org/abs/0710.0050v1

57
57

Sep 18, 2013
09/13

by
Ragnar Freij; Matthias Henze; Moritz W. Schmitt; Günter M. Ziegler

texts

######
eye 57

######
favorite 0

######
comment 0

We analyze a remarkable class of centrally symmetric polytopes, the Hansen polytopes of split graphs. We confirm Kalai's 3^d-conjecture for such polytopes (they all have at least 3^d nonempty faces) and show that the Hanner polytopes among them (which have exactly 3^d nonempty faces) correspond to threshold graphs. Our study produces a new family of Hansen polytopes that have only 3^d+16 nonempty faces.

Source: http://arxiv.org/abs/1201.5790v1