Search

We introduce the Dyck path triangulation of the cartesian product of two simplices $\Delta_{n-1}\times\Delta_{n-1}$. The maximal simplices of this triangulation are given by Dyck paths, and its construction naturally generalizes to produce triangulations of $\Delta_{r\ n-1}\times\Delta_{n-1}$ using rational Dyck paths. Our study of the Dyck path triangulation is motivated by extendability problems of partial triangulations of products of two simplices. We show that whenever$m\geq k>n$, any triangulations of $\Delta_{m-1}^{(k-1)}\times\Delta_{n-1}$ extends to a unique triangulation of $\Delta_{m-1}\times\Delta_{n-1}$. Moreover, with an explicit construction, we prove that the bound $k>n$ is optimal. We also exhibit interpretations of our results in the language of tropical oriented matroids, which are analogous to classical results in oriented matroid theory., Nous introduisons la triangulation par chemins de Dyck du produit cartésien de deux simplexes $\Delta_{n-1}\times\Delta_{n-1}$. Les simplexes maximaux de cette triangulation sont donnés par des chemins de Dyck, et cette construction se généralise de façon naturelle pour produire des triangulations $\Delta_{r\ n-1}\times\Delta_{n-1}$ qui utilisent des chemins de Dyck rationnels. Notre étude de la triangulation par chemins de Dyck est motivée par des problèmes de prolongement de triangulations partielles de produits de deux simplexes. On montre que $m\geq k>n$ alors toute triangulation de $\Delta_{m-1}^{(k-1)}\times\Delta_{n-1}$ se prolonge en une unique triangulation de $\Delta_{m-1}\times\Delta_{n-1}$. De plus, avec une construction explicite, nous montrons que la borne $k>n$ est optimale. Nous présentons aussi des interprétations de nos résultats dans le langage des matroïdes orientés tropicaux, qui sont analogues aux résultats classiques de la théorie des matroïdes orientés.

We study a natural generalization of the noncrossing relation between pairs of elements in $[n]$ to $k$-tuples in $[n]$. We show that the flag simplicial complex on $\binom{[n]}{k}$ induced by this relation is a regular, unimodular and flag triangulation of the order polytope of the poset given by the product $[k] \times [n-k]$ of two chains, and it is the join of a simplex and a sphere (that is, it is a Gorenstein triangulation). This shows the existence of a flag simplicial polytope whose Stanley-Reisner ideal is an initial ideal of the Graßmann-Plücker ideal, while previous constructions of such a polytope did not guaranteed flagness. The simplicial complex and the polytope derived from it naturally reflect the relations between Graßmannians with different parameters, in particular the isomorphism $G_{k,n} \cong G_{n-k,n}$. This simplicial complex is closely related to the weak separability complex introduced by Zelevinsky and Leclerc., Nous étudions une généralisation naturelle de la relation entre les paires d’éléments non-croisés de $[n]$ et les $k$-uplets de $[n]$. Nous montrons que le complexe simplicial de drapeau sur $\binom{[n]}{k}$ induit par cette relation est une triangulation régulière, unimodulaire et de drapeau du polytope d’ordre de l’ensemble partiellement ordonné obtenu par le produit $[k] \times [n-k]$ des deux chaînes, et c’est la jointure d’un simplexe et une sphère (c’est-à-dire qu’elle est une triangulation de Gorenstein). Cela montre l’existence d’un polytope simplicial de drapeau dont l’idéal de Stanley-Reisner est un idéal initial de l’idéal de Graßmann-Plücker, tandis que les constructions précédentes d’un tel polytope ne garantissaient pas la propriété de drapeau. Le complexe simplicial et le polytope qui en découle reflètent naturellement les relations entre les Grassmanniens avec différents paramètres, en particulier l’isomorphisme $G_{k,n} \cong G_{n-k,n}$. Ce complexe simplicial est étroitement lié au complexe de séparabilité faible étudié par Zelevinskyet Leclerc.

We present a very simple explicit technique to generate a large family of point configurations with neighborly Delaunay triangulations. This proves that there are superexponentially many combinatorially distinct neighborly $d$-polytopes with $n$ vertices that admit realizations inscribed on the sphere. These are the first examples of inscribable neighborly polytopes that are not cyclic polytopes, and provide the current best lower bound for the number of combinatorial types of inscribable polytopes (and thus also of Delaunay triangulations). It coincides with the current best lower bound for the number of combinatorial types of polytopes., Nous présentons une technique explicite simple pour générer une large famille de configurations de points dont les triangulations de Delaunay sontneighborly. Cela prouve que le nombre de $d$-polytopes combinatoirement distincts avec $n$ sommets et admettant une réalisation inscrite sur la sphère est surexponentiel. Ce sont les premiers exemples de polytopes inscriptibles neighborly qui ne sont pas des polytopes cycliques et ils donnent la meilleure borne inférieure actuelle pour le nombre de types combinatoires de polytopes inscriptibles (et donc aussi de triangulations de Delaunay). Cette borne coïncide avec la meilleure borne inférieure actuelle pour le nombre de types combinatoires de polytopes.

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., Étant donné un simplex $Δ _N$ de dimension $N$ ayant les sommets colorés, une face de $Δ _N$ est dite arc-en-ciel, si tous les sommets de cette face ont des couleurs différentes. Toute fonction continue d'un simplex $Δ _N$ de dimension $N$ aux sommets colorés vers une variété $d$-dimensionnelle $M$ doit envoyer $r$ points provenant de faces arc-en-ciel disjointes de $Δ _N$ au mêmes points dans $M$ ; en supposant que $N ≥(r-1)(d +1)$, un ensemble de $r$ sommets de $Δ _N$ doit être coloré à l'aide d'au moins deux couleurs. Notre démonstration requiert que $r$ soit un nombre premier. Ce résultat est une extension de notre "nouveau théorème de Tverberg coloré'', le cas particulier où $M = ℝ^d$. Il est également une généralisation du théorème de Tverberg topologique de Volovikov datant de 1996, pour les fonctions vers une variété, dont les classes de couleurs sont de taille 1 (c'est-à-dire sans contraintes de couleur). Dans ce cas particulier, la démonstration de Volovikov et la nôtre fonctionnent lorsque r est une puissance d'un premier.

The polymake software system deals with convex polytopes and related objects from geometric combinatorics. This note reports on a new implementation of a subclass for lattice polytopes. The features displayed are enabled by recent changes to the polymake core, which will be discussed briefly., 12 pages, 1 figure

Schrijver introduced the stable Kneser graph $SG_{n,k}, n \geq 1, k \geq 0$. This graph is a vertex critical graph with chromatic number $k+2$, its vertices are certain subsets of a set of cardinality $m=2n+k$. Björner and de Longueville have shown that its box complex is homotopy equivalent to a sphere, $\mathrm{Hom}(K_2,SG_{n,k}) \simeq \mathbb{S}^k$. The dihedral group $D_{2m}$ acts canonically on $SG_{n,k}$. We study the $D_{2m}$ action on $\mathrm{Hom}(K_2,SG_{n,k})$ and define a corresponding orthogonal action on $\mathbb{R}^{k+1} \supset \mathbb{S}^k$. We establish a close equivariant relationship between the graphs $SG_{n,k}$ and Borsuk graphs of the $k$-sphere and use this together with calculations in the $\mathbb{Z}_2$-cohomology ring of $D_{2m}$ to tell which stable Kneser graphs are test graphs in the sense of Babson and Kozlov. The graphs $SG_{2s,4}$ are test graphs, i.e. for every graph $H$ and $r \geq 0$ such that $\mathrm{Hom}(SG_{2s,4},H)$ is $(r-1)$-connected, the chromatic number $\chi (H)$ is at least $r+6$. On the other hand, if $k \notin \{0,1,2,4,8\}$ and $n \geq N(k)$ then $SG_{n,k}$ is not a homotopy test graph, i.e. there are a graph $G$ and an $r \geq 1$ such that $\mathrm{Hom}(SG_{n,k}, G)$ is $(r-1)$-connected and $\chi (G) < r+k+2$. The latter result also depends on a new necessary criterion for being a test graph, which involves the automorphism group of the graph., Schrijver a défini le graphe de Kneser stable $SG_{n,k}$, avec $n \geq 1$ et $k \geq 0$. Le graphe $SG_{n,k}$ est un graphe critique (par rapport aux sommets) de nombre chromatique $k+2$, dont les sommets correspondent à certains sous-ensembles d'un ensemble de cardinalité $m=2n+k$. Björner et de Longueville ont démontré que son complexe de boîtes et la sphère sont homotopiquement équivalents, c'est-à-dire $\mathrm{Hom}(K_2,SG_{n,k}) \simeq \mathbb{S}^k$. Le groupe diédral $D_{2m}$ agit sur $SG_{n,k}$ canoniquement. Nous étudions l'action de $D_{2m}$ sur $\mathrm{Hom}(K_2,SG_{n,k})$ et nous définissons une action orthogonale correspondante sur $\mathbb{R}^{k+1} \supset \mathbb{S}^k$. Par ailleurs, nous fournissons une relation équivariante étroite entre les graphes $SG_{n,k}$ et les graphes de Borsuk de la sphère de dimension $k$. Utilisant cette relation et certains calculs dans l'anneau de cohomologie de $D_{2m}$ sur $\mathbb{Z}_2$, nous décrivons quels graphes de Kneser stables sont des graphes de tests selon la notion de Babson et Kozlov. Les graphes $SG_{2s,4}$ sont des graphes de tests, c'est-à-dire que pour tout $H$ et $r \geq 0$ tels que $\mathrm{Hom}(SG_{2s,4},H)$ est $(r-1)$-connexe, le nombre chromatique $\chi (H)$ est au moins $r+6$. D'autre part, si $k \notin \{0,1,2,4,8\}$ et $n \geq N(k)$, alors $SG_{n,k}$ n'est pas un graphe de tests d'homologie: il existe un graphe $G$ et un entier $r \geq 1$ tels que $\mathrm{Hom}(SG_{n,k}, G)$ est $(r-1)$-connexe et $\chi (G) < r+k+2$. Ce dernier résultat dépend d'un nouveau critère nécessaire pour être un graphe de tests, qui implique le groupe d'automorphismes du graphe.