Search

A well‐known theorem of Whitney states that a 3‐connected planar graph admits an essentially unique embedding into the 2‐sphere. We prove a 3‐dimensional analogue: a simply‐connected 2‐complex every link graph of which is 3‐connected admits an essentially unique locally flat embedding into the 3‐sphere, if it admits one at all. This can be thought of as a generalisation of the 3‐dimensional Schoenflies theorem. [ABSTRACT FROM AUTHOR]

We prove a topological extension of Dirac's theorem suggested by Gowers in 2005: for any connected, closed surface S, we show that any two-dimensional simplicial complex on n vertices in which each pair of vertices belongs to at least n/3 + o(n) facets contains a homeomorph of S spanning all the vertices. This result is asymptotically sharp, and implies in particular that any 3-uniform hypergraph on n vertices with minimum codegree exceeding n/3 + o(n) contains a spanning triangulation of the sphere. [ABSTRACT FROM AUTHOR]

Let G be a finitely generated group acting faithfully and properly discontinuously by homeomorphisms on a planar surface X ⊆ S2. We prove that G admits such an action that is in addition co-compact, provided we can replace X by another surface Y ⊆ S2. We also prove that if a group H has a finitely generated Cayley (multi-) graph C equivariantly embeddable in S2, then C can be chosen so as to have no infinite path on the boundary of a face. The proofs of these facts are intertwined, and the classes of groups they define coincide. In the orientation-preserving case they are exactly the (isomorphism types of) finitely generated Kleinian function groups. We construct a finitely generated planar Cayley graph whose group is not in this class. In passing, we observe that the Freudenthal compactification of every planar surface is homeomorphic to the sphere. [ABSTRACT FROM AUTHOR]

Abstract Any n -vertex 3-graph with minimum codegree at least ⌊ n ∕ 3 ⌋ must have a spanning tight component, but immediately below this threshold it is possible for no tight component to span more than ⌈ 2 n ∕ 3 ⌉ vertices. Motivated by this observation, we ask which codegree forces a tight component of at least any given size. The corresponding function seems to have infinitely many discontinuities, but we provide upper and lower bounds, which asymptotically converge as the function nears the origin. [ABSTRACT FROM AUTHOR]

We show that a group admits a planar, finitely generated, Cayley graph if and only if it admits a special kind of group presentation we introduce, called a planar presentation. Planar presentations can be recognised algorithmically. As a consequence, we obtain an effective enumeration of the planar Cayley graphs, yielding in particular an affirmative answer to a question of Droms et al. asking whether the planar groups can be effectively enumerated. [ABSTRACT FROM AUTHOR]

We provide an algorithm with constant running time that given a weighted tournament T , distinguishes with high probability of success between the cases that T can be represented by a Bradley–Terry model, or cannot even be approximated by one. The same algorithm tests whether the corresponding Markov chain is reversible. [ABSTRACT FROM AUTHOR]

We prove that every vertex transitive, planar, 1-ended, graph covers every graph whose balls of radius r are isomorphic to the ball of radius r in G for a sufficiently large r . It is natural to ask whether this is true for all finitely presented Cayley graphs, but the answer turns out to be negative (de la Salle and Tessera, 2015). [ABSTRACT FROM AUTHOR]

We classify the planar cubic Cayley graphs of connectivity 2, providing an explicit presentation and embedding for each of them. Combined with Georgakopoulos (2017) this yields a complete description of all planar cubic Cayley graphs. [ABSTRACT FROM AUTHOR]

We study equilibrium configurations of infinitely many identical particles on the real line or finitely many particles on the circle, such that the (repelling) force they exert on each other depends only on their distance. The main question is whether each equilibrium configuration needs to be an arithmetic progression. Under very broad assumptions on the force we show this for the particles on the circle. In the case of infinitely many particles on the line we show the same result under the assumption that the maximal (or the minimal) gap between successive points is finite (positive) and assumed at some pair of successive points. Under the assumption of analyticity for the force field (e.g. the Coulomb force) we deduce some extra rigidity for the configuration: knowing an equilibrium configuration of points in a half-line determines it throughout. Various properties of the equlibrium configuration are proved. [ABSTRACT FROM AUTHOR]

The aim of this paper is to clarify the relationship between Gromov-hyperbolicity and amenability for planar maps. [ABSTRACT FROM AUTHOR]

We exhibit a close connection between hitting times of the simple random walk on a graph, the Wiener index, and related graph invariants. In the case of trees, we obtain a simple identity relating hitting times to the Wiener index. It is well known that the vertices of any graph can be put in a linear preorder so that vertices appearing earlier in the preorder are 'easier to reach' by a random walk, but 'more difficult to get out of.' We define various other natural preorders and study their relationships. These preorders coincide when the graph is a tree, but not necessarily otherwise. Our treatise is self-contained, and puts some known results relating the behavior or random walk on a graph to its eigenvalues in a new perspective. [ABSTRACT FROM AUTHOR]

Answering a question of Benjamini and Schramm (Ann Probab 24(3):1219-1238, ), we show that the Poisson boundary of any planar, uniquely absorbing (e.g. one-ended and transient) graph with bounded degrees can be realised geometrically as a circle, which arises from a discrete version of Riemann's mapping theorem. This implies a conjecture of Northshield (Potential Anal 2(4):299-314, ). Some of our technique apply to the non-planar case and might have further applications. When the graph is also hyperbolic then, under mild conditions, we prove the equivalence of several boundary constructions. [ABSTRACT FROM AUTHOR]

We consider weighted graphs with an infinite set of vertices. We show that boundedness of all functions of finite energy can be seen as a notion of ‘relative compactness’ for such graphs and study sufficient and necessary conditions for this property in terms of various metrics. We then equip graphs satisfying this property with a finite measure and investigate the associated Laplacian and its semigroup. In this context, our results include the trace class property for the semigroup, uniqueness and existence of solutions to the Dirichlet Problem with boundary arising from the natural compactification, an explicit description of the domain of the Dirichlet Laplacian, convergence of the heat semigroup for large times as well as stochastic incompleteness and transience of the corresponding random walk in continuous time. [ABSTRACT FROM AUTHOR]

We extend the notion of effective resistance to metric spaces that are similar to graphs but can also be similar to fractals. Combined with other basic facts proved in the paper, this lays the ground for a construction of Brownian Motion on such spaces completed in [10]. [ABSTRACT FROM AUTHOR]

Abstract: We prove that a Cayley graph can be embedded in the Euclidean plane without accumulation points of vertices if and only if it is the 1-skeleton of a Cayley complex that can be embedded in the plane after removing redundant simplices. We also give a characterisation of these Cayley graphs in term of group presentations, and deduce that they can be effectively enumerated. [Copyright &y& Elsevier]

We solve the game of Babylon when played with chips of two colors, giving a winning strategy for the second player in all previously unsolved cases. [ABSTRACT FROM AUTHOR]

Abstract: We generalise a fundamental graph-theoretical fact, stating that every element of the cycle space of a graph is a sum of edge-disjoint cycles, to arbitrary continua. To achieve this we replace graph cycles by topological circles, and replace the cycle space of a graph by a new homology group for continua which is a quotient of the first singular homology group . This homology seems to be particularly apt for studying spaces with infinitely generated , e.g. infinite graphs or fractals. [Copyright &y& Elsevier]

Abstract: Motivated by work of Diestel and Kühn on the cycle spaces of infinite graphs we study the ramifications of allowing infinite sums in a module . We show that every generating set in this setup contains a basis if the ground set M is countable, but not necessarily otherwise. Given a family , we determine when the infinite-sum span of is closed under infinite sums, i.e.when . We prove that this is the case if R is a field or a finite ring and each element of M lies in the support of only finitely many elements of . This is, in a sense, best possible. We finally relate closures under infinite sums to topological closures in the product space . [Copyright &y& Elsevier]

Abstract: Let be a graph each edge of which is given a length . This naturally induces a distance between any two vertices , and we let  denote the completion of the corresponding metric space. It turns out that several well-studied topologies on infinite graphs are special cases of . Moreover, it seems that is the right setting for studying various problems. The aim of this paper is to introduce , providing basic facts, motivating examples and open problems, and indicate possible applications. Parts of this work suggest interactions between graph theory and other fields, including algebraic topology and geometric group theory. [Copyright &y& Elsevier]

Eberhard proved that for every sequence ( p), 3≤ k≤ r, k≠6, of nonnegative integers satisfying Euler's formula ∑(6− k) p=12, there are infinitely many values p such that there exists a simple convex polyhedron having precisely p faces of size k for every k≥3, where p=0 if k> r. In this paper we prove a similar statement when nonnegative integers p are given for 3≤ k≤ r, except for k=5 and k=7 (but including p). We prove that there are infinitely many values p, p such that there exists a simple convex polyhedron having precisely p faces of size k for every k≥3. We derive an extension to arbitrary closed surfaces, yielding maps of arbitrarily high face-width. Our proof suggests a general method for obtaining results of this kind. [ABSTRACT FROM AUTHOR]

We show that if the sum of the resistances of an electrical network N is finite, then there is a unique electrical current in N, provided that we do not allow, in a sense made precise in the paper, any flow to escape to infinity. [ABSTRACT FROM PUBLISHER]

Abstract: We prove Diestel''s conjecture that the square of a 2-connected locally finite graph G has a Hamilton circle, a homeomorphic copy of the complex unit circle in the Freudenthal compactification of . [Copyright &y& Elsevier]

Abstract: Let be an -partite -graph, all of whose sides have the same size . Suppose that there exist two sides of , each satisfying the following condition: the degree of each legal -tuple contained in the complement of this side is strictly larger than . We prove that under this condition must have a perfect matching. This answers a question of Kühn and Osthus. [Copyright &y& Elsevier]

A well-known result of Benjamini, Lyons, Peres, and Schramm states that if G is a finitely generated Cayley graph of a group Γ , then Γ is amenable if and only if G admits a Γ -invariant random spanning tree with at most two ends. We show that this is equivalent to the existence of a Γ -invariant random spanning double ray in a power of G. [ABSTRACT FROM AUTHOR]

Abstract: We give a short proof of the fact that the square of a 2-connected finite graph is Hamiltonian. [Copyright &y& Elsevier]

Abstract: We prove a strong version of the Max-Flow Min-Cut theorem for countable networks, namely that in every such network there exist a flow and a cut that are “orthogonal” to each other, in the sense that the flow saturates the cut and is zero on the reverse cut. If the network does not contain infinite trails then this flow can be chosen to be mundane, i.e. to be a sum of flows along finite paths. We show that in the presence of infinite trails there may be no orthogonal pair of a cut and a mundane flow. We finally show that for locally finite networks there is an orthogonal pair of a cut and a flow that satisfies Kirchhoff''s first law also for ends. [Copyright &y& Elsevier]