bluuebunny/crossref_metadata_2025 huggingface dataset:
Acyclic, Star and Oriented Colourings of Graph Subdivisions
Authors: Wood David R.
Published: August 2021

Let G be a graph with chromatic number χ (G). A vertex colouring of G is \emphacyclic if each bichromatic subgraph is a forest. A \emphstar colouring of G is an acyclic colouring in which each bichromatic subgraph is a star forest. Let χ _a(G) and χ _s(G) denote the acyclic and star chromatic numbers of G. This paper investigates acyclic and star colourings of subdivisions. Let G' be the graph obtained from G by subdividing each edge once. We prove that acyclic (respectively, star) colourings of G' correspond to vertex partitions of G in which each subgraph has small arboricity (chromatic index). It follows that χ _a(G'), χ _s(G') and χ (G) are tied, in the sense that each is bounded by a function of the other. Moreover the binding functions that we establish are all tight. The \emphoriented chromatic number χ ^→(G) of an (undirected) graph G is the maximum, taken over all orientations D of G, of the minimum number of colours in a vertex colouring of D such that between any two colour classes, all edges have the same direction. We prove that χ ^→(G')=χ (G) whenever χ (G)≥ 9.
Balanced Avoidance Games on Random Graphs
Authors: Marciniszyn Martin , Mitsche Dieter , Stojaković Miloš
Published: August 2021

We introduce and study balanced online graph avoidance games on the random graph process. The game is played by a player we call Painter. Edges of the complete graph with $n$ vertices are revealed two at a time in a random order. In each move, Painter immediately and irrevocably decides on a balanced coloring of the new edge pair: either the first edge is colored red and the second one blue or vice versa. His goal is to avoid a monochromatic copy of a given fixed graph $H$ in both colors for as long as possible. The game ends as soon as the first monochromatic copy of $H$ has appeared. We show that the duration of the game is determined by a threshold function $m_H = m_H(n)$. More precisely, Painter will asymptotically almost surely (a.a.s.) lose the game after $m = \omega (m_H)$ edge pairs in the process. On the other hand, there is an essentially optimal strategy, that is, if the game lasts for $m = o(m_H)$ moves, then Painter will a.a.s. successfully avoid monochromatic copies of H using this strategy. Our attempt is to determine the threshold function for certain graph-theoretic structures, e.g., cycles.
On infinite permutations
Authors: Fon-Der-Flaass Dmitri G. , Frid Anna E.
Published: August 2021

We define an infinite permutation as a sequence of reals taken up to the order, or, equivalently, as a linear ordering of a finite or countable set. Then we introduce and characterize periodic permutations; surprisingly, for each period $t$ there is an infinite number of distinct $t$-periodic permutations. At last, we introduce a complexity notion for permutations analogous to subword complexity for words, and consider the problem of minimal complexity of non-periodic permutations. Its answer is different for the right infinite and the bi-infinite case.
Equivalent Subgraphs of Order $3$
Authors: Nakamigawa Tomoki
Published: August 2021

It is proved that any graph of order $14n/3 + O(1)$ contains a family of n induced subgraphs of order $3$ such that they are vertex-disjoint and equivalent to each other.
An extremal problem on trees and database theory
Authors: Katona Gyula O.H. , Tichler Krisztián
Published: August 2021

We consider an extremal problem on labelled directed trees and applications to database theory. Among others, we will show explicit keysystems on an underlying set of size $n$, that cannot be represented by a database of less than $2^{n(1-c\cdot \log \log n / \log n)}$ rows.
Discrepancy of Products of Hypergraphs
Authors: Doerr Benjamin , Gnewuch Michael , Hebbinghaus Nils
Published: August 2021

For a hypergraph $\mathcal{H} = (V,\mathcal{E})$, its $d$―fold symmetric product is $\Delta^d \mathcal{H} = (V^d,\{ E^d | E \in \mathcal{E} \})$. We give several upper and lower bounds for the $c$-color discrepancy of such products. In particular, we show that the bound $\textrm{disc}(\Delta^d \mathcal{H},2) \leq \textrm{disc}(\mathcal{H},2)$ proven for all $d$ in [B. Doerr, A. Srivastav, and P. Wehr, Discrepancy of Cartesian products of arithmetic progressions, Electron. J. Combin. 11(2004), Research Paper 5, 16 pp.] cannot be extended to more than $c = 2$ colors. In fact, for any $c$ and $d$ such that $c$ does not divide $d!$, there are hypergraphs having arbitrary large discrepancy and $\textrm{disc}(\Delta^d \mathcal{H},c) = \Omega_d(\textrm{disc}(\mathcal{H},c)^d)$. Apart from constant factors (depending on $c$ and $d$), in these cases the symmetric product behaves no better than the general direct product $\mathcal{H}^d$, which satisfies $\textrm{disc}(\mathcal{H}^d,c) = O_{c,d}(\textrm{disc}(\mathcal{H},c)^d)$.
Non-Determinism and Nash Equilibria for Sequential Game over Partial Order
Authors: Le Roux Stéphane
Published: August 2021

In sequential games of traditional game theory, backward induction guarantees existence of Nash equilibrium by yielding a sub-game perfect equilibrium. But if payoffs range over a partially ordered set instead of the reals, then the backward induction predicate does no longer imply the Nash equilibrium predicate. Non-determinism is a solution: a suitable non-deterministic backward induction function returns a non-deterministic strategy profile which is a non-deterministic Nash equilibrium. The main notions and results in this article are constructive, conceptually simple and formalised in the proof assistant Coq.
Classical Combinatory Logic
Authors: Nour Karim
Published: August 2021

Combinatory logic shows that bound variables can be eliminated without loss of expressiveness. It has applications both in the foundations of mathematics and in the implementation of functional programming languages. The original combinatory calculus corresponds to minimal implicative logic written in a system "à la Hilbert''. We present in this paper a combinatory logic which corresponds to propositional classical logic. This system is equivalent to the system $λ ^{Sym}_{Prop}$ of Barbanera and Berardi.
The call-by-value λµ∧∨-calculus
Authors: Nour Karim , Saber Khelifa
Published: August 2021

In this paper, we introduce the $λ μ ^{∧∨}$ - call-by-value calculus and we give a proof of the Church-Rosser property of this system. This proof is an adaptation of that of Andou (2003) which uses an extended parallel reduction method and complete development.
On-line coloring of $I_s$-free graphs
Authors: Cieslik Iwona , Kozik Marcin , Micek Piotr
Published: August 2021

An on-line vertex coloring algorithm receives vertices of a graph in some externally determined order. Each new vertex is presented together with a set of the edges connecting it to the previously presented vertices. As a vertex is presented, the algorithm assigns it a color which cannot be changed afterwards. The on-line coloring problem was addressed for many different classes of graphs defined in terms of forbidden structures. We analyze the class of $I_s$-free graphs, i.e., graphs in which the maximal size of an independent set is at most $s-1$. An old Szemerédi's result implies that for each on-line algorithm A there exists an on-line presentation of an $I_s$-free graph $G$ forcing A to use at least $\frac{s}{2}χ ^{(G)}$ colors. We prove that any greedy algorithm uses at most $\frac{s}{2}χ^{(G)}$ colors for any on-line presentation of any $I_s$-free graph $G$. Since the class of co-planar graphs is a subclass of $I_5$-free graphs all greedy algorithms use at most $\frac{5}{2}χ (G)$ colors for co-planar $G$'s. We prove that, even in a smaller class, this is an almost tight bound.
On-line Adaptive Chain Covering of Upgrowing Posets
Authors: Bosek Bartłomiej , Micek Piotr
Published: August 2021

We analyze on-line chain partitioning problem and its variants as a two-person game. One person (Spoiler) builds an on-line poset presenting one point at time. The other one (Algorithm) assigns new point to a chain. Kierstead gave a strategy for Algorithm showing that width w posets can be on-line chain partitioned into $\frac{{5}^{w-1}}{4}$ chains. Felsner proved that if Spoiler presents an upgrowing poset, i.e., each new point is maximal at the moment of its arrival then there is a strategy for Algorithm using at most $\binom{w+1}{2}$ chains and it is best possible. An adaptive variant of this problem allows Algorithm to assign to the new point a set of chains and than to remove some of them (but not all) while covering next points. Felsner stated a hypothesis that in on-line adaptive chain covering of upgrowing posets Algorithm may use smaller number of chains than in non-adaptive version. In this paper we provide an argument suggesting that it is true. We present a class of upgrowing posets in which Spoiler has a strategy forcing Algorithm to use at least $\binom{w+1}{2}$ chains (in non-adaptive version) and Algorithm has a strategy using at most $O(w\sqrt{w})$ chains in adaptive version.
Random Boolean expressions
Authors: Gardy Danièle
Published: August 2021

We examine how we can define several probability distributions on the set of Boolean functions on a fixed number of variables, starting from a representation of Boolean expressions by trees. Analytic tools give us a systematic way to prove the existence of probability distributions, the main challenge being the actual computation of the distributions. We finally consider the relations between the probability of a Boolean function and its complexity.
Dihedral f-tilings of the sphere by rhombi and triangles
Authors: Breda Ana , Santos Altino F.
Published: August 2021

We classify, up to an isomorphism, the class of all dihedral f-tilings of S^2, whose prototiles are a spherical triangle and a spherical rhombus. The equiangular case was considered and classified in Ana M. Breda and Altino F. Santos, Dihedral f-tilings of the sphere by spherical triangles and equiangular well-centered quadrangles. Here we complete the classification considering the case of non-equiangular rhombi.
$S$-constrained random matrices
Authors: Gravier Sylvain , Ycart Bernard
Published: August 2021

Let $S$ be a set of $d$-dimensional row vectors with entries in a $q$-ary alphabet. A matrix $M$ with entries in the same $q$-ary alphabet is $S$-constrained if every set of $d$ columns of $M$ contains as a submatrix a copy of the vectors in $S$, up to permutation. For a given set $S$ of $d$-dimensional vectors, we compute the asymptotic probability for a random matrix $M$ to be $S$-constrained, as the numbers of rows and columns both tend to infinity. If $n$ is the number of columns and $m=m_n$ the number of rows, then the threshold is at $m_n= \alpha_d \log (n)$, where $\alpha_d$ only depends on the dimension $d$ of vectors and not on the particular set $S$. Applications to superimposed codes, shattering classes of functions, and Sidon families of sets are proposed. For $d=2$, an explicit construction of a $S$-constrained matrix is given.
Label-based parameters in increasing trees
Authors: Kuba Markus , Panholzer Alois
Published: August 2021

Grown simple families of increasing trees are a subclass of increasing trees, which can be constructed by an insertion process. Three such tree families contained in the grown simple families of increasing trees are of particular interest: $\textit{recursive trees}$, $\textit{plane-oriented recursive trees}$ and $\textit{binary increasing trees}$. Here we present a general approach for the analysis of a number of label-based parameters in a random grown simple increasing tree of size $n$ as, e.g., $\textit{the degree of the node labeled j}$, $\textit{the subtree-size of the node labeled j}$, etc. Further we apply the approach to the random variable $X_{n,j,a}$, which counts the number of size-$a$ branches attached to the node labeled $j$ (= subtrees of size $a$ rooted at the children of the node labeled $j$) in a random grown simple increasing tree of size $n$. We can give closed formulæ for the probability distribution and the factorial moments. Furthermore limiting distribution results for $X_{n,j,a}$ are given dependent on the growth behavior of $j=j(n)$ compared to $n$.
Bipartite Random Graphs and Cuckoo Hashing
Authors: Kutzelnigg Reinhard
Published: August 2021

The aim of this paper is to extend the analysis of Cuckoo Hashing of Devroye and Morin in 2003. In particular we make several asymptotic results much more precise. We show, that the probability that the construction of a hash table succeeds, is asymptotically $1-c(\varepsilon)/m+O(1/m^2)$ for some explicit $c(\varepsilon)$, where $m$ denotes the size of each of the two tables, $n=m(1- \varepsilon)$ is the number of keys and $\varepsilon \in (0,1)$. The analysis rests on a generating function approach to the so called Cuckoo Graph, a random bipartite graph. We apply a double saddle point method to obtain asymptotic results covering tree sizes, the number of cycles and the probability that no complex component occurs.
Extended Rate, more GFUN
Authors: Rubey Martin
Published: August 2021

We present a software package that guesses formulas for sequences of, for example, rational numbers or rational functions, given the first few terms. Thereby we extend and complement Christian Krattenthaler’s program $\mathtt{Rate}$ and the relevant parts of Bruno Salvy and Paul Zimmermann’s $\mathtt{GFUN}$.
Limit distribution of the size of the giant component in a web random graph
Authors: Pavlov Yuri
Published: August 2021

Consider random graph with $N+ 1$ vertices as follows. The degrees of vertices $1,2,\ldots, N$ are the independent identically distributed random variables $\xi_1, \xi_2, \ldots , \xi_N$ with distribution $\mathbf{P}\{\xi_1 \geq k\}=k^{− \tau},$ $k= 1,2,\ldots,$ $\tau \in (1,2)$,(1) and the vertex $N+1$ has degree $0$, if the sum $\zeta_N=\xi_1+ \ldots +\xi_N$ is even, else degree is $1$. From (1) we get that $p_k=\mathbf{P}\{\xi_1=k\}=k^{−\tau}−(k+ 1)^{−\tau}$, $k= 1,2,\ldots$ Let $G(k_1, \ldots , k_N)$ be a set of graphs with $\xi_1=k_1,\ldots, \xi_N=k_N$. If $g$ is a realization of random graph then $\mathbf{P}\{g \in G(k_1, \ldots , k_N)\}=p_{k_1} \cdot \ldots \cdot p_{k_N}$. The probability distribution on the set of graph is defined such that for a vector $(k_1, \ldots, k_N)$ all graphs, lying in $G(k_1, \ldots , k_N)$, are equiprobable. Studies of the past few years show that such graphs are good random graph models for Internet and other networks topology description (see, for example, H. Reittu and I. Norros (2004)).To build the graph, we have $N$ numbered vertices and incident to vertex $i \xi_i$ stubs, $i= 1, \ldots , N$.All stubs need to be connected to another stub to construct the graph. The stubs are numbered in an arbitrary order from $1$ to $\zeta_N$. Let $\eta_{(N)}$ be the maximum degree of the vertices.
An extension to overpartitions of Rogers-Ramanujan identities for even moduli
Authors: Corteel Sylvie , Lovejoy Jeremy , Mallet Olivier
Published: August 2021

We investigate class of well-poised basic hypergeometric series $\tilde{J}_{k,i}(a;x;q)$, interpreting these series as generating functions for overpartitions defined by multiplicity conditions. We also show how to interpret the $\tilde{J}_{k,i}(a;1;q)$ as generating functions for overpartitions whose successive ranks are bounded, for overpartitions that are invariant under a certain class of conjugations, and for special restricted lattice paths. We highlight the cases $(a,q) \to (1/q,q)$, $(1/q,q^2)$, and $(0,q)$, where some of the functions $\tilde{J}_{k,i}(a;x;q)$ become infinite products. The latter case corresponds to Bressoud's family of Rogers-Ramanujan identities for even moduli.
Mixed Powers of Generating Functions
Authors: Lladser Manuel
Published: August 2021

Given an integer $m \geq 1$, let $\| \cdot \|$ be a norm in $\mathbb{R}^{m+1}$ and let $\mathbb{S}_+^m$ denote the set of points $\mathbf{d}=(d_0,\ldots,d_m)$ in $\mathbb{R}^{m+1}$ with nonnegative coordinates and such that $\| \mathbf{d} \|=1$. Consider for each $1 \leq j \leq m$ a function $f_j(z)$ that is analytic in an open neighborhood of the point $z=0$ in the complex plane and with possibly negative Taylor coefficients. Given $\mathbf{n}=(n_0,\ldots,n_m)$ in $\mathbb{Z}^{m+1}$ with nonnegative coordinates, we develop a method to systematically associate a parameter-varying integral to study the asymptotic behavior of the coefficient of $z^{n_0}$ of the Taylor series of $\prod_{j=1}^m \{f_j(z)\}^{n_j}$, as $\| \mathbf{n} \| \to \infty$. The associated parameter-varying integral has a phase term with well specified properties that make the asymptotic analysis of the integral amenable to saddle-point methods: for many $\mathbf{d} \in \mathbb{S}_+^m$, these methods ensure uniform asymptotic expansions for $[z^{n_0}] \prod_{j=1}^m \{f_j(z)\}^{n_j}$ provided that $\mathbf{n}/ \| \mathbf{n} \|$ stays sufficiently close to $\mathbf{d}$ as $\| \mathbf{n} \| \to \infty$. Our method finds applications in studying the asymptotic behavior of the coefficients of a certain multivariable generating functions as well as in problems related to the Lagrange inversion formula for instance in the context random planar maps.
The first ascent of size $d$ or more in compositions
Authors: Brennan Charlotte , Knopfmacher Arnold
Published: August 2021

A composition of a positive integer $n$ is a finite sequence of positive integers $a_1, a_2, \ldots, a_k$ such that $a_1+a_2+ \cdots +a_k=n$. Let $d$ be a fixed nonnegative integer. We say that we have an ascent of size $d$ or more at position $i$, if $a_{i+1}\geq a_i+d$. We study the average position, initial height and end height of the first ascent of size $d$ or more in compositions of $n$ as $n \to \infty$.
On the non-randomness of modular arithmetic progressions: a solution to a problem by V. I. Arnold
Authors: Cesaratto Eda , Plagne Alain , Vallée Brigitte
Published: August 2021

We solve a problem by V. I. Arnold dealing with "how random" modular arithmetic progressions can be. After making precise how Arnold proposes to measure the randomness of a modular sequence, we show that this measure of randomness takes a simplified form in the case of arithmetic progressions. This simplified expression is then estimated using the methodology of dynamical analysis, which operates with tools coming from dynamical systems theory. In conclusion, this study shows that modular arithmetic progressions are far from behaving like purely random sequences, according to Arnold's definition.
The Diameter of the Minimum Spanning Tree of a Complete Graph
Authors: Addario-Berry Louigi , Broutin Nicolas , Reed Bruce
Published: August 2021

Let $X_1,\ldots,X_{n\choose 2}$ be independent identically distributed weights for the edges of $K_n$. If $X_i \neq X_j$ for$ i \neq j$, then there exists a unique minimum weight spanning tree $T$ of $K_n$ with these edge weights. We show that the expected diameter of $T$ is $Θ (n^{1/3})$. This settles a question of [Frieze97].
A probabilistic analysis of a leader election algorithm
Authors: Mohamed Hanene
Published: August 2021

A leader election algorithm is an elimination process that divides recursively into tow subgroups an initial group of n items, eliminates one subgroup and continues the procedure until a subgroup is of size 1. In this paper the biased case is analyzed. We are interested in the cost of the algorithm e. the number of operations needed until the algorithm stops. Using a probabilistic approach, the asymptotic behavior of the algorithm is shown to be related to the behavior of a hitting time of two random sequences on [0,1].
Queue Layouts of Graph Products and Powers
Authors: Wood David R.
Published: August 2021

A \emphk-queue layout of a graph G consists of a linear order σ of V(G), and a partition of E(G) into k sets, each of which contains no two edges that are nested in σ . This paper studies queue layouts of graph products and powers
Minimal and maximal plateau lengths in Motzkin paths
Authors: Prodinger Helmut , Wagner Stephan
Published: August 2021

The minimal length of a plateau (a sequence of horizontal steps, preceded by an up- and followed by a down-step) in a Motzkin path is known to be of interest in the study of secondary structures which in turn appear in mathematical biology. We will treat this and the related parameters  maximal plateau length, horizontal segment and maximal horizontal segment as well as some similar parameters in unary-binary trees by a pure generating functions approach―-Motzkin paths are derived from Dyck paths by a substitution process. Furthermore, we provide a pretty general analytic method to obtain means and limiting distributions for these parameters. It turns out that the maximal plateau and the maximal horizontal segment follow a Gumbel distribution.
The average position of the first maximum in a sample of geometric random variables
Authors: Archibald Margaret , Knopfmacher Arnold
Published: August 2021

We consider samples of n geometric random variables $(Γ _1, Γ _2, \dots Γ _n)$ where $\mathbb{P}\{Γ _j=i\}=pq^{i-1}$, for $1≤j ≤n$, with $p+q=1$. The parameter we study is the position of the first occurrence of the maximum value in a such a sample. We derive a probability generating function for this position with which we compute the first two (factorial) moments. The asymptotic technique known as Rice's method then yields the main terms as well as the Fourier expansions of the fluctuating functions arising in the expected value and the variance.
Tail Bounds for the Wiener Index of Random Trees
Authors: Khan Tämur Ali , Neininger Ralph
Published: August 2021

Upper and lower bounds for the tail probabilities of the Wiener index of random binary search trees are given. For upper bounds the moment generating function of the vector of Wiener index and internal path length is estimated. For the lower bounds a tree class with sufficiently large probability and atypically large Wiener index is constructed. The methods are also applicable to related random search trees.
Uniqueness of polynomial canonical representations
Authors: Lladser Manuel
Published: August 2021

Let $P(z)$ and $Q(y)$ be polynomials of the same degree $k \geq 1$ in the complex variables $z$ and $y$, respectively. In this extended abstract we study the non-linear functional equation $P(z)=Q(y(z))$, where $y(z)$ is restricted to be analytic in a neighborhood of $z=0$. We provide sufficient conditions to ensure that all the roots of $Q(y)$ are contained within the range of $y(z)$ as well as to have $y(z)=z$ as the unique analytic solution of the non-linear equation. Our results are motivated from uniqueness considerations of polynomial canonical representations of the phase or amplitude terms of oscillatory integrals encountered in the asymptotic analysis of the coefficients of mixed powers and multivariable generating functions via saddle-point methods. Uniqueness shall prove important for developing algorithms to determine the Taylor coefficients of the terms appearing in these representations. The uniqueness of Levinson's polynomial canonical representations of analytic functions in several variables follows as a corollary of our one-complex variables results.
Connectedness of number theoretical tilings
Authors: Akiyama Shigeki , Gjini Nertila
Published: August 2021

Let T=T(A,D) be a self-affine tile in \reals^n defined by an integral expanding matrix A and a digit set D. In connection with canonical number systems, we study connectedness of T when D corresponds to the set of consecutive integers \0,1,..., |det(A)|-1\. It is shown that in \reals^3 and \reals^4, for any integral expanding matrix A, T(A,D) is connected. We also study the connectedness of Pisot dual tilings which play an important role in the study of β -expansion, substitution and symbolic dynamical system. It is shown that each tile generated by a Pisot unit of degree 3 is arcwise connected. This is naturally expected since the digit set consists of consecutive integers as above. However surprisingly, we found families of disconnected Pisot dual tiles of degree 4. Also we give a simple necessary and sufficient condition for the connectedness of the Pisot dual tiles of degree 4. As a byproduct, a complete classification of the β -expansion of 1 for quartic Pisot units is given.
Why almost all satisfiable $k$-CNF formulas are easy
Authors: Coja-Oghlan Amin , Krivelevich Michael , Vilenchik Dan
Published: August 2021

Finding a satisfying assignment for a $k$-CNF formula $(k \geq 3)$, assuming such exists, is a notoriously hard problem. In this work we consider the uniform distribution over satisfiable $k$-CNF formulas with a linear number of clauses (clause-variable ratio greater than some constant). We rigorously analyze the structure of the space of satisfying assignments of a random formula in that distribution, showing that basically all satisfying assignments are clustered in one cluster, and agree on all but a small, though linear, number of variables. This observation enables us to describe a polynomial time algorithm that finds $\textit{whp}$ a satisfying assignment for such formulas, thus asserting that most satisfiable $k$-CNF formulas are easy (whenever the clause-variable ratio is greater than some constant). This should be contrasted with the setting of very sparse $k$-CNF formulas (which are satisfiable $\textit{whp}$), where experimental results show some regime of clause density to be difficult for many SAT heuristics. One explanation for this phenomena, backed up by partially non-rigorous analytical tools from statistical physics, is the complicated clustering of the solution space at that regime, unlike the more "regular" structure that denser formulas possess. Thus in some sense, our result rigorously supports this explanation.
Randomized Optimization: a Probabilistic Analysis
Authors: Cardinal Jean , Langerman Stefan , Louchard Guy
Published: August 2021

In 1999, Chan proposed an algorithm to solve a given optimization problem: express the solution as the minimum of the solutions of several subproblems and apply the classical randomized algorithm for finding the minimum of $r$ numbers. If the decision versions of the subproblems are easier to solve than the subproblems themselves, then a faster algorithm for the optimization problem may be obtained with randomization. In this paper we present a precise probabilistic analysis of Chan's technique.
A Note on the Approximation of Perpetuities
Authors: Knape Margarete , Neininger Ralph
Published: August 2021

We propose and analyze an algorithm to approximate distribution functions and densities of perpetuities. Our algorithm refines an earlier approach based on iterating discretized versions of the fixed point equation that defines the perpetuity. We significantly reduce the complexity of the earlier algorithm. Also one particular perpetuity arising in the analysis of the selection algorithm Quickselect is studied in more detail. Our approach works well for distribution functions. For densities we have weaker error bounds although computer experiments indicate that densities can also be well approximated.
Lattice reduction in two dimensions: analyses under realistic probabilistic models
Authors: Vallée Brigitte , Vera Antonio
Published: August 2021

The Gaussian algorithm for lattice reduction in dimension 2 is precisely analysed under a class of realistic probabilistic models, which are of interest when applying the Gauss algorithm "inside'' the LLL algorithm. The proofs deal with the underlying dynamical systems and transfer operators. All the main parameters are studied: execution parameters which describe the behaviour of the algorithm itself as well as output parameters, which describe the geometry of reduced bases.
Two Pile Move-Size Dynamic Nim
Authors: Holshouser Arthur , Reiter Harold
Published: August 2021

The purpose of this paper is to solve a special class of combinational games consisting of two-pile counter pickup games for which the maximum number of counters that can be removed on each successive move changes during the play of the games. Two players alternate moving. Each player in his turn first chooses one of the piles, and his choice of piles can change from move to move. He then removes counters from this chosen pile. A function f:Z^+ → Z^+ is given which determines the maximum size of the next move in terms of the current move size. The game ends as soon as one of the two piles is empty, and the winner is the last player to move in the game. The games for which f(k)=k, f(k)=2k, and f(k)=3k use the same formula for computing the smallest winning move size. Here we find all the functions f for which this formula works, and we also give the winning strategy for each function. See Holshouser, A, James Rudzinski and Harold Reiter: Dynamic One-Pile Nim for a discussion of the single pile game.
Hamming distance from irreducible polynomials over $\mathbb {F}_2$
Authors: Lee Gilbert , Ruskey Frank , Williams Aaron
Published: August 2021

We study the Hamming distance from polynomials to classes of polynomials that share certain properties of irreducible polynomials. The results give insight into whether or not irreducible polynomials can be effectively modeled by these more general classes of polynomials. For example, we prove that the number of degree $n$ polynomials of Hamming distance one from a randomly chosen set of $\lfloor 2^n/n \rfloor$ odd density polynomials, each of degree $n$ and each with non-zero constant term, is asymptotically $(1-e^{-4}) 2^{n-2}$, and this appears to be inconsistent with the numbers for irreducible polynomials. We also conjecture that there is a constant $c$ such that every polynomial has Hamming distance at most $c$ from an irreducible polynomial. Using exhaustive lists of irreducible polynomials over $\mathbb{F}_2$ for degrees $1 ≤ n ≤ 32$, we count the number of polynomials with a given Hamming distance to some irreducible polynomial of the same degree. Our work is based on this "empirical" study.
The continuous limit of large random planar maps
Authors: Le Gall Jean-François
Published: August 2021

We discuss scaling limits of random planar maps chosen uniformly over the set of all $2p$-angulations with $n$ faces. This leads to a limiting space called the Brownian map, which is viewed as a random compact metric space. Although we are not able to prove the uniqueness of the distribution of the Brownian map, many of its properties can be investigated in detail. In particular, we obtain a complete description of the geodesics starting from the distinguished point called the root. We give applications to various properties of large random planar maps.
Point process stabilization methods and dimension estimation
Authors: Yukich J. E.
Published: August 2021

We provide an overview of stabilization methods for point processes and apply these methods to deduce a central limit theorem for statistical estimators of dimension.
Error bounds in stochastic-geometric normal approximation
Authors: Penrose Mathew , Rosoman Tom
Published: August 2021

We provide normal approximation error bounds for sums of the form $\sum_x \xi_x$, indexed by the points $x$ of a Poisson process (not necessarily homogeneous) in the unit $d$-cube, with each term $\xi_x$ determined by the configuration of Poisson points near to $x$ in some sense. We consider geometric graphs and coverage processes as examples of our general results.
Concentration of measure and mixing for Markov chains
Authors: Luczak Malwina
Published: August 2021

We consider Markovian models on graphs with local dynamics. We show that, under suitable conditions, such Markov chains exhibit both rapid convergence to equilibrium and strong concentration of measure in the stationary distribution. We illustrate our results with applications to some known chains from computer science and statistical mechanics.
Polynomial tails of additive-type recursions
Authors: Schopp Eva-Maria
Published: August 2021

Polynomial bounds and tail estimates are derived for additive random recursive sequences, which typically arise as functionals of recursive structures, of random trees, or in recursive algorithms. In particular they arise as parameters of divide and conquer type algorithms. We mainly focuss on polynomial tails that arise due to heavy tail bounds of the toll term and the starting distributions. Besides estimating the tail probability directly we use a modified version of a theorem from regular variation theory. This theorem states that upper bounds on the asymptotic tail probability can be derived from upper bounds of the Laplace―Stieltjes transforms near zero.
Generating Functions of Stochastic L-Systems and Application to Models of Plant Development
Authors: Loi Cedric , Cournède Paul Henry
Published: August 2021

If the interest of stochastic L-systems for plant growth simulation and visualization is broadly acknowledged, their full mathematical potential has not been taken advantage of. In this article, we show how to link stochastic L-systems to multitype branching processes, in order to characterize the probability distributions and moments of the numbers of organs in plant structure. Plant architectural development can be seen as the combination of two subprocesses driving the bud population dynamics, branching and differentiation. By writing the stochastic L-system associated to each subprocess, we get the generating function associated to the whole system by compounding the associated generating functions. The modelling of stochastic branching is classical, but to model differentiation, we introduce a new framework based on multivariate phase-type random vectors.
Branching processes in random environment die slowly
Authors: Vatutin Vladimir , Kyprianou Andreas
Published: August 2021

Let $Z_n,n=0,1,\ldots,$ be a branching process evolving in the random environment generated by a sequence of iid generating functions $f_0(s),f_1(s),\ldots,$ and let $S_0=0$, $S_k=X_1+ \ldots +X_k,k \geq 1$, be the associated random walk with $X_i=\log f_{i-1}^{\prime}(1), \tau (m,n)$ be the left-most point of minimum of $\{S_k,k \geq 0 \}$ on the interval $[m,n]$, and $T=\min \{ k:Z_k=0\}$. Assuming that the associated random walk satisfies the Doney condition $P(S_n > 0) \to \rho \in (0,1), n \to \infty$, we prove (under the quenched approach) conditional limit theorems, as $n \to \infty$, for the distribution of $Z_{nt}, Z_{\tau (0,nt)}$, and $Z_{\tau (nt,n)}, t \in (0,1)$, given $T=n$. It is shown that the form of the limit distributions essentially depends on the location of $\tau (0,n)$ with respect to the point $nt$.
On density of truth of the intuitionistic logic in one variable
Authors: Kostrzycka Zofia
Published: August 2021

In this paper we focus on the intuitionistic propositional logic with one propositional variable. More precisely we consider the standard fragment $\{ \to ,\vee ,\bot \}$ of this logic and compute the proportion of tautologies among all formulas. It turns out that this proportion is different from the analog one in the classical logic case.
Volume Laws for Boxed Plane Partitions and Area Laws for Ferrers Diagrams
Authors: Schwerdtfeger Uwe
Published: August 2021

We asymptotically analyse the volume random variables of general, symmetric and cyclically symmetric plane partitions fitting inside a box. We consider the respective symmetry class equipped with the uniform distribution. We also prove area limit laws for two ensembles of Ferrers diagrams. Most limit laws are Gaussian.
Plane recursive trees, Stirling permutations and an urn model
Authors: Janson Svante
Published: August 2021

We exploit a bijection between plane recursive trees and Stirling permutations; this yields the equivalence of some results previously proven separately by different methods for the two types of objects as well as some new results. We also prove results on the joint distribution of the numbers of ascents, descents and plateaux in a random Stirling permutation. The proof uses an interesting generalized Pólya urn.
Reduction formulae from the factorization Theorem of Littlewood-Richardson polynomials by King, Tollu and Toumazet
Authors: Cho Soojin , Jung Eun-Kyoung , Moon Dongho
Published: August 2021

The factorization theorem by King, Tollu and Toumazet gives four different reduction formulae of Littlewood-Richardson coefficients. One of them is the classical reduction formula of the first type while others are new. Moreover, the classical reduction formula of the second type is not a special case of KTT theorem. We give combinatorial proofs of reduction formulae in terms of tableaux or hives. The proofs for the cases $r=1, 2, n-2$ in terms of tableaux and the proof for the classical reduction formula of the second type in terms of hives are new.

Le Théorème de factorisation par King, Tollu, et Toumazet donne quatre formules différentes de réduction des coefficients de Littlewood-Richardson. L'une d'entre eux est la formule classique de réduction du premier type alors que les trois autres sont nouvelles. De plus, la formule classique de réduction du deuxième type n'est pas un cas spécial du KTT théorème. Nous donnons preuves combinatoires des formules de réduction en termes de tableaux ou $\textit{hives}$. Les preuves pour les cas $r = 1, 2, n-2$ en termes de tableaux et la preuve pour la formule classique de réduction du deuxième type en termes de $\textit{hives}$ sont nouvelles.
The cluster basis $\mathbb{Z}[x_{1,1},…,x_{3,3}]
Authors: Skandera Mark
Published: August 2021

We show that the set of cluster monomials for the cluster algebra of type $D_4$ contains a basis of the $\mathbb{Z}$-module $\mathbb{Z}[x_{1,1},\ldots ,x_{3,3}]$. We also show that the transition matrices relating this cluster basis to the natural and the dual canonical bases are unitriangular and nonnegative. These results support a conjecture of Fomin and Zelevinsky on the equality of the cluster and dual canonical bases. In the event that this conjectured equality is true, our results also imply an explicit factorization of each dual canonical basis element as a product of cluster variables.

Nous montrons que l'ensemble des monômes de l'algebre "cluster'' $D_4$ contient une base-$\mathbb{Z}$ pour le module $\mathbb{Z}[x_{1,1},\ldots ,x_{3,3}]$. Nous montrons aussi que les matrices transitoires qui relient cette base à la base canonique duale sont unitriangulaires. Ces résultats renforcent une conjecture de Fomin et de Zelevinsky sur l'égalité de ces deux bases. Si cette égalité s'avérait être vraie, notre résultat donnerait aussi une factorisation des éléments de la base canonique duale.
On randomly colouring locally sparse graphs
Authors: Frieze Alan , Vera Juan
Published: August 2021

We consider the problem of generating a random q-colouring of a graph G=(V,E). We consider the simple Glauber Dynamics chain. We show that if for all v ∈ V the average degree of the subgraph H_v induced by the neighbours of v ∈ V is #x226a Δ where Δ is the maximum degree and Δ >c_1\ln n then for sufficiently large c_1, this chain mixes rapidly provided q/Δ >α , where α #x2248 1.763 is the root of α = e^\1/α \. For this class of graphs, which includes planar graphs, triangle free graphs and random graphs G_\n,p\ with p #x226a 1, this beats the 11Δ /6 bound of Vigoda for general graphs.
Nestings of Matchings and Permutations and North Steps in PDSAWs
Authors: Rubey Martin
Published: August 2021

We present a simple bijective proof of the fact that matchings of $[2n]$ with N nestings are equinumerous to $\textit{partially directed self avoiding walks}$ confined to the symmetric wedge defined by $y= \pm x$, with $n$ east steps and $N$ north steps. A very similar construction connects permutations with $N$ nestings and $\textit{PDSAWs}$ remaining below the $x$-axis, again with $N$ north steps. Furthermore, both bijections transport several combinatorially meaningful parameters.
The quasiinvariants of the symmetric group
Authors: Bandlow Jason , Musiker Gregg
Published: August 2021

For $m$ a non-negative integer and $G$ a Coxeter group, we denote by $\mathbf{QI_m}(G)$ the ring of $m$-quasiinvariants of $G$, as defined by Chalykh, Feigin, and Veselov. These form a nested series of rings, with $\mathbf{QI_0}(G)$ the whole polynomial ring, and the limit $\mathbf{QI}_{\infty}(G)$ the usual ring of invariants. Remarkably, the ring $\mathbf{QI_m}(G)$ is freely generated over the ideal generated by the invariants of $G$ without constant term, and the quotient is isomorphic to the left regular representation of $G$. However, even in the case of the symmetric group, no basis for $\mathbf{QI_m}(G)$ is known. We provide a new description of $\mathbf{QI_m}(S_n)$, and use this to give a basis for the isotypic component of $\mathbf{QI_m}(S_n)$ indexed by the shape $[n-1,1]$.

Pour $m$ un entier positif ou nul et $G$ un groupe de Coxeter, nous notons $\mathbf{QI_m}(G)$ l'anneau des quasiinvariants définis par Chalykh, Feigin et Veselov. On obtient ainsi une série d'anneaux emboités, $\mathbf{QI_0}(G)$ étant l'anneau des polynômes, et la limite $\mathbf{QI}_{\infty}(G)$ l'anneau des invariants usuels. Il est remarquable que l'anneau $\mathbf{QI_m}(G)$ est librement généré sur l'idéal engendré par les invariants de $G$ sans terme constant, et le quotient est isomorphe à la représentation régulière à gauche de $G$. Cependant, même dans le cas du groupe symétrique, aucune base de $\mathbf{QI_m}(G)$ n'est connue. Nous donnons une nouvelle description de $\mathbf{QI_m}(G)$ et l'utilisons pour obtenir une base du composant isotypique de $\mathbf{QI_m}(S_n)$ indexée par la partition $(n-1,1)$.
Common intervals in permutations
Authors: Corteel Sylvie , Louchard Guy , Pemantle Robin
Published: August 2021

An interval of a permutation is a consecutive substring consisting of consecutive symbols. For example, 4536 is an interval in the permutation 71453682. These arise in genetic applications. For the applications, it makes sense to generalize so as to allow gaps of bounded size δ -1, both in the locations and the symbols. For example, 4527 has gaps bounded by 1 (since 3 and 6 are missing) and is therefore a δ -interval of 389415627 for δ =2. After analyzing the distribution of the number of intervals of a uniform random permutation, we study the number of 2-intervals. This is exponentially large, but tightly clustered around its mean. Perhaps surprisingly, the quenched and annealed means are the same. Our analysis is via a multivariate generating function enumerating pairs of potential 2-intervals by size and intersection size.\par
Enumerating alternating tree families
Authors: Kuba Markus , Panholzer Alois
Published: August 2021

We study two enumeration problems for $\textit{up-down alternating trees}$, i.e., rooted labelled trees $T$, where the labels $ v_1, v_2, v_3, \ldots$ on every path starting at the root of $T$ satisfy $v_1 < v_2 > v_3 < v_4 > \cdots$. First we consider various tree families of interest in combinatorics (such as unordered, ordered, $d$-ary and Motzkin trees) and study the number $T_n$ of different up-down alternating labelled trees of size $n$. We obtain for all tree families considered an implicit characterization of the exponential generating function $T(z)$ leading to asymptotic results of the coefficients $T_n$ for various tree families. Second we consider the particular family of up-down alternating labelled ordered trees and study the influence of such an alternating labelling to the average shape of the trees by analyzing the parameters $\textit{label of the root node}$, $\textit{degree of the root node}$ and $\textit{depth of a random node}$ in a random tree of size $n$. This leads to exact enumeration results and limiting distribution results.

Nous étudions deux problèmes de dénombrement d'$\textit{arbres alternés haut-bas}$ : par définition, ce sont des arbres munis d'une racine et tels que, pour tout chemin partant de la racine, les valeurs $v_1,v_2,v_3,\ldots$ associées aux nœuds du chemin satisfont la chaîne d'inégalités $v_1 < v_2 > v_3 < v_4 > \cdots$. D'une part, nous considérons diverses familles d'arbres intéressantes du point de vue de l'analyse combinatoire (comme les arbres de Motzkin, les arbres non ordonnés, ordonnés et $d$-aires) et nous étudions pour chaque famille le nombre total $T_n$ d'arbres alternés haut-bas de taille $n$. Nous obtenons pour toutes les familles d'arbres considérées une caractérisation implicite de la fonction génératrice exponentielle $T(z)$. Cette caractérisation nous renseigne sur le comportement asymptotique des coefficients $T_n$ de plusieurs familles d'arbres. D'autre part, nous examinons le cas particulier de la famille des arbres ordonnés : nous étudions l'influence de l'étiquetage alterné haut-bas sur l'allure générale de ces arbres en analysant trois paramètres dans un arbre aléatoire (valeur de la racine, degré de la racine et profondeur d'un nœud aléatoire). Nous obtenons alors des résultats en terme de distribution limite, mais aussi de dénombrement exact.
A combinatorial realization of Schur-Weyl duality via crystal graphs and dual equivalence graphs
Authors: Assaf S.
Published: August 2021

For any polynomial representation of the special linear group, the nodes of the corresponding crystal may be indexed by semi-standard Young tableaux. Under certain conditions, the standard Young tableaux occur, and do so with weight $0$. Standard Young tableaux also parametrize the vertices of dual equivalence graphs. Motivated by the underlying representation theory, in this paper, we explain this connection by giving a combinatorial manifestation of Schur-Weyl duality. In particular, we put a dual equivalence graph structure on the $0$-weight space of certain crystal graphs, producing edges combinatorially from the crystal edges. The construction can be expressed in terms of the local characterizations given by Stembridge for crystal graphs and the author for dual equivalence graphs.
Combinatorial interpretation and positivity of Kerov's character polynomials
Authors: Féray Valentin
Published: August 2021

Kerov's polynomials give irreducible character values of the symmetric group in term of the free cumulants of the associated Young diagram. Using a combinatorial approach with maps, we prove in this article a positivity result on their coefficients, which extends a conjecture of S. Kerov.

Les polynômes de Kerov expriment les valeurs des caractères irréductibles du groupe symétrique en fonction des cumulants libres du diagramme de Young associé. Grâce à une approche combinatoire à base de cartes, nous prouvons dans cet article un résultat de positivité sur leurs coefficients, qui généralise une conjecture de S. Kerov.
The first descent in samples of geometric random variables and permutations
Authors: Knopfmacher Arnold , Prodinger Helmut
Published: August 2021

For words of length n, generated by independent geometric random variables, we study the average initial and end heights of the first descent in the word. In addition we compute the average initial and end height of the first descent for a random permutation of n letters.