Integral trees of odd diameters

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. Recently, Csikvári proved the existence of integral trees of any even diameter. In the odd case, integral trees have been constructed with diameter at most 7. In this article, we show that for every odd integer n>1, there are infinitely many integral trees of diameter n. © 2011 Wiley Periodicals, Inc. J Graph Theory     

We like to walk on the comb

This is a brief account on how we have entertained ourselves in the last two years, that is, a summary of the results we have obtained in a joint work with E. Csáki, M. Csörg? and P. Révész on random walks on a comb.     

A generalized central limit theorem in infinite ergodic theory

We prove a generalized central limit theorem for dynamical systems with an infinite ergodic measure which induce a Gibbs–Markov map on some subset, provided the return time to this subset has regularly varying tails. We adapt a method designed by Csáki and Földes for observables of random walks to show that the partial sums of some functions of the system—the return time and the observable—are asymptotically independent. Some applications to random walks and Pomeau–Manneville maps are discussed.     

Recurrence time and range for a generalized random walk

The notions of recurrence time, range, and the limit of probabilities P_k of return to the origin arise in the study of random walks on groups. We examine these notions and develop relationships among them in an ergodic theory setting in which the usual requirement of independence of the increments of the random walk can be relaxed to simply an ergodic requirement. Thus we consider generalized random walks or GRWs. The ergodic theory setting is related to Mackey's virtual group theory in that the GRW determines a virtual group homomorphism (or cocycle). We relate the condition- that the homomorphism is trivial (the cocycle is a coboundary) to the Cesáro limit of P_k. The basic ideas of virtual group theory were established by Mackey and further developed by Ramsay. Our virtual group homomorphism result does not require familiarity with the technicalities of virtual group theory.     

Semigroups, Rings, and Markov Chains

We analyze random walks on a class of semigroups called left-regular bands. These walks include the hyperplane chamber walks of Bidigare, Hanlon, and Rockmore. Using methods of ring theory, we show that the transition matrices are diagonalizable and we calculate the eigenvalues and multiplicities. The methods lead to explicit formulas for the projections onto the eigenspaces. As examples of these semigroup walks, we construct a random walk on the maximal chains of any distributive lattice, as well as two random walks associated with any matroid. The examples include a q-analogue of the Tsetlin library. The multiplicities of the eigenvalues in the matroid walks are generalized derangement numbers, which may be of independent interest.     

On the graphical relaxation of the symmetric traveling salesman polytope

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope as well. In this paper we give an affirmative answer to this question for n ≥ 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to the starting vertex. Thus there must have been a third vertex on the way.      

Random walks and the effective resistance of networks

In this article we present an interpretation ofeffective resistance in electrical networks in terms of random walks on underlying graphs. Using this characterization we provide simple and elegant proofs for some known results in random walks and electrical networks. We also interpret the Reciprocity theorem of electrical networks in terms of traversals in random walks. The byproducts are (a) precise version of thetriangle inequality for effective resistances, and (b) an exact formula for the expectedone-way transit time between vertices.     

On the critical exponents of generalized ballot sequences in three dimensions and large tandem walks

We answer some questions on the asymptotics of ballot walks raised in [S. B. Ekhad and D. Zeilberger, April 2021] and prove that these models are not D-finite. This short note demonstrates how the powerful tools developed in the last decades on lattice paths in convex cones help us to answer some challenging problems that were out of reach for a long time. On the way we generalize tandem walks to the family of large tandem walks whose steps are of arbitrary length and map them bijectively to a generalization of ballot walks in three dimensions.

     

Classifying lattice walks restricted to the quarter plane

This work considers the nature of generating functions of random lattice walks restricted to the first quadrant. In particular, we find combinatorial criteria to decide if related series are algebraic, transcendental holonomic or otherwise. Complete results for walks taking their steps in a maximum of three directions of restricted amplitude are given, as is a well-supported conjecture for all walks with steps taken from a subset of ²{0,±1}. New enumerative results are presented for several classes, each obtained with a variant of the kernel method.     

On the number of closed walks in vertex-transitive graphs

The results of Širáň and the first author [A construction of vertex-transitive non-Cayley graphs, Australas. J. Combin. 10 (1994) 105–114; More constructions of vertex-transitive non-Cayley graphs based on counting closed walks, Australas. J. Combin. 14 (1996) 121–132] are generalized, and new formulas for the number of closed walks of length $p^r$ or pq, where p and q are primes, valid for all vertex-transitive graphs are found. Based on these formulas, several simple tests for vertex-transitivity are presented, as well as lower bounds on the orders of the smallest vertex- and arc-transitive groups of automorphisms for vertex-transitive graphs of given valence.     

Walks on the slit plane

 In the first part of this paper, we enumerate exactly walks on the square lattice that start from the origin, but otherwise avoid the half-line . We call them walks on the slit plane. We count them by their length, and by the coordinates of their endpoint. The corresponding three variable is algebraic of degree 8. Moreover, for any point (i, j), the length for walks of this type ending at (i, j) is also algebraic, of degree 2 or 4, and involves the famous Catalan numbers. Our method is based on the solution of a functional equation, established via a simple combinatorial argument. It actually works for more general models, in which walks take their steps in a finite subset of ℤ² satisfying two simple conditions. The corresponding are always algebraic. In the second part of the paper, we derive from our enumerative results a number of probabilistic corollaries. For instance, we can compute exactly the probability that an ordinary random walk starting from (i, j) hits for the first time the half-line at position (k, 0), for any triple (i, j, k). This generalizes a question raised by R. Kenyon, which was the starting point of this paper. Taking uniformly at random all n-step walks on the slit plane, we also compute the probability that they visit a given point (k, 0), and the average number of visits to this point. In other words, we quantify the transience of the walks. Finally, we derive an explicit limit law for the coordinates of their endpoint. Received: 22 December 2001 / Revised version: 19 February 2002 / Published online: 30 September 2002 Both authors were partially supported by the INRIA, via the cooperative research action Alcophys. Mathematics Subject Classification (2000): O5A15-60C05     

Families of prudent self-avoiding walks

A self-avoiding walk (SAW) on the square lattice is prudent if it never takes a step towards a vertex it has already visited. Prudent walks differ from most classes of SAW that have been counted so far in that they can wind around their starting point.Their enumeration was first addressed by Préa in 1997. He defined 4 classes of prudent walks, of increasing generality, and wrote a system of recurrence relations for each of them. However, these relations involve more and more parameters as the generality of the class increases.The first class actually consists of partially directed walks, and its generating function is well known to be rational. The second class was proved to have an algebraic (quadratic) generating function by Duchi (2005). Here, we solve exactly the third class, which turns out to be much more complex: its generating function is not algebraic, nor even D-finite.The fourth class—general prudent walks—is the only isotropic one, and still defeats us. However, we design an isotropic family of prudent walks on the triangular lattice, which we count exactly. Again, the generating function is proved to be non-D-finite.We also study the asymptotic properties of these classes of walks, with the (somewhat disappointing) conclusion that their endpoint moves away from the origin at a positive speed. This is confirmed visually by the random generation procedures we have designed.     

On arc reversal in balanced digraphs

In this note we consider closed walks, which are cycles that are not necessarily elementary. We prove that any arc reversal in a balanced multidigraph without loops decreases the number of closed walks. This also proves that arc reversal in a simple balanced digraph decreases the number of closed walks.     

Synchronization and functional central limit theorems for interacting reinforced random walks

We obtain Central Limit Theorems in Functional form for a class of time-inhomogeneous interacting random walks. Due to a reinforcement mechanism and interaction, the walks are strongly correlated and converge almost surely to the same, possibly random, limit. We study random walks interacting through a mean-field rule and compare the rate they converge to their limit with the rate of synchronization, i.e. the rate at which their mutual distances converge to zero. We show that, under certain conditions, synchronization is faster than convergence. Even if our focus is on theoretical results, we propose as main motivations two contexts in which such results could directly apply: urn models and opinion dynamics in a random network evolving via preferential attachment.     

Weakly directed self-avoiding walks

We define a new family of self-avoiding walks (SAW) on the square lattice, called weakly directed walks. These walks have a simple characterization in terms of the irreducible bridges that compose them. We determine their generating function. This series has a complex singularity structure and in particular, is not D-finite. The growth constant is approximately 2.54 and is thus larger than that of all natural families of SAW enumerated so far (but smaller than that of general SAW, which is about 2.64). We also prove that the end-to-end distance of weakly directed walks grows linearly. Finally, we study a diagonal variant of this model.     

Functional centrality in graphs

In this article, we introduce the functional centrality as a generalization of the subgraph centrality. We propose a general method for characterizing nodes in the graph according to the number of closed walks starting and ending at the node. Closed walks are appropriately weighted according to the topological features that we need to measure.     

空间随机行走比对问题的动态规划算法

受计算生物学中两个蛋白质结构比对问题的启发,定义了三维空间随机步以及两个随机步同构等的概念.研究了步长为k的随机步非同构意义下的个数.最后提出了两个非同构随机步对齐的优化问题,通过研究随机步的同构,采用动态规划给出了将一个随机步对齐到另一个随机步所需最少的操作步数的算法.     

Entangled Markov chains

Motivated by the problem of finding a satisfactory quantum generalization of the classical random walks, we construct a new class of quantum Markov chains which are at the same time purely generated and uniquely determined by a corresponding classical Markov chain. We argue that this construction yields as a corollary, a solution to the problem of constructing quantum analogues of classical random walks which are “entangled” in a sense specified in the paper.The formula giving the joint correlations of these quantum chains is obtained from the corresponding classical formula by replacing the usual matrix multiplication by Schur multiplication.The connection between Schur multiplication and entanglement is clarified by showing that these quantum chains are the limits of vector states whose amplitudes, in a given basis (e.g. the computational basis of quantum information), are complex square roots of the joint probabilities of the corresponding classical chains. In particular, when restricted to the projectors on this basis, the quantum chain reduces to the classical one. In this sense we speak of entangled lifting, to the quantum case, of a classical Markov chain. Since random walks are particular Markov chains, our general construction also gives a solution to the problem that motivated our study.In view of possible applications to quantum statistical mechanics too, we prove that the ergodic type of an entangled Markov chain with finite state space (thus excluding random walks) is completely determined by the corresponding ergodic type of the underlying classical chain. Mathematics Subject Classification (2000) Primary 46L53, 60J99; Secondary 46L60, 60G50, 62B10     

Dirichlet forms on fractals: Poincaré constant and resistance

Summary We study Dirichlet forms associated with random walks on fractal-like finite grahs. We consider related Poincaré constants and resistance, and study their asymptotic behaviour. We construct a Markov semi-group on fractals as a subsequence of random walks, and study its properties. Finally we construct self-similar diffusion processes on fractals which have a certain recurrence property and plenty of symmetries.Partly supported by the JSPS Program     

Length of clustering algorithms based on random walks with an application to neuroscience

In this paper we show how the notions of conductance and cutoff can be used to determine the length of the random walks in some clustering algorithms. We consider graphs which are globally sparse but locally dense. They present a community structure: there exists a partition of the set of vertices into subsets which display strong internal connections but few links between each other. Using a distance between nodes built on random walks we consider a hierarchical clustering algorithm which provides a most appropriate partition. The length of these random walks has to be chosen in advance and has to be appropriate. Finally, we introduce an extension of this clustering algorithm to dynamical sequences of graphs on the same set of vertices.