bluuebunny/crossref_metadata_2025 huggingface dataset:
An inequality of Kostka numbers and Galois groups of Schubert problems
Authors: Brooks Christopher J. , Campo Abraham Martín , Sottile Frank
Published: August 2021

We show that the Galois group of any Schubert problem involving lines in projective space contains the alternating group. Using a criterion of Vakil and a special position argument due to Schubert, this follows from a particular inequality among Kostka numbers of two-rowed tableaux. In most cases, an easy combinatorial injection proves the inequality. For the remaining cases, we use that these Kostka numbers appear in tensor product decompositions of $\mathfrak{sl}_2\mathbb{C}$ -modules. Interpreting the tensor product as the action of certain commuting Toeplitz matrices and using a spectral analysis and Fourier series rewrites the inequality as the positivity of an integral. We establish the inequality by estimating this integral.

On montre que le groupe de Galois de tout problème de Schubert concernant des droites dans l'espace projective contient le groupe alterné. En utilisant un critère de Vakil et l'argument de position spéciale due à Schubert, ce résultat se déduit d'une inégalité particulière des nombres de Kostka des tableaux ayant deux rangées. Dans la plupart des cas, une injection combinatoriale facile montre l’inégalité. Pour les cas restants, on utilise le fait que ces nombres de Kostka apparaissent dans la décomposition en produit tensoriel des $\mathfrak{sl}_2\mathbb{C}$-modules. En interprétant le produit tensoriel comme l'action de certaines matrices de Toeplitz commutant entre elles, et en utilisant de l'analyse spectrale et les séries de Fourier, on réécrit l’inégalité comme la positivité d'une intégrale. L’inégalité sera établie en estimant cette intégrale.
The distribution of m-ary search trees generated by van der Corput sequences
Authors: Steiner Wolfgang
Published: August 2021

We study the structure of $m$-ary search trees generated by the van der Corput sequences. The height of the tree is calculated and a generating function approach shows that the distribution of the depths of the nodes is asymptotically normal. Additionally a local limit theorem is derived.
Counting occurrences of some subword patterns
Authors: Burstein Alexander , Mansour Toufik
Published: August 2021

We find generating functions the number of strings (words) containing a specified number of occurrences of certain types of order-isomorphic classes of substrings called subword patterns. In particular, we find generating functions for the number of strings containing a specified number of occurrences of a given 3-letter subword pattern.
Characterisations of Ideal Threshold Schemes
Authors: Pieprzyk Josef , Zhang Xian-Mo
Published: August 2021

We characterise ideal threshold schemes from different approaches. Since the characteristic properties are independent to particular descriptions of threshold schemes all ideal threshold schemes can be examined by new points of view and new results on ideal threshold schemes can be discovered.
A Note on t-designs with t Intersection Numbers
Authors: Pawale Rajendra M.
Published: August 2021

We discuss Ray-Chaudhari and Wilson inequality for a 0-design and give simple proof of the result '\emphFor fixed block size k, there exist finitely many parametrically feasible t-designs with t intersection numbers and λ > 1'.
Frogs and some other interacting random walks models
Authors: Popov Serguei Yu.
Published: August 2021

We review some recent results for a system of simple random walks on graphs, known as \emphfrog model. Also, we discuss several modifications of this model, and present a few open problems. A simple version of the frog model can be described as follows: There are active and sleeping particles living on some graph. Each active particle performs a simple random walk with discrete time and at each moment it may disappear with probability 1-p. When an active particle hits a sleeping particle, the latter becomes active.
The b-chromatic number of power graphs
Authors: Effantin Brice , Kheddouci Hamamache
Published: August 2021

The b-chromatic number of a graph G is defined as the maximum number k of colors that can be used to color the vertices of G, such that we obtain a proper coloring and each color i, with 1 ≤ i≤ k, has at least one representant x_i adjacent to a vertex of every color j, 1 ≤ j ≠ i ≤ k. In this paper, we discuss the b-chromatic number of some power graphs. We give the exact value of the b-chromatic number of power paths and power complete binary trees, and we bound the b-chromatic number of power cycles.
Individuals at the origin in the critical catalytic branching random walk
Authors: Topchii Valentin , Vatutin Vladimir
Published: August 2021

A continuous time branching random walk on the lattice $\mathbb{Z}$ is considered in which individuals may produce children at the origin only. Assuming that the underlying random walk is symmetric and the offspring reproduction law is critical we prove a conditional limit theorem for the number of individuals at the origin.
Joint Burke's Theorem and RSK Representation for a Queue and a Store
Authors: Draief Moez , Mairesse Jean , O'Connell Neil
Published: August 2021

Consider the single server queue with an infinite buffer and a FIFO discipline, either of type M/M/1 or Geom/Geom/1. Denote by $\mathcal{A}$ the arrival process and by $s$ the services. Assume the stability condition to be satisfied. Denote by $\mathcal{D}$ the departure process in equilibrium and by $r$ the time spent by the customers at the very back of the queue. We prove that $(\mathcal{D},r)$ has the same law as $(\mathcal{A},s)$ which is an extension of the classical Burke Theorem. In fact, $r$ can be viewed as the departures from a dual storage model. This duality between the two models also appears when studying the transient behavior of a tandem by means of the RSK algorithm: the first and last row of the resulting semi-standard Young tableau are respectively the last instant of departure in the queue and the total number of departures in the store.
Linear Phase Transition in Random Linear Constraint Satisfaction Problems
Authors: Gamarnik David
Published: August 2021

Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints $C$ on $K$ variables is fixed. From a pool of $n$ variables, $K$ variables are chosen uniformly at random and a constraint is chosen from $C$ also uniformly at random. This procedure is repeated $m$ times independently. We are interested in whether the resulting linear programming problem is feasible. We prove that the feasibility property experiences a linear phase transition,when $n→∞$ and $m=cn$ for a constant $c$. Namely, there exists a critical value $c^*$ such that, when $c < c^*$, the problem is feasible or is asymptotically almost feasible, as $n→∞$, but, when $c > c^*$, the "distance" to feasibility is at least a positive constant independent of $n$. Our result is obtained using the combination of a powerful local weak convergence method developed in Aldous [1992, 2000], Aldous and Steele [2003], Steele [2002] and martingale techniques. By exploiting a linear programming duality, our theorem impliesthe following result in the context of sparse random graphs $G(n, cn)$ on $n$ nodes with $cn$ edges, where edges are equipped with randomly generated weights. Let $\mathcal{M}(n,c)$ denote maximum weight matching in $G(n, cn)$. We prove that when $c$ is a constant and $n→∞$, the limit $lim_{n→∞} \mathcal{M}(n,c)/n$, exists, with high probability. We further extend this result to maximum weight b-matchings also in $G(n,cn)$.
Profiles of random trees: plane-oriented recursive trees
Authors: Hwang Hsien-Kuei
Published: August 2021

We summarize several limit results for the profile of random plane-oriented recursive trees. These include the limit distribution of the normalized profile, asymptotic bimodality of the variance, asymptotic approximations of the expected width and the correlation coefficients of two level sizes. We also unveil an unexpected connection between the profile of plane-oriented recursive trees (with logarithmic height) and that of random binary trees (with height proportional to the square root of tree size).
Quadratic exact-size and linear approximate-size random generation of planar graphs
Authors: Fusy Eric
Published: August 2021

This extended abstract introduces a new algorithm for the random generation of labelled planar graphs. Its principles rely on Boltzmann samplers as recently developed by Duchon, Flajolet, Louchard, and Schaeffer. It combines the Boltzmann framework, a judicious use of rejection, a new combinatorial bijection found by Fusy, Poulalhon and Schaeffer, as well as a precise analytic description of the generating functions counting planar graphs, which was recently obtained by Giménez and Noy. This gives rise to an extremely efficient algorithm for the random generation of planar graphs. There is a preprocessing step of some fixed small cost. Then, for each generation, the time complexity is quadratic for exact-size uniform sampling and linear for approximate-size sampling. This greatly improves on the best previously known time complexity for exact-size uniform sampling of planar graphs with $n$ vertices, which was a little over $\mathcal{O}(n^7)$.
Asymptotic analysis of a nonlinear AIMD algorithm
Authors: Baryshnikov Y. , Coffman E. , Feng J. , Momčilović P.
Published: August 2021

The Additive-Increase-Multiplicative Decrease (AIMD) algorithm is an effective technique for controlling competitive access to a shared resource. Let $N$ be the number of users and let $x_i(t)$ be the amount of the resource in possession of the $i$-th user. The allocations $x_i(t)$ increase linearly until the aggregate demand $\sum_i x_i(t)$ exceeds a given nominal capacity, at which point a user is selected at a random time and its allocation reduced from $x_i(t)$ to $x_i(t)/ \gamma$ , for some given parameter $\gamma >1$. In our new, generalized version of AIMD, the choice of users to have their allocations cut is determined by a selection rule whereby the probabilities of selection are proportional to $x_i^{\alpha} (t)/ \sum_j x_j^{\alpha}$, with $\alpha$ a parameter of the policy. Variations of parameters allows one to adjust fairness under AIMD (as measured for example by the variance of $x_i(t)$) as well as to provide for differentiated service. The primary contribution here is an asymptotic, large-$N$ analysis of the above nonlinear AIMD algorithm within a baseline mathematical model that leads to explicit formulas for the density function governing the allocations $x_i(t)$ in statistical equilibrium. The analysis yields explicit formulas for measures of fairness and several techniques for supplying differentiated service via AIMD.
Efficient maxima-finding algorithms for random planar samples
Authors: Chen Wei-Mei , Hwang Hsien-Kuei , Tsai Tsung-Hsi
Published: August 2021

We collect major known algorithms in the literature for finding the maxima of multi-dimensional points and provide a simple classification. Several new algorithms are proposed. In particular, we give a new maxima-finding algorithm with expected complexity n+O(√n\log n) when the input is a sequence of points uniformly chosen at random from general planar regions. We also give a sequential algorithm, very efficient for practical purposes.
Distribution of inter-node distances in digital trees
Authors: Aguech Rafik , Lasmar Nabil , Mahmoud Hosam
Published: August 2021

We investigate distances between pairs of nodes in digital trees (digital search trees (DST), and tries). By analytic techniques, such as the Mellin Transform and poissonization, we describe a program to determine the moments of these distances. The program is illustrated on the mean and variance. One encounters delayed Mellin transform equations, which we solve by inspection. Interestingly, the unbiased case gives a bounded variance, whereas the biased case gives a variance growing with the number of keys. It is therefore possible in the biased case to show that an appropriately normalized version of the distance converges to a limit. The complexity of moment calculation increases substantially with each higher moment; A shortcut to the limit is needed via a method that avoids the computation of all moments. Toward this end, we utilize the contraction method to show that in biased digital search trees the distribution of a suitably normalized version of the distances approaches a limit that is the fixed-point solution (in the Wasserstein space) of a distributional equation. An explicit solution to the fixed-point equation is readily demonstrated to be Gaussian.
Analysis of tree algorithm for collision resolution
Authors: Gyorfi Laszlo , Gyori Sándor
Published: August 2021

For the tree algorithm introduced by [Cap79] and [TsMi78] let $L_N$ denote the expected collision resolution time given the collision multiplicity $N$. If $L(z)$ stands for the Poisson transform of $L_N$, then we show that $L_N - L(N) ≃ 1.29·10^-4 \cos (2 π \log _2 N + 0.698)$.
A tight upper bound on the size of the antidictionary of a binary string
Authors: Morita Hiroyoshi , Ota Takahiro
Published: August 2021

A tight upper bound of the size of the antidictionary of a binary string is presented. And it is shown that the size of the antidictionary of a binary sting is always smaller than or equal to that of its dictionary. Moreover, an algorithm to reconstruct its dictionary from its antidictionary is given.
Two-anticoloring of planar and related graphs
Authors: Berend Daniel , Korach Ephraim , Zucker Shira
Published: August 2021

An $\textit{anticoloring}$ of a graph is a coloring of some of the vertices, such that no two adjacent vertices are colored in distinct colors. We deal with the anticoloring problem with two colors for planar graphs, and, using Lipton and Tarjan's separation algorithm, provide an algorithm with some bound on the error. In the particular cases of graphs which are strong products of two paths or two cycles, we provide an explicit optimal solution.
Distance graphs with maximum chromatic number
Authors: Barajas Javier , Serra Oriol
Published: August 2021

Let $D$ be a finite set of integers. The distance graph $G(D)$ has the set of integers as vertices and two vertices at distance $d ∈D$ are adjacent in $G(D)$. A conjecture of Xuding Zhu states that if the chromatic number of $G (D)$ achieves its maximum value $|D|+1$ then the graph has a clique of order $|D|$. We prove that the chromatic number of a distance graph with $D=\{ a,b,c,d\}$ is five if and only if either $D=\{1,2,3,4k\}$ or $D=\{ a,b,a+b,a+2b\}$ with $a \equiv 0 (mod 2)$ and $b \equiv 1 (mod 2)$. This confirms Zhu's conjecture for $|D|=4$.
Pebble Game Algorithms and (k,l)-Sparse Graphs
Authors: Lee Audrey , Streinu Ileana
Published: August 2021

A multi-graph $G$ on n vertices is $(k,l)$-sparse if every subset of $n'≤n$ vertices spans at most $kn'-l$ edges, $0 ≤l < 2k$. $G$ is tight if, in addition, it has exactly $kn - l$ edges. We characterize $(k,l)$-sparse graphs via a family of simple, elegant and efficient algorithms called the $(k,l)$-pebble games. As applications, we use the pebble games for computing components (maximal tight subgraphs) in sparse graphs, to obtain inductive (Henneberg) constructions, and, when $l=k$, edge-disjoint tree decompositions.
On the Grone-Merris conjecture
Authors: Stephen Tamon
Published: August 2021

Grone and Merris [GM94] conjectured that the Laplacian spectrum of a graph is majorized by its conjugate vertex degree sequence. We prove that this conjecture holds for a class of graphs including trees. We also show that this conjecture and its generalization to graphs with Dirichlet boundary conditions are equivalent.
$K_{\ell}^{-}$-factors in graphs
Authors: Kühn Daniela , Osthus Deryk
Published: August 2021

Let $K_ℓ^-$ denote the graph obtained from $K_ℓ$ by deleting one edge. We show that for every $γ >0$ and every integer $ℓ≥4$ there exists an integer $n_0=n_0(γ ,ℓ)$ such that every graph $G$ whose order $n≥n_0$ is divisible by $ℓ$ and whose minimum degree is at least $(\frac{ℓ^2-3ℓ+1}{/ ℓ(ℓ-2)}+γ )n$ contains a $K_ℓ^-$-factor, i.e. a collection of disjoint copies of $K_ℓ^-$ which covers all vertices of $G$. This is best possible up to the error term $γn$ and yields an approximate solution to a conjecture of Kawarabayashi.
Packing triangles in low degree graphs and indifference graphs
Authors: Manić Gordana , Wakabayashi Yoshiko
Published: August 2021

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation guarantee known so far for these problems has ratio $3/2 + ɛ$, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver in 1989. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs.
NBC Complexes of Convex Geometries
Authors: Kashiwabara Kenji , Nakamura Masataka
Published: August 2021

We introduce a notion of a $\textit{broken circuit}$ and an $\textit{NBC complex}$ for an (abstract) convex geometry. Based on these definitions, we shall show the analogues of the Whitney-Rota's formula and Brylawski's decomposition theorem for broken circuit complexes on matroids for convex geometries. We also present an Orlik-Solomon type algebra on a convex geometry, and show the NBC generating theorem.
Decomposable graphs and definitions with no quantifier alternation
Authors: Pikhurko Oleg , Spencer Joel , Verbitsky Oleg
Published: August 2021

Let $D(G)$ be the minimum quantifier depth of a first order sentence $\Phi$ that defines a graph $G$ up to isomorphism in terms of the adjacency and the equality relations. Let $D_0(G)$ be a variant of $D(G)$ where we do not allow quantifier alternations in $\Phi$. Using large graphs decomposable in complement-connected components by a short sequence of serial and parallel decompositions, we show examples of $G$ on $n$ vertices with $D_0(G) \leq 2 \log^{\ast}n+O(1)$. On the other hand, we prove a lower bound $D_0(G) \geq \log^{\ast}n-\log^{\ast}\log^{\ast}n-O(1)$ for all $G$. Here $\log^{\ast}n$ is equal to the minimum number of iterations of the binary logarithm needed to bring $n$ below $1$.
A sufficient condition for bicolorable hypergraphs
Authors: Défossez David
Published: August 2021

In this note we prove Sterboul's conjecture, that provides a sufficient condition for the bicolorability of hypergraphs.
Chromatic Turán problems and a new upper bound for the Turán density of $\mathcal{K}_4^-$
Authors: Talbot John
Published: August 2021

We consider a new type of extremal hypergraph problem: given an $r$-graph $\mathcal{F}$ and an integer $k≥2$ determine the maximum number of edges in an $\mathcal{F}$-free, $k$-colourable $r$-graph on $n$ vertices. Our motivation for studying such problems is that it allows us to give a new upper bound for an old problem due to Turán. We show that a 3-graph in which any four vertices span at most two edges has density less than $\frac{33}{ 100}$, improving previous bounds of $\frac{1}{ 3}$ due to de Caen [1], and $\frac{1}{ 3}-4.5305×10^-6$ due to Mubayi [9].
Recognizing Maximal Unfrozen Graphs with respect to Independent Sets is CO-NP-complete
Authors: Abbas Nesrine , Culberson Joseph , Stewart Lorna
Published: August 2021

A graph is unfrozen with respect to k independent set if it has an independent set of size k after the addition of any edge. The problem of recognizing such graphs is known to be NP-complete. A graph is maximal if the addition of one edge means it is no longer unfrozen. We designate the problem of recognizing maximal unfrozen graphs as MAX(U(k-SET)) and show that this problem is CO-NP-complete. This partially fills a gap in known complexity cases of maximal NP-complete problems, and raises some interesting open conjectures discussed in the conclusion.
On the number of series parallel and outerplanar graphs
Authors: Bodirsky Manuel , Gimenez Omer , Kang Mihyun , Noy Marc
Published: August 2021

We show that the number $g_n$ of labelled series-parallel graphs on $n$ vertices is asymptotically $g_n \sim g \cdot n^{-5/2} \gamma^n n!$, where $\gamma$ and $g$ are explicit computable constants. We show that the number of edges in random series-parallel graphs is asymptotically normal with linear mean and variance, and that the number of edges is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs.
A Min-Max theorem about the Road Coloring Conjecture
Authors: Hegde Rajneesh , Jain Kamal
Published: August 2021

The Road Coloring Conjecture is an old and classical conjecture e posed in Adler and Weiss (1970); Adler et al. (1977). Let $G$ be a strongly connected digraph with uniform out-degree $2$. The Road Coloring Conjecture states that, under a natural (necessary) condition that $G$ is "aperiodic'', the edges of $G$ can be colored red and blue such that "universal driving directions'' can be given for each vertex. More precisely, each vertex has one red and one blue edge leaving it, and for any vertex $v$ there exists a sequence $s_v$ of reds and blues such that following the sequence from $\textit{any}$ starting vertex in $G$ ends precisely at the vertex $v$. We first generalize the conjecture to a min-max conjecture for all strongly connected digraphs. We then generalize the notion of coloring itself. Instead of assigning exactly one color to each edge we allow multiple colors to each edge. Under this relaxed notion of coloring we prove our generalized Min-Max theorem. Using the Prime Number Theorem (PNT) we further show that the number of colors needed for each edge is bounded above by $O(\log n / \log \log n)$, where $n$ is the number of vertices in the digraph.
On the Frobenius’ Problem of three numbers
Authors: Aguiló Francesc , Miralles Alícia
Published: August 2021

Given $k$ natural numbers $\{a_1, \ldots ,a_k\} \subset \mathbb{N}$ with $1 \leq a_1 < a_2 < \ldots < a_k$ and $\mathrm{gcd} (a_1, \ldots ,a_k)=1$, let be $R(a_1, \ldots ,a_k) = \{ \lambda_1 a_1+ \cdots + \lambda_k a_k | \space \lambda_i \in \mathbb{N}, i=1 \div k\}$ and $\overline{R}(a_1, \ldots ,a_k) = \mathbb{N} \backslash R (a_1, \ldots ,a_k)$. It is easy to see that $| \overline{R}(a_1, \ldots ,a_k)| < \infty$. The $\textit{Frobenius Problem}$ related to the set $\{a_1, \ldots ,a_k\}$ consists on the computation of $f(a_1, \ldots ,a_k)=\max \overline{R} (a_1, \ldots ,a_k)$, also called the $\textit{Frobenius number}$, and the cardinal $| \overline{R}(a_1, \ldots ,a_k)|$. The solution of the Frobenius Problem is the explicit computation of the set $\overline{R} (a_1,\ldots ,a_k)$. In some cases it is known a sharp upper bound for the Frobenius number. When $k=3$ this bound is known to be $$F(N)=\max\limits_{\substack{0 \lt a \lt b \lt N \\ \mathrm{gcd}(a,b,N)=1}} f(a,b,N)= \begin{cases} 2(\lfloor N/2 \rfloor -1)^2-1 & \textrm{if } N \equiv 0 (\mod 2),\\ 2 \lfloor N/2 \rfloor (\lfloor N/2 \rfloor -1) -1 & \textrm{if } N \equiv 1 (\mod 2).\\ \end{cases}$$ This bound is given in [Dixmier1990]. In this work we give a geometrical proof of this bound which allows us to give the solution of the Frobenius problem for all the sets $\{\alpha ,\beta ,N\}$ such that $f(\alpha ,\beta ,N)=F(N)$.
Analysis of a new skip list variant
Authors: Louchard Guy , Prodinger Helmut
Published: August 2021

For a skip list variant, introduced by Cho and Sahni, we analyse what is the analogue of horizontal plus vertical search cost in the original skip list model. While the average in Pugh's original version behaves like $Q \log_Q n$, with $Q = \frac{1}{q}$ a parameter, it is here given by $(Q+1) \log_Q n$.
Constrained exchangeable partitions
Authors: Gnedin Alexander
Published: August 2021

For a class of random partitions of an infinite set a de Finetti-type representation is derived, and in one special case a central limit theorem for the number of blocks is shown.
A Cross Entropy Algorithm for Classification with $\delta$−Patterns
Authors: Alexe Gabriela , Bhanot Gyan , Climescu-Haulica Adriana
Published: August 2021

A classification strategy based on $\delta$-patterns is developed via a combinatorial optimization problem related with the maximal clique generation problem on a graph. The proposed solution uses the cross entropy method and has the advantage to be particularly suitable for large datasets. This study is tailored for the particularities of the genomic data.
On the number of decomposable trees
Authors: Wagner Stephan G.
Published: August 2021

A tree is called $k$-decomposable if it has a spanning forest whose components are all of size $k$. Analogously, a tree is called $T$-decomposable for a fixed tree $T$ if it has a spanning forest whose components are all isomorphic to $T$. In this paper, we use a generating functions approach to derive exact and asymptotic results on the number of $k$-decomposable and $T$-decomposable trees from a so-called simply generated family of trees - we find that there is a surprisingly simple functional equation for the counting series of $k$-decomposable trees. In particular, we will study the limit case when $k$ goes to $\infty$. It turns out that the ratio of $k$-decomposable trees increases when $k$ becomes large.
Computing generating functions of ordered partitions with the transfer-matrix method
Authors: Ishikawa Masao , Kasraoui Anisse , Zeng Jiang
Published: August 2021

An ordered partition of $[n]:=\{1,2,\ldots, n\}$ is a sequence of disjoint and nonempty subsets, called blocks, whose union is $[n]$. The aim of this paper is to compute some generating functions of ordered partitions by the transfer-matrix method. In particular, we prove several conjectures of Steingrímsson, which assert that the generating function of some statistics of ordered partitions give rise to a natural $q$-analogue of $k!S(n,k)$, where $S(n,k)$ is the Stirling number of the second kind.
On the Recognition of Bipolarizable and P_4-simplicial Graphs
Authors: Nikolopoulos Stavros D. , Palios Leonidas
Published: August 2021

The classes of Raspail (also known as Bipolarizable) and P_4-simplicial graphs were introduced by Hoàng and Reed who showed that both classes are perfectly orderable and admit polynomial-time recognition algorithms HR1. In this paper, we consider the recognition problem on these classes of graphs and present algorithms that solve it in O(n m) time. In particular, we prove properties and show that we can produce bipolarizable and P_4-simplicial orderings on the vertices of the input graph G, if such orderings exist, working only on P_3s that participate in a P_4 of G. The proposed recognition algorithms are simple, use simple data structures and both require O(n + m) space. Additionally, we show how our recognition algorithms can be augmented to provide certificates, whenever they decide that G is not bipolarizable or P_4-simplicial; the augmentation takes O(n + m) time and space. Finally, we include a diagram on class inclusions and the currently best recognition time complexities for a number of perfectly orderable classes of graphs.
One-sided Variations on Tries: Path Imbalance, Climbing, and Key Sampling
Authors: Christophi Costas A. , Mahmoud Hosam M.
Published: August 2021

One-sided variations on path length in a trie (a sort of digital trees) are investigated: They include imbalance factors, climbing under different strategies, and key sampling. For the imbalance factor accurate asymptotics for the mean are derived for a randomly chosen key in the trie via poissonization and the Mellin transform, and the inverse of the two operations. It is also shown from an analysis of the moving poles of the Mellin transform of the poissonized moment generating function that the imbalance factor (under appropriate centering and scaling) follows a Gaussian limit law. The method extends to several variations of sampling keys from a trie and we sketch results of climbing under different strategies. The exact probability distribution is computed in one case, to demonstrate that such calculations can be done, at least in principle.
The Size of the rth Smallest Component in Decomposable Structures with a Restricted Pattern
Authors: Dong Li , Gao Zhicheng , Panario Daniel
Published: August 2021

In our previous work [paper1], we derived an asymptotic expression for the probability that a random decomposable combinatorial structure of size n in the \exp -\log class has a given restricted pattern. In this paper, under similar conditions, we provide the probability that a random decomposable combinatorial structure has a given restricted pattern and the size of its rth smallest component is bigger than k, for r,k given integers. Our studies apply to labeled and unlabeled structures. We also give several concrete examples.
Analysis of the total costs for variants of the Union-Find algorithm
Authors: Kuba Markus , Panholzer Alois
Published: August 2021

We study the average behavior of variants of the UNION-FIND algorithm to maintain partitions of a finite set under the random spanning tree model. By applying the method of moments we can characterize the limiting distribution of the total costs of the algorithms "Quick Find Weighted'' and "Quick Find Biased'' extending the analysis of Knuth and Schönhage, Yao, and Chassaing and Marchand.
Counting occurrences for a finite set of words: an inclusion-exclusion approach
Authors: Bassino Frédérique , Clément Julien , Fayolle J. , Nicodème P.
Published: August 2021

In this paper, we give the multivariate generating function counting texts according to their length and to the number of occurrences of words from a finite set. The application of the inclusion-exclusion principle to word counting due to Goulden and Jackson (1979, 1983) is used to derive the result. Unlike some other techniques which suppose that the set of words is reduced (i..e., where no two words are factor of one another), the finite set can be chosen arbitrarily. Noonan and Zeilberger (1999) already provided a MAPLE package treating the non-reduced case, without giving an expression of the generating function or a detailed proof. We give a complete proof validating the use of the inclusion-exclusion principle and compare the complexity of the method proposed here with the one using automata for solving the problem.
Properties of Random Graphs via Boltzmann Samplers
Authors: Panagiotou Konstantinos , Weißl Andreas
Published: August 2021

This work is devoted to the understanding of properties of random graphs from graph classes with structural constraints. We propose a method that is based on the analysis of the behaviour of Boltzmann sampler algorithms, and may be used to obtain precise estimates for the maximum degree and maximum size of a biconnected block of a "typical'' member of the class in question. We illustrate how our method works on several graph classes, namely dissections and triangulations of convex polygons, embedded trees, and block and cactus graphs.
The height of random binary unlabelled trees
Authors: Broutin Nicolas , Flajolet Philippe
Published: August 2021

This extended abstract is dedicated to the analysis of the height of non-plane unlabelled rooted binary trees. The height of such a tree chosen uniformly among those of size $n$ is proved to have a limiting theta distribution, both in a central and local sense. Moderate as well as large deviations estimates are also derived. The proofs rely on the analysis (in the complex plane) of generating functions associated with trees of bounded height.
The register function for lattice paths
Authors: Louchard Guy , Prodinger Helmut
Published: August 2021

The register function for binary trees is the minimal number of extra registers required to evaluate the tree. This concept is also known as Horton-Strahler numbers. We extend this definition to lattice paths, built from steps $\pm 1$, without positivity restriction. Exact expressions are derived for appropriate generating functions. A procedure is presented how to get asymptotics of all moments, in an almost automatic way; this is based on an earlier paper of the authors.
On square permutations
Authors: Duchi Enrica , Poulalhon Dominique
Published: August 2021

Severini and Mansour introduced $\textit{square polygons}$, as graphical representations of $\textit{square permutations}$, that is, permutations such that all entries are records (left or right, minimum or maximum), and they obtained a nice formula for their number. In this paper we give a recursive construction for this class of permutations, that allows to simplify the derivation of their formula and to enumerate the subclass of square permutations with a simple record polygon. We also show that the generating function of these permutations with respect to the number of records of each type is algebraic, answering a question of Wilf in a particular case.
Small parts in the Bernoulli sieve
Authors: Gnedin Alexander , Iksanov Alex , Roesler Uwe
Published: August 2021

Sampling from a random discrete distribution induced by a 'stick-breaking' process is considered. Under a moment condition, it is shown that the asymptotics of the sequence of occupancy numbers, and of the small-parts counts (singletons, doubletons, etc) can be read off from a limiting model involving a unit Poisson point process and a self-similar renewal process on the half-line.
Hopcroft's automaton minimization algorithm and Sturmian words
Authors: Berstel Jean , Boasson Luc , Carton Olivier
Published: August 2021

This paper is concerned with the analysis of the worst case behavior of Hopcroft's algorithm for minimizing deterministic finite state automata. We extend a result of Castiglione, Restivo and Sciortino. They show that Hopcroft's algorithm has a worst case behavior for the automata recognizing Fibonacci words. We prove that the same holds for all standard Sturmian words having an ultimately periodic directive sequence (the directive sequence for Fibonacci words is $(1,1,\ldots)$).
Analytic Combinatorics of the Mabinogion Urn
Authors: Flajolet Philippe , Huillet Thierry
Published: August 2021

The Mabinogion urn is a simple model of the spread of influences amongst versatile populations. It corresponds to a non-standard urn with balls of two colours: each time a ball is drawn, it causes a ball of the other kind to switch its colour. The process stops once unanimity has been reached. This note provides analytic expressions describing the evolution of the Mabinogion urn, based on a time-reversal transformation applied to the classical Ehrenfest urn. Consequences include a precise asymptotic analysis of the stopping-time distribution―it is asymptotically normal in the "unfair'' case and akin to an extreme-value (double exponential) distribution in the "fair'' case―as well as a characterization of the exponentially small probability of reversing a majority.
A variation on the tableau switching and a Pak-Vallejo's conjecture
Authors: Azenhas Olga
Published: August 2021

Pak and Vallejo have defined fundamental symmetry map as any Young tableau bijection for the commutativity of the Littlewood-Richardson coefficients $c_{\mu,\nu}^{\lambda}=c_{\nu, \mu}^{\lambda}$. They have considered four fundamental symmetry maps and conjectured that they are all equivalent (2004). The three first ones are based on standard operations in Young tableau theory and, in this case, the conjecture was proved by Danilov and Koshevoy (2005). The fourth fundamental symmetry, given by the author in (1999;2000) and reformulated by Pak and Vallejo, is defined by nonstandard operations in Young tableau theory and will be shown to be equivalent to the first one defined by the involution property of the Benkart-Sottile-Stroomer tableau switching. The proof of this equivalence provides, in the case the first tableau is Yamanouchi, a variation of the tableau switching algorithm which shows $\textit{switching}$ as an operation that takes two tableaux sharing a common border and moves them trough each other by decomposing the first tableau into a sequence of tableaux whose sequence of partition shapes defines a Gelfand-Tsetlin pattern. This property leads to a $\textit{jeu de taquin-chain sliding}$ on Littlewood-Richardson tableaux.

Pak et Vallejo ont défini la transformation de la symétrie fondamentale comme une bijection de tableaux de Young pour la comutativité des coefficients de Littlewood-Richardson $c_{\mu,\nu}^{\lambda}=c_{\nu, \mu}^{\lambda}$. Ils ont considéré quatre bijections fondamentaux et ont conjecturé qu’elles sont équivalentes (2004). Les trois premières sont basées sur des opérations standard de la théorie des tableaux de Young et, dans ce cas, la conjecture a été confirmée par Danilov et Koshevoy (2005). La quatrième symétrie fondamentale, donnée par l’auteur (1999;2000) et reformulée par Pak et Vallejo, est définie par des opérations $\textit{nonstandard}$ dans la théorie des tableaux de Young. Cette bijection sera montrée équivalente à la première définie pour la propriété involutoire du $\textit{tableau switching}$ de Benkart-Sottile-Stroomer. La preuve de cette équivalence, dans le cas le premier tableau est de Yamanouchi, donne une variation du algorithme de $\textit{tableau switching}$ qui montre $\textit{switching}$ comme une opération qui prendre deux tableaux avec une même borde et meut un à travers de l’autre en décomposant le premier dans une séquence de tableaux dont la séquence des partitions des formats définit une diagramme de Gelfand-Tsetlin. Cette propriété conduit à un algorithme du type $\textit{jeu de taquin-glissements sur chaînes}$ pour les tableaux de Littlewood-Richardson.
Perfect Matchings and Cluster Algebras of Classical Type
Authors: Musiker Gregg
Published: August 2021

In this paper we give a graph theoretic combinatorial interpretation for the cluster variables that arise in most cluster algebras of finite type. In particular, we provide a family of graphs such that a weighted enumeration of their perfect matchings encodes the numerator of the associated Laurent polynomial while decompositions of the graphs correspond to the denominator. This complements recent work by Schiffler and Carroll-Price for a cluster expansion formula for the $A_n$ case while providing a novel interpretation for the $B_n$, $C_n$, and $D_n$ cases.

Dans cet article nous donnons une interprétation combinatoire en termes de théorie des graphes pour les variables de clusters qui apparaissent dans la plupart des algèbres à clusters de type fini. En particulier, nous décrivons une famille de graphes tels qu'une énumération pondérée de leurs matchings parfaits encode le numérateur du polynôme de Laurent associé, tandis que les décompositions du graphe correspondent au dénominateur. Ceci complète les récents travaux de Schiffler et Carroll-Price qui donnent une formule pour le développement d'une variable de cluster dans le cas $A_n$, tout en fournissant une nouvelle interprétation dans les cas $B_n$, $C_n$ et $D_n$.
Pattern-Avoidance in Binary Fillings of Grid Shapes (short version)
Authors: Spiridonov Alexey
Published: August 2021

A $\textit{grid shape}$ is a set of boxes chosen from a square grid; any Young diagram is an example. This paper considers a notion of pattern-avoidance for $0-1$ fillings of grid shapes, which generalizes permutation pattern-avoidance. A filling avoids some patterns if none of its sub-shapes equal any of the patterns. We focus on patterns that are $\textit{pairs}$ of $2 \times 2$ fillings. For some shapes, fillings that avoid specific $2 \times 2$ pairs are in bijection with totally nonnegative Grassmann cells, or with acyclic orientations of bipartite graphs. We prove a number of results analogous to Wilf-equivalence for these objects ―- that is, we show that for certain classes of shapes, some pattern-avoiding fillings are equinumerous with others.

Une $\textit{forme de grille}$ est un ensemble de cases choisies dans une grille carrée; un diagramme de Young en est un exemple. Cet article considère une notion de motif exclu pour un remplissage d'une forme de grille par des $0$ et des $1$, qui généralise la notion correspondante pour les permutations. Un remplissage évite certains motifs si aucune de ses sous-formes n'est égale à un motif. Nous nous concentrons sur les motifs qui sont des $\textit{paires de remplissages}$ de taille $2 \times 2$. Pour certaines formes, les remplissages évitant certaines paires de taille $2 \times 2$ sont en bijection avec les cellules de Grassmann totalement positives, ou bien avec les orientations acycliques de graphes bipartis. Nous démontrons plusieurs résultats analogues à l'équivalence de Wilf pour ces objets ―- c'est-à-dire, nous montrons que, pour certaines classes de formes, des remplissages évitant un motif donné sont en nombre égal à d'autres remplissages.
Enumeration of bilaterally symmetric 3-noncrossing partitions
Authors: Xin Guoce , Zhang Terence Y. J.
Published: August 2021

Schützenberger's theorem for the ordinary RSK correspondence naturally extends to Chen et. al's correspondence for matchings and partitions. Thus the counting of bilaterally symmetric $k$-noncrossing partitions naturally arises as an analogue for involutions. In obtaining the analogous result for $3$-noncrossing partitions, we use a different technique to develop a $\mathsf{MAPLE}$ package for $2$-dimensional vacillating lattice walk enumeration problems. As an application, we find an interesting relation between two special bilaterally symmetric partitions.
The Rees product of the cubical lattice with the chain
Authors: Muldoon Patricia , Readdy Margaret A.
Published: August 2021

We study enumerative and homological properties of the Rees product of the cubical lattice with the chain. We give several explicit formulas for the Möbius function. The last formula is expressed in terms of the permanent of a matrix and is given by a bijective proof.

Nous étudions des propriétés énumératives et homologiques du produit de Rees du treillis cubique avec la chaîne. Nous donnons plusieurs formules explicites de la fonction de Möbius de ce poset. La dernière de ces formules est exprimée en termes du permanent d’une matrice et le résultat est donné par une preuve bijective.
Hecke group algebras as degenerate affine Hecke algebras
Authors: Hivert Florent , Schilling Anne , Thiéry Nicolas M.
Published: August 2021

The Hecke group algebra $\operatorname{H} \mathring{W}$ of a finite Coxeter group $\mathring{W}$, as introduced by the first and last author, is obtained from $\mathring{W}$ by gluing appropriately its $0$-Hecke algebra and its group algebra. In this paper, we give an equivalent alternative construction in the case when $\mathring{W}$ is the classical Weyl group associated to an affine Weyl group $W$. Namely, we prove that, for $q$ not a root of unity, $\operatorname{H} \mathring{W}$ is the natural quotient of the affine Hecke algebra $\operatorname{H}(W)(q)$ through its level $0$ representation. The proof relies on the following core combinatorial result: at level $0$ the $0$-Hecke algebra acts transitively on $\mathring{W}$. Equivalently, in type $A$, a word written on a circle can be both sorted and antisorted by elementary bubble sort operators. We further show that the level $0$ representation is a calibrated principal series representation $M(t)$ for a suitable choice of character $t$, so that the quotient factors (non trivially) through the principal central specialization. This explains in particular the similarities between the representation theory of the classical $0$-Hecke algebra and that of the affine Hecke algebra at this specialization.

L'algèbre de Hecke groupe $\operatorname{H} \mathring{W}$ d'un groupe de Coxeter fini $\mathring{W}$, introduite par le premier et le dernier auteur, est obtenue en recollant de manière appropriée son algèbre de Hecke dégénérée et son algèbre de groupe. Dans cet article, nous donnons une construction alternative dans le cas où $\mathring{W}$ est un groupe de Weyl associé à un groupe de Weyl affine $W$. Plus précisément, nous montrons que quand $q$ n'est ni nul ni une racine de l'unité, $\operatorname{H} \mathring{W}$ est le quotient naturel de l'algèbre de Hecke affine $\operatorname{H}(W)(q)$ dans sa représentation de niveau $0$. Nous montrons de plus que la représentation de niveau $0$ est une représentation de série principale calibrée $M(t)$ pour un certain caractère $t$, de sorte que le quotient se factorise par la spécialisation centrale principale. Ce fait explique en particulier les similarités entre les théories des représentations de l'algèbre de Hecke dégénérée et de l'algèbre de Hecke affine sous cette spécialisation.
A Quantization of a theorem of Goulden and Jackson
Authors: Konvalinka Matjaž , Skandera Mark
Published: August 2021

A theorem of Goulden and Jackson which gives interesting formulae for character immanants also implies MacMahon's Master Theorem. We quantize Goulden and Jackson's theorem to give formulae for quantum character immanants in such a way as to obtain a known quantization of MacMahon's Master Theorem due to Garoufalidis-Lê-Zeilberger. In doing so, we also quantize formulae of Littlewood, Merris and Watkins concerning induced character immanants.

Le Théorème Master de MacMahon peut être vu comme un corollaire d'un résultat de Goulden et Jackson décrivant certaines formules satisfaites par les caractères immanants. Dans cet article, on obtient une version quantique des formules de Goulden et Jackson, ce qui permet de donner une nouvelle preuve du résultat de Garoufalidis, Lê et Zeilberger sur la quantification du Théorème Master de MacMahon. Ce faisant, on arrive aussi à quantifier les formules de Littlewood, Merris et Watkins concernant les caractères immanants induits.
Affine descents and the Steinberg torus
Authors: Dilks Kevin , Petersen T. Kyle , Stembridge John R.
Published: August 2021

Let $W \ltimes L$ be an irreducible affine Weyl group with Coxeter complex $\Sigma$, where $W$ denotes the associated finite Weyl group and $L$ the translation subgroup. The Steinberg torus is the Boolean cell complex obtained by taking the quotient of $\Sigma$ by the lattice $L$. We show that the ordinary and flag $h$-polynomials of the Steinberg torus (with the empty face deleted) are generating functions over $W$ for a descent-like statistic first studied by Cellini. We also show that the ordinary $h$-polynomial has a nonnegative $\gamma$-vector, and hence, symmetric and unimodal coefficients. In the classical cases, we also provide expansions, identities, and generating functions for the $h$-polynomials of Steinberg tori.

Nous considérons un groupe de Weyl affine irréductible $W \ltimes L$ avec complexe de Coxeter $\Sigma$, où $W$ désigne le groupe de Weyl fini associé et $L$ le sous-groupe des translations. Le tore de Steinberg est le complexe cellulaire Booléen obtenu comme le quotient de $\Sigma$ par $L$. Nous montrons que les $h$-polynômes, ordinaires et de drapeaux, du tore de Steinberg (sans la face vide) sont des fonctions génératrices sur $W$ pour une statistique de type descente, étudiée en premier lieu par Cellini. Nous montrons également qu'un $h$-polynôme ordinaire possède un $\gamma$-vecteur positif, et par conséquent, a des coefficients symétriques et unimodaux. Dans les cas classiques, nous donnons également des développements, des identités et des fonctions génératrices pour les $h$-polynômes des tores de Steinberg.