On well-covered triangulations: Part II

A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper [A. Finbow, B. Hartnell, R. Nowakowski, M. Plummer, On well-covered triangulations: Part I, Discrete Appl. Math., 132, 2004, 97-108] that there are no 5-connected planar well-covered triangulations. It is the aim of the present paper to completely determine the 4-connected well-covered triangulations containing two adjacent vertices of degree 4. In a subsequent paper [A. Finbow, B. Hartnell, R. Nowakowski, M. Plummer, On well-covered triangulations: Part III (submitted for publication)], we show that every 4-connected well-covered triangulation contains two adjacent vertices of degree 4 and hence complete the task of characterizing all 4-connected well-covered planar triangulations. There turn out to be only four such graphs. This stands in stark contrast to the fact that there are infinitely many 3-connected well-covered planar triangulations.     

A combinatorial result with applications to self-interacting random walks

We give a series of combinatorial results that can be obtained from any two collections (both indexed by Z×N) of left and right pointing arrows that satisfy some natural relationship. When applied to certain self-interacting random walk couplings, these allow us to reprove some known transience and recurrence results for some simple models. We also obtain new results for one-dimensional multi-excited random walks and for random walks in random environments in all dimensions.     

A bijection for covered maps, or a shortcut between Harer-Zagier?s and Jackson?s formulas

We consider maps on orientable surfaces. A map is called unicellular if it has a single face. A covered map is a map (of genus g) with a marked unicellular spanning submap (which can have any genus in {0,1,…,g}). Our main result is a bijection between covered maps with n edges and genus g and pairs made of a plane tree with n edges and a unicellular bipartite map of genus g with n+1 edges. In the planar case, covered maps are maps with a marked spanning tree and our bijection specializes into a construction obtained by the first author in Bernardi (2007) [4].Covered maps can also be seen as shuffles of two unicellular maps (one representing the unicellular submap, the other representing the dual unicellular submap). Thus, our bijection gives a correspondence between shuffles of unicellular maps, and pairs made of a plane tree and a unicellular bipartite map. In terms of counting, this establishes the equivalence between a formula due to Harer and Zagier for general unicellular maps, and a formula due to Jackson for bipartite unicellular maps.We also show that the bijection of Bouttier, Di Francesco and Guitter (2004) [8] (which generalizes a previous bijection by Schaeffer, 1998 [33]) between bipartite maps and so-called well-labeled mobiles can be obtained as a special case of our bijection.     

Linear extensions of finite posets and a conjecture of G. Kreweras on permutations

We prove a conjecture of G. Kreweras on the number of solutions of the equation xy=z for permutations of a given signature.     

On the cell-growth problem for arbitrary polygons

We solve a variation of the cell-growth problem by enumerating (unlabeled) polygonal clusters, whose constituent cells are all n-gons. The corresponding labeled problem had already been solved by one of us and its solution provides an initial step in the procedure developed here. It will be seen that when n = 3, this amounts to counting triangulations of the disk.     

Generating even triangulations on the torus

A triangulation on a surface $\mathbf{F}$ is a fixed embedding of a loopless graph on $\mathbf{F}$ with each face bounded by a cycle of length three. A triangulation is even if each vertex has even degree. We define two reductions for even triangulations on surfaces, called the 4-contraction and the twin-contraction. In this paper, we first determine the complete list of minimal 3-connected even triangulations on the torus with respect to these two reductions. Secondly, allowing a vertex of degree 2 and replacing the twin-contraction with another reduction, called the 2-contraction, we establish the list for all minimal even triangulations on the torus. We also describe several applications of the lists for solving problems on even triangulations.     

Catalan Triangulations of the Möbius Band

A Catalan triangulation of the Möbius band is an abstract simplicial complex triangulating the Möbius band which uses no interior vertices, and has vertices labelled 1, 2, …, n in order as one traverses the boundary. We prove two results about the structure of this set, analogous to well-known results for Catalan triangulations of the disk. The first is a generating function for Catalan triangulations of M having n vertices, and the second is that any two such triangulations are connected by a sequence of diagonal-flips.     

The infection time of graphs

Consider k particles, 1 red and k-1 white, chasing each other on the nodes of a graph G. If the red one catches one of the white, it “infects” it with its color. The newly red particles are now available to infect more white ones. When is it the case that all white will become red? It turns out that this simple question is an instance of information propagation between random walks and has important applications to mobile computing where a set of mobile hosts acts as an intermediary for the spread of information.In this paper we model this problem by k concurrent random walks, one corresponding to the red particle and k-1 to the white ones. The infection timeT_k of infecting all the white particles with red color is then a random variable that depends on k, the initial position of the particles, the number of nodes and edges of the graph, as well as on the structure of the graph.In this work we develop a set of probabilistic tools that we use to obtain upper bounds on the (worst case w.r.t. initial positions of particles) expected value of T_k for general graphs and important special cases. We easily get that an upper bound on the expected value of T_k is the worst case (over all initial positions) expected meeting timem^* of two random walks multiplied by . We demonstrate that this is, indeed, a tight bound; i.e. there is a graph G (a special case of the “lollipop” graph), a range of values k<n (such that ) and an initial position of particles achieving this bound.When G is a clique or has nice expansion properties, we prove much smaller bounds for T_k. We have evaluated and validated all our results by large scale experiments which we also present and discuss here. In particular, the experiments demonstrate that our analytical results for these expander graphs are tight.     

Distance-restricted matching extension in planar triangulations

A graph G is said to have property E(m,n) if it contains a perfect matching and for every pair of disjoint matchings M and N in G with |M|=m and |N|=n, there is a perfect matching F in G such that M⊆F and N∩F=0?. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m,n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3,0), it was proved there that if the distance among the three edges is at least two, then they can always be extended to a perfect matching. In the present paper, we extend these results by considering the properties E(m,n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension.     

Long Excursions of a Random Walk

In Csáki et al. ⁽¹⁾ and Révész and Willekens⁽⁹⁾ it was proved that the length of the longest excursion among the first n excursions of a plane random walk is nearly equal to the total sum of the lenghts of these excursions. In this paper several results are proved in the same spirit, for plane random walks and for random walks in higher dimensions.     

On total progeny of multitype Galton-Watson process and the first passage time of random walk on lattice

In this paper,we form a method to calculate the probability generating function of the total progeny of multitype branching process.As examples,we calculate probability generating function of the total progeny of the multitype branching processes within random walk which could stay at its position and(2-1) random walk.Consequently,we could give the probability generating functions and the distributions of the first passage time of corresponding random walks.Especially,for recurrent random walk which could stay at its position with probability 0 r 1,we show that the tail probability of the first passage time decays as 2/(π(1-r)~(1/2)) n~(1/1)= when n →∞.     

Counting 5‐connected planar triangulations

Let t_n be the number of rooted 5‐connected planar triangulations with 2n faces. We find t_n exactly for small n, as well as an asymptotic formula for n → ∞. Our results are found by compositions of lower connectivity maps whose faces are triangles or quadrangles. We also find the asymptotic number of cyclically 5‐edge connected cubic planar graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 18–35, 2001     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.     

Central limit theorems for a branching random walk with a random environment in time

We consider a branching random walk with a random environment in time, in which the offspring distribution of a particle of generation n and the distribution of the displacements of its children depend on an environment indexed by the time n. The environment is supposed to be independent and identically distributed. For A ?, let Z_n(A) be the number of particles of generation n located in A. We show central limit theorems for the counting measure Z_n(·) with appropriate normalization.     

Counting solutions to binomial complete intersections

We study the problem of counting the total number of affine solutions of a system of n binomials in n   variables over an algebraically closed field of characteristic zero. We show that we may decide in polynomial time if that number is finite. We give a combinatorial formula for computing the total number of affine solutions (with or without multiplicity) from which we deduce that this counting problem is #P$\#P$-complete. We discuss special cases in which this formula may be computed in polynomial time; in particular, this is true for generic exponent vectors.     

Sharp remainder estimates in the Weyl formula for the Neumann Laplacian on a class of planar regions

We obtain estimates for the counting function of the Neumann Laplacian on a planar domain bounded by the graph of a lower semicontinuous L₁-function. These estimates imply necessary and sufficient conditions for the validity of the classical one-term Weyl formula for the counting function and, under certain restrictions, give an order sharp remainder estimate in this formula.     

Compactifying Exchange Graphs I: Annuli and Tubes

We introduce the notion of an asymptotic triangulation of the annulus. We show that asymptotic triangulations can be mutated as the usual triangulations and describe their exchange graph. Viewing asymptotic triangulations as limits of triangulations under the action of the mapping class group, we compactify the exchange graph of the triangulations of the annulus. The cases of tubes are also considered.