bluuebunny/crossref_metadata_2025 huggingface dataset:
The representation of the symmetric group on $m$-Tamari intervals (conference version)
Authors: Bousquet-Mélou Mireille , Chapuy Guillaume , Préville-Ratelle Louis-François
Published: August 2021

An $m$-ballot path of size $n$ is a path on the square grid consisting of north and east unit steps, starting at (0,0), ending at $(mn,n)$, and never going below the line $\{x=my\}$. The set of these paths can be equipped with a lattice structure, called the $m$-Tamari lattice and denoted by $\mathcal{T}{_n}^{(m)}$, which generalizes the usual Tamari lattice $\mathcal{T}n$ obtained when $m=1$. This lattice was introduced by F. Bergeron in connection with the study of diagonally coinvariant spaces in three sets of $n$ variables. The representation of the symmetric group $\mathfrak{S}_n$ on these spaces is conjectured to be closely related to the natural representation of $\mathfrak{S}_n$ on (labelled) intervals of the $m$-Tamari lattice studied in this paper. An interval $[P,Q$] of $\mathcal{T}{_n}^{(m)}$ is labelled if the north steps of $Q$ are labelled from 1 to $n$ in such a way the labels increase along any sequence of consecutive north steps. The symmetric group $\mathfrak{S}_n$ acts on labelled intervals of $\mathcal{T}{_n}^{(m)}$by permutation of the labels. We prove an explicit formula, conjectured by F. Bergeron and the third author, for the character of the associated representation of $\mathfrak{S}_n$. In particular, the dimension of the representation, that is, the number of labelled $m$-Tamari intervals of size $n$, is found to be $(m+1)^n(mn+1)^{n-2}$. These results are new, even when $m=1$. The form of these numbers suggests a connection with parking functions, but our proof is not bijective. The starting point is a recursive description of $m$-Tamari intervals. It yields an equation for an associated generating function, which is a refined version of the Frobenius series of the representation. The form of this equation is highly non-standard: it involves two additional variables $x$ and $y$, a derivative with respect to $y$ and iterated divided differences with respect to $x$. The hardest part of the proof consists in solving it, and we develop original techniques to do so.
On singularity confinement for the pentagram map
Authors: Glick Max
Published: August 2021

The pentagram map, introduced by R. Schwartz, is a birational map on the configuration space of polygons in the projective plane. We study the singularities of the iterates of the pentagram map. We show that a ``typical'' singularity disappears after a finite number of iterations, a confinement phenomenon first discovered by Schwartz. We provide a method to bypass such a singular patch by directly constructing the first subsequent iterate that is well-defined on the singular locus under consideration. The key ingredient of this construction is the notion of a decorated (twisted) polygon, and the extension of the pentagram map to the corresponding decorated configuration space.

L'application pentagramme de R. Schwartz est une application birationnelle sur l'espace des polygones dans le plan projectif. Nous ètudions les singularitès des itèrations de l'application pentagramme. Nous montrons qu'une singularitè ``typique'' disparaî t après un nombre fini d'itèrations, un phènomène dècouvert par Schwartz. Nous fournissons une mèthode pour contourner une telle singularitè en construisant la première itèration qui est bien dèfinie. L'ingrèdient principal de cette construction est la notion d'un polygone dècorè et l'extension de l'application pentagramme á l'espace de configuration dècorè.
Cayley and Tutte polytopes
Authors: Konvalinka Matjaž , Pak Igor
Published: August 2021

Cayley polytopes were defined recently as convex hulls of Cayley compositions introduced by Cayley in 1857. In this paper we resolve Braun's conjecture, which expresses the volume of Cayley polytopes in terms of the number of connected graphs. We extend this result to a two-variable deformations, which we call Tutte polytopes. The volume of the latter is given via an evaluation of the Tutte polynomial of the complete graph. Our approach is based on an explicit triangulation of the Cayley and Tutte polytope. We prove that simplices in the triangulations correspond to labeled trees and forests. The heart of the proof is a direct bijection based on the neighbors-first search graph traversal algorithm.

Les polytopes de Cayley ont été définis récemment comme des ensembles convexes de compositions de Cayley introduits par Cayley en 1857. Dans ce papier, nous résolvons la conjecture de Braun. Cette dernière exprime le volume du polytopes de Cayley en termes du nombre de graphes connexes. Nous étendons ce résultat à des déformations de polytopes de Cayley à deux variables, à savoir les polytopes de Tutte. Le volume de ces derniers est donnè par une évaluation du polynôme de Tutte du graphe complet. Notre approche est basée sur une triangulation explicite des polytopes de Cayley et Tutte. Nous démontrons que les simplexes de ces triangulations correspondent à des arbres marqués. La pierre angulaire de notre démonstration est une bijection directe basées sur l'algorithme de la recherche du premier voisin sur le graphe.
Chromatic roots as algebraic integers
Authors: Bohn Adam
Published: August 2021

A chromatic root is a zero of the chromatic polynomial of a graph. At a Newton Institute workshop on Combinatorics and Statistical Mechanics in 2008, two conjectures were proposed on the subject of which algebraic integers can be chromatic roots, known as the ``$α +n$ conjecture'' and the ``$nα$ conjecture''. These say, respectively, that given any algebraic integer α there is a natural number $n$ such that $α +n$ is a chromatic root, and that any positive integer multiple of a chromatic root is also a chromatic root. By computing the chromatic polynomials of two large families of graphs, we prove the $α +n$ conjecture for quadratic and cubic integers, and show that the set of chromatic roots satisfying the nα conjecture is dense in the complex plane.

Une racine chromatique est un zéro du polynôme chromatique d'un graphe. A un atelier au Newton Institute sur la combinatoire et la mécanique statistique en 2008, deux conjectures ont été proposées dont le sujet des entiers algébriques peut être racines chromatiques, connus sous le nom ``la conjecture $α + n$'' et ``la conjecture $n α$ ''. Les conjectures veulent dire, respectivement, que pour chaque entier algébrique $α$ il y a un nombre entier naturel $n$, tel que $α + n$ est une racine chromatique, et que chaque multiple entier positif d'une racine chromatique est aussi une racine chromatique . En calculant les polynômes chromatiques de deux grandes familles de graphes, on prouve la conjecture $α + n$ pour les entiers quadratiques et cubiques, et montre que l'ensemble des racines chromatiques qui confirme la conjecture $nα$ est dense dans le plan complexe.
Classification of Ehrhart polynomials of integral simplices
Authors: Higashitani Akihiro
Published: August 2021

Let $δ (\mathcal{P} )=(δ _0,δ _1,\ldots,δ _d)$ be the $δ$ -vector of an integral convex polytope $\mathcal{P}$ of dimension $d$. First, by using two well-known inequalities on $δ$ -vectors, we classify the possible $δ$ -vectors with $\sum_{i=0}^d δ _i ≤3$. Moreover, by means of Hermite normal forms of square matrices, we also classify the possible $δ$ -vectors with $\sum_{i=0}^d δ _i = 4$. In addition, for $\sum_{i=0}^d δ _i ≥5$, we characterize the $δ$ -vectors of integral simplices when $\sum_{i=0}^d δ _i$ is prime.

Soit $δ (\mathcal{P} )=(δ _0,δ _1,\ldots,δ _d)$ le $δ$ -vecteur d'un polytope intégrante de dimension d. Tout d'abord, en utilisant deux bien connus des inégalités sur $δ$ -vecteurs, nous classons les $δ$ -vecteurs possibles avec $\sum_{i=0}^d δ _i ≤3$ En outre, par le biais de Hermite formes normales, nous avons également classer les $δ$ -vecteurs avec $\sum_{i=0}^d δ _i = 4$. De plus, pour $\sum_{i=0}^d δ _i ≥5$, nous caractérisons les $δ$-vecteurs des simplex inégalités lorsque $\sum_{i=0}^d δ _i$ est premier.
The multivariate arithmetic Tutte polynomial
Authors: Brändèn Petter , Moci Luca
Published: August 2021

We introduce an arithmetic version of the multivariate Tutte polynomial recently studied by Sokal, and a quasi-polynomial that interpolates between the two. We provide a generalized Fortuin-Kasteleyn representation for representable arithmetic matroids, with applications to arithmetic colorings and flows. We give a new proof of the positivity of the coefficients of the arithmetic Tutte polynomial in the more general framework of pseudo-arithmetic matroids. In the case of a representable arithmetic matroid, we provide a geometric interpretation of the coefficients of the arithmetic Tutte polynomial.

Nous introduisons une version arithmétique du polynôme de Tutte multivariée récemment étudié par Sokal, et un quasi-polynôme qui interpole entre les deux. Nous proposons une représentation de Fortuin-Kasteleyn neutralise pour les matroïdes arithmétiques représentables, avec des applications aux colorations et flux arithmétiques. Nous donnons une nouvelle preuve de la positivité des coefficients du polynôme de Tutte arithmétique dans le cadre plus général des matroïdes pseudo-arithmétiques. Dans le cas d'un matroïde arithmétique représentable, nous proposons une interprétation géométrique des coefficients du polynôme de Tutte arithmétique.
Cumulants of the q-semicircular law, Tutte polynomials, and heaps
Authors: Josuat-Vergès Matthieu
Published: August 2021

The q-semicircular law as introduced by Bożejko and Speicher interpolates between the Gaussian law and the semicircular law, and its moments have a combinatorial interpretation in terms of matchings and crossings. We prove that the cumulants of this law are, up to some factor, polynomials in q with nonnegative coefficients. This is done by showing that they are obtained by an enumeration of connected matchings, weighted by the evaluation at (1,q) of a Tutte polynomial. The two particular cases q=0 and q=2 have also alternative proofs, related with the fact that these particular evaluation of the Tutte polynomials count some orientations on graphs. Our methods also give a combinatorial model for the cumulants of the free Poisson law.

La loi q-semicirculaire introduite par Bożejko et Speicher interpole entre la loi gaussienne et la loi semi-circulaire, et ses moments ont une interprétation combinatoire en termes de couplages et croisements. Nous prouvons que les cumulants de cette loi sont, à un facteur près, des polynômes en q à coefficients positifs. La méthode consiste à obtenir ces cumulants par une énumération de couplages connexes, pondérés par l’évaluation en (1,q) d'un polynôme de Tutte. Les cas particuliers q=0 et q=2 ont une preuve alternative, reliè au fait que des évaluations particulières du polynôme de Tutte comptent certaines orientations de graphes. Nos méthodes donnent aussi un modèle combinatoire aux cumulants de la loi de Poisson libre.
Involutions on Baxter Objects
Authors: Dilks Kevin
Published: August 2021

Baxter numbers are known to count several families of combinatorial objects, all of which come equipped with natural involutions. In this paper, we add a combinatorial family to the list, and show that the known bijections between these objects respect these involutions. We also give a formula for the number of objects fixed under this involution, showing that it is an instance of Stembridge's "$q=-1$ phenomenon''.

Les nombres Baxter comptent plusieurs familles d'objets combinatoires, qui sont tous équipés avec des involutions naturels. Dans ce papier, nous ajoutons une famille combinatoire à la liste, et nous montrons que les bijections connus entre ces objets respectent ces involutions. En plus, nous donnons une formule pour le nombre d'objets fixés par cette involution et nous montrons qu'elle est une instance du "phénomène $q =-1$'' de Stembridge.
Enumeration of permutations sorted with two passes through a stack and D_8 symmetries
Authors: Bouvel Mathilde , Guibert Olivier
Published: August 2021

We examine the sets of permutations that are sorted by two passes through a stack with a $D_8$ operation performed in between. From a characterization of these in terms of generalized excluded patterns, we prove two conjectures on their enumeration, that can be refined with the distribution of some statistics. The results are obtained by generating trees.

On étudie les ensembles de permutations qui sont triées par deux passages dans une pile séparés par une opération du groupe $D_8$. À partir d'une caractérisation de ces ensembles en termes de motifs exclus généralisés, on démontre deux conjectures sur leur énumération, qui peuvent être raffinées par la distribution de certaines statistiques. Ces résultats sont obtenus à l'aide d'arbres de génération.
Computing Tutte Polynomials
Authors: Monagan Michael
Published: August 2021

We present a new edge selection heuristic and vertex ordering heuristic that together enable one to compute the Tutte polynomial of much larger sparse graphs than was previously doable. As a specific example, we are able to compute the Tutte polynomial of the truncated icosahedron graph using our Maple implementation in under 4 minutes on a single CPU. This compares with a recent result of Haggard, Pearce and Royle whose special purpose C++ software took one week on 150 computers.

Nous présentons deux nouvelles heuristiques pour le calcul du polynôme de Tutte de graphes de faible densité, basées sur les principes de sélection d'arêtes et d'arrangement linéaire de sommets, et qui permettent de traiter des graphes de bien plus grande tailles que les méthodes existantes. Par exemple, en utilisant notre implémentation en Maple, nous pouvons calculer le polynôme de Tutte de l'isocahédron tronqué en moins de 4 minutes sur un ordinateur à processeur unique, alors qu'un programme ad-hoc récent de Haggard, Pearce et Royle, utilisant 150 ordinateurs, a nécessité une semaine de calcul pour obtenir le même résultat.
Universal Polynomials for Severi Degrees of Toric Surfaces
Authors: Ardila Federico , Block Florian
Published: August 2021

The Severi variety parametrizes plane curves of degree $d$ with $\delta$ nodes. Its degree is called the Severi degree. For large enough $d$, the Severi degrees coincide with the Gromov-Witten invariants of $\mathbb{CP}^2$. Fomin and Mikhalkin (2009) proved the 1995 conjecture that for fixed $\delta$, Severi degrees are eventually polynomial in $d$. In this paper, we study the Severi varieties corresponding to a large family of toric surfaces. We prove the analogous result that the Severi degrees are eventually polynomial as a function of the multidegree. More surprisingly, we show that the Severi degrees are also eventually polynomial "as a function of the surface". Our strategy is to use tropical geometry to express Severi degrees in terms of Brugallé and Mikhalkin's floor diagrams, and study those combinatorial objects in detail. An important ingredient in the proof is the polynomiality of the discrete volume of a variable facet-unimodular polytope.

La variété de Severi paramétrise les courbes planes de degré $d$ avec $\delta$ nœuds. Son degré s'appelle le degré de Severi. Pour $d$ assez grand, les degrés de Severi coïncident avec les invariants de Gromov-Witten de $\mathbb{CP}^2$. Fomin et Mikhalkin (2009) ont prouvé une conjecture de 1995 que pour $\delta$ fixé, les degrés de Severi sont à terme des polynômes en $d$. Nous étudions les variétés de Severi correspondant à une large famille de surfaces toriques. Nous prouvons le résultat analogue que les degrés de Severi sont à terme des fonctions polynomiales du multidegré. De manière plus surprenante, nous montrons que les degrés de Severi sont à terme des polynômes en tant que "fonction de la surface''. Notre stratégie est d'utiliser la géométrie tropicale pour exprimer les degrés de Severi en fonction des "floor diagrams" de Brugallé et Mikhalkin, et d'utiliser ces objets combinatoires en détail. Un autre ingrédient important de la preuve est la polynomialité du volume discret d'un polytope face-unimodulaire variable.
Some lattices of closure systems on a finite set
Authors: Caspard Nathalie , Monjardet Bernard
Published: August 2021

In this paper we study two lattices of significant particular closure systems on a finite set, namely the union stable closure systems and the convex geometries. Using the notion of (admissible) quasi-closed set and of (deletable) closed set, we determine the covering relation \prec of these lattices and the changes induced, for instance, on the irreducible elements when one goes from C to C' where C and C' are two such closure systems satisfying C \prec C'. We also do a systematic study of these lattices of closure systems, characterizing for instance their join-irreducible and their meet-irreducible elements.
The ABC's of affine Grassmannians and Hall-Littlewood polynomials
Authors: Dalal Avinash J. , Morse Jennifer
Published: August 2021

We give a new description of the Pieri rule for $k$-Schur functions using the Bruhat order on the affine type-$A$ Weyl group. In doing so, we prove a new combinatorial formula for representatives of the Schubert classes for the cohomology of affine Grassmannians. We show how new combinatorics involved in our formulas gives the Kostka-Foulkes polynomials and discuss how this can be applied to study the transition matrices between Hall-Littlewood and $k$-Schur functions.

Nous présentons une nouvelle description, issue de l'ordre de Bruhat du groupe de Weyl affine de type $A$, de la règle de Pieri pour les fonctions $k$-Schur. Ce faisant, nous obtenons une nouvelle formule combinatoire pour les représentants des classes de Schubert de la cohomologie des Grassmannienne affines. Nous décrivons aussi comment notre approche permet d'obtenir les polynômes de Kostka-Foulkes et comment elle peut être appliquée à l’étude des matrices de transition entre les polynômes de Hall-Littlewood et les fonctions $k$-Schur.
Perturbation of transportation polytopes
Authors: Liu Fu
Published: August 2021

We describe a perturbation method that can be used to compute the multivariate generating function (MGF) of a non-simple polyhedron, and then construct a perturbation that works for any transportation polytope. Applying this perturbation to the family of central transportation polytopes of order $kn \times n$, we obtain formulas for the MGF of the polytope. The formulas we obtain are enumerated by combinatorial objects. A special case of the formulas recovers the results on Birkhoff polytopes given by the author and De Loera and Yoshida. We also recover the formula for the number of maximum vertices of transportation polytopes of order $kn \times n$.

Nous décrivons une méthode de perturbation qui peut être utilisée pour calculer la fonction génératrice multivariée (MGF) d'un polyèdre non-simple, et ensuite construire une perturbation qui fonctionne pour tout polytope de transport. Appliquant cette perturbation à la famille des centraux de transport polytopes de l'ordre $kn \times n$, nous obtenons des formules pour le MGF du polytope. Les formules que nous obtenons sont énumérées par les objets combinatoires. Un cas spécial des formules récupère les résultats sur des polytopes de Birkhoff donnés par l'auteur et De Loera et Yoshida. Nous récupérons également la formule pour le nombre de sommets maximum des de transport polytopes d'ordre $kn \times n$.
Rare Events and Conditional Events on Random Strings
Authors: Régnier Mireille , Denise Alain
Published: August 2021

Some strings -the texts- are assumed to be randomly generated, according to a probability model that is either a Bernoulli model or a Markov model. A rare event is the over or under-representation of a word or a set of words. The aim of this paper is twofold. First, a single word is given. One studies the tail distribution of the number of its occurrences. Sharp large deviation estimates are derived. Second, one assumes that a given word is overrepresented. The distribution of a second word is studied; formulae for the expectation and the variance are derived. In both cases, the formulae are accurate and actually computable. These results have applications in computational biology, where a genome is viewed as a text.
On Cheating Immune Secret Sharing
Authors: Pieprzyk Josef , Zhang Xian-Mo
Published: August 2021

The paper addresses the cheating prevention in secret sharing. We consider secret sharing with binary shares. The secret also is binary. This model allows us to use results and constructions from the well developed theory of cryptographically strong boolean functions. In particular, we prove that for given secret sharing, the average cheating probability over all cheating vectors and all original vectors, i.e., 1/n 2^n ∑ _c=1...n ∑ _α ∈V n ρ _c,α , denoted by øverlineρ , satisfies øverlineρ ≥ \frac12 , and the equality holds if and only if ρ _c,α satisfies ρ _c,α = \frac12 for every cheating vector δ _c and every original vector α . In this case the secret sharing is said to be cheating immune. We further establish a relationship between cheating-immune secret sharing and cryptographic criteria of boolean functions.This enables us to construct cheating-immune secret sharing.
Generating functions and the satisfiability threshold
Authors: Puyhaubert Vincent
Published: August 2021

The 3-SAT problem consists in determining if a boolean formula with 3 literals per clause is satisfiable. When the ratio between the number of clauses and the number of variables increases, a threshold phenomenon is observed: the probability of satisfiability appears to decrease sharply from 1 to 0 in the neighbourghood of a threshold value, conjectured to be close to 4.25. Although the threshold has been proved to exist for the 2-SAT formulæ and for closely related problems like 3-XORSAT, there is still no proof for the 3-sat problem. Recent works have provided so far upper and lower bounds for the threshold's potential location. We present here a unified approach to upper bounds that is based on urn models, generating functions, and saddle-point bounds. In this way, we re-derive some of the most significant upper bounds known in a simple and uniform manner.
Analysis of some statistics for increasing tree families
Authors: Panholzer Alois , Prodinger Helmut
Published: August 2021

This paper deals with statistics concerning distances between randomly chosen nodes in varieties of increasing trees. Increasing trees are labelled rooted trees where labels along any branch from the root go in increasing order. Many mportant tree families that have applications in computer science or are used as probabilistic models in various applications, like \emphrecursive trees, heap-ordered trees or \emphbinary increasing trees (isomorphic to binary search trees) are members of this variety of trees. We consider the parameters \textitdepth of a randomly chosen node, \textitdistance between two randomly chosen nodes, and the generalisations where \textitp nodes are randomly chosen Under the restriction that the node-degrees are bounded, we can prove that all these parameters converge in law to the Normal distribution. This extends results obtained earlier for binary search trees and heap-ordered trees to a much larger class of structures.
Efficient Algorithms on the Family Associated to an Implicational System
Authors: Bertet Karell , Nebut Mirabelle
Published: August 2021

An implication system (IS) on a finite set S is a set of rules called Σ -implications of the kind A →_Σ B, with A,B ⊆ S. A subset X ⊆ S satisfies A →_Σ B when ''A ⊆ X implies B ⊆ X'' holds, so ISs can be used to describe constraints on sets of elements, such as dependency or causality. ISs are formally closely linked to the well known notions of closure operators and Moore families. This paper focuses on their algorithmic aspects. A number of problems issued from an IS Σ (e.g. is it minimal, is a given implication entailed by the system) can be reduced to the computation of closures φ _Σ (X), where φ _Σ is the closure operator associated to Σ . We propose a new approach to compute such closures, based on the characterization of the direct-optimal IS Σ _do which has the following properties: \beginenumerate ıtemit is equivalent to Σ ıtemφ _Σ _do(X) (thus φ _Σ (X)) can be computed by a single scanning of Σ _do-implications ıtemit is of minimal size with respect to ISs satisfying 1. and 2. \endenumerate We give algorithms that compute Σ _do, and from Σ _do closures φ _Σ (X) and the Moore family associated to φ _Σ .
q-gram analysis and urn models
Authors: Nicodème Pierre
Published: August 2021

Words of fixed size q are commonly referred to as $q$-grams. We consider the problem of $q$-gram filtration, a method commonly used to speed upsequence comparison. We are interested in the statistics of the number of $q$-grams common to two random texts (where multiplicities are not counted) in the non uniform Bernoulli model. In the exact and dependent model, when omitting border effects, a $q$-gramin a random sequence depends on the $q-1$ preceding $q$-grams. In an approximate and independent model, we draw randomly a $q$-gram at each position, independently of the others positions. Using ball and urn models, we analyze the independent model. Numerical simulations show that this model is an excellent first order approximationto the dependent model. We provide an algorithm to compute the moments.
Bindweeds or random walks in random environments on multiplexed trees and their asympotics
Authors: Menshikov Mikhail , Petritis Dimitri , Popov Serguei
Published: August 2021

We report on the asymptotic behaviour of a new model of random walk, we term the bindweed model, evolving in a random environment on an infinite multiplexed tree.The term multiplexed means that the model can be viewed as a nearest neighbours random walk on a tree whose vertices carry an internal degree of freedom from the finite set $\{1,...,d\}$, for some integer $d$. The consequence of the internal degree of freedom is an enhancement of the tree graph structure induced by the replacement of ordinary edges by multi-edges, indexed by the set $\{1,...,d\} × \{1,...,d\}.$ This indexing conveys the information on the internal degree of freedom of the vertices contiguous to each edge. The term random environment means that the jumping rates for the random walk are a family of edge-indexed random variables, independent of the natural filtration generated by the random variables entering in the definition of the random walk; their joint distribution depends on the index of each component of the multi-edges. We study the large time asymptotic behaviour of this random walk and classify it with respect to positive recurrence or transience in terms of a specific parameter of the probability distribution of the jump rates.This classifying parameter is shown to coincide with the critical value of a matrix-valued multiplicative cascade on the ordinary tree (i.e.the one without internal degrees of freedom attached to the vertices) having the same vertex set as the state space of the random walk. Only results are presented here since the detailed proofs will appear elsewhere.
Non Uniform Random Walks
Authors: Vishnoi Nisheeth
Published: August 2021

Given $\epsilon _i ∈ [0,1)$ for each $1 < i < n$, a particle performs the following random walk on $\{1,2,...,n\:\}$par If the particle is at $n$, it chooses a point uniformly at random (u.a.r.) from $\{1,...,n-1\}$. If the current position of the particle is $m (1 < m < n)$, with probability $\epsilon _m$ it decides to go back, in which case it chooses a point u.a.r. from $\{m+1,...,n\}$. With probability $1-\epsilon _m$ it decides to go forward, in which case it chooses a point u.a.r. from $\{1,...,m-1\}$. The particle moves to the selected point. What is the expected time taken by the particle to reach 1 if it starts the walk at $n$? Apart from being a natural variant of the classical one dimensional random walk, variants and special cases of this problemarise in Theoretical Computer Science [Linial, Fagin, Karp, Vishnoi]. In this paper we study this problem and observe interesting properties of this walk. First we show that the expected number of times the particle visits $i$ (before getting absorbed at 1) is the same when the walk is started at $j$, for all $j > i$. Then we show that for the following parameterized family of $\epsilon 's: \epsilon _i = \frac{n-i}{n-i+ α · (i-1)}$,$1 < i < n$ where $α$ does not depend on $i$, the expected number of times the particle visits $i$ is the same when the walk is started at $j$, for all $j < i$. Using these observations we obtain the expected absorption time for this family of $\epsilon 's$. As $α$ varies from infinity to 1, this time goes from $Θ (log n) to Θ (n)$. Finally we studythe behavior of the expected convergence timeas a function of $\epsilon$ . It remains an open question to determine whether this quantity increases when all $\epsilon 's$ are increased. We give some preliminary results to this effect.
The Speed of Simple Random Walk and Anchored Expansion on Percolation Clusters: an Overview
Authors: Chen Dayue , Peres Yuval
Published: August 2021

Benjamini, Lyons and Schramm (1999) considered properties of an infinite graph $G$, and the simple random walk on it, that are preserved by random perturbations. To address problems raised by those authors, we study simple random walk on the infinite percolation cluster in Cayley graphs of certain amenable groups known as "lamplighter groups''.We prove that zero speed for random walk on a lamplighter group implies zero speed for random walk on an infinite cluster, for any supercritical percolation parameter $p$. For $p$ large enough, we also establish the converse. We prove that if $G$ has a positive anchored expansion constant then so does every infinite cluster of independent percolation with parameter $p$ sufficiently close to 1; We also show that positivity of the anchored expansion constant is preserved under a random stretch if, and only if, the stretching law has an exponential tail.
Some results for directed lattice walkers in a strip
Authors: Chan Yao-Ban , Guttmann Anthony J.
Published: August 2021

Using a transfer matrix method, we present some results for directed lattice walkers in a horizontal strip of finite width. Some cases with two walkers in a small width are solved exactly, as are a couple of cases with vicious walkers in a small width; a conjecture is made for a case with three walkers. We also derive the general transfer matrix for two walkers. Lastly, we examine the dependence of the growth constant on the width and friendliness.
Discrete Random Walks on One-Sided ``Periodic'' Graphs
Authors: Drmota Michael
Published: August 2021

In this paper we consider discrete random walks on infinite graphs that are generated by copying and shifting one finite (strongly connected) graph into one direction and connecting successive copies always in the same way. With help of generating functions it is shown that there are only three types for the asymptotic behaviour of the random walk. It either converges to the stationary distribution or it can be approximated in terms of a reflected Brownian motion or by a Brownian motion. In terms of Markov chains these cases correspond to positive recurrence, to null recurrence, and to non recurrence.
Rigorous Result for the CHKNS Random Graph Model
Authors: Durrett Rick
Published: August 2021

We study the phase transition in a random graph in which vertices and edges are added at constant rates. Two recent papers in Physical Review E by Callaway, Hopcroft, Kleinberg, Newman, and Strogatz, and Dorogovstev, Mendes, and Samukhin have computed the critical value of this model, shown that the fraction of vertices in finite clusters is infinitely differentiable at the critical value, and that in the subcritical phase the cluster size distribution has a polynomial decay rate with a continuously varying power. Here we sketch rigorous proofs for the first and third results and a new estimates about connectivity probabilities at the critical value.
Rooted trees and moments of large sparse random matrices
Authors: Khorunzhiy Oleksiy
Published: August 2021

In these expository paper we describe the role of the rooted trees as a base for convenient tools in studies ofrandom matrices. Regarding the Wigner ensemble of random matrices, we represent main ingredients ofthis approach. Also werefine our previous result on the limit of the spectral norm of adjacency matrix of large random graphs.
The number of distinct part sizes of some multiplicity in compositions of an Integer. A probabilistic Analysis
Authors: Louchard Guy
Published: August 2021

Random compositions of integers are used as theoretical models for many applications. The degree of distinctness of a composition is a natural and important parameter. A possible measure of distinctness is the number $X$ of distinct parts (or components). This parameter has been analyzed in several papers. In this article we consider a variant of the distinctness: the number $X(m)$ of distinct parts of multiplicity m that we call the $m$-distinctness. A firstmotivation is a question asked by Wilf for random compositions: what is the asymptotic value of the probability that a randomly chosen part size in a random composition of an integer $ν$ has multiplicity $m$. This is related to $\mathbb{E}(X(m))$, which has been analyzed by Hitczenko, Rousseau and Savage. Here, we investigate, from a probabilistic point of view, the first full part, the maximum part size and the distribution of $X(m)$. We obtain asymptotically, as $ν → ∞$, the moments and an expression for a continuous distribution $φ$ , the (discrete) distribution of $X(m,ν )$ being computable from $φ$ .
Transient Probability Functions: A Sample Path Approach
Authors: Green Michael L. , Krinik Alan , Mortensen Carrie , Rubino Gerardo , Swift Randall J.
Published: August 2021

A new approach is used to determine the transient probability functions of Markov processes. This new solution method is a sample path counting approach and uses dual processes and randomization. The approach is illustrated by determining transient probability functions for a three-state Markov process. This approach also provides a way to calculate transient probability functions for Markov processes which have specific sample path characteristics.
The profile of unlabeled trees
Authors: Gittenberger Bernhard
Published: August 2021

We consider the number of nodes in the levels of unlabeled rooted random trees and show that the joint distribution of several level sizes (where the level number is scaled by $\sqrt{n}$) weakly converges to the distribution of the local time of a Brownian excursion evaluated at the times corresponding to the level numbers. This extends existing results for simply generated trees and forests to the case of unlabeled rooted trees.
Order statistics and estimating cardinalities of massive data sets
Authors: Giroire Frédéric
Published: August 2021

We introduce a new class of algorithms to estimate the cardinality of very large multisets using constant memory and doing only one pass on the data. It is based on order statistics rather that on bit patterns in binary representations of numbers. We analyse three families of estimators. They attain a standard error of $\frac{1}{\sqrt{M}}$ using $M$ units of storage, which places them in the same class as the best known algorithms so far. They have a very simple internal loop, which gives them an advantage in term of processing speed. The algorithms are validated on internet traffic traces.
And/or tree probabilities of Boolean functions
Authors: Gardy Danièle , Woods Alan
Published: August 2021

We consider two probability distributions on Boolean functions defined in terms of their representations by $\texttt{and/or}$ trees (or formulas). The relationships between them, and connections with the complexity of the function, are studied. New and improved bounds on these probabilities are given for a wide class of functions, with special attention being paid to the constant function $\textit{True}$ and read-once functions in a fixed number of variables.
A hooray for Poisson approximation
Authors: Grübel Rudolf
Published: August 2021

We give several examples for Poisson approximation of quantities of interest in the analysis of algorithms: the distribution of node depth in a binary search tree, the distribution of the number of losers in an election algorithm and the discounted profile of a binary search tree. A simple and well-known upper bound for the total variation distance between the distribution of a sum of independent Bernoulli variables and the Poisson distribution with the same mean turns out to be very useful in all three cases.
Cache miss analysis of WHT algorithms
Authors: Furis Mihai , Hitczenko Paweł , Johnson Jeremy
Published: August 2021

On modern computers memory access patterns and cache utilization are as important, if not more important, than operation count in obtaining high-performance implementations of algorithms. In this work, the memory behavior of a large family of algorithms for computing the Walsh-Hadamard transform, an important signal processing transform related to the fast Fourier transform, is investigated. Empirical evidence shows that the family of algorithms exhibit a wide range of performance, despite the fact that all algorithms perform the same number of arithmetic operations. Different algorithms, while having the same number of memory operations, access memory in different patterns and consequently have different numbers of cache misses. A recurrence relation is derived for the number of cache misses and is used to determine the distribution of cache misses over the space of WHT algorithms.
Algorithmic and combinatoric aspects of multiple harmonic sums
Authors: Costermans Christian , Enjalbert Jean-Yves , Minh Hoang Ngoc
Published: August 2021

Ordinary generating series of multiple harmonic sums admit a full singular expansion in the basis of functions $\{(1-z)^α \log^β (1-z)\}_{α ∈ℤ, β ∈ℕ}$, near the singularity $z=1$. A constructive proof of this result is given, and, by combinatoric aspects, an explicit evaluation of Taylor coefficients of functions in some polylogarithmic algebra is obtained. In particular, the asymptotic expansion of multiple harmonic sums is easily deduced.
The Lyapunov tortoise and the dyadic hare
Authors: Daireaux Benoît , Maume-Deschamps Véronique , Vallée Brigitte
Published: August 2021

We study a gcd algorithm directed by Least Significant Bits, the so―called LSB algorithm, and provide a precise average―case analysis of its main parameters [number of iterations, number of shifts, etc...]. This analysis is based on a precise study of the dynamical systems which provide a continuous extension of the algorithm, and, here, it is proved convenient to use both a 2―adic extension and a real one. This leads to the framework of products of random matrices, and our results thus involve a constant $γ$ which is the Lyapunov exponent of the set of matrices relative to the algorithm. The algorithm can be viewed as a race between a dyadic hare with a speed of 2 bits by step and a "real'' tortoise with a speed equal to $γ /\textit{log} \ 2 \sim 0.05$ bits by step. Even if the tortoise starts before the hare, the hare easily catches up with the tortoise [unlike in Aesop's fable [Ae]\ldots], and the algorithm terminates.
The distribution of ascents of size $d$ or more in samples of geometric random variables
Authors: Brennan Charlotte , Knopfmacher Arnold
Published: August 2021

We consider words or strings of characters $a_1a_2a_3 \ldots a_n$ of length $n$, where the letters $a_i \in \mathbb{Z}$ are independently generated with a geometric probability $\mathbb{P} \{ X=k \} = pq^{k-1}$ where $p+q=1$. Let $d$ be a fixed nonnegative integer. We say that we have an ascent of size $d$ or more if $a_{i+1} \geq a_i+d$. We determine the mean, variance and limiting distribution of the number of ascents of size $d$ or more in a random geometrically distributed word.
Classification of large Pólya-Eggenberger urns with regard to their asymptotics
Authors: Pouyanne Nicolas
Published: August 2021

This article deals with Pólya generalized urn models with constant balance in any dimension. It is based on the algebraic approach of Pouyanne (2005) and classifies urns having "large'' eigenvalues in five classes, depending on their almost sure asymptotics. These classes are described in terms of the spectrum of the urn's replacement matrix and examples of each case are treated. We study the cases of so-called cyclic urns in any dimension and $m$-ary search trees for $m \geq 27$.
Distributional analysis of Robin Hood linear probing hashing with buckets
Authors: Viola Alfredo
Published: August 2021

This paper presents the first distributional analysis of a linear probing hashing scheme with buckets of size $b$. The exact distribution of the cost of successful searches for a $b \alpha$ -full table is obtained, and moments and asymptotic results are derived. With the use of the Poisson transform distributional results are also obtained for tables of size $m$ and $n$ elements. A key element in the analysis is the use of a new family of numbers that satisfies a recurrence resembling that of the Bernoulli numbers. These numbers may prove helpful in studying recurrences involving truncated generating functions, as well as in other problems related with buckets.
Average profiles, from tries to suffix-trees
Authors: Nicodème Pierre
Published: August 2021

We build upon previous work of Fayolle (2004) and Park and Szpankowski (2005) to study asymptotically the average internal profile of tries and of suffix-trees. The binary keys and the strings are built from a Bernoulli source $(p,q)$. We consider the average number $p_{k,\mathcal{P}}(\nu)$ of internal nodes at depth $k$ of a trie whose number of input keys follows a Poisson law of parameter $\nu$. The Mellin transform of the corresponding bivariate generating function has a major singularity at the origin, which implies a phase reversal for the saturation rate $p_{k,\mathcal{P}}(\nu)/2^k$ as $k$ reaches the value $2\log(\nu)/(\log(1/p)+\log(1/q))$. We prove that the asymptotic average profiles of random tries and suffix-trees are mostly similar, up to second order terms, a fact that has been experimentally observed in Nicodème (2003); the proof follows from comparisons to the profile of tries in the Poisson model.
Structure of spaces of rhombus tilings in the lexicograhic case
Authors: Rémila Éric
Published: August 2021

Rhombus tilings are tilings of zonotopes with rhombohedra. We study a class of \emphlexicographic rhombus tilings of zonotopes, which are deduced from higher Bruhat orders relaxing the unitarity condition. Precisely, we fix a sequence $(v_1, v_2,\dots, v_D)$ of vectors of $ℝ^d$ and a sequence $(m_1, m_2,\dots, m_D)$ of positive integers. We assume (lexicographic hypothesis) that for each subsequence $(v_{i1}, v_{i2},\dots, v_{id})$ of length $d$, we have $det(v_{i1}, v_{i2},\dots, v_{id}) > 0$. The zonotope $Z$ is the set $\{ Σα _iv_i 0 ≤α _i ≤m_i \}$. Each prototile used in a tiling of $Z$ is a rhombohedron constructed from a subsequence of d vectors. We prove that the space of tilings of $Z$ is a graded poset, with minimal and maximal element.
Mader Tools
Authors: Göring Frank
Published: August 2021

The deep theorem of Mader concerning the number of internally disjoint H-paths is a very powerfull tool. Nevertheless its use is very difficult, because one has to deal with a very reach family of separators. This paper shows several ways to strengthen Mader's theorem by certain additional restrictions of the appearing separators.
A Note on Set Systems with no Union of Cardinality 0 modulo m
Authors: Grolmusz Vince
Published: August 2021

\emphAlon, Kleitman, Lipton, Meshulam, Rabin and \emphSpencer (Graphs. Combin. 7 (1991), no. 2, 97-99) proved, that for any hypergraph \textbf\textitF=\F_1,F_2,\ldots, F_d(q-1)+1\, where q is a prime-power, and d denotes the maximal degree of the hypergraph, there exists an \textbf\textitF_0⊂ \textbf\textitF, such that |\bigcup_F∈\textbf\textitF_0F| ≡ 0 (q). We give a direct, alternative proof for this theorem, and we also show that an explicit construction exists for a hypergraph of degree d and size Ω (d^2) which does not contain a non-empty sub-hypergraph with a union of size 0 modulo 6, consequently, the theorem does not generalize for non-prime-power moduli.
Finding a Strong Stable Set or a Meyniel Obstruction in any Graph
Authors: Cameron Kathie , Edmonds Jack
Published: August 2021

A strong stable set in a graph $G$ is a stable set that contains a vertex of every maximal clique of $G$. A Meyniel obstruction is an odd circuit with at least five vertices and at most one chord. Given a graph $G$ and a vertex $v$ of $G$, we give a polytime algorithm to find either a strong stable set containing $v$ or a Meyniel obstruction in $G$. This can then be used to find in any graph, a clique and colouring of the same size or a Meyniel obstruction.
Nonrepetitive colorings of graphs
Authors: Alon Noga , Grytczuk Jaroslaw
Published: August 2021

A vertex coloring of a graph $G$ is $k \textit{-nonrepetitive}$ if one cannot find a periodic sequence with $k$ blocks on any simple path of $G$. The minimum number of colors needed for such coloring is denoted by $\pi _k(G)$ . This idea combines graph colorings with Thue sequences introduced at the beginning of 20th century. In particular Thue proved that if $G$ is a simple path of any length greater than $4$ then $\pi _2(G)=3$ and $\pi_3(G)=2$. We investigate $\pi_k(G)$ for other classes of graphs. Particularly interesting open problem is to decide if there is, possibly huge, $k$ such that $\pi_k(G)$ is bounded for planar graphs.
Quadratic LYM-type inequalities for intersecting Sperner families
Authors: Bey Christian
Published: August 2021

Let $\mathcal{F}\subseteq 2^{[n]}$ be a intersecting Sperner family (i.e. $A \not\subset B, A \cap B \neq \emptyset$ for all $A,B \in \mathcal{F}$) with profile vector $(f_i)_{i=0 \ldots n}$ (i.e. $f_i=|\mathcal{F} \cap \binom{[n]}{i}|$). We present quadratic inequalities in the $f_i$'s which sharpen the previously known linear $\mathrm{LYM}$-type inequalities.
Graphs of low chordality
Authors: Chandran Sunil , Lozin Vadim V. , Subramanian C.R.
Published: August 2021

The chordality of a graph with at least one cycle is the length of the longest induced cycle in it. The odd (even) chordality is defined to be the length of the longest induced odd (even) cycle in it. Chordal graphs have chordality at most 3. We show that co-circular-arc graphs and co-circle graphs have even chordality at most 4. We also identify few other classes of graphs having bounded (by a constant) chordality values.
On the 3/4-Conjecture for Fix-Free Codes
Authors: Deppe Christian , Schnettler Holger
Published: August 2021

In this paper we concern ourself with the question, whether there exists a fix-free code for a given sequence of codeword lengths. We focus mostly on results which shows the $\frac{3 }{ 4}$-conjecture for special kinds of lengths sequences.
Hadamard matrices of order 36 and double-even self-dual [72,36,12] codes
Authors: Bouyukliev Iliya , Fack Veerle , Winne Joost
Published: August 2021

Before this work, at least 762 inequivalent Hadamard matrices of order 36 were known. We found 7238 Hadamard matrices of order 36 and 522 inequivalent [72,36,12] double-even self-dual codes which are obtained from all 2-(35,17,8) designs with an automorphism of order 3 and 2 fixed points and blocks.