Search

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]

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 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]

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]

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]

We show that the expected time for a random walk on a (multi-)graph G to traverse all m edges of G, and return to its starting point, is at most 2m2; if each edge must be traversed in both directions, the bound is 3m2. Both bounds are tight and may be applied to graphs with arbitrary edge lengths. This has interesting implications for Brownian motion on certain metric spaces, including some fractals. [ABSTRACT FROM PUBLISHER]

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]

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]

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]

Abstract: It is proved that every graph containing no infinite path has an unfriendly partition. [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]