BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Florian Lehner

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.COmath.GRDiscrete MathematicsFormal Languages and Automata Theorymath.PR

Catalog footprint

Research overview

21works
5topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

21 publications

preprint2024arXiv

Self-avoiding walk is ballistic on graphs with more than one end

We prove that on any transitive graph GG with infinitely many ends, a self-avoiding walk of length nn is ballistic with extremely high probability, in the sense that there exist constants c,t>0c,t>0 such that Pn(dG(w0,wn)≥cn)≥1−e−tn\mathbb{P}_n(d_G(w_0,w_n)\geq cn)\geq 1-e^{-tn} for every n≥1n\geq 1. Furthermore, we show that the number of self-avoiding walks of length nn grows asymptotically like μwnμ_w^n, in the sense that there exists C>0C>0 such that μwn≤cn≤Cμwnμ_w^n\leq c_n\leq Cμ_w^n for every n≥1n\geq 1. Our results extend more generally to quasi-transitive graphs with infinitely many ends, satisfying the additional technical property that there is a quasi-transitive group of automorphisms of GG which does not fix an end of GG.

Open access
preprint2022arXiv

A note on classes of subgraphs of locally finite graphs

We investigate the question how `small' a graph can be, if it contains all members of a given class of locally finite graphs as subgraphs or induced subgraphs. More precisely, we give necessary and sufficient conditions for the existence of a connected, locally finite graph HH containing all elements of a graph class G\mathcal G. These conditions imply that such a graph HH exists for the class Gd\mathcal G_d consisting of all graphs with maximum degree <d<d which raises the question whether in this case HH can be chosen to have bounded maximum degree. We show that this is not the case, thereby answering a question recently posed by Huynh et al.

Open access
preprint2022arXiv

Self-avoiding walks and multiple context-free languages

Let GG be a quasi-transitive, locally finite, connected graph rooted at a vertex oo, and let cn(o)c_n(o) be the number of self-avoiding walks of length nn on GG starting at oo. We show that if GG has only thin ends, then the generating function FSAW,o(z)=∑n≥0cn(o)znF_{\mathrm{SAW},o}(z)=\sum_{n \geq 0} c_n(o) z^n is an algebraic function. In particular, the connective constant of such a graph is an algebraic number. If GG is deterministically edge labelled, that is, every (directed) edge carries a label such that any two edges starting at the same vertex have different labels, then the set of all words which can be read along the edges of self-avoiding walks starting at oo forms a language denoted by LSAW,oL_{\mathrm{SAW},o}. Assume that the group of label-preserving graph automorphisms acts quasi-transitively. We show that LSAW,oL_{\mathrm{SAW},o} is a kk-multiple context-free language if and only if the size of all ends of GG is at most 2k2k. Applied to Cayley graphs of finitely generated groups this says that LSAW,oL_{\mathrm{SAW},o} is multiple context-free if and only if the group is virtually free.

Open access
preprint2022arXiv

Universal planar graphs for the topological minor relation

Huynh et al. recently showed that a countable graph GG which contains every countable planar graph as a subgraph must contain arbitrarily large finite complete graphs as topological minors, and an infinite complete graph as a minor. We strengthen this result by showing that the same conclusion holds, if GG contains every countable planar graph as a topological minor. In particular, there is no countable planar graph containing every countable planar graph as a topological minor, answering a question by Diestel and Kühn. Moreover, we construct a locally finite planar graph which contains every locally finite planar graph as a topological minor. This shows that in the above result it is not enough to require that GG contains every locally finite planar graph as a topological minor.

Open access
preprint2020arXiv

A bound for the distinguishing index of regular graphs

An edge-colouring of a graph is distinguishing, if the only automorphism which preserves the colouring is the identity. It has been conjectured that all but finitely many connected, finite, regular graphs admit a distinguishing edge-colouring with two colours. We show that all such graphs except K2K_2 admit a distinguishing edge-colouring with three colours. This result also extends to infinite, locally finite graphs. Furthermore, we are able to show that there are arbitrary large infinite cardinals κκ such that every connected κκ-regular graph has distinguishing edge-colouring with two colours.

Open access
preprint2020arXiv

Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs" [arXiv:2003.13166]

Recently, Huang gave a very elegant proof of the Sensitivity Conjecture by proving that hypercube graphs have the following property: every induced subgraph on a set of more than half its vertices has maximum degree at least d\sqrt{d}, where dd is the valency of the hypercube. This was generalised by Alon and Zheng who proved that every Cayley graph on an elementary abelian 22-group has the same property. Very recently, Potechin and Tsang proved an analogous results for Cayley graphs on abelian groups. They also conjectured that all Cayley graphs have the analogous property. We disprove this conjecture by constructing various counterexamples, including an infinite family of Cayley graphs of unbounded valency which admit an induced subgraph of maximum valency 11 on a set of more than half its vertices.

Open access
preprint2020arXiv

Hamiltonian decompositions of 4-regular Cayley graphs of infinite abelian groups

A well-known conjecture of Alspach says that every 2k2k-regular Cayley graph of an abelian group can be decomposed into Hamiltonian cycles. We consider an analogous question for infinite abelian groups. In this setting one natural analogue of a Hamiltonian cycle is a spanning double-ray. However, a naive generalisation of Alspach's conjecture fails to hold in this setting due to the existence of 2k2k-regular Cayley graphs with finite cuts FF where ∣F∣|F| and kk differ in parity, which necessarily preclude the existence of a decomposition into spanning double-rays. We show that every 44-regular Cayley graph of an infinite abelian group all of whose finite cuts are even can be decomposed into spanning double-rays, and so characterise when such decompositions exist. We also characterise when such graphs can be decomposed either into Hamiltonian circles, a more topological generalisation of a Hamiltonian cycle in infinite graphs, or into a Hamiltonian circle and a spanning double-ray.

Open access
preprint2020arXiv

On asymmetric colourings of graphs with bounded degrees and infinite motion

A vertex colouring of a graph is called asymmetric if the only automorphism which preserves it is the identity. Tucker conjectured that if every automorphism of a connected, locally finite graph moves infinitely many vertices, then there is an asymmetric colouring with 22 colours. We make progress on this conjecture in the special case of graphs with bounded maximal degree. More precisely, we prove that if every automorphism of a connected graph with maximal degree ΔΔ moves infinitely many vertices, then there is an asymmetric colouring using O(Δlog⁡Δ)\mathcal O(\sqrt Δ\log Δ) colours. This is the first improvement over the trivial bound of O(Δ)\mathcal O(Δ).

Open access
preprint2020arXiv

On fixity of arc-transitive graphs

The relative fixity of a permutation group is the maximum proportion of the points fixed by a non-trivial element of the group and the relative fixity of a graph is the relative fixity of its automorphism group, viewed as a permutation group on the vertex-set of the graph. We prove in this paper that the relative fixity of connected 22-arc-transitive graphs of a fixed valence tends to 00 as the number of vertices grows to infinity. We prove the same result for the class of arc-transitive graphs of a fixed prime valence, and more generally, for any class of arc-transitive locally-LL graphs, where LL is a fixed quasiprimitive graph-restrictive permutation group.

Open access
preprint2015arXiv

Cops, robbers, and infinite graphs

Cops and robbers is a game between two players, where one tries to catch the other by moving along the edges of a graph. It is well known that on a finite graph the cop has a winning strategy if and only if the graph is constructible and that finiteness is necessary for this result. We propose the notion of weakly cop-win graphs, a winning criterion for infinite graphs which could lead to a generalisation. In fact, we generalise one half of the result, that is, we prove that every constructible graph is weakly cop-win. We also show that a similar notion studied by Chastand et al. (which they also dubbed weakly cop-win) is not sufficient to generalise the above result to infinite graphs. In the locally finite case we characterise the constructible graphs as the graphs for which the cop has a so-called protective strategy and prove that the existence of such a strategy implies constructibility even for non-locally finite graphs.

Open access
preprint2015arXiv

Fast Factorization of Cartesian products of Hypergraphs

Cartesian products of graphs and hypergraphs have been studied since the 1960s. For (un)directed hypergraphs, unique \emph{prime factor decomposition (PFD)} results with respect to the Cartesian product are known. However, there is still a lack of algorithms, that compute the PFD of directed hypergraphs with respect to the Cartesian product. In this contribution, we focus on the algorithmic aspects for determining the Cartesian prime factors of a finite, connected, directed hypergraph and present a first polynomial time algorithm to compute its PFD. In particular, the algorithm has time complexity O(∣E∣∣V∣r2)O(|E||V|r^2) for hypergraphs H=(V,E)H=(V,E), where the rank rr is the maximum number of vertices contained in an hyperedge of HH. If rr is bounded, then this algorithm performs even in O(∣E∣log⁡2(∣V∣))O(|E|\log^2(|V|)) time. Thus, our method additionally improves also the time complexity of PFD-algorithms designed for undirected hypergraphs that have time complexity O(∣E∣∣V∣r6Δ6)O(|E||V|r^6Δ^6), where ΔΔ is the maximum number of hyperedges a vertex is contained in.

Open access
preprint2015arXiv

Local finiteness, distinguishing numbers and Tucker's conjecture

A distinguishing colouring of a graph is a colouring of the vertex set such that no non-trivial automorphism preserves the colouring. Tucker conjectured that if every non-trivial automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing 2-colouring. We show that the requirement of local finiteness is necessary by giving a non-locally finite graph for which no finite number of colours suffices.

Open access
preprint2013arXiv

Distinguishing graphs with infinite motion and nonlinear growth

The distinguishing number D⁡(G)\operatorname D(G) of a graph GG is the least cardinal dd such that GG has a labeling with dd labels which is only preserved by the trivial automorphism. We show that the distinguishing number of infinite, locally finite, connected graphs GG with infinite motion and growth o(n2log⁡2n)o \left(\frac{n^2}{\log_2 n} \right) is either 11 or 22, which proves the Infinite Motion Conjecture of Tom Tucker for this type of graphs. The same holds true for graphs with countably many ends that do not grow too fast. We also show that graphs GG of arbitrary cardinality are 22-distinguishable if every nontrivial automorphism moves at least uncountably many vertices m(G)m(G), where m(G)≥∣Aut⁡(G)∣m(G) \geq \left\vert\operatorname{Aut}(G)\right\vert. This extends a result of Imrich et al. to graphs with automorphism groups of arbitrary cardinality.

Open access
preprint2013arXiv

Endomorphism Breaking in Graphs

We introduce the {\it endomorphism distinguishing number} De(G)D_e(G) of a graph GG as the least cardinal dd such that GG has a vertex coloring with dd colors that is only preserved by the trivial endomorphism. This generalizes the notion of the distinguishing number D(G)D(G) of a graph GG, which is defined for automorphisms instead of endomorphisms. As the number of endomorphisms can vastly exceed the number of automorphisms, the new concept opens challenging problems, several of which are presented here. In particular, we investigate relationships between De(G)D_e(G) and the endomorphism motion of a graph GG, that is, the least possible number of vertices moved by a nontrivial endomorphism of GG. Moreover, we extend numerous results about the distinguishing number of finite and infinite graphs to the endomorphism distinguishing number. This is the main concern of the paper.

Open access
preprint2013arXiv

Random colorings and automorphism breaking in locally finite graphs

A colouring of a graph G is called distinguishing if its stabiliser in Aut G is trivial. It has been conjectured that, if every automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing 2-colouring. We study properties of random 2-colourings of locally finite graphs and show that the stabiliser of such a colouring is almost surely nowhere dense in Aut G and a null set with respect to the Haar measure on the automorphism group. We also investigate random 2-colourings in several classes of locally finite graphs where the existence of a distinguishing 2-colouring has already been established. It turns out that in all of these cases a random 2-colouring is almost surely distinguishing.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.