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 Gran Via de les Corts Catalanes, 585 08007 Barcelona, Spain Email: firstname.lastname@domain domain =gmail.com Office: P232 ORCID: 0000-0002-8151-2184

Research Interests
(ordered by length)

• Representations of oriented matroids and other oriented structures
• Geometric intersection graphs and geometric hypergraphs
• Lattices and polyhedra from graphs and matroids
• Graph drawing
• Cayley graphs
• Partial cubes

Grants

• 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
• Member of the ANR projet GATO: ANR-16-CE40-0009-01: Graphs, Algorithms and Topology
• Member of the ANR projet DISTANCIA: ANR-17-CE40-0015: Metric Graph Theory
• Member of the ANR projet CAPPS: ANR-17-CE40-0018: Combinatorial Analysis of Polytopes and Polyhedral Subdivisions
  past:
• Leader 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
  past:
• Organizing the conference Stefan is 60 in Berlin, September 2022.
• Lecturing BGSMath course Fragments of Algebraic Graph Theory with Miguel Angel Fiol Mora and Juilan Pfeifle
• Organizer of the weekly research seminar Réunion ACRO at LIS Marseille.
• Organizing the workshop Metrics in Marseille in Luminy, April 2018.
• Organizing the International workshop on graphs, semigroups, and semigroup acts in Berlin, October 2017.
• Organizing the EuroGIGA GraDR midterm meeting in Berlin, October 2012.
• Organizer of the weekly research seminar Mittagsseminar at TU Berlin.

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)

67. On endomorphism universality of sparse graph classes
    with Gil Puig i Surroca
    
    • (submitted)
    
    
68. Lattice path matroids and quotients
    with Carolina Benedetti-Velásquez
    
    • (submitted)
    
    
69. Beyond symmetry in generalized Petersen graphs
    with Ignacio García-Marco
    
    • (submitted)
    
    
70. Kirchberger's Theorem for Complexes of Oriented Matroids
    with Winfried Hochstättler and Sophia Keip
    
    • (submitted)
    
    
71. Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth
    with Hoang La and Petru Valicov
    
    • Electronic Journal of Combinatorics (accepted)
    
    
72. Ehrhart theory of lattice path matroid polytopes
    with Carolina Benedetti-Velásquez and Jerónimo Valencia
    
    • (submitted)
    
    
73. Labeled sample compression schemes for complexes of oriented matroids
    with Victor Chepoi and Manon Philibert
    
    • (submitted)
    
    
74. On monoid graphs
    with Gil Puig i Surroca
    
    • Mediterranean Journal of Mathematics (accepted)
    
    
75. 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)
    
    
76. Finitary affine oriented matroids
    with Emanuele Delucchi
    
    • FPSAC 2021 (accepted as poster)
    
    
77. Colouring bottomless rectangles and arborescences
    with Jean Cardinal, Piotr Micek, Dömötör Pálvölgyi, Torsten Ueckerdt, and Narmada Varadarajan
    
    • (submitted)
    
    
78. On sensitivity in bipartite Cayley graphs
    with Ignacio García-Marco
    
    • Journal of Combinatorial Theory, Series B, 154, pages 211-238 (2022)
    
    
79. 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)
    
    
80. Plattenbauten: Touching Rectangles in Space
    with Stefan Felsner and Torsten Ueckerdt
    
    • Graph-Theoretic Concepts in Computer Science, WG2020, 13, (2020)
    
    
81. Corners and simpliciality in oriented matroids and partial cubes
    with Tilen Marc
    
    • (submitted)
    
    
82. Cayley posets
    with Ignacio García-Marco and Guillaume Mercui-Voyant
    
    • Mediterranean Journal of Mathematics, 17(186), (2020)
    
    
83. Planar cubic graphs of small diameter
    with Piotr Micek
    
    • only on arXiv
    
    
84. Enumerating k-arc-connected orientations
    with Sarah Blind and Petru Valicov
    
    • Algorithmica, 82, pages 3588-3603 (2020)
    
    
85. 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)
    
    
86. Two-dimensional partial cubes
    with Victor Chepoi and Manon Philibert
    
    • Electronic Journal of Combinatorics, 27 (40), p3.29, (2020)
    
    
87. Complete Acyclic Colorings
    with Stefan Felsner, Winfried Hochstättler, and Raphael Steiner
    
    • Electronic Journal of Combinatorics, 27 (2), p2.40, (2020)
    
    
88. 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)
    
    
89. Abelian doppelsemigroups
    with Anatolii V. Zhuchok
    
    • Algebra and Discrete Mathematics, 26 (2), pages 290-304, (2019)
    
    
90. 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)
    
    
91. 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)
    
    
92. 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)
    
    
93. Cuts in matchings of 3-connected cubic graphs
    with Petru Valicov
    
    • European Journal of Combinatorics, 76, pages 27-36, (2019)
    
    
94. Computing metric hulls in graphs
    with Nicolas Nisse
    
    • Discrete Mathematics & Theoretical Computer Science, 21 (1), ICGT 2018, (2019)
    
    
95. 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)
    
    
96. Chomp on numerical semigroups
    with Ignacio García-Marco
    
    • Algebraic Combinatorics, 1 (3), pages 371-394, (2018)
    
    
97. On tope graphs of complexes of oriented matroids
    with Tilen Marc
    
    • Discrete & Computational Geometry, 63 (2), pages 377-417, (2020)
    
    
98. 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)
    
    
99. A correction of a characterization of planar partial cubes
    with Rémi Desgranges
    
    • Discrete Mathematics, 340 (6), pages 1151-1153 (2017)
    
    
100. Hypercellular graphs: partial cubes without Q₃^- as partial cube minor
     with Victor Chepoi and Tilen Marc
     
     • Discrete Mathematics, 343 (4), (2020)
     
     
101. 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)
     
     
102. COMs: Complexes of Oriented Matroids
     with Hans-Jürgen Bandelt and Victor Chepoi
     
     • Journal of Combinatorial Theory Series A, 156, pages 195-237 (2018)
     
     
103. Graph Drawings with One Bend and Few Slopes
     with Bartosz Walczak
     
     • Lecture Notes in Computer Science, 9644, pages 549-561, LATIN, (2016)
     
     
104. Drawing graphs with vertices and edges in convex position
     with Ignacio García-Marco
     
     • Computational Geometry: Theory and Applications58, pages 25-33, (2016)
     • Lecture Notes in Computer Science, 9411, pages 348-359, GD, (2015)
     
     
105. Planar digraphs without large acyclic sets
     with Petru Valicov and Paul S. Wenger
     
     • Journal of Graph Theory, 85 (1), pages 288-291, (2017)
     
     
106. 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)
     
     
107. Orienting Triangulations
     with Boris Albar and Daniel Gonçalves
     
     • Journal of Graph Theory, 83 (4), pages 392-405, (2016)
     • Proceedings EuroCG, (2015)
     
     
108. 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)
     
     
109. 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)
     
     
110. Online and Size Anti-Ramsey Numbers
     with Maria Axenovich, Judith Stumpp, and Torsten Ueckerdt
     
     • Journal of Combinatorics, 5(1), pages 87-114, (2014)
     
     
111. 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)
     
     
112. On planar right groups
     with Ulrich Knauer
     
     • Semigroup Forum, 92 (1), pages 142-157, (2016)
     
     
113. 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)
     
     
114. 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)
     
     
115. 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)
     
     
116. Making Triangles Colorful
     with Jean Cardinal, Piotr Micek, and Torsten Ueckerdt
     
     • Journal of Computational Geometry 4 (1), pages 240-246, (2013)
     
     
117. 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)
     
     
118. Simple treewidth
     with Torsten Ueckerdt
     
     • Midsummer Combinatorial Workshop Prague (2012)
     
     
119. 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)
     
     
120. 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)
     
     
121. Three ways to cover a graph
     with Torsten Ueckerdt
     
     • Discrete Mathematics, 339, pages 745-758, (2016)
     
     
122. 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)
     
     
123. 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)
     
     
124. Edge-intersection graphs of grid paths: the bend-number
     with Daniel Heldt and Torsten Ueckerdt
     
     • Discrete Applied Mathematics, 167, pages 144-162 , (2014)
     
     
125. 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)
     
     
126. 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)
     
     
127. Toroidal Embeddings of Right Groups
     with Ulrich Knauer
     
     • Thai Journal of Mathematics, 8 (3), pages 483-490, (2010)
     
     
128. Chip-Firing, Antimatroids, and Polyhedra
     
     • Electronic Notes in Discrete Mathematics, 34, pages 9-13, EuroComb, (2009)
     
     
129. How to Eat 4/9 of a Pizza
     with Piotr Micek and Torsten Ueckerdt
     
     • Discrete Mathematics, 311 (16), pages 1635-1645, (2011)
     
     
130. Distributive Lattices, Polyhedra, and Generalized Flow
     with Stefan Felsner
     
     • European Journal of Combinatorics, 32 (1), pages 45-59, (2011)
     
     
131. ULD-Lattices and Δ-Bonds
     with Stefan Felsner
     
     • Combinatorics, Probability and Computing, 18 (5), pages 707-724, (2009)
     
     
132. Distributive Lattices from Graphs
     with Stefan Felsner
     
     • Proceedings of VI. Jornadas de Matematica Discreta y Algoritmica Lleida, pages 11-23, (2008)
     
     
133. Distributive Lattices on Graph Orientations
     
     • Proceedings of the International Conference on Semigroups, Acts and Categories
       with Applications to Graphs, pages 79-91, (2007)
     
     

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

• 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 March 2022