Kolja Knauer Ramón y Cajal researcher Maître de conférences (on leave) Address: Universitat de Barcelona Departament de Matemàtiques i Informàtica Combinatorics Gran Via de les Corts Catalanes, 585 08007 Barcelona, Spain Member of IMUB and CRM and RSME Email: firstname.lastname@domain domain =gmail.com Office: P232 ORCID: 0000-0002-8151-2184 Scopus: 29067881400

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
• Member of the MICINN project ALCOIN: PID2019-104844GB-I00: Álgebra Conmutativa y sus interacciones
  past:
• Member of the ANR projet DISTANCIA: ANR-17-CE40-0015: Metric Graph Theory
• Member of the ANR projet GATO: ANR-16-CE40-0009-01: Graphs, Algorithms and Topology
• Member of the ANR projet CAPPS: ANR-17-CE40-0018: Combinatorial Analysis of Polytopes and Polyhedral Subdivisions
• PI of the PEPS project Efficient Representations of Oriented Systems.
• Member of the ANR project Embedded Graphs and their Oriented Structures.
• Member of the ANR project New trends in matroids: base polytopes, algorithms, structures, and interactions.
• Member of the EuroGiga project Graph Drawings and Representations.

Events

• Organizing the Three Talks in Combinatorics seminar series at Universitat de Barcelona
  
• Organizing the sessions De grafos y gráficas and Geometría discreta y matroides at the VI Encuentro Conjunto RSME-SMM , Valencia, July 2024.
  past:
• Organizing the 1st Geometry and Algebra in Combinatorics Workshop, Tenerife, April 2024.
• Organizing the Discrete Math Session of Barcelona Math Days, Barcelona, November 2023.
• Organizing the conference Stefan is 60 Berlin, September 2022.
• Lecturing BGSMath course Fragments of Algebraic Graph Theory with Miguel Angel Fiol Mora and Juilan Pfeifle, Barcelona, February 2021.
• Organizing the workshop Metrics in Marseille Luminy, April 2018.
• Organizing the International workshop on graphs, semigroups, and semigroup acts Berlin, October 2017.
• Organizing the EuroGIGA GraDR midterm meeting Berlin, October 2012.

Books

• Algebraic graph theory. Morphisms, monoids and matrices
  with Ulrich Knauer
  
• De Gruyter Studies in Mathematics, 331 pages, (2019)
  
  
• Diskrete und algebraische Strukturen - kurz gefasst
  with Ulrich Knauer
  
• Springer Spektrum, 271 pages, (2015)
  

Book chapters

• Popopo - posets, polynômes, polytopes
  
• Informatique Mathématique, une photographie en 2019, Jérémie Chalopin et Pierre Guillon (éd.), CNRS Editions (2019)
  

Preprints and Publications
(conferences and journals merged)

77. 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).
    
    
78. Coloring minimal Cayley graphs
    with Ignacio García-Marco
    
    • European Journal of Combinatorics (accepted).
    
    
79. Geometry of convex geometries
    with Jérémie Chalopin and Victor Chepoi
    
    • (submitted).
    
    
80. Oriented Matroids Today
    with Günter M. Ziegler and Laura Anderson
    
    • Dynamic Survey in the Electronic Journal of Combinatorics, #DS4, (2024).
    
    
81. Outerplanar Partial Cubes
    with Bernat Rovira Segú
    
    • Electronic Journal of the SCM (accepted)
    
    
82. 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)
    
    
83. On k-neighborly reorientations of oriented matroids
    with Rangel Hernández-Ortiz and Luis Pedro Montejano
    
    • European Journal of Combinatorics (accepted)
    
    
84. Roudneff's Conjecture in Dimension 4
    with Rangel Hernández-Ortiz, Luis Pedro Montejano, and Manfred Scheucher
    
    • Experimental Mathematics (accepted).
    
    
85. Clustered independence and bounded treewidth
    with Torsten Ueckerdt
    
    • (submitted)
    
    
86. Concepts of Dimension for Convex Geometries
    with William T. Trotter
    
    • SIAM Journal of Discrete Mathematics (accepted)
    
    
87. The signed Varchenko Determinant for Complexes of Oriented Matroids
    with Winfried Hochstättler and Sophia Keip
    
    • Combinatorica (accepted)
    
    
88. On endomorphism universality of sparse graph classes
    with Gil Puig i Surroca
    
    • (submitted)
    
    
89. Lattice path matroids and quotients
    with Carolina Benedetti-Velásquez
    
    • Combinatorica (accepted)
    
    
90. Beyond symmetry in generalized Petersen graphs
    with Ignacio García-Marco
    
    • Journal of Algebraic Combinatorics (accepted)
    
    
91. Kirchberger's Theorem for Complexes of Oriented Matroids
    with Winfried Hochstättler and Sophia Keip
    
    • Linear Algebra and Its Applications (accepted)
    
    
92. 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).
    
    
93. On lattice path matroid polytopes: alcoved triangulations and snake decompositions
    with Carolina Benedetti-Velásquez and Jerónimo Valencia
    
    • (submitted)
    
    
94. Labeled sample compression schemes for complexes of oriented matroids
    with Victor Chepoi and Manon Philibert
    
    • Journal of Computer and System Sciences (accepted)
    
    
95. On monoid graphs
    with Gil Puig i Surroca
    
    • Mediterranean Journal of Mathematics, 20, 1, 26, 24 p. (2023).
    
    
96. 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)
    
    
97. Finitary affine oriented matroids
    with Emanuele Delucchi
    
    • Discrete and Computational Geometry (accepted)
    • FPSAC 2021 (accepted as poster)
    
    
98. 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).
    
    
99. On sensitivity in bipartite Cayley graphs
    with Ignacio García-Marco
    
    • Journal of Combinatorial Theory, Series B, 154, pages 211-238 (2022)
    
    
100. 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)
     
     
101. Plattenbauten: Touching Rectangles in Space
     with Stefan Felsner and Torsten Ueckerdt
     
     • Graph-Theoretic Concepts in Computer Science, WG2020, 13, (2020)
     
     
102. Corners and simpliciality in oriented matroids and partial cubes
     with Tilen Marc
     
     • European Journal of Combinatorics 112, 103714, 27 p. (2023).
     
     
103. Cayley posets
     with Ignacio García-Marco and Guillaume Mercui-Voyant
     
     • Mediterranean Journal of Mathematics, 17(186), (2020)
     
     
104. Enumerating k-arc-connected orientations
     with Sarah Blind and Petru Valicov
     
     • Algorithmica, 82, pages 3588-3603 (2020)
     
     
105. 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)
     
     
106. Two-dimensional partial cubes
     with Victor Chepoi and Manon Philibert
     
     • Electronic Journal of Combinatorics, 27 (40), p3.29, (2020)
     
     
107. Complete Acyclic Colorings
     with Stefan Felsner, Winfried Hochstättler, and Raphael Steiner
     
     • Electronic Journal of Combinatorics, 27 (2), p2.40, (2020)
     
     
108. 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)
     
     
109. Abelian doppelsemigroups
     with Anatolii V. Zhuchok
     
     • Algebra and Discrete Mathematics, 26 (2), pages 290-304, (2019)
     
     
110. 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)
     
     
111. 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)
     
     
112. 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)
     
     
113. Cuts in matchings of 3-connected cubic graphs
     with Petru Valicov
     
     • European Journal of Combinatorics, 76, pages 27-36, (2019)
     
     
114. Computing metric hulls in graphs
     with Nicolas Nisse
     
     • Discrete Mathematics & Theoretical Computer Science, 21 (1), ICGT 2018, (2019)
     
     
115. 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)
     
     
116. Chomp on numerical semigroups
     with Ignacio García-Marco
     
     • Algebraic Combinatorics, 1 (3), pages 371-394, (2018)
     
     
117. On tope graphs of complexes of oriented matroids
     with Tilen Marc
     
     • Discrete & Computational Geometry, 63 (2), pages 377-417, (2020)
     
     
118. 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)
     
     
119. A correction of a characterization of planar partial cubes
     with Rémi Desgranges
     
     • Discrete Mathematics, 340 (6), pages 1151-1153 (2017)
     
     
120. Hypercellular graphs: partial cubes without Q₃^- as partial cube minor
     with Victor Chepoi and Tilen Marc
     
     • Discrete Mathematics, 343 (4), (2020)
     
     
121. 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)
     
     
122. COMs: Complexes of Oriented Matroids
     with Hans-Jürgen Bandelt and Victor Chepoi
     
     • Journal of Combinatorial Theory Series A, 156, pages 195-237 (2018)
     
     
123. Graph Drawings with One Bend and Few Slopes
     with Bartosz Walczak
     
     • Lecture Notes in Computer Science, 9644, pages 549-561, LATIN, (2016)
     
     
124. 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)
     
     
125. Planar digraphs without large acyclic sets
     with Petru Valicov and Paul S. Wenger
     
     • Journal of Graph Theory, 85 (1), pages 288-291, (2017)
     
     
126. 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)
     
     
127. Orienting Triangulations
     with Boris Albar and Daniel Gonçalves
     
     • Journal of Graph Theory, 83 (4), pages 392-405, (2016)
     • Proceedings EuroCG, (2015)
     
     
128. 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)
     
     
129. 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)
     
     
130. Online and Size Anti-Ramsey Numbers
     with Maria Axenovich, Judith Stumpp, and Torsten Ueckerdt
     
     • Journal of Combinatorics, 5(1), pages 87-114, (2014)
     
     
131. 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)
     
     
132. On planar right groups
     with Ulrich Knauer
     
     • Semigroup Forum, 92 (1), pages 142-157, (2016)
     
     
133. 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)
     
     
134. 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)
     
     
135. 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)
     
     
136. Making Triangles Colorful
     with Jean Cardinal, Piotr Micek, and Torsten Ueckerdt
     
     • Journal of Computational Geometry 4 (1), pages 240-246, (2013)
     
     
137. 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)
     
     
138. Simple treewidth
     with Torsten Ueckerdt
     
     • Midsummer Combinatorial Workshop Prague (2012)
     
     
139. 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)
     
     
140. 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)
     
     
141. Three ways to cover a graph
     with Torsten Ueckerdt
     
     • Discrete Mathematics, 339, pages 745-758, (2016)
     
     
142. 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)
     
     
143. 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)
     
     
144. Edge-intersection graphs of grid paths: the bend-number
     with Daniel Heldt and Torsten Ueckerdt
     
     • Discrete Applied Mathematics, 167, pages 144-162 , (2014)
     
     
145. 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)
     
     
146. 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)
     
     
147. Toroidal Embeddings of Right Groups
     with Ulrich Knauer
     
     • Thai Journal of Mathematics, 8 (3), pages 483-490, (2010)
     
     
148. Chip-Firing, Antimatroids, and Polyhedra
     
     • Electronic Notes in Discrete Mathematics, 34, pages 9-13, EuroComb, (2009)
     
     
149. How to Eat 4/9 of a Pizza
     with Piotr Micek and Torsten Ueckerdt
     
     • Discrete Mathematics, 311 (16), pages 1635-1645, (2011)
     
     
150. Distributive Lattices, Polyhedra, and Generalized Flow
     with Stefan Felsner
     
     • European Journal of Combinatorics, 32 (1), pages 45-59, (2011)
     
     
151. ULD-Lattices and Δ-Bonds
     with Stefan Felsner
     
     • Combinatorics, Probability and Computing, 18 (5), pages 707-724, (2009)
     
     
152. Distributive Lattices from Graphs
     with Stefan Felsner
     
     • Proceedings of VI. Jornadas de Matematica Discreta y Algoritmica Lleida, pages 11-23, (2008)
     
     
153. 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)

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)

Graphs

• all minimal Cayley graphs of groups on up to 107 elements, (I also have them up to 127)
  in the file the g6 encoding of each such graph is preceeded by a line of the form n k [some permutations], which gives a representation as Cayley graph of SmallGroup(n,k) as in GAP with respect to generators represented by the permutations
  

Last update December 2024