Recent zbMATH articles in MSC 05C81 https://zbmath.org/atom/cc/05C81 2022-06-24T15:10:38.853281Z Werkzeug Some further results on the maximal hitting times of trees with some given parameters https://zbmath.org/1485.05086 2022-06-24T15:10:38.853281Z "Li, Shuchao" https://zbmath.org/authors/?q=ai:li.shuchao "Xu, Yangyang" https://zbmath.org/authors/?q=ai:xu.yangyang "Zhang, Huihui" https://zbmath.org/authors/?q=ai:zhang.huihui Summary: Given a connected graph $$G$$ with vertex set $$V_G ,$$ the hitting time $$H_G(u,v )$$ of vertices $$u$$ and $$v$$ in $$G$$ is defined as the expected number of steps that a random walk takes to go from $$u$$ to $$v .$$ Then the $$ZZ$$ index of $$G$$, denoted by $$\psi (G)$$, is defined as $$\psi(G)=\max_{\{u,v \}\subseteq V_G}H_G(u,v )$$. This hitting-time-based invariant was first proposed by \textit{X. Zhu} and \textit{X.-D. Zhang} [Graphs Comb. 37, No. 6, 2365--2386 (2021; Zbl 1479.05332)]. In this paper, some further extremal problems on the $$ZZ$$ index of trees with some given parameters are considered. Firstly, the extremal graphs with the second largest and the third largest $$ZZ$$ indices are characterized among all the trees with given diameter (resp. matching number, domination number, vertex bipartition, the number of leaves). Secondly, the unique graph with the largest $$ZZ$$ index is determined among all the trees with given segment sequence (resp. the number of segments). Hamiltonicity via cohomology of right-angled Artin groups https://zbmath.org/1485.05095 2022-06-24T15:10:38.853281Z "Flores, Ramón" https://zbmath.org/authors/?q=ai:flores.ramon-j "Kahrobaei, Delaram" https://zbmath.org/authors/?q=ai:kahrobaei.delaram "Koberda, Thomas" https://zbmath.org/authors/?q=ai:koberda.thomas Summary: Let $$\Gamma$$ be a finite graph and let $$A(\Gamma)$$ be the corresponding right-angled Artin group. We characterize the Hamiltonicity of $$\Gamma$$ via the structure of the cohomology algebra of $$A(\Gamma)$$. In doing so, we define and develop a new canonical graph associated to a matrix, which as a consequence provides a novel perspective on the matrix determinant. Improved mixing rates of directed cycles by added connection https://zbmath.org/1485.05164 2022-06-24T15:10:38.853281Z "Gerencsér, Balázs" https://zbmath.org/authors/?q=ai:gerencser.balazs "Hendrickx, Julien M." https://zbmath.org/authors/?q=ai:hendrickx.julien-m The theme of this paper is the effect that the addition of random edges and non-reversibility have on the mixing time of a random walk on a graph. This is studied on a cycle of $$n$$ vertices. Thereon, $$k$$ disjoint paths are selected randomly and they are directed in the clockwise direction. For any two of them, the edges between the end of one and the beginning of the other are added. So if the particle that performs this random walk is at the beginning of such a path and chooses to follow the path the next hub (in the clockwise direction), it follows it all the way until its end in the clockwise direction with probability 1. If it choose to jump it selects the beginning of another interval selected uniformly at random. The parameter $$k$$ depends on $$n$$ and, in particular, it is set to $$n^{\sigma}$$ for some $$0< \sigma < 1$$. The parameter that is considered here is the spectral gap of the transition matrix. The main result is that this is greater than $$k/n$$, up to a polylogarithmic factor, with high probability over the random choice of the $$k$$ paths. The proof relies on the analysis of the spectral gap for a random walk on a similar random graph, where $$k$$ directed paths are formed which have length that is geometrically distributed and are joined as described above. Reviewer: Nikolaos Fountoulakis (Birmingham) On the average hitting times of the squares of cycles https://zbmath.org/1485.05166 2022-06-24T15:10:38.853281Z "Doi, Yoshiaki" https://zbmath.org/authors/?q=ai:doi.yoshiaki "Konno, Norio" https://zbmath.org/authors/?q=ai:konno.norio "Nakamigawa, Tomoki" https://zbmath.org/authors/?q=ai:nakamigawa.tomoki "Sakuma, Tadashi" https://zbmath.org/authors/?q=ai:sakuma.tadashi "Segawa, Etsuo" https://zbmath.org/authors/?q=ai:segawa.etsuo "Shinohara, Hidehiro" https://zbmath.org/authors/?q=ai:shinohara.hidehiro "Tamura, Shunya" https://zbmath.org/authors/?q=ai:tamura.shunya "Tanaka, Yuuho" https://zbmath.org/authors/?q=ai:tanaka.yuuho "Toyota, Kosuke" https://zbmath.org/authors/?q=ai:toyota.kosuke Summary: The exact formula for the average hitting time (HT, as an abbreviation) of simple random walks from one vertex to any other vertex on the square $$C_N^2$$ of an $$N$$-vertex cycle graph $$C_N$$ was given by \textit{N. Chair} [J. Stat. Phys. 154, No. 4, 1177--1190 (2014; Zbl 1291.82049)]. In that paper, the author gives the expression for the even $$N$$ case and the expression for the odd $$N$$ case separately. In this paper, by using an elementary method different from Chair [loc. cit.], we give a much simpler single formula for the HT's of simple random walks on $$C_N^2$$. Our proof is considerably short and fully combinatorial, in particular, has no-need of any spectral graph theoretical arguments. Not only the formula itself but also intermediate results through the process of our proof describe clear relations between the HT's of simple random walks on $$C_N^2$$ and the Fibonacci numbers. Large deviations for random walks on free products of finitely generated groups https://zbmath.org/1485.60007 2022-06-24T15:10:38.853281Z "Corso, Emilio" https://zbmath.org/authors/?q=ai:corso.emilio This paper is concerned with the theory of random walks on a class of finitely generated groups, and specifically to the investigation of the asymptotic properties of the distribution of the renormalized distance from the origin. The main result establishes the existence of the large deviation principle, with a proper convex rate function, for the distribution of the renormalized distance from the origin of a random walk on a free product of finitely generated groups, under a non-degeneracy assumption on the semigroup $$\Gamma$$ generated by the support of a probability measure $$\mu$$. From this result, it derives the same principle for nearest-neighbour random walks on regular trees.\\ The paper starts with the presentation of some preliminaries on random walks on finitely generated groups and reviewing some standard terminology from the theory of large deviations. This serves the purpose of provide the notation to be used, clarify the nature of the assumption imposed on the semigroup $$\Gamma$$, and explains some general facts that are employed in the proof of the main result. At the end of the article, some ideas on possible generalizations of the main theorem are brought together, and some open questions and conjectures are formulated. Reviewer: Hernando Burgos-Soto (Toronto) Random walks with multiple step lengths https://zbmath.org/1485.68243 2022-06-24T15:10:38.853281Z "Boczkowski, Lucas" https://zbmath.org/authors/?q=ai:boczkowski.lucas "Guinard, Brieuc" https://zbmath.org/authors/?q=ai:guinard.brieuc "Korman, Amos" https://zbmath.org/authors/?q=ai:korman.amos "Lotker, Zvi" https://zbmath.org/authors/?q=ai:lotker.zvi "Renault, Marc" https://zbmath.org/authors/?q=ai:renault.marc-s|renault.marc-p Summary: In nature, search processes that use randomly oriented steps of different lengths have been observed at both the microscopic and the macroscopic scales. Physicists have analyzed in depth two such processes on grid topologies: intermittent search, which uses two step lengths, and Lévy walk, which uses many. Taking a computational perspective, this paper considers the number of distinct step lengths $$k$$ as a complexity measure of the considered process. Our goal is to understand what is the optimal achievable time needed to cover the whole terrain, for any given value of $$k$$. Attention is restricted to dimension one, since on higher dimensions, the simple random walk already displays a quasi linear cover time. We say $$X$$ is a $$k$$-intermittent search on the one dimensional $$n$$-node cycle if there exists a probability distribution $$\mathbf{p}=(p_i)_{i=1}^k$$, and integers $$L_1,L_2,\ldots, L_k$$, such that on each step $$X$$ makes a jump $$\pm L_i$$ with probability $$p_i$$, where the direction of the jump $$(+$$ or $$-)$$ is chosen independently with probability 1/2. When performing a jump of length $$L_i$$, the process consumes time $$L_i$$, and is only considered to visit the last point reached by the jump (and not any other intermediate nodes). This assumption is consistent with biological evidence, in which entities do not search while moving ballistically. We provide upper and lower bounds for the cover time achievable by $$k$$-intermittent searches for any integer $$k$$. In particular, we prove that in order to reduce the cover time $${\varTheta}(n^2)$$ of a simple random walk to linear in $$n$$ up to logarithmic factors, roughly $$\frac{\log n}{\log\log n}$$ step lengths are both necessary and sufficient, and we provide an example where the lengths form an exponential sequence. In addition, inspired by the notion of intermittent search, we introduce the Walk or Probe Problem, which can be defined with respect to arbitrary graphs. Here, it is assumed that querying (probing) a node takes significantly more time than moving to a random neighbor. Hence, to efficiently probe all nodes, the goal is to balance the time spent walking randomly and the time spent probing. We provide preliminary results for connected graphs and regular graphs. For the entire collection see [Zbl 1428.68007].