bluuebunny/crossref_metadata_2025 huggingface dataset:
Phylogenetic trees and the tropical geometry of flag varieties
Authors: Manon Christopher
Published: August 2021

We will discuss some recent theorems relating the space of weighted phylogenetic trees to the tropical varieties of each flag variety of type A. We will also discuss the tropicalizations of the functions corresponding to semi-standard tableaux, in particular we relate them to familiar functions from phylogenetics. We close with some remarks on the generalization of these results to the tropical geometry of arbitrary flag varieties. This involves the family of Bergman complexes derived from the hyperplane arrangements associated to simple Dynkin diagrams.

Nous allons discuter de quelques théorèmes récents concernant l'espace des arbres phylogénétiques aux variétés Tropicales de chaque variété de drapeaux de type A. Nous allons également discuter des tropicalisations des fonctions correspondant à tableaux semi-standard, en particulier, nous les rapporter à des fonctions familières de la phylogénétique. Nous terminerons avec quelques remarques sur la généralisation de ces résultats à la géométrie tropicale de variétés de drapeaux arbitraires. Il s'agit de la famille de complexes Bergman provenant des arrangements d'hyperplans associés à des diagrammes de Dynkin simples.
Product of Stanley symmetric functions
Authors: Li Nan
Published: August 2021

We study the problem of expanding the product of two Stanley symmetric functions $F_w·F_u$ into Stanley symmetric functions in some natural way. Our approach is to consider a Stanley symmetric function as a stabilized Schubert polynomial $F_w=\lim _n→∞\mathfrak{S}_{1^n×w}$, and study the behavior of the expansion of $\mathfrak{S} _{1^n×w}·\mathfrak{S} _{1^n×u}$ into Schubert polynomials, as $n$ increases. We prove that this expansion stabilizes and thus we get a natural expansion for the product of two Stanley symmetric functions. In the case when one permutation is Grassmannian, we have a better understanding of this stability.

Nous étudions le problème de développement du produit de deux fonctions symétriques de Stanley $F_w·F_u$ en fonctions symétriques de Stanley de façon naturelle. Notre méthode consiste à considérer une fonction symétrique de Stanley comme un polynôme du Schubert stabilisè $F_w=\lim _n→∞\mathfrak{S}_{1^n×w}$, et à étudier le comportement de développement de $\mathfrak{S} _{1^n×w}·\mathfrak{S} _{1^n×u}$ en polynômes de Schubert lorsque $n$ augmente. Nous prouvons que cette développement se stabilise et donc nous obtenons une développement naturelle pour le produit de deux fonctions symétriques de Stanley. Dans le cas où l'une des permutations est Grassmannienne, nous avons une meilleure compréhension de cette stabilité.
A simple formula for bipartite and quasi-bipartite maps with boundaries
Authors: Collet Gwendal , Fusy Eric
Published: August 2021

We obtain a very simple formula for the generating function of bipartite (resp. quasi-bipartite) planar maps with boundaries (holes) of prescribed lengths, which generalizes certain expressions obtained by Eynard in a book to appear. The formula is derived from a bijection due to Bouttier, Di Francesco and Guitter combined with a process (reminiscent of a construction of Pitman) of aggregating connected components of a forest into a single tree.

Nous obtenons une formule très simple pour la série génératrice des cartes biparties ayant des bords (trous) de tailles fixées, généralisant certaines expressions obtenues par Eynard dans un livre à paraître. Nous obtenons la formule à partir d'une bijection due à Bouttier, Di Francesco et Guitter, combinée avec un processus (dans l'esprit d'une construction due à Pitman) pour agréger les composantes connexes d'une forêt en un unique arbre.
Triangulations of cyclic polytopes
Authors: Oppermann Steffen , Thomas Hugh
Published: August 2021

We give a new description of the combinatorics of triangulations of even-dimensional cyclic polytopes, and of their bistellar flips. We show that the tropical exchange relation governing the number of intersections between diagonals of a polygon and a lamination (which generalizes to arbitrary surfaces) can also be generalized in a different way, to the setting of higher dimensional cyclic polytopes.

Nous donnons une nouvelle description de la combinatoire des triangulations des polytopes cycliques, et de leurs mouvements bistellaires. Nous démontrons que la relation d’échange qui gouverne le nombre d'intersections entre les diagonaux d'une polygone et une lamination (qui peut être généralisée à une surface arbitraire) peut également être généralisée au cadre des polytopes cycliques.
Extremal Statistics on Non-Crossing Configurations
Authors: Mier Anna , Noy Marc
Published: August 2021

We obtain several properties of extremal statistics in non-crossing configurations with n vertices. We prove that the maximum degree and the largest component are of logarithmic order, and the diameter is of order $\sqrt{n}$. The proofs are based on singularity analysis, an application of the first and second moment method and on the analysis of iterated functions.

On obtient des propriétés de paramètres extrémales dans les configurations sans croisement avec n sommets. On démontre que le degré maximal et la composante plus large sont d'ordre logarithmique, et le diamètre est d'ordre $\sqrt{n}$. Les preuves utilisent l'analyse de singularités, une application de la méthode du premier et second moment, et l'analyse de fonctions itérées.
An algorithm which generates linear extensions for a non-simply-laced d-complete poset with uniform probability
Authors: Nakada Kento
Published: August 2021

\textbfAbstract. The purpose of this paper is to present an algorithm which generates linear extensions for a non-simply-laced d-complete poset with uniform probability. ≠wline

Le but de ce papier est prèsenter un algorithme qui produit des extensions linèaires pour une non-simply-laced d-complete poset avec probabilitè constante.
Dyck tilings, linear extensions, descents, and inversions
Authors: Kim Jang Soo , Mészáros Karola , Panova Greta , Wilson David B.
Published: August 2021

Dyck tilings were introduced by Kenyon and Wilson in their study of double-dimer pairings. They are certain kinds of tilings of skew Young diagrams with ribbon tiles shaped like Dyck paths. We give two bijections between "cover-inclusive'' Dyck tilings and linear extensions of tree posets. The first bijection maps the statistic (area + tiles)/2 to inversions of the linear extension, and the second bijection maps the "discrepancy'' between the upper and lower boundary of the tiling to descents of the linear extension.

Les pavages de Dyck ont été introduits par Kenyon et Wilson dans leur étude du modèle des "double-dimères''. Ce sont des pavages des diagrammes de Young gauches avec des tuiles en forme de rubans qui ressemblent à des chemins de Dyck. Nous donnons deux bijections entre les pavages de Dyck ``couvre-inclusive'' et les extensions linéaires de posets dont le diagramme de Hasse est un arbre. La première bijection transforme la statistique (aire + tuiles) / 2 en inversions de l'extension linéaire, et la deuxième bijection transforme la "discordance'' entre la limite supérieure et inférieure du pavage en descentes de l'extension linéaire.
Combinatorial specification of permutation classes
Authors: Bassino Frédérique , Bouvel Mathilde , Pierrot Adeline , Pivoteau Carine , Rossin Dominique
Published: August 2021

This article presents a methodology that automatically derives a combinatorial specification for the permutation class $\mathcal{C} = Av(B)$, given its basis $B$ of excluded patterns and the set of simple permutations in $\mathcal{C}$, when these sets are both finite. This is achieved considering both pattern avoidance and pattern containment constraints in permutations.The obtained specification yields a system of equations satisfied by the generating function of $\mathcal{C}$, this system being always positive and algebraic. It also yields a uniform random sampler of permutations in $\mathcal{C}$. The method presented is fully algorithmic.

Cet article présente une méthodologie qui calcule automatiquement une spécification combinatoire pour la classe de permutations $\mathcal{C} = Av(B)$, étant donnés une base $B$ de motifs interdits et l’ensemble des permutations simples de $\mathcal{C}$, lorsque ces deux ensembles sont finis. Ce résultat est obtenu en considérant à la fois des contraintes de motifs interdits et de motifs obligatoires dans les permutations. La spécification obtenue donne un système d’équations satisfait par la série génératrice de la classe $\mathcal{C}$, système qui est toujours positif et algébrique. Elle fournit aussi un générateur aléatoire uniforme de permutations dans $\mathcal{C}$. La méthode présentée est complètement algorithmique.
Maximal Newton polygons via the quantum Bruhat graph
Authors: Beazley Elizabeth T.
Published: August 2021

This paper discusses a surprising relationship between the quantum cohomology of the variety of complete flags and the partially ordered set of Newton polygons associated to an element in the affine Weyl group. One primary key to establishing this connection is the fact that paths in the quantum Bruhat graph, which is a weighted directed graph with vertices indexed by elements in the finite Weyl group, encode saturated chains in the strong Bruhat order on the affine Weyl group. This correspondence is also fundamental in the work of Lam and Shimozono establishing Peterson's isomorphism between the quantum cohomology of the finite flag variety and the homology of the affine Grassmannian. In addition, using some geometry associated to the poset of Newton polygons, one obtains independent proofs for several combinatorial statements about paths in the quantum Bruhat graph and its symmetries, which were originally proved by Postnikov using the tilted Bruhat order. An important geometric application of this work is an inequality which provides a necessary condition for non-emptiness of certain affine Deligne-Lusztig varieties in the affine flag variety.

Cet article étudie une relation surprenante entre la cohomologie quantique de la variété de drapeaux complets et l'ensemble partiellement ordonné de polygones de Newton associé à un élément du groupe de Weyl affine. L’élément clé pour établir cette connexion est le fait que les chemins dans le graphe de Bruhat quantique, qui est un graphe orienté pondéré dont les sommets sont indexés par des éléments du groupe de Weyl fini, encodent des chaînes saturées dans l'ordre de Bruhat fort sur le groupe de Weyl affine. Cette correspondance est aussi fondamentale dans les travaux de Lam et Shimonozo qui établissent l'isomorphisme de Peterson entre la cohomologie quantique de la variété de drapeaux finie et l'homologie de la Grassmannienne affine. De plus, en utilisant la géométrie associée à l'ensemble partiellement ordonné des polygones de Newton, on obtient des preuves indépendantes pour plusieurs assertions combinatoires sur les chemins dans le graphe de Bruhat quantiques et les symétries de ce graphe, qui ont été originellement démontrées par Postnikov en utilisant l'ordre de Bruhat incliné. Une application géométrique importante de ce travail est une inégalité qui donne une condition nécessaire pour que certaines variétés de Deligne-Lusztig affines dans la variété de drapeaux affine soient non-vides.
$q$-Floor Diagrams computing Refined Severi Degrees for Plane Curves
Authors: Block Florian
Published: August 2021

The Severi degree is the degree of the Severi variety parametrizing plane curves of degree $d$ with $\delta$ nodes. Recently, Göttsche and Shende gave two refinements of Severi degrees, polynomials in a variable $q$, which are conjecturally equal, for large $d$. At $q=1$, one of the refinements, the relative Severi degree, specializes to the (non-relative) Severi degree. We give a combinatorial description of the refined Severi degrees, in terms of a $q$-analog count of Brugallé and Mikhalkin's floor diagrams. Our description implies that, for fixed $\delta$, the refined Severi degrees are polynomials in $d$ and $q$, for large $d$. As a consequence, we show that, for $\delta \leq 4$ and all $d$, both refinements of Göttsche and Shende agree and equal our $q$-count of floor diagrams.

Le degré de Severi est le degré de la variété de Severi paramétrisant les courbes planes de degré $d$ à $\delta$ nœuds. Récemment, Göttsche et Shende ont donné deux raffinements des degrés de Severi, polynomiaux en la variable $q$, qui sont conjecturalement égaux pour $d$ assez grand. Pour $q=1$, un des ces raffinements, le degré de Severi relatif, se spécialise en le degré de Severi (non relatif). Nous donnons une description combinatoire des degrés de Severi raffinés, en fonction d'un comptage $q$-analogue des "floor diagrams'' de Brugallé et Mikhalkin. Notre description implique que, pour $\delta$ fixé, les degrés de Severi raffinés sont polynomiaux en $d$ et $q$, pour $d$ grand. On montre que, par conséquent, pour $\delta \leq 4$ et pour tout $d$, les deux raffinements de Göttsche et Shende coïncident et sont égaux à notre $q$-analogue de "floor diagrams''.
Extending from bijections between marked occurrences of patterns to all occurrences of patterns
Authors: Remmel Jeffrey , Tiefenbruck Mark
Published: August 2021

We consider two recent open problems stating that certain statistics on various sets of combinatorial objects are equidistributed. The first, posed by Anders Claesson and Svante Linusson, relates nestings in matchings on $\{1,2,\ldots,2n\}$ to occurrences of a certain pattern in permutations in $S_n$. The second, posed by Miles Jones and Jeffrey Remmel, relates occurrences of a large class of consecutive permutation patterns to occurrences of the same pattern in the cycles of permutations. We develop a general method that solves both of these problems and many more. We further employ the Garsia-Milne involution principle to obtain purely bijective proofs of these results.

Nous considérons deux derniers problèmes ouverts indiquant que certaines statistiques sur les divers ensembles d'objets combinatoires sont équiréparties. La première, posée par Anders Claesson et Svante Linusson, concerne les imbrications dans des filtrages sur $\{1,2,\ldots,2n\}$ pour les occurrences d'un certain modèle de permutations dans $S_n$. La seconde, posée par Miles Jones et Jeffrey Remmel, concerne les occurrences d'une large classe de schémas de permutation consécutive aux évènements du même modèle dans les cycles de permutations. Nous développons une méthode générale qui résout ces deux problèmes et beaucoup plus. Nous avons également utiliser le principe d'involution Garsia-Milne pour obtenir des preuves purement bijectives de ces résultats.
Improved Expansion of Random Cayley Graphs
Authors: Loh Po-Shen , Schulman Leonard J.
Published: August 2021

In Random Cayley Graphs and Expanders, N. Alon and Y. Roichman proved that for every ε > 0 there is a finite c(ε ) such that for any sufficiently large group G, the expected value of the second largest (in absolute value) eigenvalue of the normalized adjacency matrix of the Cayley graph with respect to c(ε ) log |G| random elements is less than ε . We reduce the number of elements to c(ε )log D(G) (for the same c), where D(G) is the sum of the dimensions of the irreducible representations of G. In sufficiently non-abelian families of groups (as measured by these dimensions), log D(G) is asymptotically (1/2)log|G|. As is well known, a small eigenvalue implies large graph expansion (and conversely); see Tanner84 and AlonMilman84-2,AlonMilman84-1. For any specified eigenvalue or expansion, therefore, random Cayley graphs (of sufficiently non-abelian groups) require only half as many edges as was previously known.
On Linear Layouts of Graphs
Authors: Dujmović Vida , Wood David R.
Published: August 2021

In a total order of the vertices of a graph, two edges with no endpoint in common can be \emphcrossing, \emphnested, or \emphdisjoint. A \emphk-stack (respectively, \emphk-queue, \emphk-arch) \emphlayout of a graph consists of a total order of the vertices, and a partition of the edges into k sets of pairwise non-crossing (non-nested, non-disjoint) edges. Motivated by numerous applications, stack layouts (also called \emphbook embeddings) and queue layouts are widely studied in the literature, while this is the first paper to investigate arch layouts.\par Our main result is a characterisation of k-arch graphs as the \emphalmost (k+1)-colourable graphs; that is, the graphs G with a set S of at most k vertices, such that G S is (k+1)-colourable.\par In addition, we survey the following fundamental questions regarding each type of layout, and in the case of queue layouts, provide simple proofs of a number of existing results. How does one partition the edges given a fixed ordering of the vertices? What is the maximum number of edges in each type of layout? What is the maximum chromatic number of a graph admitting each type of layout? What is the computational complexity of recognising the graphs that admit each type of layout?\par A comprehensive bibliography of all known references on these topics is included. \par
Numerical Studies of the Asymptotic Height Distribution in Binary Search Trees
Authors: Knessl Charles
Published: August 2021

We study numerically a non-linear integral equation that arises in the study of binary search trees. If the tree is constructed from n elements, this integral equation describes the asymptotic (as n→∞) distribution of the height of the tree. This supplements some asymptotic results we recently obtained for the tails of the distribution. The asymptotic height distribution is shown to be unimodal with highly asymmetric tails.
A Context free language associated with interval maps
Authors: Archana M , Kannan V
Published: August 2021

For every interval map with finitely many periodic points of periods 1 and 2, we associate a word by taking the periods of these points from left to right. It is natural to ask which words arise in this manner. In this paper we give two different characterizations of the language obtained in this way.
Statistical properties of general Markov dynamical sources: applications to information theory
Authors: Chazal Frédéric , Maume-Deschamps Véronique
Published: August 2021

In \textitDynamical sources in information theory: fundamental intervals and word prefixes, B. Vallée studies statistical properties of words generated by dynamical sources. This is done using generalized Ruelle operators. The aim of this article is to generalize sources for which the results hold. First, we avoid the use of Grotendieck theory and Fredholm determinants, this allows dynamical sources that cannot be extended to a complex disk or that are not analytic. Second, we consider Markov sources: the language generated by the source over an alphabet \textbfM is not necessarily \textbfM^*.
Towards automated proofs of observational properties
Authors: Berregeb Narjes , Robbana Riadh , Tiwari Ashish
Published: August 2021

Observational theories are a generalization of first-order theories where two objects are observationally equal if they cannot be distinguished by experiments with observable results. Such experiments, called contexts, are usually infinite. Therfore, we consider a special finite set of contexts, called cover-contexts, ''\emphcovering'' all the observable contexts. Then, we show that to prove that two objects are observationally equal, it is sufficient to prove that they are equal (in the classical sense) under these cover-contexts. We give methods based on rewriting techniques, for constructing such cover-contexts for interesting classes of observational specifications.
Osculating Random Walks on Cylinders
Authors: Mitra Saibal , Nienhuis Bernard
Published: August 2021

We consider random paths on a square lattice which take a left or a right turn at every vertex. The possible turns are taken with equal probability, except at a vertex which has been visited before. In such case the vertex is left via the unused edge. When the initial edge is reached the path is considered completed. We also consider families of such paths which together cover every edge of the lattice once and visit every vertex twice. Because these paths may touch but not intersect each other and themselves, we call them osculating walks. The ensemble of such families is also known as the dense $O(n=1)$ model. We consider in particular such paths in a cylindrical geometry, with the cylindrical axis parallel with one of the lattice directions. We formulate a conjecture for the probability that a face of the lattice is surrounded by m distinct osculating paths. For even system sizes we give a conjecture for the probability that a path winds round the cylinder. For odd system sizes we conjecture the probability that a point is visited by a path spanning the infinite length of the cylinder. Finally we conjecture an expression for the asymptotics of a binomial determinant
Generating functions for the area below some lattice paths
Authors: Merlini Donatella
Published: August 2021

We study some lattice paths related to the concept ofgenerating trees. When the matrix associated to this kind of trees is a Riordan array $D=(d(t),h(t))$, we are able to find the generating function for the total area below these paths expressed in terms of the functions $d(t)$ and $h(t)$.
Percolation on a non-homogeneous Poisson blob process
Authors: Machado Fabio P.
Published: August 2021

We present the main results of a study for the existence of vacant and occupied unbounded connected components in a non-homogeneous Poisson blob process. The method used in the proofs is a multi-scale percolation comparison.
Approximation and Analytical Studies of Inter-clustering Performances of Space-Filling Curves
Authors: Dai Ho-Kwok , Su Hung-Chi
Published: August 2021

A discrete space-filling curve provides a linear traversal/indexing of a multi-dimensional grid space.This paper presents an application of random walk to the study of inter-clustering of space-filling curves and an analytical study on the inter-clustering performances of 2-dimensional Hilbert and z-order curve families.Two underlying measures are employed: the mean inter-cluster distance over all inter-cluster gaps and the mean total inter-cluster distance over all subgrids.We show how approximating the mean inter-cluster distance statistics of continuous multi-dimensional space-filling curves fits into the formalism of random walk, and derive the exact formulas for the two statistics for both curve families.The excellent agreement in the approximate and true mean inter-cluster distance statistics suggests that the random walk may furnish an effective model to develop approximations to clustering and locality statistics for space-filling curves.Based upon the analytical results, the asymptotic comparisons indicate that z-order curve family performs better than Hilbert curve family with respect to both statistics.
Random Infinite Permutations and the Cyclic Time Random Walk
Authors: Angel Omer
Published: August 2021

The random stirring process is a natural random walk on the set of permutations of the vertex set of a graph. The cyclic time random walk is a self interacting random walk on a graph. It is influenced by its past, in that it is constrained to repeat its past choices if it returns to a previously visited edge after a multiple of some period of time. The two models are fundamentally equivalent to each other as well as to a certain coalescence and fragmentation process.
Some remarks concerning harmonic functions on homogeneous graphs
Authors: Karlsson Anders
Published: August 2021

We obtain a new result concerning harmonic functions on infinite Cayley graphs $X$: either every nonconstant harmonic function has infinite radial variation in a certain uniform sense, or there is a nontrivial boundary with hyperbolic properties at infinity of $X$. In the latter case, relying on a theorem of Woess, it follows that the Dirichlet problem is solvable with respect to this boundary. Certain relations to group cohomology are also discussed.
A new two-variable generalization of the chromatic polynomial
Authors: Dohmen Klaus , Poenitz André , Tittmann Peter
Published: August 2021

We present a two-variable polynomial, which simultaneously generalizes the chromatic polynomial, the independence polynomial, and the matching polynomial of a graph. This new polynomial satisfies both an edge decomposition formula and a vertex decomposition formula. We establish two general expressions for this new polynomial: one in terms of the broken circuit complex and one in terms of the lattice of forbidden colorings. We show that the new polynomial may be considered as a specialization of Stanley's chromatic symmetric function. We finally give explicit expressions for the generalized chromatic polynomial of complete graphs, complete bipartite graphs, paths, and cycles, and show that it can be computed in polynomial time for trees and graphs of restricted pathwidth.
The number of distinct values of some multiplicity in sequences of geometrically distributed random variables
Authors: Louchard Guy , Prodinger Helmut , Ward Mark Daniel
Published: August 2021

We consider a sequence of $n$ geometric random variables and interpret the outcome as an urn model. For a given parameter $m$, we treat several parameters like what is the largest urn containing at least (or exactly) $m$ balls, or how many urns contain at least $m$ balls, etc. Many of these questions have their origin in some computer science problems. Identifying the underlying distributions as (variations of) the extreme value distribution, we are able to derive asymptotic equivalents for all (centered or uncentered) moments in a fairly automatic way.
Pattern distribution in various types of random trees
Authors: Kok Gerard
Published: August 2021

Let $\mathcal{T}_n$ denote the set of unrooted unlabeled trees of size $n$ and let $\mathcal{M}$ be a particular (finite) tree. Assuming that every tree of $\mathcal{T}_n$ is equally likely, it is shown that the number of occurrences $X_n$ of $\mathcal{M}$ as an induced sub-tree satisfies $\mathbf{E} X_n \sim \mu n$ and $\mathbf{V}ar X_n \sim \sigma^2 n$ for some (computable) constants $\mu > 0$ and $\sigma \geq 0$. Furthermore, if $\sigma > 0$ then $(X_n - \mathbf{E} X_n) / \sqrt{\mathbf{V}ar X_n}$ converges to a limiting distribution with density $(A+Bt^2)e^{-Ct^2}$ for some constants $A,B,C$. However, in all cases in which we were able to calculate these constants, we obtained $B=0$ and thus a normal distribution. Further, if we consider planted or rooted trees instead of $T_n$ then the limiting distribution is always normal. Similar results can be proved for planar, labeled and simply generated trees.
Convex hull for intersections of random lines
Authors: Berend Daniel , Braverman Vladimir
Published: August 2021

The problem of finding the convex hull of the intersection points of random lines was studied in Devroye and Toussaint, 1993 and Langerman, Golin and Steiger, 2002, and algorithms with expected linear time were found. We improve the previous results of the model in Devroye and Toussaint, 1993 by giving a universal algorithm for a wider range of distributions.
Analysis of the average depth in a suffix tree under a Markov model
Authors: Fayolle Julien , Ward Mark Daniel
Published: August 2021

In this report, we prove that under a Markovian model of order one, the average depth of suffix trees of index n is asymptotically similar to the average depth of tries (a.k.a. digital trees) built on n independent strings. This leads to an asymptotic behavior of $(\log{n})/h + C$ for the average of the depth of the suffix tree, where $h$ is the entropy of the Markov model and $C$ is constant. Our proof compares the generating functions for the average depth in tries and in suffix trees; the difference between these generating functions is shown to be asymptotically small. We conclude by using the asymptotic behavior of the average depth in a trie under the Markov model found by Jacquet and Szpankowski ([JaSz91]).
Performance of binary exponential backoff CSMA in WiFi and optimal routing in mobile ad hoc networks
Authors: Jacquet Philippe , Naimi Amina Meraihi , Rodolakis Georgios
Published: August 2021

In this paper we show that the CSMA IEEE 802.11 protocol (Wifi) provides packet access delays asymptotics in power law. This very feature allows us to specify optimal routing via polynomial algorithm while the general case is NP-hard.
The master ring problem
Authors: Shachnai Hadas , Zhang Lisa
Published: August 2021

We consider the $\textit{master ring problem (MRP)}$ which often arises in optical network design. Given a network which consists of a collection of interconnected rings $R_1, \ldots, R_K$, with $n_1, \ldots, n_K$ distinct nodes, respectively, we need to find an ordering of the nodes in the network that respects the ordering of every individual ring, if one exists. Our main result is an exact algorithm for MRP whose running time approaches $Q \cdot \prod_{k=1}^K (n_k/ \sqrt{2})$ for some polynomial $Q$, as the $n_k$ values become large. For the $\textit{ring clearance problem}$, a special case of practical interest, our algorithm achieves this running time for rings of $\textit{any}$ size $n_k \geq 2$. This yields the first nontrivial improvement, by factor of $(2 \sqrt{2})^K \approx (2.82)^K$, over the running time of the naive algorithm, which exhaustively enumerates all $\prod_{k=1}^K (2n_k)$ possible solutions.
Analysis of the multiplicity matching parameter in suffix trees
Authors: Ward Mark Daniel , Szpankowski Wojciech
Published: August 2021

In a suffix tree, the multiplicity matching parameter (MMP) $M_n$ is the number of leaves in the subtree rooted at the branching point of the $(n+1)$st insertion. Equivalently, the MMP is the number of pointers into the database in the Lempel-Ziv '77 data compression algorithm. We prove that the MMP asymptotically follows the logarithmic series distribution plus some fluctuations. In the proof we compare the distribution of the MMP in suffix trees to its distribution in tries built over independent strings. Our results are derived by both probabilistic and analytic techniques of the analysis of algorithms. In particular, we utilize combinatorics on words, bivariate generating functions, pattern matching, recurrence relations, analytical poissonization and depoissonization, the Mellin transform, and complex analysis.
Matroid matching with Dilworth truncation
Authors: Makai Márton
Published: August 2021

Let $H=(V,E)$ be a hypergraph and let $k≥ 1$ and$ l≥ 0$ be fixed integers. Let $\mathcal{M}$ be the matroid with ground-set $E s.t. a$ set $F⊆E$ is independent if and only if each $X⊆V$ with $k|X|-l≥ 0$ spans at most $k|X|-l$ hyperedges of $F$. We prove that if $H$ is dense enough, then $\mathcal{M}$ satisfies the double circuit property, thus the min-max formula of Dress and Lovász on the maximum matroid matching holds for $\mathcal{M}$ . Our result implies the Berge-Tutte formula on the maximum matching of graphs $(k=1, l=0)$, generalizes Lovász' graphic matroid (cycle matroid) matching formula to hypergraphs $(k=l=1)$ and gives a min-max formula for the maximum matroid matching in the 2-dimensional rigidity matroid $(k=2, l=3)$.
The Windy Postman Problem on Series-Parallel Graphs
Authors: Martínez Francisco Javier Zaragoza
Published: August 2021

The windy postman problem is the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of traversal of an edge depends on the direction. Given an undirected graph $G$, we consider the polyhedron $O(G)$ induced by the linear programming relaxation of a well-known integer programming formulation of the problem. We say that $G$ is windy postman perfect if $O(G)$ is integral. There exists a polynomial-time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. Eulerian graphs and trees are windy postman perfect. By considering a family of polyhedra related to $O(G)$, we prove that series-parallel graphs are windy postman perfect, therefore solving a conjecture of [Win1987a].
Connected τ -critical hypergraphs of minimal size
Authors: Stehlík Matěj
Published: August 2021

A hypergraph $\mathscr{H}$ is $τ$ -critical if $τ (\mathscr{H}-E) < τ (\mathscr{H})$ for every edge $E ∈\mathscr{H}$, where $τ (\mathscr{H})$ denotes the transversal number of $\mathscr{H}$. It can be shown that a connected $τ$ -critical hypergraph $\mathscr{H}$ has at least $2τ (\mathscr{H})-1$ edges; this generalises a classical theorem of Gallai on $χ$ -vertex-critical graphs with connected complements. In this paper we study connected $τ$ -critical hypergraphs $\mathscr{H}$ with exactly $2τ (\mathscr{H)}-1$ edges. We prove that such hypergraphs have at least $2τ (\mathscr{H})-1$ vertices, and characterise those with $2τ (\mathscr{H})-1$ vertices using a directed odd ear decomposition of an associated digraph. Using Seymour's characterisation of $χ$ -critical 3-chromatic square hypergraphs, we also show that a connected square hypergraph $\mathscr{H}$ with fewer than $2τ (\mathscr{H})$ edges is $τ$ -critical if and only if it is $χ$ -critical 3-chromatic. Finally, we deduce some new results on $χ$ -vertex-critical graphs with connected complements.
Packing non-returning A-paths algorithmically
Authors: Pap Gyula
Published: August 2021

In this paper we present an algorithmic approach to packing A-paths. It is regarded as a generalization of Edmonds' matching algorithm, however there is the significant difference that here we do not build up any kind of alternating tree. Instead we use the so-called 3-way lemma, which either provides augmentation, or a dual, or a subgraph which can be used for contraction. The method works in the general setting of packing non-returning A-paths. It also implies an ear-decomposition of criticals, as a generalization of the odd ear-decomposition of factor-critical graph.
A bijection between planar constellations and some colored Lagrangian trees
Authors: Chauve Cedric
Published: August 2021

Constellations are colored planar maps that generalize different families of maps (planar maps, bipartite planar maps, bi-Eulerian planar maps, planar cacti, ...) and are strongly related to factorizations of permutations. They were recently studied by Bousquet-Mélou and Schaeffer who describe a correspondence between these maps and a family of trees, called Eulerian trees. In this paper, we derive from their result a relationship between planar constellations and another family of trees, called stellar trees. This correspondence generalizes a well known result for planar cacti, and shows that planar constellations are colored Lagrangian objects (that is objects that can be enumerated by the Good-Lagrange formula). We then deduce from this result a new formula for the number of planar constellations having a given face distribution, different from the formula one can derive from the results of Bousquet-Mélou and Schaeffer, along with systems of functional equations for the generating functions of bipartite and bi-Eulerian planar maps enumerated according to the partition of faces and vertices.
Multigraph decomposition into multigraphs with two underlying edges
Authors: Priesler Miri , Tarsi Michael
Published: August 2021

Due to some intractability considerations, reasonable formulation of necessary and sufficient conditions for decomposability of a general multigraph G into a fixed connected multigraph H, is probably not feasible if the underlying simple graph of H has three or more edges. We study the case where H consists of two underlying edges. We present necessary and sufficient conditions for H-decomposability of G, which hold when certain size parameters of G lies within some bounds which depends on the multiplicities of the two edges of H. We also show this result to be "tight" in the sense that even a slight deviation of these size parameters from the given bounds results intractability of the corresponding decision problem.
Degree-correlation of Scale-free graphs
Authors: Nikoloski Zoran , Deo Narsingh , Kucera Ludek
Published: August 2021

Barabási and Albert [1] suggested modeling scale-free networks by the following random graph process: one node is added at a time and is connected to an earlier node chosen with probability proportional to its degree. A recent empirical study of Newman [5] demonstrates existence of degree-correlation between degrees of adjacent nodes in real-world networks. Here we define the \textitdegree correlation―-correlation of the degrees in a pair of adjacent nodes―-for a random graph process. We determine asymptotically the joint probability distribution for node-degrees, $d$ and $d'$, of adjacent nodes for every $0≤d≤ d'≤n^1 / 5$, and use this result to show that the model of Barabási and Albert does not generate degree-correlation. Our theorem confirms the result in [KR01], obtained by using the mean-field heuristic approach.
Excluded subposets in the Boolean lattice
Authors: Katona Gyula O.H.
Published: August 2021

We are looking for the maximum number of subsets of an n-element set not containing 4 distinct subsets satisfying $A ⊂B, C ⊂B, C ⊂D$. It is proved that this number is at least the number of the $\lfloor \frac{n }{ 2}\rfloor$ -element sets times $1+\frac{2}{ n}$, on the other hand an upper bound is given with 4 replaced by the value 2.
Largest cliques in connected supermagic graphs
Authors: Lladó Anna
Published: August 2021

A graph $G=(V,E)$ is said to be $\textit{magic}$ if there exists an integer labeling $f: V \cup E \to [1, |V \cup E|]$ such that $f(x)+f(y)+f(xy)$ is constant for all edges $xy \in E$. Enomoto, Masuda and Nakamigawa proved that there are magic graphs of order at most $3n^2+o(n^2)$ which contain a complete graph of order $n$. Bounds on Sidon sets show that the order of such a graph is at least $n^2+o(n^2)$. We close the gap between those two bounds by showing that, for any given graph $H$ of order $n$, there are connected magic graphs of order $n^2+o(n^2)$ containing $H$ as an induced subgraph. Moreover it can be required that the graph admits a supermagic labelling $f$, which satisfies the additional condition $f(V)=[1,|V|]$.
Labeling planar graphs with a condition at distance two
Authors: Bella Peter , Král Daniel , Mohar Bojan , Quittnerová Katarina
Published: August 2021

An $L(2,1)$-labeling of a graph is a mapping $c:V(G) \to \{0,\ldots,K\}$ such that the labels assigned to neighboring vertices differ by at least $2$ and the labels of vertices at distance two are different. Griggs and Yeh [SIAM J. Discrete Math. 5 (1992), 586―595] conjectured that every graph $G$ with maximum degree $\Delta$ has an $L(2,1)$-labeling with $K \leq \Delta^2$. We verify the conjecture for planar graphs with maximum degree $\Delta \neq 3$.
Fast separation in a graph with an excluded minor
Authors: Reed Bruce , Wood David R.
Published: August 2021

Let $G$ be an $n$-vertex $m$-edge graph with weighted vertices. A pair of vertex sets $A,B \subseteq V(G)$ is a $\frac{2}{3} - \textit{separation}$ of $\textit{order}$ $|A \cap B|$ if $A \cup B = V(G)$, there is no edge between $A \backslash B$ and $B \backslash A$, and both $A \backslash B$ and $B \backslash A$ have weight at most $\frac{2}{3}$ the total weight of $G$. Let $\ell \in \mathbb{Z}^+$ be fixed. Alon, Seymour and Thomas [$\textit{J. Amer. Math. Soc.}$ 1990] presented an algorithm that in $\mathcal{O}(n^{1/2}m)$ time, either outputs a $K_\ell$-minor of $G$, or a separation of $G$ of order $\mathcal{O}(n^{1/2})$. Whether there is a $\mathcal{O}(n+m)$ time algorithm for this theorem was left as open problem. In this paper, we obtain a $\mathcal{O}(n+m)$ time algorithm at the expense of $\mathcal{O}(n^{2/3})$ separator. Moreover, our algorithm exhibits a tradeoff between running time and the order of the separator. In particular, for any given $\epsilon \in [0,\frac{1}{2}]$, our algorithm either outputs a $K_\ell$-minor of $G$, or a separation of $G$ with order $\mathcal{O}(n^{(2-\epsilon )/3})$ in $\mathcal{O}(n^{1+\epsilon} +m)$ time.
Minor-monotone crossing number
Authors: Bokal Drago , Fijavž Gašper , Mohar Bojan
Published: August 2021

The minor crossing number of a graph $G$, $rmmcr(G)$, is defined as the minimum crossing number of all graphs that contain $G$ as a minor. We present some basic properties of this new minor-monotone graph invariant. We give estimates on mmcr for some important graph families using the topological structure of graphs satisfying \$mcr(G) ≤k$.
Linear choosability of graphs
Authors: Esperet Louis , Montassier Mickael , Raspaud André
Published: August 2021

A proper vertex coloring of a non oriented graph $G=(V,E)$ is linear if the graph induced by the vertices of two color classes is a forest of paths. A graph $G$ is $L$-list colorable if for a given list assignment $L=\{L(v): v∈V\}$, there exists a proper coloring $c$ of $G$ such that $c(v)∈L(v)$ for all $v∈V$. If $G$ is $L$-list colorable for every list assignment with $|L(v)|≥k$ for all $v∈V$, then $G$ is said $k$-choosable. A graph is said to be lineary $k$-choosable if the coloring obtained is linear. In this paper, we investigate the linear choosability of graphs for some families of graphs: graphs with small maximum degree, with given maximum average degree, planar graphs... Moreover, we prove that determining whether a bipartite subcubic planar graph is lineary 3-colorable is an NP-complete problem.
Relaxed Two-Coloring of Cubic Graphs
Authors: Berke Robert , Szabó Tibor
Published: August 2021

We show that any graph of maximum degree at most $3$ has a two-coloring, such that one color-class is an independent set while the other color induces monochromatic components of order at most $189$. On the other hand for any constant $C$ we exhibit a $4$-regular graph, such that the deletion of any independent set leaves at least one component of order greater than $C$. Similar results are obtained for coloring graphs of given maximum degree with $k+ \ell$ colors such that $k$ parts form an independent set and $\ell$ parts span components of order bounded by a constant. A lot of interesting questions remain open.
Enumeration of walks reaching a line
Authors: Nadeau Philippe
Published: August 2021

We enumerate walks in the plane $\mathbb{R}^2$, with steps East and North, that stop as soon as they reach a given line; these walks are counted according to the distance of the line to the origin, and we study the asymptotic behavior when the line has a fixed slope and moves away from the origin. When the line has a rational slope, we study a more general class of walks, and give exact as well as asymptotic enumerative results; for this, we define a nice bijection from our walks to words of a rational language. For a general slope, asymptotic results are obtained; in this case, the method employed leads us to find asymptotic results for a wider class of walks in $\mathbb{R}^m$.
Acyclic Coloring of Graphs of Maximum Degree $\Delta$
Authors: Fertin Guillaume , Raspaud André
Published: August 2021

An acyclic coloring of a graph $G$ is a coloring of its vertices such that: (i) no two neighbors in $G$ are assigned the same color and (ii) no bicolored cycle can exist in $G$. The acyclic chromatic number of $G$ is the least number of colors necessary to acyclically color $G$, and is denoted by $a(G)$. We show that any graph of maximum degree $\Delta$ has acyclic chromatic number at most $\frac{\Delta (\Delta -1) }{ 2}$ for any $\Delta \geq 5$, and we give an $O(n \Delta^2)$ algorithm to acyclically color any graph of maximum degree $\Delta$ with the above mentioned number of colors. This result is roughly two times better than the best general upper bound known so far, yielding $a(G) \leq \Delta (\Delta -1) +2$. By a deeper study of the case $\Delta =5$, we also show that any graph of maximum degree $5$ can be acyclically colored with at most $9$ colors, and give a linear time algorithm to achieve this bound.
Every $3$-connected, essentially $11$-connected line graph is hamiltonian
Authors: Lai Hong-Jian , Shao Yehong , Zhou Ju , Wu Hehui
Published: August 2021

Thomassen conjectured that every $4$-connected line graph is hamiltonian. A vertex cut $X$ of $G$ is essential if $G-X$ has at least two nontrivial components. We prove that every $3$-connected, essentially $11$-connected line graph is hamiltonian. Using Ryjáček's line graph closure, it follows that every $3$-connected, essentially $11$-connected claw-free graph is hamiltonian.
Random Inscribing Polytopes
Authors: Richardson Ross M. , Vu Van H. , Wu Lei
Published: August 2021

For convex bodies $K$ with $\mathcal{C}^2$ boundary in $\mathbb{R}^d$, we provide results on the volume of random polytopes with vertices chosen along the boundary of $K$ which we call $\textit{random inscribing polytopes}$. In particular, we prove results concerning the variance and higher moments of the volume, as well as show that the random inscribing polytopes generated by the Poisson process satisfy central limit theorem.
Stacks, Queues and Tracks: Layouts of Graph Subdivisions
Authors: Dujmović Vida , Wood David R.
Published: August 2021

A \emphk-stack layout (respectively, \emphk-queuelayout) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the vertex ordering. A \emphk-track layout of a graph consists of a vertex k-colouring, and a total order of each vertex colour class, such that between each pair of colour classes no two edges cross. The \emphstack-number (respectively, \emphqueue-number, \emphtrack-number) of a graph G, denoted by sn(G) (qn(G), tn(G)), is the minimum k such that G has a k-stack (k-queue, k-track) layout.\par This paper studies stack, queue, and track layouts of graph subdivisions. It is known that every graph has a 3-stack subdivision. The best known upper bound on the number of division vertices per edge in a 3-stack subdivision of an n-vertex graph G is improved from O(log n) to O(log min\sn(G),qn(G)\). This result reduces the question of whether queue-number is bounded by stack-number to whether 3-stack graphs have bounded queue number.\par It is proved that every graph has a 2-queue subdivision, a 4-track subdivision, and a mixed 1-stack 1-queue subdivision. All these values are optimal for every non-planar graph. In addition, we characterise those graphs with k-stack, k-queue, and k-track subdivisions, for all values of k. The number of division vertices per edge in the case of 2-queue and 4-track subdivisions, namely O(log qn(G)), is optimal to within a constant factor, for every graph G. \par Applications to 3D polyline grid drawings are presented. For example, it is proved that every graph G has a 3D polyline grid drawing with the vertices on a rectangular prism, and with O(log qn(G)) bends per edge. Finally, we establish a tight relationship between queue layouts and so-called 2-track thickness of bipartite graphs. \par
Survival probability of a critical multi-type branching process in random environment
Authors: Dyakonova Elena
Published: August 2021

We study a multi-type branching process in i.i.d. random environment. Assuming that the associated random walk satisfies the Doney-Spitzer condition, we find the asymptotics of the survival probability at time $n$ as $n \to \infty$.
Analytic Combinatorics of Lattice Paths: Enumeration and Asymptotics for the Area
Authors: Banderier Cyril , Gittenberger Bernhard
Published: August 2021

This paper tackles the enumeration and asymptotics of the area below directed lattice paths (walks on $\mathbb{N}$ with a finite set of jumps). It is a nice surprise (obtained via the "kernel method'') that the generating functions of the moments of the area are algebraic functions, expressible as symmetric functions in terms of the roots of the kernel. For a large class of walks, we give full asymptotics for the average area of excursions ("discrete'' reflected Brownian bridge) and meanders ("discrete'' reflected Brownian motion). We show that drift is not playing any role in the first case. We also generalise previous works related to the number of points below a path and to the area between a path and a line of rational slope.