math_groups_discgeom

Published

The publications are divided into 3 Focus Areas. If you only want to see articles from a specific focus area just search for "Focus Area i" using the search bar below.


29 publications

Topological designs

Justin Malestein, Louis Theran

http://arxiv.org/abs/1008.1837

Focus Area 1: High-complexity Geometry We give a combinatorial characterization of generic minimal rigidity for planar periodic frameworks. The characterization is a true analogue of the Maxwell-Laman Theorem from rigidity theory: it is stated in terms of a finite combinatorial object and the conditions are checkable by polynomial time combinatorial algorithms. To prove our rigidity theorem we introduce and develop periodic direction networks and Z2-graded-sparse colored graphs.

On diagonal resolvable spheres

Pavle Blagojević, Aleksandra Dimitrijević Blagojević, Ljubiša Kočinacc

Appeared In: Topology and its Applications 160 (2013), 2335–2339

http://www.sciencedirect.com/science/art ...

Focus Area 3: Topological connectivity and diameter of Discrete Structures In this paper we give the complete answer to a question posed by A. Arhangelʼskii and prove that the sphere S_n is diagonal resolvable if and only if S_n is an H-space if and only if n∈{0,1,3,7}. Moreover, we prove that any upper half even dimensional Q-sphere cannot be diagonal resolvable.

The Schwarz genus of the Stiefel manifold and counting geometric configurations

Pavle Blagojević, Roman Karasev

Appeared In: Topology and its Applications Volume 160, Issue 18, 1 December 2013, Pages 2335–2339

http://arxiv.org/pdf/1211.5003v1.pdfhttp://www.sciencedirect.com/science/art ...

Focus Area 3: Topological connectivity and diameter of Discrete Structures In this paper we compute: the Schwarz genus of the Stiefel manifold $V_k(\mathbb R^n)$ with respect to the action of the Weyl group $W_k:=(\mathbb Z/2)^{k}\rtimes\Sigma_k$, and the Lusternik--Schnirelmann category of the quotient space $V_k(\mathbb R^n)/W_k$. Furthermore, these results are used in estimating the number of: critically outscribed parallelotopes around the strictly convex body, and Birkhoff--James orthogonal bases of the normed finite dimensional vector space.

There is no triangulation of the torus with vertex degrees 5, 6, ..., 6, 7 and related results: Geometric proofs for combinatorial theorems.

Ivan Izmestiev, Rob Kusner, Günter Rote, Boris Springborn, John M. Sullivan

Appeared In: Geom. Dedicata, 166 (2013), 15-29

http://www.arxiv.org/abs/1207.3605http://link.springer.com/article/10.1007 ...

Focus Area 2: Delaunay Geometry There is no 5,7-triangulation of the torus, that is, no triangulation with exactly two exceptional vertices, of degree 5 and 7. Similarly, there is no 3,5-quadrangulation. The vertices of a 2,4-hexangulation of the torus cannot be bicolored. Similar statements hold for 4,8-triangulations and 2,6-quadrangulations. We prove these results, of which the first two are known and the others seem to be new, as corollaries of a theorem on the holonomy group of a euclidean cone metric on the torus with just two cone points. We provide two proofs of this theorem: One argument is metric in nature, the other relies on the induced conformal structure and proceeds by invoking the residue theorem. Similar methods can be used to prove a theorem of Dress on infinite triangulations of the plane with exactly two irregular vertices. The non-existence results for torus decompositions provide infinite families of graphs which cannot be embedded in the torus.

The entropic discriminant

Raman Sanyal, Bernd Sturmfels, Cynthia Vinzantc

Appeared In: Advances in Mathematics, Volume 244, 10 September 2013, Pages 678–707

http://www.sciencedirect.com/science/art ...

- Focus Area 3: Topological connectivity - The entropic discriminant is a non-negative polynomial associated to a matrix. It arises in contexts ranging from statistics and linear programming to singularity theory and algebraic geometry. It describes the complex branch locus of the polar map of a real hyperplane arrangement, and it vanishes when the equations defining the analytic center of a linear program have a complex double root. We study the geometry of the entropic discriminant, and we express its degree in terms of the characteristic polynomial of the underlying matroid. Singularities of reciprocal linear spaces play a key role. In the corank-one case, the entropic discriminant admits a sum of squares representation derived from the discriminant of a characteristic polynomial of a symmetric matrix.

Parallelogram tilings, worms and finite orientations

Dirk Frettlöh, Edmund Harriss

Appeared In: Discrete & Computational Geometry April 2013, Volume 49, Issue 3, pp 531-539

http://link.springer.com/article/10.1007 ...http://arxiv.org/abs/1202.4686

Focus Area 1: High-complexity Geometry This paper studies properties of tilings of the plane by parallelograms. In particular it is established that in parallelogram tilings using a finite number of shapes all tiles occur in only finitely many orientations.

Frameworks with forced symmetry II: Orientation-preserving crystallographic groups

Justin Malestein, Louis Theran

Appeared In: Geometriae Dedicata, to appear.

http://arxiv.org/abs/1304.0756

- Focus Area 1: High-complexity Geometry - We give a combinatorial characterization of minimally rigid planar frameworks with orientation-preserving crystallographic symmetry, under the constraint of forced symmetry. The main theorems are proved by extending the methods of the first paper in this sequence from groups generated by a single rotation to groups generated by translations and rotations. The proofs make use of a new family of matroids defined on crystallographic groups and associated submodular functions.

Functions, measures, and equipartitioning convex k-fans

Imre Bárány, Pavle Blagojević, Aleksandra Dimitrijević Blagojević

Appeared In: Discrete & Computational Geometry, March 2013, Volume 49, Issue 2, pp 382-401

Focus Area 3: Topological connectivity and diameter of Discrete Structures A k-fan in the plane is a point x∈ℝ2 and k halflines starting from x. There are k angular sectors σ 1,…,σ k between consecutive halflines. The k-fan is convex if every sector is convex. A (nice) probability measure μ is equipartitioned by the k-fan if μ(σ i )=1/k for every sector. One of our results: Given a nice probability measure μ and a continuous function f defined on sectors, there is a convex 5-fan equipartitioning μ with f(σ 1)=f(σ 2)=f(σ 3).

Perfect colourings of cyclotomic integers

E. Paulo Bugarin, M. Louise A.N. de las Penas, Dirk Frettlöh

Appeared In: Geometriae Dedicacta 162 (2013) 271-282

http://link.springer.com/article/10.1007 ...http://arxiv.org/abs/0905.4048

Focus Area 1: High-complexity Geometry Perfect colourings of the rings of cyclotomic integers of class number one are studied. It is shown that all colourings induced by ideals (q) are chirally perfect, and vice versa. A necessary and sufficient condition for a colouring to be perfect is obtained, depending on the factorisation of q. This result yields the colour symmetry group H in general. Furthermore, the colour preserving group K is determined in all but finitely many cases. An application to colourings of quasicrystals is given.

Turán numbers for K(s,t)-free graphs: topological obstructions and algebraic constructions

Pavle Blagojević, Boris Bukh, Roman Karasev

Appeared In: Israel Journal of Mathematics, October 2013, Volume 197, Issue 1, pp 199-214

http://link.springer.com/article/10.1007 ...

Focus Area 3: Topological connectivity and diameter of Discrete Structures We show that every hypersurface in ℝ s × ℝ s contains a large grid, i.e., the set of the form S × T, with S, T ⊂ ℝ s . We use this to deduce that the known constructions of extremal K 2,2-free and K 3,3-free graphs cannot be generalized to a similar construction of K s,s-free graphs for any s ≥ 4. We also give new constructions of extremal K s,t -free graphs for large t.

Generic combinatorial rigidity of periodic frameworks

Justin Malestein, Louis Theran

Appeared In: Advances in Mathematics, 233(1), 291–331, 2013.

http://arxiv.org/abs/1008.1837http://www.sciencedirect.com/science/art ...

- Focus Area 1: High-complexity Geometry - We give a combinatorial characterization of generic minimal rigidity for planar periodic frameworks. The characterization is a true analogue of the Maxwell-Laman Theorem from rigidity theory: it is stated in terms of a finite combinatorial object and the conditions are checkable by polynomial time combinatorial algorithms. To prove our rigidity theorem we introduce and develop periodic direction networks and Z2-graded-sparse colored graphs.

A problem related to Barany-Grünbaum conjecture

Pavle Blagojević, Aleksandra Dimitrijević Blagojević

Appeared In: Filomat 27:1 (2013), 103-107

http://www.pmf.ni.ac.rs/pmf/publikacije/ ...

Focus Area 3: Topological connectivity and diameter of Discrete Structures

Infinitesimal rigidity of smooth convex surfaces through the second derivative of the Hilbert-Einstein functional

Ivan Izmestiev

Appeared In: Dissertationes Math., to appear

http://arxiv.org/abs/1105.5067http://journals.impan.gov.pl/dm/all.html

Focus Area 1: High-complexity Geometry The paper is centered around a new proof of the infinitesimal rigidity of smooth closed surfaces with everywhere positive Gauss curvature. We use a reformulation that replaces deformation of an embedding by deformation of the metric inside the body bounded by the surface. The proof is obtained by studying derivatives of the Hilbert-Einstein functional with boundary term. This approach is in a sense dual to proving the Gauss infinitesimal rigidity, that is rigidity with respect to the Gauss curvature parametrized by the Gauss map, by studying derivatives of the volume bounded by the surface. We recall that Blaschke's classical proof of the infinitesimal rigidity is also related to the Gauss infinitesimal rigidity, but in a different way: while Blaschke uses Gauss rigidity of the same surface, we use the Gauss rigidity of the polar dual. In the spherical and in the hyperbolic-de Sitter space, there is a perfect duality between the Hilbert-Einstein functional and the volume, as well as between both kinds of rigidity. We also indicate directions for future research, including the infinitesimal rigidity of convex cores of hyperbolic 3--manifolds.

Extensions of theorems of Rattray and Makeev

Pavle Blagojević, Roman Karasev

Appeared In: Topological Methods in Nonlinear Analysis, Vol. 40, No. 1, 2012, 189-214

http://www.tmna.ncu.pl/htmls/archives/vo ...http://arxiv.org/pdf/1011.0869

Focus Area 3: Topological connectivity and diameter of Discrete Structures We consider extensions of the Rattray theorem and two Makeev's theorems, showing that they hold for several maps, measures, or functions simultaneously, when we consider orthonormal $k$-frames in $\R^n$ instead of orthonormal basis (full frames). We also present new results on simultaneous partition of several measures into parts by $k$ mutually orthogonal hyperplanes. In the case $k=2$ we relate the Rattray and Makeev type results with the well known embedding problem for projective spaces.

Selfdual substitutions in dimension One

Valérie Berthé, Dirk Frettlöh, Victor Sirvent

Appeared In: European Journal of Combinatorics 33 (2012) 981-1000

http://www.sciencedirect.com/science/art ...http://arxiv.org/pdf/1108.5053v2

Focus Area 1: High-complexity Geometry There are several notions of the ‘dual’ of a word/tile substitution. We show that the most common ones are equivalent for substitutions in dimension one, where we restrict ourselves to the case of two letters/tiles. Furthermore, we obtain necessary and sufficient arithmetic conditions for substitutions being selfdual in this case. Since many connections between the different notions of word/tile substitution are discussed, this paper may also serve as a survey paper on this topic.

Foldable triangulations of lattice Polygons

Michael Joswig, Günter M. Ziegler

Appeared In: American Math. Monthly, to appear

http://arxiv.org/abs/1207.6865

Focus Area 1: High-complexity Geometry 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".

Convex equipartitions via equivariant obstruction theory

Pavle V. M. Blagojević, Günter M. Ziegler

Appeared In: Israel J. Math, to appear

http://arxiv.org/abs/1202.5504

Focus Area 3: Topological connectivity and diameter of Discrete Structures We describe a regular cell complex model for the configuration space F(\R^d,n). Based on this, we use equivariant obstruction theory in order 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. For a generalization of the conjecture we get a complete answer: It holds IF AND ONLY IF n is a prime power

Realizing the associahedron: Mysteries and questions

Cesar Ceballos, Günter M. Ziegler

Appeared In: “Associahedra, Tamari Lattices and Related Structures”, Tamari Memorial Festschrift Progress in Mathematics, Vol. 299, Springer Basel 2012, 119-127;

http://arxiv.org/abs/1110.4059http://link.springer.com/chapter/10.1007 ...

Focus Area 1: High-complexity Geometry 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.

Discrete Morse Theory for manifolds with boundary

Bruno Benedetti

Appeared In: Transactions of the AMS 364 (2012), 6631-6670

http://arxiv.org/pdf/1007.3175http://www.ams.org/journals/tran/2012-36 ...

We introduce a version of discrete Morse theory specific for manifolds with boundary. The idea is to consider Morse functions for which all boundary cells are critical. We obtain ``Relative Morse Inequalities'' relating the homology of the manifold to the number of interior critical cells. We also derive a Ball Theorem, in analogy to Forman's Sphere Theorem. The main corollaries of our work are: For each and for each , there is a PL -sphere on which any discrete Morse function has more than critical -cells. (This solves a problem by Chari.) Focus Area 3: Topological connectivity and diameter of Discrete Structures For fixed and , there are exponentially many combinatorial types of simplicial -manifolds (counted with respect to the number of facets) that admit discrete Morse functions with at most critical interior -cells. (This connects discrete Morse theory to enumerative combinatorics/ discrete quantum gravity.) The barycentric subdivision of any simplicial constructible -ball is collapsible. (This ``almost'' solves a problem by Hachimori.) Every constructible ball collapses onto its boundary minus a facet. (This improves a result by the author and Ziegler.) Any -ball with a knotted spanning edge cannot collapse onto its boundary minus a facet. (This strengthens a classical result by Bing and a recent result by the author and Ziegler.)

Inscribable stacked polytopes

Bernd Gonska, Günter M. Ziegler

Appeared In: Advances in Geometry, to appear

http://arxiv.org/abs/1111.5322

Focus Area 2: Delaunay Geometry 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.

Spectral sequences in combinatorial geometry: Cheeses, inscribed sets, and Borsuk–Ulam type theorems

Pavle Blagojević, Aleksandra Dimitrijević Blagojević,John McCleary

Appeared In: Topology and its Applications Volume 158, Issue 15, 15 September 2011, Pages 1920–1936

Focus Area 3: Topological connectivity and diameter of Discrete Structures Algebraic topological methods are especially well suited for determining the non-existence of continuous mappings satisfying certain properties. In combinatorial problems it is sometimes possible to define a mapping from a space X of configurations to a Euclidean space Rm in which a subspace, a discriminant, often an arrangement of linear subspaces A, expresses a target condition on the configurations. Add symmetries of all these data under a group G for which the mapping is equivariant. If we remove the discriminant from Rm, we can pose the problem of the existence of an equivariant mapping from X to the complement of the discriminant in Rm. Algebraic topology may sometimes be applied to show that no such mapping exists, and hence the image of the original equivariant mapping must meet the discriminant. We introduce a general framework, based on a comparison of Leray–Serre spectral sequences. This comparison can be related to the theory of the Fadell–Husseini index. We apply the framework to: • solve a mass partition problem (antipodal cheeses) in Rd, • determine the existence of a class of inscribed 5-element sets on a deformed 2-sphere, • obtain two different generalizations of the theorem of Dold for the non-existence of equivariant maps which generalizes the Borsuk–Ulam theorem

A tight colored Tverberg theorem for maps to manifolds

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

Appeared In: Topology and its Applications, Volume 158, Issue 12, 1 August 2011, Pages 1445–1452

http://www.sciencedirect.com/science/art ...

Focus Area 3: Topological connectivity and diameter of Discrete Structures We prove that any continuous map of an N-dimensional simplex ΔN with colored vertices to a d-dimensional manifold M must map r points from disjoint rainbow faces of ΔN to the same point in M: For this we have to assume that N⩾(r−1)(d+1), no r vertices of ΔN get the same color, and our proof needs that r is a prime. A face of ΔN is a rainbow face if all vertices have different colors. This result is an extension of our recent “new colored Tverberg theorem”, the special case of M=Rd. It is also a generalization of Volovikovʼs 1996 topological Tverberg theorem for maps to manifolds, which arises when all color classes have size 1 (i.e., without color constraints); for this special case Volovikovʼs proof, as well as ours, works when r is a prime power.

The ideal-valued index for a dihedral group action, and mass partition by two hyperplanes

Pavle Blagojević, Günter M. Ziegler

Appeared In: Topology and its Applications Volume 158, Issue 12, 1 August 2011, Pages 1326–1351

http://www.sciencedirect.com/science/art ...

Focus Area 3: Topological connectivity and diameter of Discrete Structures

The Bárány–Larman conjecture and the colored Tverberg theorems

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

Appeared In: Mathematisches Forschungsinstitut Oberwolfach, Topological and Geometric Combinatorics, Report No. 08/2011, pages 358-361

Focus Area 3: Topological connectivity and diameter of Discrete Structures

On locally constructible spheres and balls

Bruno Benedetti, Günter M. Ziegler

Appeared In: Acta Mathematica June 2011, Volume 206, Issue 2, pp 205-243

http://link.springer.com/article/10.1007 ...

Focus Area 3: Topological connectivity and diameter of Discrete Structures 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 constructibility, and obtain hierarchies of such properties for simplicial balls and spheres. The main corollaries from this study are: – Not all simplicial 3-spheres are locally constructible. (This solves a problem by Durhuus and Jonsson.) There are only exponentially many shellable simplicial 3-spheres with given number of facets. (This answers a question by Kalai.) – All simplicial constructible 3-balls are collapsible. (This answers a question by Hachimori.) – Not every collapsible 3-ball collapses onto its boundary minus a facet. (This property appears in papers by Chillingworth and Lickorish.)

Optimal bounds for a colorful Tverberg-Vrecica type problem

Pavle Blagojević, Benjamin Matschke, Günter M. Ziegler

Appeared In: Advances in Mathematics, Volume 226, Issue 6, 1 April 2011, Pages 5198–5215

http://www.sciencedirect.com/science/art ...http://arxiv.org/abs/0911.2692

Focus Area 3: Topological connectivity and diameter of Discrete Structures We prove the following optimal colorful Tverberg-Vrecica type transversal theorem: For prime r and for any k+1 colored collections of points C^l of size |C^l|=(r-1)(d-k+1)+1 in R^d, where each C^l is a union of subsets (color classes) C_i^l of size smaller than r, l=0,...,k, there are partition of the collections C^l into colorful sets F_1^l,...,F_r^l such that there is a k-plane that meets all the convex hulls conv(F_j^l), under the assumption that r(d-k) is even or k=0. Along the proof we obtain three results of independent interest: We present two alternative proofs for the special case k=0 (our optimal colored Tverberg theorem (2009)), calculate the cohomological index for joins of chessboard complexes, and establish a new Borsuk-Ulam type theorem for (Z_p)^m-equivariant bundles that generalizes results of Volovikov (1996) and Zivaljevic (1999).

Optimal elliptic Sobolev regularity near three-dimensional, multi-material Neumann vertices

Robert Haller-Dintelmann, Wolfgang Höppner, Hans-Christoph Kaiser, Joachim Rehberg, Günter M. Ziegler

Appeared In: Functional Analysis and its Applications, to appear

http://opus4.kobv.de/opus4-matheon/files ...

Focus Area 2: Delaunay Geometry

A tight colored Tverberg theorem for maps to manifolds (extended abstract)

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

Appeared In: In Proc. FPSAC 2011 (Reykjavík, Iceland), Discrete Mathematics and Theoretical Computer Science (DMTCS), Vol. AO, http://www.dmtcs.org, page 183–190, 2011.

http://www.dmtcs.org/dmtcs-ojs/index.php ...

Focus Area 3: Topological connectivity and diameter of Discrete Structures Any continuous map of an N-dimensional simplex ΔN with colored vertices to a d-dimensional manifold M must map r points from disjoint rainbow faces of ΔN to the same point in M, assuming that N≥(r-1)(d+1), no r vertices of ΔN get the same color, and our proof needs that r is a prime. A face of ΔN is called a rainbow face if all vertices have different colors. This result is an extension of our recent ``new colored Tverberg theorem'', the special case of M=ℝd. It is also a generalization of Volovikov's 1996 topological Tverberg theorem for maps to manifolds, which arises when all color classes have size 1 (i.e., without color constraints); for this special case Volovikov's proofs, as well as ours, work when r is a prime power.

Turán numbers for K(s,t)-free graphs: topological obstructions and algebraic constructions (extended abstract)

Pavle Blagojević, Boris Bukh, Roman Karasev

Appeared In: Electronic Notes in Discrete Mathematics 38 (2011) 141-145, The Sixth European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2011

http://www.sciencedirect.com/science/art ...http://arxiv.org/abs/1108.5254

Focus Area 3: Topological connectivity and diameter of Discrete Structures We show that every hypersurface in $\R^s\times \R^s$ contains a large grid, i.e., the set of the form $S\times T$, with $S,T\subset \R^s$. We use this to deduce that the known constructions of extremal $K_{2,2}$-free and $K_{3,3}$-free graphs cannot be generalized to a similar construction of $K_{s,s}$-free graphs for any $s\geq 4$. We also give new constructions of extremal $K_{s,t}$-free graphs for large $t$.