<?xml version="1.0" encoding="utf-8"?> <feed xmlns="http://www.w3.org/2005/Atom"> <title type="text">Recent zbMATH articles in MSC 60C05</title> <id>https://zbmath.org/atom/cc/60C05</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/" /> <link href="https://zbmath.org/atom/cc/60C05" rel="self" /> <generator>Werkzeug</generator> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Counting partitions by genus. I. Genus 0 to 2</title> <id>https://zbmath.org/1552.05033</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.05033" /> <author> <name>&quot;Zuber, Jean-Bernard&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zuber.jean-bernard</uri> </author> <content type="text">Summary: The counting of partitions according to their genus is revisited. The case of genus 0 -- non-crossing partitions -- is well known. Our approach relies on two pillars: first a functional equation between generating functions, originally written in genus 0 and interpreted graphically by \textit{P. Cvitanovic} [Phys. Lett., B 99, No. 1, 49--52 (1981; \url{doi:10.1016/0370-2693(81)90801-7})], is generalized to higher genus; secondly, we show that all partitions may be reconstructed from the ``(semi)-primitive'' ones introduced by \textit{R. Cori} and \textit{G. Hetyei} [Electron. J. Comb. 25, No. 4, Research Paper P4.26, 37 p. (2018; Zbl 1402.05101)]. Explicit results for the generating functions of all types of partitions are obtained in genus 1 and 2.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Hamilton cycles in pseudorandom graphs</title> <id>https://zbmath.org/1552.05114</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.05114" /> <author> <name>&quot;Glock, Stefan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:glock.stefan</uri> </author> <author> <name>&quot;Munh谩 Correia, David&quot;</name> <uri>https://zbmath.org/authors/?q=ai:munha-correia.david</uri> </author> <author> <name>&quot;Sudakov, Benny&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sudakov.benny</uri> </author> <content type="text">Summary: Finding general conditions which ensure that a graph is Hamiltonian is a central topic in graph theory. An old and well-known conjecture in the area states that any \(d\)-regular \(n\)-vertex graph \(G\) whose second largest eigenvalue in absolute value \(\lambda(G)\) is at most \(d/C\), for some universal constant \(C &gt; 0\), has a Hamilton cycle. In this paper, we obtain two main results which make substantial progress towards this problem. Firstly, we settle this conjecture in full when the degree \(d\) is at least a small power of \(n\). Secondly, in the general case we show that \(\lambda(G) \leq d/C (\log n)^{1/3}\) implies the existence of a Hamilton cycle, improving the 20-year old bound of \(d/\log^{1 - o (1)} n\) of \textit{M. Krivelevich} and \textit{B. Sudakov} [Bolyai Soc. Math. Stud. 15, 199--262 (2006; Zbl 1098.05075)]. We use in a novel way a variety of methods, such as a robust P贸sa rotation-extension technique, the Friedman-Pippenger tree embedding with rollbacks and the absorbing method, combined with additional tools and ideas. Our results have several interesting applications. In particular, they imply the currently best-known bounds on the number of generators which guarantee the Hamiltonicity of random Cayley graphs, which is an important partial case of the well known Hamiltonicity conjecture of \textit{L. Lov谩sz} [in: Combinatorial structures and their applications. Proceedings of the Calgary international conference on combinatorial structures and their applications held at the University of Calgary, Calgary, Alberta, Canada, June, 1969. New York-London-Paris: Gordon and Breach, Science Publishers. 243--246 (1970; Zbl 0257.05122)]. They can also be used to improve a result of \textit{N. Alon} and \textit{J. Bourgain} [Geom. Funct. Anal. 24, No. 3, 721--739 (2014; Zbl 1377.11013)] on additive patterns in multiplicative subgroups.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Orthonormal representations, vector chromatic number, and extension complexity</title> <id>https://zbmath.org/1552.05132</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.05132" /> <author> <name>&quot;Balla, Igor&quot;</name> <uri>https://zbmath.org/authors/?q=ai:balla.igor</uri> </author> <content type="text">Summary: We construct a bipartite generalization of \textit{N. Alon} and \textit{M. Szegedy}'s nearly orthogonal vectors [Graphs Comb. 15, No. 1, 1--4 (1999; Zbl 0923.05006)], thereby obtaining strong bounds for several extremal problems involving the Lov谩sz theta function, vector chromatic number, minimum semidefinite rank, nonnegative rank, and extension complexity of polytopes. In particular, we answer a question from our previous work [\textit{I. Balla} et al., Discrete Comput. Geom. 64, No. 3, 654--670 (2020; Zbl 1450.05057)], while also addressing a question of \textit{P. Hrube拧} [Inf. Process. Lett. 112, No. 11, 457--461 (2012; Zbl 1243.15003)] and of \textit{M. Kwan} et al. [Trans. Am. Math. Soc. 375, No. 6, 4209--4250 (2022; Zbl 1491.52012)]. Along the way, we derive a couple of general lower bounds for the vector chromatic number which may be of independent interest. {\copyright} 2024 The Author(s). The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">The GHP scaling limit of uniform spanning trees of dense graphs</title> <id>https://zbmath.org/1552.05172</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.05172" /> <author> <name>&quot;Archer, Eleanor&quot;</name> <uri>https://zbmath.org/authors/?q=ai:archer.eleanor</uri> </author> <author> <name>&quot;Shalev, Matan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:shalev.matan</uri> </author> <content type="text">Summary: We consider dense graph sequences that converge to a connected graphon and prove that the GHP scaling limit of their uniform spanning trees (USTs) is Aldous' Brownian CRT. Furthermore, we are able to extract the precise scaling constant from the limiting graphon. As an example, we can apply this to the scaling limit of the USTs of the Erd枚s-R茅nyi sequence \((G(n,p))_{n\geq 1}\) for any fixed \(p\in (0,1]\), and sequences of dense expanders. A consequence of GHP convergence is that several associated quantities of the spanning trees also converge, such as the height, diameter and law of a simple random walk. {\copyright} 2024 The Authors. \textit{Random Structures \&amp; Algorithms} published by Wiley Periodicals LLC.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Asymptotic behaviour of the first positions of uniform parking functions</title> <id>https://zbmath.org/1552.60016</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60016" /> <author> <name>&quot;Bellin, Etienne&quot;</name> <uri>https://zbmath.org/authors/?q=ai:bellin.etienne</uri> </author> <content type="text">A parking function of size \(n\) is a function \(\pi_n: [\![1, n]\!] \rightarrow [\![1, n]\!]\) such that, if \(\pi'_n(1) \leq \cdots \leq \pi'_n(n)\) is the non-decreasing rearrangement of \((\pi_n(1), \dots, \pi_n(n))\), then \(\pi'_n(i) \leq i\) for all \(i\). Parking functions have been studied in a variety of contexts since their introduction by \textit{A. G. Konheim} and \textit{B. Weiss} [SIAM J. Appl. Math. 14, 1266--1274 (1966; Zbl 0201.50204)]. This paper studies the asymptotic behaviour of a random uniform parking function \(\pi_n\) of size \(n\), concentrating in particular on the probabilistic properties of the first \(k_n\) places. In a previous work by \textit{P. Diaconis} and \textit{A. Hicks} [Adv. Appl. Math. 89, 125--155 (2017; Zbl 1373.60019)], this asymptotics was studied in terms of the total variation distance when \(k_n=1\) and in terms of the Kolmogorov distance when \(k_n &lt;\!\!&lt;\sqrt{n/\log n}\). The author improves these results and shows that the first \(k_n\) places \((\pi_n(1), \dots, \pi_n(k_n))\) of \(\pi_n\) are asymptotically independent and identically distributed (i.i.d.) and uniform on \(\{1, 2, \dots, n\}\), for the total variation distance when \(k_n=o(\sqrt{n})\), and for the Kolmogorov distance when \(k_n=o(n)\). The main proof idea is to express the law of \(\pi_n\) in terms of a conditioned random walk and to control its moments uniformly in time. Such uniform estimates on conditioned random walks are delicate to establish and are of independent interest. The author further gives bounds for the rate of convergence and obtains limit theorems for the maximum and the sum of the first \(k_n\) parking places. Reviewer: Mei Yin (Denver)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Parking on Cayley trees and frozen Erd艖s-R茅nyi</title> <id>https://zbmath.org/1552.60017</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60017" /> <author> <name>&quot;Contat, Alice&quot;</name> <uri>https://zbmath.org/authors/?q=ai:contat.alice</uri> </author> <author> <name>&quot;Curien, Nicolas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:curien.nicolas</uri> </author> <content type="text">Summary: Consider a uniform rooted Cayley tree \(T_n\) with \(n\) vertices and let \(m\) cars arrive sequentially, independently, and uniformly on its vertices. Each car tries to park on its arrival node, and if the spot is already occupied, it drives towards the root of the tree and parks as soon as possible. \textit{M.-L. Lackner} and \textit{A. Panholzer} [J. Comb. Theory, Ser. A 142, 1--28 (2016; Zbl 1337.05048)] established a phase transition for this process when \(m \approx \frac{n}{2}\). In this work, we couple this model with a variant of the classical Erd艖s-R茅nyi random graph process. This enables us to describe the phase transition for the size of the components of parked cars using a modification of the multiplicative coalescent which we name the \textit{frozen multiplicative coalescent}. The geometry of critical parked clusters is also studied. Those trees are very different from Bienaym茅-Galton-Watson trees and should converge towards the growth-fragmentation trees canonically associated to the \(3 / 2\)-stable process that already appeared in the study of random planar maps.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Eve, Adam and the preferential attachment tree</title> <id>https://zbmath.org/1552.60018</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60018" /> <author> <name>&quot;Contat, Alice&quot;</name> <uri>https://zbmath.org/authors/?q=ai:contat.alice</uri> </author> <author> <name>&quot;Curien, Nicolas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:curien.nicolas</uri> </author> <author> <name>&quot;Lacroix, Perrine&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lacroix.perrine</uri> </author> <author> <name>&quot;Lasalle, Etienne&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lasalle.etienne</uri> </author> <author> <name>&quot;Rivoirard, Vincent&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rivoirard.vincent</uri> </author> <content type="text">This paper investigates a problem of network archaeology in the context of the Barab谩si-Albert (BA) model. The objective is to identify the initial vertex (``Adam'') in a large, growing random tree structure by outputting a subset of vertices (called the ``packet'') that contains Adam with high probability. The key insight presented is that Adam is either a high-degree vertex or closely connected to one (called ``Eve''). The study offers a new statistical approach for identifying this initial vertex by constructing confidence sets with reduced sizes, compared to previous methods, for achieving the desired level of certainty. The key contributions of this paper can be summarized as follows: \begin{itemize} \item[1.] Sharper bound for the size of the confidence set: The paper fills a gap in the literature by proving that the lower bound on the size of the confidence set is sharp. It constructs a confidence set, \(P_\varepsilon(n)\), which contains Adam with probability at least \(1-\varepsilon\). The authors demonstrate that this set's size scales as \(\varepsilon^{-1-\eta}\) for small \(\eta&gt;0\), improving upon previously known bounds that suggested the set's size could be as large as \(\varepsilon^{-2+o(1)}.\) \item[2.] Utilizing Eve to find Adam: The novel aspect of this work is the introduction of Eve, a vertex adjacent to Adam with a potentially large degree. The authors show that even if Adam has a relatively small degree, Eve is likely to have a high degree, allowing Adam's identification through their connection. This insight refines the search for Adam and reduces the size of the packet. \item[3.] Estimation of the degrees of vertices: The paper introduces precise asymptotic results for the degrees of vertices in the BA model. It provides upper and lower bounds on the probability that Adam and Eve's degrees meet specific conditions, enabling the effective construction of \(P_\varepsilon(n)\) based on their joint degree distribution. \item[4.] Application of stochastic techniques: The paper uses advanced stochastic tools, such as martingale theory and Beta and Gamma distributions, to derive the limiting degree distributions for vertices in the BA tree. These techniques are used to estimate the probability that Adam and Eve are included in the packet, providing rigorous justification for the proposed approach. \end{itemize} This paper offers a significant contribution to the study of random trees and network archaeology by providing a new method for identifying the initial vertex in a preferential attachment tree. The introduction of Eve as a tool to locate Adam and the sharper bounds on the size of the confidence set advance the theoretical understanding of random graph models. Reviewer: Da Wu (Philadelphia)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Erratum to: ``Statistical test for an urn model with random multidrawing and random addition''.</title> <id>https://zbmath.org/1552.60019</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60019" /> <author> <name>&quot;Crimaldi, Irene&quot;</name> <uri>https://zbmath.org/authors/?q=ai:crimaldi.irene</uri> </author> <author> <name>&quot;Louis, Pierre-Yves&quot;</name> <uri>https://zbmath.org/authors/?q=ai:louis.pierre-yves</uri> </author> <author> <name>&quot;Minelli, Ida G.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:minelli.ida-germana</uri> </author> <content type="text">Erratum to the authors' paper [ibid. 158, 342--360 (2023; Zbl 1519.60016)].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Polarised random \(k\)-SAT</title> <id>https://zbmath.org/1552.60020</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60020" /> <author> <name>&quot;Danielsson, Joel Larsson&quot;</name> <uri>https://zbmath.org/authors/?q=ai:danielsson.joel-larsson</uri> </author> <author> <name>&quot;Markstr枚m, Klas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:markstrom.klas</uri> </author> <content type="text">Summary: In this paper we study a variation of the random \(k\)-SAT problem, called polarised random \(k\)-SAT, which contains both the classical random \(k\)-SAT model and the random version of monotone \(k\)-SAT another well-known NP-complete version of SAT. In this model there is a polarisation parameter \(p\), and in half of the clauses each variable occurs negated with probability \(p\) and pure otherwise, while in the other half the probabilities are interchanged. For \(p=1/2\) we get the classical random \(k\)-SAT model, and at the other extreme we have the fully polarised model where \(p=0\), or 1. Here there are only two types of clauses: clauses where all \(k\) variables occur pure, and clauses where all \(k\) variables occur negated. That is, for \(p=0\), and \(p=1\), we get an instance of random \textit{monotone} \(k\)-SAT. We show that the threshold of satisfiability does not decrease as \(p\) moves away from \(\frac{1}{2}\) and thus that the satisfiability threshold for polarised random \(k\)-SAT with \(p\neq \frac{1}{2}\) is an upper bound on the threshold for random \(k\)-SAT. Hence the satisfiability threshold for random monotone \(k\)-SAT is at least as large as for random \(k\)-SAT, and we conjecture that asymptotically, for a fixed \(k\), the two thresholds coincide.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Records in the infinite occupancy scheme</title> <id>https://zbmath.org/1552.60021</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60021" /> <author> <name>&quot;Derbazi, Zakaria&quot;</name> <uri>https://zbmath.org/authors/?q=ai:derbazi.zakaria</uri> </author> <author> <name>&quot;Gnedin, Alexander&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gnedin.alexander-v</uri> </author> <author> <name>&quot;Marynych, Alexander&quot;</name> <uri>https://zbmath.org/authors/?q=ai:marynych.alexander-v</uri> </author> <content type="text">Summary: We consider the classic infinite occupancy scheme, where balls are thrown in boxes independently, with probability \(p_j\) of hitting box \(j\). Each time a box receives its first ball we speak of a \textit{record} and, more generally, call an \(r\)-\textit{record} every event when a box receives its \(r\)th ball. Assuming that the sequence \((p_j)\) is not decaying too fast, we show that after many balls have been thrown, the suitably scaled point process of \(r\)-record times is approximately Poisson. The joint convergence of \(r\)-record processes is argued under a condition of regular variation.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Asymptotic normality of pattern counts in conjugacy classes</title> <id>https://zbmath.org/1552.60022</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60022" /> <author> <name>&quot;F茅ray, Valentin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:feray.valentin</uri> </author> <author> <name>&quot;Kammoun, Mohamed Slim&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kammoun.slim</uri> </author> <content type="text">Summary: We prove, under mild conditions on fixed points and 2-cycles, the asymptotic normality of vincular pattern counts for a permutation chosen uniformly at random in a conjugacy class. Additionally, we prove that the limiting variance is always non-degenerate for classical pattern counts. The proof uses weighted dependency graphs.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">The Ulam-Hammersley problem for multiset permutations</title> <id>https://zbmath.org/1552.60023</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60023" /> <author> <name>&quot;Gerin, Lucas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gerin.lucas</uri> </author> <content type="text">Summary: We obtain the asymptotic behaviour of the longest increasing/non-decreasing subsequences in a random uniform multiset permutation in which each element in \(\{1,\dots,n\}\) occurs \(k\) times, where \(k\) may depend on \(n\). This generalises the famous Ulam-Hammersley problem of the case \(k=1\). The proof relies on poissonisation and on a careful non-asymptotic analysis of variants of the Hammersley-Aldous-Diaconis particle system.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">An absorbing version of the top-to-random shuffle</title> <id>https://zbmath.org/1552.60024</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60024" /> <author> <name>&quot;Lewis, Joel Brewster&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lewis.joel-brewster</uri> </author> <author> <name>&quot;Rai, Mehr&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rai.mehr</uri> </author> <content type="text">Summary: Consider a randomly shuffled deck of \(2n\) cards with \(n\) red cards and \(n\) black cards. We study the average number of moves it takes to go from a randomly shuffled deck to a deck that alternates in color by performing the following move: if the top card and the bottom card of the deck differ in color, place the top card at the bottom of the deck; otherwise, insert the top card randomly in the deck. We use tools from combinatorics, probability, and linear algebra to study this process.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Coboundary expansion for the union of determinantal hypertrees</title> <id>https://zbmath.org/1552.60025</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60025" /> <author> <name>&quot;M茅sz谩ros, Andr谩s&quot;</name> <uri>https://zbmath.org/authors/?q=ai:meszaros.andras</uri> </author> <content type="text">Summary: We prove that for any large enough constant \(k\), the union of \(k\) independent \(d\)-dimensional determinantal hypertrees is a coboundary expander with high probability. {\copyright} 2024 Wiley Periodicals LLC.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">A combinatorial problem related to the classical probability</title> <id>https://zbmath.org/1552.60026</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60026" /> <author> <name>&quot;Zhou, Jiang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhou.jiang|jiang.zhou|zhou.jiang.1</uri> </author> <content type="text">Summary: In the classical probability model, let \(f(n)\) be the maximum number of pairwise independent events for the sample space with \(n\) sample points. The determination of \(f(n)\) is equivalent to the problem of determining the maximum cardinality of specific intersecting families on the set \(\{1, 2, \dots, n\}\). We show that \(f(n) \leq n + 1\), and \(f(n) = n + 1\) if there exists a Hadamard matrix of order \(n\).</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">A strong FKG inequality for multiple events</title> <id>https://zbmath.org/1552.60038</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60038" /> <author> <name>&quot;Gladkov, Nikita&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gladkov.nikita-a</uri> </author> <content type="text">Summary: We extend the Fortuin-Kasteleyn-Ginibre (FKG) inequality to cover multiple events with equal pairwise intersections. We then apply this inequality to resolve Kahn's question on positive associated measures, as well as prove new inequalities concerning random graphs and probabilities of connection in Bernoulli percolation. {\copyright} 2024 The Author(s). \textit{Bulletin of the London Mathematical Society} is copyright {\copyright} London Mathematical Society.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">A continuous version of the selfish parking problem</title> <id>https://zbmath.org/1552.60127</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60127" /> <author> <name>&quot;Ananjevskii, S. M.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ananjevskii.sergey-m|ananjevskii.s-m</uri> </author> <author> <name>&quot;Chen, A. P.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chen.aleksandr-petrovich</uri> </author> <content type="text">Summary: A new model of the random filling of a segment of large length with intervals of smaller length is studied. A new statement of the problem is considered. A model in which unit intervals are placed on a segment only if the segment being filled has a length of at least 2 is considered. The position of the interval to be placed is subject to a uniform distribution law. The behavior of the average number of intervals placed is studied depending on the length of the segment to be filled. An exact expression is obtained for the analog of R茅nyi's constant.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Markov chains generating random permutations and set partitions</title> <id>https://zbmath.org/1552.60214</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60214" /> <author> <name>&quot;Stark, Dudley&quot;</name> <uri>https://zbmath.org/authors/?q=ai:stark.dudley</uri> </author> <content type="text">Summary: The Chinese Restaurant Process may be considered to be a Markov chain which generates permutations on \(n\) elements proportionally to absorption probabilities \(\theta^{|\pi|}, \theta &gt;0\), where \(|\pi|\) is the number of cycles of permutation \(\pi\). We prove a theorem which provides a way of finding Markov chains, restricted to directed graphs called arborescences, and with given absorption probabilities. We find transition probabilities for the Chinese Restaurant Process arborescence with variable absorption probabilities. The method is applied to an arborescence constructing set partitions, resulting in an analogue of the Chinese Restaurant Process for set partitions. We also apply our method to an arborescence for the Feller Coupling Process. We show how to modify the Chinese Restaurant Process, its set partition analogue, and the Feller Coupling Process to generate derangements and set partitions having no blocks of size one.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Affine diminishing urns</title> <id>https://zbmath.org/1552.60275</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60275" /> <author> <name>&quot;Gao, Sh.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gao.shuyang.1</uri> </author> <author> <name>&quot;Mahmoud, H.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:mahmoud.hosam-m</uri> </author> <content type="text">Summary: We consider a large class of white-blue affine balanced urns diminished by the repeated drawing of multisets. We investigate the composition of the urn at different stages of drawing. Assuming the urn starts with \(n\) balls, of which \(\alpha n + g(n)\), with \(\alpha \in [0,1]\) and \(g(n) = o(n)\), are white, we find a major phase transition between a sublinear number of draws \(j = o(n)\) and the linear case in which \(j = \theta n + h(n)\). In both sublinear and linear phases, we get central limit theorems; however, the normalization in each phase is significantly different. The interplay of the different forces, such as \(\theta, \alpha \), and the perturbation functions \(g(n)\) and \(h(n)\), enforce a number of restrictions and influences the parameterization in the central limit theorem. The methods of proof are based on recurrence, martingales, and asymptotic analysis. We then discuss two possible applications of this class. One application is a generalized OK Corral urn, and the other is on the dynamics of market depth in the stock market.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Mixing trichotomy for an Ehrenfest urn with impurities</title> <id>https://zbmath.org/1552.60286</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60286" /> <author> <name>&quot;Quattropani, Matteo&quot;</name> <uri>https://zbmath.org/authors/?q=ai:quattropani.matteo</uri> </author> <content type="text">Summary: We consider a version of the classical Ehrenfest urn model with two urns and two types of balls: regular and heavy. Each ball is selected independently according to a Poisson process having rate 1 for regular balls and rate \(\alpha\in(0, 1)\) for heavy balls, and once a ball is selected, is placed in a urn uniformly at random. We study the asymptotic behavior when the total number of balls, \(N\), goes to infinity, and the number of heavy ball is set to \(m_N\in\{1, \dots, N - 1\}\). We focus on the observable given by the total number of balls in the left urn, which converges to a binomial distribution of parameter 1/2, regardless of the choice of the two parameters, \(\alpha\) and \(m_N\). We study the speed of convergence and show that this can exhibit three different phenomenologies depending on the choice of the two parameters of the model.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Gibbs partitions: a comprehensive phase diagram</title> <id>https://zbmath.org/1552.60289</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60289" /> <author> <name>&quot;Stufler, Benedikt&quot;</name> <uri>https://zbmath.org/authors/?q=ai:stufler.benedikt</uri> </author> <content type="text">Summary: We study Gibbs partition models, also known as composition schemes. Our main results comprehensively describe their phase diagram, including a phase transition from the convergent case described in [\textit{B. Stufler}, Random Struct. Algorithms 53, No. 3, 537--558 (2018; Zbl 1398.05184)] to a new dense regime characterized by a linear number of components with fluctuations of smaller order quantified by an \(\alpha\)-stable law for \(1 &lt; \alpha \leq 2\). We prove a functional scaling limit for a process whose jumps correspond to the component sizes and discuss applications to extremal component sizes. At the transition we observe a mixture of the two asymptotic shapes. We also treat extended composition schemes and prove a local limit theorem in a dilute regime with the limiting law being related to an \(\alpha\)-stable law for \(0 &lt; \alpha &lt; 1\). We describe the asymptotic size of the largest components via a point process limit.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/60C05"> <title type="text">Long-range first-passage percolation on the torus</title> <id>https://zbmath.org/1552.60291</id> <updated>2025-03-24T18:23:18.698908Z</updated> <link href="https://zbmath.org/1552.60291" /> <author> <name>&quot;van der Hofstad, Remco&quot;</name> <uri>https://zbmath.org/authors/?q=ai:van-der-hofstad.remco-w</uri> </author> <author> <name>&quot;Lodewijks, Bas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lodewijks.bas</uri> </author> <content type="text">Summary: We study a geometric version of first-passage percolation on the complete graph, known as long-range first-passage percolation. Here, the vertices of the complete graph \(\mathcal{K}_n\) are embedded in the \(d\)-dimensional torus \(\mathbb{T}_n^d\), and each edge \(e\) is assigned an independent transmission time \(T_e =\Vert e\Vert_{\mathbb{T}_n^d}^{\alpha} E_e\), where \(E_e\) is a rate-one exponential random variable associated with the edge \(e, \Vert \cdot \Vert_{\mathbb{T}_n^d}\) denotes the torus-norm, and \(\alpha \geq 0\) is a parameter. We are interested in the case \(\alpha \in [0,d)\), which corresponds to the instantaneous percolation regime for long-range first-passage percolation on \(\mathbb{Z}^d\) studied by \textit{S. Chatterjee} and \textit{P. S. Dey} [Commun. Pure Appl. Math. 69, No. 2, 203--256 (2016; Zbl 1332.60133)], and which extends first-passage percolation on the complete graph (the \(\alpha =0\) case) studied by \textit{S. Janson} [Comb. Probab. Comput. 8, No. 4, 347--361 (1999; Zbl 0934.05115)]. We consider the typical distance, flooding time, and diameter of the model. Our results show a 1, 2, 3-type result, akin to first-passage percolation on the complete graph as shown by Janson [loc. cit.]. The results also provide a quantitative perspective to the qualitative results observed by Chatterjee and Dey [loc. cit.] on \(\mathbb{Z}^d\).</content> </entry> </feed>