Florian Lehner's Webpage
I am a post-doctoral researcher at the Institute of Discrete Mathematics at Graz University of Technology. My position is funded by the Austrian Science Fund (FWF) via projects Walks and boundaries — a wide range PI: W. Woess, project number P 31889-N35, and Graphs and groups Erwin Schrödinger Fellowship, project number J 3850-N32.
My research interests cover a wide variety of topics in graph theory and combinatorics. Much of my work concerns problems on the interface of group theory and graph theory, but I also enjoy working on topics with a geometric or probabilistic flavour.
Asymmetric graph colouring
How hard is it, to get rid of the symmetries of a discrete structure? More precisely, how many colours do we need to colour the vertices of a graph in a way that no automorphism except the identity preserves the colouring?
The least number of colours required is called the asymmetric colouring number or distinguishing number of the graph. I have studied this graph invariant in various settings, including random colourings, edge colourings, and most recently colourings of graphs with bounded maximum degree.
Combinatorial game theory
The study of pursuit-evasion games on graphs is a popular topic in combinatorial game theory. These are games where one player's objective is to capture the other player, whereas the other player attempts to avoid being captured. Notable examples include Cops-and-Robber and Conway's Angel-Devil game.
My contributions mostly concern the so-called cop number, that is, the least number of pursuers needed to guarantee capture in the Cops-and-Robber game, but I am always interested in learning about other aspects of the game as well as other combinatorial games.
Tree structure in infinite graphs
Stallings' splitting theorem is one of the central results in geometric group theory. It essentially states that a finitely generated group satisfies one of two alternatives. It either has one well-connected infinite part (that is, it is one-ended), or it exhibits a large-scale tree structure (either an amalgamated free product, or a HNN extension).
Hamann, Miraftab, Rühmann, and I recently proved an analogous result for infinite graphs; I am currently working on applications as well as further extensions of this result.
You can also download a CV in PDF format.
|Project Assistant Department of Discrete Mathematics, Graz University of Technology||since 2020|
|Erwin Schrödinger Research Fellow Department of Mathematics, University of Warwick Department of Discrete Mathematics, Graz University of Technology||since 2017|
|University Assistant Department of Mathematics, University of Hamburg||2015 – 2017|
|University Assistant Institute of Geometry, Graz University of Technology||2011 – 2015|
|Teaching Assistant Mathematics Institutes and Institute for Software Technology, Graz University of Technology||2007 – 2010|
|PhD: Mathematics and Scientific Computing Graz University of Technology Graduation with highest distinctions "Sub auspiciis Praesidentis" Thesis: Symmetry breaking in graphs and groups. Adviser: J. Wallner||2011 – 2014|
|Master Programme: Mathematical Computer Science Graz University of Technology Thesis: The line graph of every locally finite 6-edge-connected graph with finitely many ends is hamiltonian. Adviser: W. Woess||2008 – 2011|
|Bachelor Programme: Technical Mathematics Graz University of Technology||2005 – 2008|
You can also download a BibTeX-file of this list.
|||Self-avoiding walks and multiple context-free languages. 2020, preprint.|
|||Hamiltonian decompositions of 4-regular Cayley graphs of infinite abelian groups. 2020, preprint.|
|||On fixity of arc-transitive graphs. 2020, preprint.|
|||Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs". Ars Mathematica Contemporanea, 2020, to appear.|
|||Comparing consecutive letter counts in multiple context-free languages. 2020, preprint.|
|||On asymmetric colourings of graphs with bounded degrees and infinite motion. 2019, preprint.|
|||A bound for the distinguishing index of regular graphs. European Journal of Combinatorics, 89, 2020.|
|||Bounding the cop number of a graph by its genus. 2019, preprint.|
|||On the cop number of toroidal graphs. 2019, preprint.|
|||A Stallings' type theorem for quasi-transitive graphs. 2019, preprint.|
|||Invariant spanning double rays in amenable groups. 2018, preprint.|
|||Distinguishing infinite graphs with bounded degrees. 2018, preprint.|
|||Distinguishing numbers of finite 4-valent vertex-transitive graphs. Ars Mathematica Contemporanea, 2020, to appear.|
|||On symmetries of edge and vertex colourings of graphs. Discrete Mathematics, 343 (9), 2020.|
|||Distinguishing density and the Distinct Spheres Condition. European Journal of Combinatorics, 89, 2020.|
|||Hamilton decompositions of one-ended Cayley graphs. Journal of Combinatorial Theory, Series B, 140, pp. 171 – 191, 2020.|
|||Trees with distinguishing index equal distinguishing number plus one. Discussiones Mathematicae Graph Theory, 40 (3), pp. 875 – 884, 2020.|
|||Firefighting on trees and Cayley graphs. Australasian Journal of Combinatorics, 75 (1), pp. 66 – 72, 2019.|
|||On tree-decompositions of one-ended graphs. Mathematische Nachrichten, 292 (3), pp. 524 – 539, 2018.|
|||A counterexample to Montgomery's conjecture on dynamic colourings of regular graphs. Discrete Applied Mathematics, 229, pp. 151 – 153, 2017.|
|||Non-reconstructible locally finite graphs. Journal of Combinatorial Theory, Series B, 133, pp. 122 – 152, 2018.|
|||A counterexample to the reconstruction conjecture for locally finite trees. Bulletin of the London Mathematical Society, 49 (4), pp. 630 – 648, 2017.|
|||Breaking graph symmetries by edge colourings. Journal of Combinatorial Theory, Series B, 127, pp. 205 – 214, 2017.|
|||Fast factorization of Cartesian products of (directed) hypergraphs. Theoretical Computer Science, 615, pp. 1 – 11, 2016.|
|||Maximising the number of independent sets in connected graphs. Graphs and Combinatorics, 33 (5), pp. 1103 – 1118, 2017.|
|||Local finiteness, distinguishing numbers and Tucker's conjecture. Electronic Journal of Combinatorics, 22 (4), 2015, research paper #P4.19.|
|||Pursuit evasion on infinite graphs. Theoretical Computer Science, 655 (Part A), pp. 30 – 40, 2016.|
|||The Cartesian product of graphs with loops. Ars Mathematica Contemporanea, 11 (1), pp. 1 – 9, 2016.|
|||Clique trees of infinite locally finite chordal graphs. Electronic Journal of Combinatorics, 25 (2), 2018, research paper #P2.9.|
|||Extending cycles locally to Hamilton cycles. Electronic Journal of Combinatorics, 23 (1), 2016, research paper #P1.49.|
|||Random colorings and automorphism breaking in locally finite graphs Combinatorics, Probability and Computing, 22 (6), pp. 885 – 909, 2013.|
|||Distinguishing graphs with intermediate growth. Combinatorica, 36 (3), pp. 333 – 347, 2016.|
|||Endomorphism breaking in graphs. Electronic Journal of Combinatorics, 21 (1), 2014, research paper #P1.16.|
|||Distinguishing graphs with infinite motion and nonlinear growth. Ars Mathematica Contemporanea, 7, pp. 201 – 213, 2014.|
|||On spanning tree packings of highly edge connected graphs. Journal of Combinatorial Theory, Series B, 105, pp. 93 – 126, 2014.|
|||Symmetry breaking in graphs and groups Ph.D. Thesis, TU Graz, 2014.|
|||The line graph of every locally finite 6-edge-connected graph with finitely many ends is hamiltonian. Master thesis, TU Graz, 2011.|