Kolja Knauer

Grants

• PI of the MICINN project ACoGe: PID2022-137283NB-C22: Algebraic combinatorics and its connections to geometry
• Member of the ANR project DAGDigDec: ANR-21-CE48-0012: DAGs and Digraph Decompositions
  

Events

• Organizing the Combinatorial Geometries & Geometric Combinatorics at CRM , Barcelona, October-November 2025.
• Organizing the Three Talks in Combinatorics seminar series at Universitat de Barcelona
  

Preprints and Publications

79. Shellability of the quotient order on lattice path matroids
    with Carolina Benedetti, Anton Dochtermann, and Yupeng Li
    
    • (submitted).
    
    
80. On rigid regular graphs and a problem of Babai and Pultr
    with Gil Puig i Surroca
    
    • Journal of Graph Theory (accepted).
    
    
81. Partitions of planar (oriented) graphs into a connected acyclic and an independent set
    with Stijn Cambie, François Dross, Hoang La, and Petru Valicov
    
    • (submitted).
    
    
82. Coloring minimal Cayley graphs
    with Ignacio García-Marco
    
    • European Journal of Combinatorics 125, Article ID 104108, 9 p. (2025).
    
    
83. Geometry of convex geometries
    with Jérémie Chalopin and Victor Chepoi
    
    • Discrete and Computational Geometry (accepted).
    
    
84. Oriented Matroids Today
    with Günter M. Ziegler and Laura Anderson
    
    • Dynamic Survey in the Electronic Journal of Combinatorics, #DS4, (2024).
    
    
85. Outerplanar Partial Cubes
    with Bernat Rovira Segú
    
    • Electronic Journal of the SCM, Vol. 8 Num. 1 (2023)
    
    
86. Boundedness for proper conflict-free and odd colorings
    with Andrea Jiménez, Carla Negri Lintzmayer, Martín Matamala, Juan Pablo Peña, Daniel A. Quiroz, Maycon Sambinelli, Yoshiko Wakabayashi, Weiqiang Yu, and José Zamora
    
    • (submitted)
    
    
87. On k-neighborly reorientations of oriented matroids
    with Rangel Hernández-Ortiz and Luis Pedro Montejano
    
    • European Journal of Combinatorics 118, Article ID 103938, 20 p. (2024),
    
    
88. Roudneff's Conjecture in Dimension 4
    with Rangel Hernández-Ortiz, Luis Pedro Montejano, and Manfred Scheucher
    
    • Experimental Mathematics, pages 1-5 (2024).
    
    
89. Clustered independence and bounded treewidth
    with Torsten Ueckerdt
    
    • (submitted)
    
    
90. Concepts of Dimension for Convex Geometries
    with William T. Trotter
    
    • SIAM Journal of Discrete Mathematics 38, No. 2, 1566-1585 (2024)
    
    
91. The signed Varchenko Determinant for Complexes of Oriented Matroids
    with Winfried Hochstättler and Sophia Keip
    
    • Combinatorica (accepted)
    
    
92. On endomorphism universality of sparse graph classes
    with Gil Puig i Surroca
    
    • (submitted)
    
    
93. Lattice path matroids and quotients
    with Carolina Benedetti-Velásquez
    
    • Combinatorica 44, No. 3, 621-650 (2024)
    
    
94. Beyond symmetry in generalized Petersen graphs
    with Ignacio García-Marco
    
    • Journal of Algebraic Combinatorics 59, No. 2, 331-357 (2024)
    
    
95. Kirchberger's Theorem for Complexes of Oriented Matroids
    with Winfried Hochstättler and Sophia Keip
    
    • Linear Algebra and Its Applications 693, 288-296 (2024)
    
    
96. Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth
    with Hoang La and Petru Valicov
    
    • Electronic Journal of Combinatorics, 29, 4, P4.16, 25 p. (2022).
    
    
97. On lattice path matroid polytopes: alcoved triangulations and snake decompositions
    with Carolina Benedetti-Velásquez and Jerónimo Valencia
    
    • (submitted)
    
    
98. Labeled sample compression schemes for complexes of oriented matroids
    with Victor Chepoi and Manon Philibert
    
    • Journal of Computer and System Sciences 144, Article ID 103543, 19 p. (2024).
    
    
99. On monoid graphs
    with Gil Puig i Surroca
    
    • Mediterranean Journal of Mathematics, 20, 1, 26, 24 p. (2023).
    
    
100. On the dichromatic number of surfaces
     with Pierre Aboulker, Frédéric Havet, and Clément Rambaud
     
     • Electronic Journal of Combinatorics, 29 (1), p1.30, (2022)
     • Extended Abstracts EuroComb 2021, Trends in Mathematics, 14, (2021)
     
     
101. Finitary affine oriented matroids
     with Emanuele Delucchi
     
     • Discrete and Computational Geometry 73, No. 1, 208-257 (2025).
     • Sémin. Lothar. Comb. 85B, Article 48, 12 p. FPSAC (2021)
     
     
102. Colouring bottomless rectangles and arborescences
     with Jean Cardinal, Piotr Micek, Dömötör Pálvölgyi, Torsten Ueckerdt, and Narmada Varadarajan
     
     • Computational Geometry: Theory and Applications 115, 102020, 17 p. (2023).
     
     
103. On sensitivity in bipartite Cayley graphs
     with Ignacio García-Marco
     
     • Journal of Combinatorial Theory, Series B, 154, pages 211-238 (2022)
     
     
104. Ample completions of oriented matroids and complexes of uniform oriented matroids
     with Victor Chepoi and Manon Philibert
     
     • SIAM Journal of Discrete Mathematics, 36(1), pages 509-535, (2022)
     
     
105. Plattenbauten: Touching Rectangles in Space
     with Stefan Felsner and Torsten Ueckerdt
     
     • Graph-Theoretic Concepts in Computer Science, WG2020, 13, (2020)
     
     
106. Corners and simpliciality in oriented matroids and partial cubes
     with Tilen Marc
     
     • European Journal of Combinatorics 112, 103714, 27 p. (2023).
     
     
107. Cayley posets
     with Ignacio García-Marco and Guillaume Mercui-Voyant
     
     • Mediterranean Journal of Mathematics, 17(186), (2020)
     
     
108. Enumerating k-arc-connected orientations
     with Sarah Blind and Petru Valicov
     
     • Algorithmica, 82, pages 3588-3603 (2020)
     
     
109. On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs
     with Sandi Klavžar and Tilen Marc
     
     • MATCH Commun. Math. Comput. Chem., 86, pages 327-342, (2021)
     
     
110. Two-dimensional partial cubes
     with Victor Chepoi and Manon Philibert
     
     • Electronic Journal of Combinatorics, 27 (40), p3.29, (2020)
     
     
111. Complete Acyclic Colorings
     with Stefan Felsner, Winfried Hochstättler, and Raphael Steiner
     
     • Electronic Journal of Combinatorics, 27 (2), p2.40, (2020)
     
     
112. Flip distances between graph orientations
     with Oswin Aichholzer, Jean Cardinal, Tony Huynh, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber
     
     • Algorithmica, 83, pages 116-143 (2021)
     • Graph-Theoretic Concepts in Computer Science, WG2019, pages 120-134, (2019)
     
     
113. Abelian doppelsemigroups
     with Anatolii V. Zhuchok
     
     • Algebra and Discrete Mathematics, 26 (2), pages 290-304, (2019)
     
     
114. The queue-number of posets of bounded width or height
     with Piotr Micek and Torsten Ueckerdt
     
     • Lecture Notes in Computer Science 11282, GD 2018, pages 200-212 (2018)
     
     
115. The interval number of a planar graph is at most three
     with Guillaume Guégan, Jonathan Rollin and Torsten Ueckerdt
     
     • Journal of Combinatorial Theory, Series B, 146, pages 61-67, (2021)
     
     
116. Chomp on generalized Kneser graphs and others
     with Ignacio García-Marco and Luis Pedro Montejano
     
     • International Journal of Game Theory, 50, pages 603-621 (2021)
     
     
117. Cuts in matchings of 3-connected cubic graphs
     with Petru Valicov
     
     • European Journal of Combinatorics, 76, pages 27-36, (2019)
     
     
118. Computing metric hulls in graphs
     with Nicolas Nisse
     
     • Discrete Mathematics & Theoretical Computer Science, 21 (1), ICGT 2018, (2019)
     
     
119. Decomposing 4-connected planar triangulations into two trees and one path
     with Torsten Ueckerdt
     
     • Journal of Combinatorial Theory Series B, 134, pages 88-109, (2019)
     
     
120. Chomp on numerical semigroups
     with Ignacio García-Marco
     
     • Algebraic Combinatorics, 1 (3), pages 371-394, (2018)
     
     
121. On tope graphs of complexes of oriented matroids
     with Tilen Marc
     
     • Discrete & Computational Geometry, 63 (2), pages 377-417, (2020)
     
     
122. On lattice path matroid polytopes: integer points and Ehrhart polynomial
     with Leonardo Martínez-Sandoval and Jorge Luis Ramírez Alfonsín
     
     • Discrete & Computational Geometry, 60 (3), pages 698-719 (2018)
     
     
123. A correction of a characterization of planar partial cubes
     with Rémi Desgranges
     
     • Discrete Mathematics, 340 (6), pages 1151-1153 (2017)
     
     
124. Hypercellular graphs: partial cubes without Q₃^- as partial cube minor
     with Victor Chepoi and Tilen Marc
     
     • Discrete Mathematics, 343 (4), (2020)
     
     
125. A Tutte polynomial inequality for lattice path matroids
     with Leonardo Martínez-Sandoval and Jorge Luis Ramírez Alfonsín
     
     • Advances in Applied Mathematics, 94, pages 23-38 (2018)
     
     
126. COMs: Complexes of Oriented Matroids
     with Hans-Jürgen Bandelt and Victor Chepoi
     
     • Journal of Combinatorial Theory Series A, 156, pages 195-237 (2018)
     
     
127. Graph Drawings with One Bend and Few Slopes
     with Bartosz Walczak
     
     • Lecture Notes in Computer Science, 9644, pages 549-561, LATIN, (2016)
     
     
128. Drawing graphs with vertices and edges in convex position
     with Ignacio García-Marco
     
     • Computational Geometry: Theory and Applications 58, pages 25-33, (2016)
     • Lecture Notes in Computer Science, 9411, pages 348-359, GD, (2015)
     
     
129. Planar digraphs without large acyclic sets
     with Petru Valicov and Paul S. Wenger
     
     • Journal of Graph Theory, 85 (1), pages 288-291, (2017)
     
     
130. On the structure of Schnyder woods on orientable surfaces
     with Daniel Gonçalves and Benjamin Lévêque
     
     • Journal of Computational Geometry, 10 (1), pages 127-163, (2019)
     
     
131. Orienting Triangulations
     with Boris Albar and Daniel Gonçalves
     
     • Journal of Graph Theory, 83 (4), pages 392-405, (2016)
     • Proceedings EuroCG, (2015)
     
     
132. How many circuits determine an oriented matroid?
     with Luis Pedro Montejano and Jorge Luis Ramírez Alfonsín
     
     • Combinatorica, 38 (4), pages 861-885, (2018)
     
     
133. Intersection Graphs of L-Shapes and Segments in the Plane
     with Stefan Felsner, George B. Mertzios, and Torsten Ueckerdt
     
     • Discrete Applied Mathematics, 206, pages 48-55, (2016)
     • Lecture Notes in Computer Science, 8635, pages 299-310, MFCS, (2014)
     
     
134. Online and Size Anti-Ramsey Numbers
     with Maria Axenovich, Judith Stumpp, and Torsten Ueckerdt
     
     • Journal of Combinatorics, 5(1), pages 87-114, (2014)
     
     
135. Convexity in Partial Cubes: the Hull Number
     with Marie Albenque
     
     • Discrete Mathematics, 339, pages 866-876, (2016)
     • Lecture Notes in Computer Science, 8392, pages 421-432, LATIN, (2014)
     
     
136. On planar right groups
     with Ulrich Knauer
     
     • Semigroup Forum, 92 (1), pages 142-157, (2016)
     
     
137. Making Octants Colorful, and Related Covering Decomposition Problems
     with Jean Cardinal, Piotr Micek, and Torsten Ueckerdt
     
     • SIAM Journal of Discrete Mathematics, 28(4), pages 1948-1959, (2014)
     • Proceedings of SODA 2014, pages 1424-1432, (2014)
     
     
138. Connected Covering Numbers
     with Jonathan Chappelon, Luis Pedro Montejano, and Jorge Luis Ramírez Alfonsín
     
     • Journal of Combinatorial Designs, 23 (12), pages 534-549, (2015)
     
     
139. Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles
     with Andrei Asinowski, Jean Cardinal, Nathann Cohen, Sebastien Collette, Thomas Hackl, Michael Hoffmann, Stefan Langerman, Michał Lasoń, Piotr Micek, Günter Rote, and Torsten Ueckerdt
     
     • Lecture Notes in Computer Science, 8037, pages 73-84, WADS, (2013)
     
     
140. Making Triangles Colorful
     with Jean Cardinal, Piotr Micek, and Torsten Ueckerdt
     
     • Journal of Computational Geometry 4 (1), pages 240-246, (2013)
     
     
141. Classification of coupled dynamical systems with multiple delays: Finding the minimal number of delays
     with Leonhard Lücken and Jan Philipp Pade
     
     • SIAM Journal of Applied Dynamical Systems, 14 (1), pages 286-304, (2015)
     • with Serhiy Yanchuk in Europhysics Letters103, 6 pages, (2013)
     
     
142. Simple treewidth
     with Torsten Ueckerdt
     
     • Midsummer Combinatorial Workshop Prague (2012)
     
     
143. A Graph-Theoretical Axiomatization of Oriented Matroids
     with Juan José Montellano-Ballesteros and Ricardo Strausz
     
     • European Journal of Combinatorics, 35 (1), pages 388-391, (2014)
       
     • Electronic Notes in Discrete Mathematics, 38, pages 523-528, EuroComb, (2011)
     
     
144. Outerplanar graph drawings with few slopes
     with Piotr Micek and Bartosz Walczak
     
     • Computational Geometry: Theory and Applications, 47 (5), pages 614-624, (2014)
     • Lecture Notes in Computer Science, 7434, pages 323-334, COCOON, (2012)
     • Proceedings EuroCG, (2012)
     
     
145. Three ways to cover a graph
     with Torsten Ueckerdt
     
     • Discrete Mathematics, 339, pages 745-758, (2016)
     
     
146. On the Duality of Semiantichains and Unichain Coverings
     with Bartłomiej Bosek, Stefan Felsner, and Grzegorz Matecki
     
     • Order, 33 (1), pages 29-38, (2016)
     • Lecture Notes in Computer Science, 7353, pages 43-51, CSR, (2012)
     
     
147. On the bend-number of planar and outerplanar graphs
     with Daniel Heldt and Torsten Ueckerdt
     
     • Discrete Applied Mathematics 179, pages 109-119, (2014)
     • Lecture Notes in Computer Science7256, pages 458-469, LATIN, (2012)
     
     
148. Edge-intersection graphs of grid paths: the bend-number
     with Daniel Heldt and Torsten Ueckerdt
     
     • Discrete Applied Mathematics, 167, pages 144-162 , (2014)
     
     
149. Cubic Time Recognition of Cocircuit Graphs of Uniform Oriented Matroids
     with Stefan Felsner, Ricardo Gómez, Juan José Montellano-Ballesteros and Ricardo Strausz
     
     • European Journal of Combinatorics, 32 (1), pages 60-66, (2011)
     
     
150. Polynomial Time Recognition of Uniform Cocircuit Graphs
     with Ricardo Gómez, Juan José Montellano-Ballesteros and Ricardo Strausz
     
     • Electronic Notes in Discrete Mathematics, 35, pages 29-34, LAGOS, (2009)
     
     
151. Toroidal Embeddings of Right Groups
     with Ulrich Knauer
     
     • Thai Journal of Mathematics, 8 (3), pages 483-490, (2010)
     
     
152. Chip-Firing, Antimatroids, and Polyhedra
     
     • Electronic Notes in Discrete Mathematics, 34, pages 9-13, EuroComb, (2009)
     
     
153. How to Eat 4/9 of a Pizza
     with Piotr Micek and Torsten Ueckerdt
     
     • Discrete Mathematics, 311 (16), pages 1635-1645, (2011)
     
     
154. Distributive Lattices, Polyhedra, and Generalized Flow
     with Stefan Felsner
     
     • European Journal of Combinatorics, 32 (1), pages 45-59, (2011)
     
     
155. ULD-Lattices and Δ-Bonds
     with Stefan Felsner
     
     • Combinatorics, Probability and Computing, 18 (5), pages 707-724, (2009)
     
     
156. Distributive Lattices from Graphs
     with Stefan Felsner
     
     • Proceedings of VI. Jornadas de Matematica Discreta y Algoritmica Lleida, pages 11-23, (2008)
     
     
157. Distributive Lattices on Graph Orientations
     
     • Proceedings of the International Conference on Semigroups, Acts and Categories
       with Applications to Graphs, pages 79-91, (2007)
     
     

Unpublished manuscripts

• Sensitivity of m-ary functions and low degree partitions of Hamming graphs
  with Sara Asensio and Ignacio García-Marco
  
  • only on arXiv (2024), (main conjecture quickly proved by Yuval Filmus)
  
  
• Partitioning a Planar Graph into two Triangle-Forests
  with Clément Rambaud and Torsten Ueckerdt
  
  • only on arXiv (2024), (main result obtained earlier by Carsten Thomassen)
  
  
• Planar cubic graphs of small diameter
  with Piotr Micek
  
  • only on arXiv (2019), (seems to be special case of graph curvature as remarked by Bojan Mohar)
  
  

Theses

• Oriented matroids and beyond: complexes, partial cubes, and corners
  Habilitation Thesis, 215 pages, (2021)
  
• Lattices and Polyhedra from Graphs
  PhD Thesis, 131 pages, (2010)
  
• Partial Orders on Orientations via Cycle Flips
  Diploma Thesis, 85 pages, (2007)

Books & Book Chapters

• Algebraic graph theory: Morphisms, monoids and matrices, De Gruyter (2019), with U. Knauer
• Diskrete und algebraische Strukturen – kurz gefasst, Springer (2015), with U. Knauer
• Popopo - posets, polynômes, polytopes in Informatique Mathématique, une photographie en 2019, Jérémie Chalopin et Pierre Guillon (éd.), CNRS Editions (2019)

PhD Students

• Gil Puig i Surroca: Acyclic Digraphs and Decompositions (2022–present)
• Manon Philibert: Cubes partiels : complétion, compression, plongement (2018–2021)
• Sarah Blind: Output-sensitive algorithms for enumeration problems in graphs (2016–2019)
• Tilen Marc: Cycling in hypercubes (2015–2018)

Other

• Minimal Cayley Graphs (with represtentation) up to order 127