Kolja B. Knauer

Merino-Welsh inequalities for matroids with controlled lattices of cyclic flats

Kolja Knauer, Leonardo Martínez-Sandoval, Criel Merino

Beke, Csáji, Csikvári, and Pituk showed that the Merino--Welsh quotient $Φ (M) = T_{M} (1, 1)^{2} / (T_{M} (2, 0) T_{M} (0, 2))$ can be arbitrarily large, so the multiplicative Merino-Welsh inequality…

Rings are $χ$ -bounded

Sara Asensio, Ignacio García-Marco, Kolja Knauer

We prove that there is a function $f : N \to N$ such that $χ (Γ (R)) \leq f (ω (Γ (R)))$ for the zero-divisor graph of any ring $R$ , if the clique number is finite. On the on…

Neither simpliciality nor mutation connectivity: conjectures of Las Vergnas and Cordovil-Las Vergnas fail

Qiyuan Gu, Kolja Knauer

We construct a simple rank- $7$ oriented matroid on $24$ elements with no simplicial tope, disproving the Las Vergnas simplex conjecture from 1980. We then show that the mutation gr…

Logarithmic basis number of graphs and regular matroids

Kolja Knauer

The basis number $bn (G)$ of a graph $G$ is the minimum edge-congestion of a basis of its cycle space. We prove that every finite $n$ -vertex multigraph satisfies $bn (G) = O (lo g n)$ ,…

Coloring semiminimal Cayley Graphs

Ignacio García-Marco, Kolja Knauer, Giuliamaria Menara

In 1978 Babai raised the question whether all semiminimal Cayley graphs have bounded chromatic number. In this paper we show that semiminimal Cayley graphs of abelian and generaliz…

Embracing exchange sequences and oriented matroid polyhedron diameter

Kristóf Bérczi, Kolja Knauer, Luis Pedro Montejano +1

We reduce the embracing exchange distance of bases of oriented matroids to the metric of oriented matroid polyhedra. This allows us to disprove recent conjectures of Caoduro, Khoda…

Hamiltonian connectivity of some base-cobase graphs

Leonardo Martínez-Sandoval, Kolja Knauer

There has been wide interest in understanding which properties of base graphs of matroids extend to base-cobase graphs of matroids. A significant result of Naddef and Pulleyblank (…

What is and is not inside a Cayley graph?

Kolja Knauer, Alvaro Soto Gomez

In this note we show that there is a cubic graph of girth $5$ that is not a subgraph of any minimal Cayley graph. On the other hand, we show that any Generalized Petersen Graph $G(…

math.CO2025★ 1 cited

Odd coloring graphs with linear neighborhood complexity

James Davies, Meike Hatzel, Kolja Knauer +2

We prove that any class of graphs with linear neighborhood complexity has bounded improper odd chromatic number. As a result, if $G$ is the class of all circle graphs, or…

Strong odd coloring in minor-closed classes

Miriam Goetze, Fabian Klute, Kolja Knauer +3

We show that the strong odd chromatic number on any proper minor-closed graph class is bounded by a constant. We almost determine the smallest such constant for outerplanar graphs.

Cell structure of mediangle graphs

Victor Chepoi, Anthony Genevois, Kolja Knauer

Mediangle graphs are a common generalization of median graphs (1-sekeleta of CAT(0) cube complexes) and Coxeter graphs (Cayley graphs of Coxeter systems). Answering a question moti…

Sensitivity and Hamming graphs

Sara Asensio, Yuval Filmus, Ignacio García-Marco +1

For any $m \geq 3$ we show that the Hamming graph $H (n, m)$ admits an imbalanced partition into $m$ sets, each inducing a subgraph of low maximum degree. This improves previous resul…

Girth in $GF (q)$ -representable matroids

James Davies, Meike Hatzel, Kolja Knauer +2

We prove a conjecture of Geelen, Gerards, and Whittle that for any finite field $GF (q)$ and any integer $t$ , every cosimple $GF (q)$ -representable matroid with sufficiently large gi…

Shellability of the quotient order on lattice path matroids

Carolina Benedetti, Anton Dochtermann, Kolja Knauer +1

The concept of a matroid quotient has connections to fundamental questions in the geometry of flag varieties. In previous work, Benedetti and Knauer characterized quotients in the…

math.CO2025★ 1 cited

On rigid regular graphs and a problem of Babai and Pultr

Kolja Knauer, Gil Puig i Surroca

A graph is \textit{rigid} if it only admits the identity endomorphism. We show that for every $d \geq 3$ there exist infinitely many mutually rigid $d$ -regular graphs of arbitrary od…

Partitions of planar (oriented) graphs into a connected acyclic and an independent set

Stijn Cambie, François Dross, Kolja Knauer +2

A question at the intersection of Barnette's Hamiltonicity and Neumann-Lara's dicoloring conjecture is: Can every Eulerian oriented planar graph be vertex-partitioned into two acyc…

Sensitivity of $m$ -ary functions and low degree partitions of Hamming graphs

Sara Asensio, Ignacio García-Marco, Kolja Knauer

The study of complexity measures of Boolean functions led Nisan and Szegedy to state the sensitivity conjecture in 1994, claiming a polynomial relation between degree and sensitivi…

Coloring minimal Cayley graphs

Ignacio García-Marco, Kolja Knauer

In 1978 Babai raised the question whether all minimal Cayley graphs have bounded chromatic number; in 1994 he conjectured a negative answer. In this paper we show that any minimal…

Geometry of convex geometries

Jérémie Chalopin, Victor Chepoi, Kolja Knauer

We prove that any convex geometry $A = (U, C)$ on $n$ points and any ideal $I = (U^{'}, C^{'})$ of $A$ can be realized as the intersection pat…