Torsten Mütze
YOU?
Author Swipe
View article: Order Dimension, Grids, and Products
Order Dimension, Grids, and Products Open
Interested in the dimension of the face lattices of d -dimensional grids, we are led to the study of fences and their products. This yields a characterization of generalized fences: F is a generalized fence if and only if $$\dim (P\times F…
View article: Combinatorial generation via permutation languages. VII. Supersolvable hyperplane arrangements
Combinatorial generation via permutation languages. VII. Supersolvable hyperplane arrangements Open
For an arrangement $\mathcal{H}$ of hyperplanes in $\mathbb{R}^n$ through the origin, a region is a connected subset of $\mathbb{R}^n\setminus\mathcal{H}$. The graph of regions $G(\mathcal{H})$ has a vertex for every region, and an edge be…
View article: Disproving two conjectures on the Hamiltonicity of Venn diagrams
Disproving two conjectures on the Hamiltonicity of Venn diagrams Open
In 1984, Winkler conjectured that every simple Venn diagram with $n$ curves can be extended to a simple Venn diagram with $n+1$ curves. His conjecture is equivalent to the statement that the dual graph of any simple Venn diagram has a Hami…
View article: Listing faces of polytopes
Listing faces of polytopes Open
This paper investigates the problem of listing faces of combinatorial polytopes, such as hypercubes, permutahedra, associahedra, and their generalizations. Firstly, we consider the face lattice, which is the inclusion order of all faces of…
View article: Combinatorial Generation via Permutation Languages. IV. Elimination Trees
Combinatorial Generation via Permutation Languages. IV. Elimination Trees Open
An elimination tree for a connected graph \(G\) is a rooted tree on the vertices of \(G\) obtained by choosing a root \(x\) and recursing on the connected components of \(G-x\) to produce the subtrees of \(x\) . Elimination trees appear in…
View article: Listing spanning trees of outerplanar graphs by pivot-exchanges
Listing spanning trees of outerplanar graphs by pivot-exchanges Open
We prove that the spanning trees of any outerplanar triangulation $G$ can be listed so that any two consecutive spanning trees differ in an exchange of two edges that share an end vertex. For outerplanar graphs $G$ with faces of arbitrary …
View article: Combinatorial generation via permutation languages. VI. Binary trees
Combinatorial generation via permutation languages. VI. Binary trees Open
In this paper we propose a notion of pattern avoidance in binary trees that generalizes the avoidance of contiguous tree patterns studied by Rowland and non-contiguous tree patterns studied by Dairyko, Pudwell, Tyner, and Wynn. Specificall…
View article: Flips in colorful triangulations
Flips in colorful triangulations Open
The associahedron is the graph $\mathcal{G}_N$ that has as nodes all triangulations of a convex $N$-gon, and an edge between any two triangulations that differ in a flip operation. A flip removes an edge shared by two triangles and replace…
View article: Graphs that admit a Hamilton path are cup-stackable
Graphs that admit a Hamilton path are cup-stackable Open
Fay, Hurlbert and Tennant recently introduced a one-player game on a finite connected graph $G$, which they called cup stacking. Stacks of cups are placed at the vertices of $G$, and are transferred between vertices via stacking moves, sub…
View article: Matchings in hypercubes extend to long cycles
Matchings in hypercubes extend to long cycles Open
The $d$-dimensional hypercube graph $Q_d$ has as vertices all subsets of $\{1,\ldots,d\}$, and an edge between any two sets that differ in a single element. The Ruskey-Savage conjecture asserts that every matching of $Q_d$, $d\ge 2$, can b…
View article: Hamiltonicity of Schrijver graphs and stable Kneser graphs
Hamiltonicity of Schrijver graphs and stable Kneser graphs Open
For integers $k\geq 1$ and $n\geq 2k+1$, the Schrijver graph $S(n,k)$ has as vertices all $k$-element subsets of $[n]:=\{1,2,\ldots,n\}$ that contain no two cyclically adjacent elements, and an edge between any two disjoint sets. More gene…
View article: On Hamilton cycles in graphs defined by intersecting set systems
On Hamilton cycles in graphs defined by intersecting set systems Open
In 1970 Lovász conjectured that every connected vertex-transitive graph admits a Hamilton cycle, apart from five exceptional graphs. This conjecture has recently been settled for graphs defined by intersecting set systems, which feature pr…
View article: Traversing combinatorial 0/1-polytopes via optimization
Traversing combinatorial 0/1-polytopes via optimization Open
In this paper, we present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets and polytopes. Our method relies on a simple and versa…
View article: Combinatorial Gray Codes — an Updated Survey
Combinatorial Gray Codes — an Updated Survey Open
A combinatorial Gray code for a class of objects is a listing that contains each object from the class exactly once such that any two consecutive objects in the list differ only by a `small change'. Such listings are known for many differe…
View article: A book proof of the middle levels theorem
A book proof of the middle levels theorem Open
We give a short constructive proof for the existence of a Hamilton cycle in the subgraph of the $(2n+1)$-dimensional hypercube induced by all vertices with exactly $n$ or $n+1$ many 1s.
View article: Kneser Graphs Are Hamiltonian
Kneser Graphs Are Hamiltonian Open
For integers k≥ 1 and n≥ 2k+1, the Kneser graph K(n,k) has as vertices all k-element subsets of an n-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Ha…
View article: Traversing combinatorial 0/1-polytopes via optimization
Traversing combinatorial 0/1-polytopes via optimization Open
In this paper, we present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets and polytopes. Our method relies on a simple and versa…
View article: On the central levels problem
On the central levels problem Open
The central levels problem asserts that the subgraph of the (2m+1)-dimensional hypercube induced by all bitstrings with at least m+1-𝓁 many 1s and at most m+𝓁 many 1s, i.e., the vertices in the middle 2𝓁 levels, has a Hamilton cycle for an…
View article: Star transposition Gray codes for multiset permutations
Star transposition Gray codes for multiset permutations Open
Given integers and , let and . An a ‐multiset permutation is a string of length that contains exactly symbols for each . In this work we consider the problem of exhaustively generating all ‐multiset permutations by star transpositions, tha…
View article: Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections
Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections Open
In this paper we propose a notion of pattern avoidance in binary trees that generalizes the avoidance of contiguous tree patterns studied by Rowland and non-contiguous tree patterns studied by Dairyko, Pudwell, Tyner, and Wynn. Specificall…
View article: Combinatorial generation via permutation languages. V. Acyclic orientations
Combinatorial generation via permutation languages. V. Acyclic orientations Open
In 1993, Savage, Squire, and West described an inductive construction for generating every acyclic orientation of a chordal graph exactly once, flipping one arc at a time. We provide two generalizations of this result. Firstly, we describe…
View article: Kneser graphs are Hamiltonian
Kneser graphs are Hamiltonian Open
For integers $k\geq 1$ and $n\geq 2k+1$, the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser gra…
View article: Combinatorial Generation via Permutation Languages. III. Rectangulations
Combinatorial Generation via Permutation Languages. III. Rectangulations Open
A generic rectangulation is a partition of a rectangle into finitely many interior-disjoint rectangles, such that no four rectangles meet in a point. In this work we present a versatile algorithmic framework for exhaustively generating a l…
View article: The Hamilton compression of highly symmetric graphs
The Hamilton compression of highly symmetric graphs Open
We say that a Hamilton cycle $C=(x_1,\ldots,x_n)$ in a graph $G$ is $k$-symmetric, if the mapping $x_i\mapsto x_{i+n/k}$ for all $i=1,\ldots,n$, where indices are considered modulo $n$, is an automorphism of $G$. In other words, if we lay …
View article: Combinatorial Gray codes-an updated survey
Combinatorial Gray codes-an updated survey Open
A combinatorial Gray code for a class of objects is a listing that contains each object from the class exactly once such that any two consecutive objects in the list differ only by a `small change'. Such listings are known for many differe…