bluuebunny/crossref_metadata_2025 huggingface dataset:
Equivalences for pattern avoiding involutions and classification
Authors: Dukes Mark , Jelínek Vít , Mansour Toufik , Reifegerste Astrid
Published: August 2021

We complete the Wilf classification of signed patterns of length 5 for both signed permutations and signed involutions. New general equivalences of patterns are given which prove Jaggard's conjectures concerning involutions in the symmetric group avoiding certain patterns of length 5 and 6. In this way, we also complete the Wilf classification of $S_5$, $S_6$, and $S_7$ for both permutations and involutions.

Nous complétons la classification de Wilf des motifs signés de longueur 5 à la fois pour les permutations signées et les involutions signées. Nous donnons de nouvelles équivalences générales de motifs qui prouvent les conjectures de Jaggard concernant les involutions dans le groupe symétrique évitant certains motifs de longueur 5 et 6. De cette manière nous complétons également la classification de Wilf de $S_5$, $S_6$ et $S_7$ à la fois pour les permutations et les involutions.
On the computability of the topological entropy of subshifts
Authors: Simonsen Jakob Grue
Published: August 2021

We prove that the topological entropy of subshifts having decidable language is uncomputable in the following sense: For no error bound less than 1/4 does there exists a program that, given a decision procedure for the language of a subshift as input, will approximate the entropy of the subshift within the error bound. In addition, we prove that not only is the topological entropy of sofic shifts computable to arbitary precision (a well-known fact), but all standard comparisons of the topological entropy with rational numbers are decidable.
Tiling Z² with translations of one set
Authors: Rao Hui , Xue Yu-Mei
Published: August 2021

Let A be a finite subset of ℤ2. We say A tiles ℤ2 with the translation set C, if any integer z∈ℤ2 can be represented as z1+z2, z1∈ A, z2∈ C in an unique way. In this case we call A a ℤ2-tile and write A ⊕ C = ℤ2. A tile A is said to be a normal ℤ2-tile if there exists a periodic set C such that A ⊕ C = ℤ2. We characterize all normal ℤ2-tiles with prime cardinality.
Recognizing HH-free, HHD-free, and Welsh-Powell Opposition Graphs
Authors: Nikolopoulos Stavros D. , Palios Leonidas
Published: August 2021

In this paper, we consider the recognition problem on three classes of perfectly orderable graphs, namely, the HH-free, the HHD-free, and the Welsh-Powell opposition graphs (or WPO-graphs). In particular, we prove properties of the chordal completion of a graph and show that a modified version of the classic linear-time algorithm for testing for a perfect elimination ordering can be efficiently used to determine in O(n min \m α (n,n), m + n^2 log n\) time whether a given graph G on n vertices and m edges contains a house or a hole; this implies an O(n min \m α (n,n), m + n^2 log n\)-time and O(n+m)-space algorithm for recognizing HH-free graphs, and in turn leads to an HHD-free graph recognition algorithm exhibiting the same time and space complexity. We also show that determining whether the complement øverlineG of the graph G is HH-free can be efficiently resolved in O(n m) time using O(n^2) space, which leads to an O(n m)-time and O(n^2)-space algorithm for recognizing WPO-graphs. The previously best algorithms for recognizing HH-free, HHD-free, and WPO-graphs required O(n^3) time and O(n^2) space.
Waiting time distributions for pattern occurrence in a constrained sequence
Authors: Stefanov Valeri T. , Szpankowski Wojciech
Published: August 2021

Analysis of Algorithms

A binary sequence of zeros and ones is called a (d; k)-sequence if it does not contain runs of zeros of length either lessthan d or greater than k, where d and k are arbitrary, but fixed, non-negative integers and d < k. Such sequences find requires that (d; k)-sequences do not contain a specific pattern w. Therefore, distribution results concerning pattern occurrence in (d; k)-sequences are of interest. In this paper we study the distribution of the waiting time until the r-th occurrence of a pattern w in a random (d; k)-sequence generated by a Markov source. Numerical examples are also provided.
A combinatorial and probabilistic study of initial and end heights of descents in samples of geometrically distributed random variables and in permutations
Authors: Louchard Guy , Prodinger Helmut
Published: August 2021

Analysis of Algorithms

In words, generated by independent geometrically distributed random variables, we study the lth descent, which is, roughly speaking, the lth occurrence of a neighbouring pair ab with a>b. The value a is called the initial height, and b the end height. We study these two random variables (and some similar ones) by combinatorial and probabilistic tools. We find in all instances a generating function Ψ(v,u), where the coefficient of vjui refers to the jth descent (ascent), and i to the initial (end) height. From this, various conclusions can be drawn, in particular expected values. In the probabilistic part, a Markov chain model is used, which allows to get explicit expressions for the heights of the second descent. In principle, one could go further, but the complexity of the results forbids it. This is extended to permutations of a large number of elements. Methods from q-analysis are used to simplify the expressions. This is the reason that we confine ourselves to the geometric distribution only. For general discrete distributions, no such tools are available.
Elements in finite classical groups whose powers have large 1-Eigenspaces
Authors: Niemeyer Alice , Praeger Cheryl
Published: August 2021

Special issue in honor of Laci Babai's 60th birthday

We estimate the proportion of several classes of elements in finite classical groups which are readily recognised algorithmically, and for which some power has a large fixed point subspace and acts irreducibly on a complement of it. The estimates are used in complexity analyses of new recognition algorithms for finite classical groups in arbitrary characteristic.
Baire and automata
Authors: Simonnet Pierre , Cagnard Benoit
Published: August 2021

In his thesis Baire defined functions of Baire class 1. A function f is of Baire class 1 if it is the pointwise limit of a sequence of continuous functions. Baire proves the following theorem. A function f is not of class 1 if and only if there exists a closed nonempty set F such that the restriction of f to F has no point of continuity. We prove the automaton version of this theorem. An ω-rational function is not of class 1 if and only if there exists a closed nonempty set F recognized by a Büchi automaton such that the restriction of f to F has no point of continuity. This gives us the opportunity for a discussion on Hausdorff's analysis of Δ°2, ordinals, transfinite induction and some applications of computer science.
Addition and multiplication of beta-expansions in generalized Tribonacci base
Authors: Ambrož Petr , Masáková Zuzana , Pelantová Edita
Published: August 2021

We study properties of β-numeration systems, where β > 1 is the real root of the polynomial x3 - mx2 - x - 1, m ∈ ℕ, m ≥ 1. We consider arithmetic operations on the set of β-integers, i.e., on the set of numbers whose greedy expansion in base β has no fractional part. We show that the number of fractional digits arising under addition of β-integers is at most 5 for m ≥ 3 and 6 for m = 2, whereas under multiplication it is at most 6 for all m ≥ 2. We thus generalize the results known for Tribonacci numeration system, i.e., for m = 1. We summarize the combinatorial properties of infinite words naturally defined by β-integers. We point out the differences between the structure of β-integers in cases m = 1 and m ≥ 2.
Computation of L_⊕ for several cubic Pisot numbers
Authors: Bernat Julien
Published: August 2021

In this article, we are dealing with β-numeration, which is a generalization of numeration in a non-integer base. We consider the class of simple Parry numbers such that dβ(1) = 0.k1d-1 kd with d ∈ ℕ, d ≥ 2 and k1 ≥ kd ≥ 1. We prove that these elements define Rauzy fractals that are stable under a central symmetry. We use this result to compute, for several cases of cubic Pisot units, the maximal length among the lengths of the finite β-fractional parts of sums of two β-integers, denoted by L_⊕. In particular, we prove that L_⊕ = 5 in the Tribonacci case.
Tag-systems for the Hilbert curve
Authors: Séébold Patrice
Published: August 2021

Hilbert words correspond to finite approximations of the Hilbert space filling curve. The Hilbert infinite word H is obtained as the limit of these words. It gives a description of the Hilbert (infinite) curve. We give a uniform tag-system to generate automatically H and, by showing that it is almost cube-free, we prove that it cannot be obtained by simply iterating a morphism.
On the size of induced acyclic subgraphs in random digraphs
Authors: Spencer Joel , Subramanian C.R.
Published: August 2021

Graphs and Algorithms

Let D ∈ D(n, p) denote a simple random digraph obtained by choosing each of the (n 2) undirected edges independently with probability 2p and then orienting each chosen edge independently in one of the two directions with equal probability 1/2. Let mas(D) denote the maximum size of an induced acyclic subgraph in D. We obtain tight concentration results on the size of mas(D). Precisely, we show that $mas(D) \le \frac{2}{ln(1-p)^-1} (ln np + 3e)$ almost surely, provided p ≥ W/n for some fixed constant W. This combined with known and new lower bounds shows that (for p satisfying p = ω(1/n) and p ≤ 0.5) $mas(D) = \frac{2(ln np)}{ln(1-p)^-1} (1± o(1))$. This proves a conjecture stated by Subramanian in 2003 for those p such that p = ω(1/n). Our results are also valid for the random digraph obtained by choosing each of the n(n − 1) directed edges independently with probability p.
On the k-restricted structure ratio in planar and outerplanar graphs
Authors: Călinescu Gruia , Fernandes Cristina G.
Published: August 2021

Graphs and Algorithms

A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1 = 2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.
Simultaneous generation for zeta values by the Markov-WZ method
Authors: Pilehrood Khodabakhsh Hessami , Pilehrood Tatiana Hessami
Published: August 2021

Combinatorics

By application of the Markov-WZ method, we prove a more general form of a bivariate generating function identity containing, as particular cases, Koecher's and Almkvist-Granville's Apéry-like formulae for odd zeta values. As a consequence, we get a new identity producing Apéry-like series for all ζ(2n+4m+3),n,m ≥ 0, convergent at the geometric rate with ratio 2−10.
Extremal K_(s,t)-free bipartite graphs
Authors: Balbuena Camino , García-Vázquez P. , Marcote Xavier , Valenzuela J. C.
Published: August 2021

Graphs and Algorithms

In this paper new exact values of the Zarankiewicz function z(m,n;s,t) are obtained assuming certain requirements on the parameters. Moreover, all the corresponding extremal graphs are characterized. Finally, an extension of this problem to 3-partite graphs is studied.
Recurrence among trees with most numerous efficient dominating sets
Authors: Bród Dorota , Skupień Zdzisław
Published: August 2021

Graphs and Algorithms

A dominating set D of vertices in a graph G is called an efficient dominating set if the distance between any two vertices in D is at least three. A tree T of order n is called maximum if T has the largest number of efficient dominating sets among all n-vertex trees. A constructive characterization of all maximum trees is given. Their structure has recurring aspects with period 7. Moreover, the number of efficient dominating sets in maximum n-vertex trees is determined and is exponential. Also the number of maximum n-vertex trees is shown to be bounded below by an increasing exponential function in n.
VC-dimensions of random function classes
Authors: Ycart Bernard , Ratsaby Joel
Published: August 2021

Combinatorics

For any class of binary functions on [n]={1, ..., n} a classical result by Sauer states a sufficient condition for its VC-dimension to be at least d: its cardinality should be at least O(nd-1). A necessary condition is that its cardinality be at least 2d (which is O(1) with respect to n). How does the size of a 'typical' class of VC-dimension d compare to these two extreme thresholds ? To answer this, we consider classes generated randomly by two methods, repeated biased coin flips on the n-dimensional hypercube or uniform sampling over the space of all possible classes of cardinality k on [n]. As it turns out, the typical behavior of such classes is much more similar to the necessary condition; the cardinality k need only be larger than a threshold of 2d for its VC-dimension to be at least d with high probability. If its expected size is greater than a threshold of O(&log;n) (which is still significantly smaller than the sufficient size of O(nd-1)) then it shatters every set of size d with high probability. The behavior in the neighborhood of these thresholds is described by the asymptotic probability distribution of the VC-dimension and of the largest d such that all sets of size d are shattered.
Directed figure codes are decidable
Authors: Kolarz Michal , Moczurad Wlodzimierz
Published: August 2021

Automata, Logic and Semantics

Two-dimensional structures of various kinds can be viewed as generalizations of words. Codicity verification and the defect effect, important properties related to word codes, are studied also in this context. Unfortunately, both are lost in the case of two common structures, polyominoes and figures. We consider directed figures defined as labelled polyominoes with designated start and end points, equipped with catenation operation that uses a merging function to resolve possible conflicts. We prove that in this setting verification whether a given finite set of directed figures is a code is decidable and we give a constructive algorithm. We also clarify the status of the defect effect for directed figures.
A construction of small regular bipartite graphs of girth 8
Authors: Balbuena Camino
Published: August 2021

Let q be a prime a power and k an integer such that 3 ≤ k ≤ q. In this paper we present a method using Latin squares to construct adjacency matrices of k-regular bipartite graphs of girth 8 on 2(kq2 -- q) vertices. Some of these graphs have the smallest number of vertices among the known regular graphs with girth 8.
Self-complementing permutations of k-uniform hypergraphs
Authors: Szymański Artur , Wojda Adam Pawel
Published: August 2021

Graphs and Algorithms

A k-uniform hypergraph H = ( V; E) is said to be self-complementary whenever it is isomorphic with its complement (H) over bar = ( V; ((V)(k)) - E). Every permutation sigma of the set V such that sigma(e) is an edge of (H) over bar if and only if e is an element of E is called self-complementing. 2-self-comlementary hypergraphs are exactly self complementary graphs introduced independently by Ringel ( 1963) and Sachs ( 1962).
 For any positive integer n we denote by lambda(n) the unique integer such that n = 2(lambda(n)) c, where c is odd.
 In the paper we prove that a permutation sigma of [1, n] with orbits O-1,..., O-m O m is a self-complementing permutation of a k-uniform hypergraph of order n if and only if there is an integer l >= 0 such that k = a2(l) + s, a is odd, 0 <= s <= 2(l) and the following two conditions hold:
 (i)n = b2(l+1) + r,r is an element of {0,..., 2(l) - 1 + s}, and
 (ii) Sigma(i:lambda(vertical bar Oi vertical bar)<= l) vertical bar O-i vertical bar <= r.
 For k = 2 this result is the very well known characterization of self-complementing permutation of graphs given by Ringel and Sachs.
A characterization of infinite smooth Lyndon words
Authors: Paquin Geneviève
Published: August 2021

Combinatorics

In a recent paper, Brlek, Jamet and Paquin showed that some extremal infinite smooth words are also infinite Lyndon words. This result raises a natural question: are they the only ones? If no, what do the infinite smooth words that are also Lyndon words look like? In this paper, we give the answer, proving that the only infinite smooth Lyndon words are m(\a ...
Tight Bounds for Delay-Sensitive Aggregation
Authors: Pignolet Yvonne Anne , Schmid Stefan , Wattenhofer Roger
Published: August 2021

Distributed Computing and Networking

This article studies the fundamental trade-off between delay and communication cost in networks. We consider an online optimization problem where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about the changes of their states and to use as few transmissions as possible. We derive an upper bound on the competitive ratio of O(min (h, c)) where h is the tree's height, and c is the transmission cost per edge. Moreover, we prove that this upper bound is tight in the sense that any oblivious algorithm has a ratio of at least Omega(min (h, c)). For chain networks, we prove a tight competitive ratio of Theta(min (root h, c)). Furthermore, we introduce a model for value-sensitive aggregation, where the cost depends on the number of transmissions and the error at the root.
On a 1, 2 Conjecture
Authors: Przybylo Jakub , WoźniaK Mariusz
Published: August 2021

Graphs and Algorithms

Let us assign positive integers to the edges and vertices of a simple graph G. As a result we obtain a vertex-colouring of G with integers, where a vertex colour is simply a sum of the weight assigned to the vertex itself and the weights of its incident edges. Can we obtain a proper colouring using only weights 1 and 2 for an arbitrary G? We give a positive answer when G is a 3-colourable, complete or 4-regular graph. We also show that it is enough to C use weights from 1 to 11, as well as from 1 to 11 [chi(G)/2] + 1, for an arbitrary graph G.
Series acceleration formulas for beta values
Authors: Pilehrood Khodabakhsh Hessami , Pilehrood Tatiana Hessami
Published: August 2021

We prove generating function identities producing fast convergent series for the sequences beta(2n + 1); beta(2n + 2) and beta(2n + 3), where beta is Dirichlet's beta function. In particular, we obtain a new accelerated series for Catalan's constant convergent at a geometric rate with ratio 2(-10); which can be considered as an analog of Amdeberhan-Zeilberger's series for zeta(3)
Covering codes in Sierpinski graphs
Authors: Beaudou Laurent , Gravier Sylvain , Klavžar Sandi , Kovse Matjaz , Mollard Michel
Published: August 2021

Graphs and Algorithms

For a graph G and integers a and b, an (a, b)-code of G is a set C of vertices such that any vertex from C has exactly a neighbors in C and any vertex not in C has exactly b neighbors in C. In this paper we classify integers a and b for which there exist (a, b)-codes in Sierpinski graphs.
Deterministic recognizability of picture languages with Wang automata
Authors: Lonati Violetta , Pradella Matteo
Published: August 2021

special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications

We present a model of automaton for picture language recognition, called Wang automaton, which is based on labeled Wang tiles. Wang automata combine features of both online tessellation acceptors and 4-way automata: as in online tessellation acceptors, computation assigns states to each picture position; as in 4-way automata, the input head visits the picture moving from one pixel to an adjacent one, according to some scanning strategy. Wang automata recognize the class REC, i.e. they are equivalent to tiling systems or online tessellation acceptors, and hence strictly more powerful than 4-way automata. We also introduce a natural notion of determinism for Wang automata, and study the resulting class, extending the more traditional approach of diagonal-based determinism, used e. g. by deterministic tiling systems. In particular, we prove that the concept of row (or column) ambiguity defines the class of languages recognized by Wang automata directed by boustrophedonic scanning strategies.
Crucial abelian k-power-free words
Authors: Glen Amy , Halldorsson Bjarni V. , Kitaev Sergey
Published: August 2021

Combinatorics

In 1961, Erdos asked whether or not there exist words of arbitrary length over a fixed finite alphabet that avoid patterns of the form XX' where X' is a permutation of X (called abelian squares). This problem has since been solved in the affirmative in a series of papers from 1968 to 1992. Much less is known in the case of abelian k-th powers, i.e., words of the form X1X2 ... X-k where X-i is a permutation of X-1 for 2 <= i <= k. In this paper, we consider crucial words for abelian k-th powers, i. e., finite words that avoid abelian k-th powers, but which cannot be extended to the right by any letter of their own alphabets without creating an abelian k-th power. More specifically, we consider the problem of determining the minimal length of a crucial word avoiding abelian k-th powers. This problem has already been solved for abelian squares by Evdokimov and Kitaev (2004), who showed that a minimal crucial word over an n-letter alphabet A(n) = \1, 2, ..., n\ avoiding abelian squares has length 4n - 7 for n >= 3. Extending this result, we prove that a minimal crucial word over A(n) avoiding abelian cubes has length 9n - 13 for n >= 5, and it has length 2, 5, 11, and 20 for n = 1, 2, 3, and 4, respectively. Moreover, for n >= 4 and k >= 2, we give a construction of length k(2) (n - 1) - k - 1 of a crucial word over A(n) avoiding abelian k-th powers. This construction gives the minimal length for k = 2 and k = 3. For k >= 4 and n >= 5, we provide a lower bound for the length of crucial words over A(n) avoiding abelian k-th powers.
Asymptotic results for silent elimination
Authors: Louchard Guy , Prodinger Helmut
Published: August 2021

Following the model of Bondesson, Nilsson, and Wikstrand, we consider randomly filled urns, where the probability of falling into urn i is the geometric probability (1-q)qi-1. Assuming n independent random entries, and a fixed parameter k, the interest is in the following parameters: Let T be the smallest index, such that urn T is non-empty, but the following k are empty, then: XT= number of balls in urn T, ST= number of balls in urns with index larger than T, and finally T itself..
Tree-width and large grid minors in planar graphs
Authors: Grigoriev Alexander
Published: August 2021

Graphs and Algorithms

We show that for a planar graph with no g-grid minor there exists a tree-decomposition of width at most 5g - 6. The proof is constructive and simple. The underlying algorithm for the tree-decomposition runs in O(n(2) log n) time.
Generation of Cubic graphs
Authors: Brinkmann Gunnar , Goedgebeur Jan , Mckay Brendan D.
Published: August 2021

Discrete Algorithms

We describe a new algorithm for the efficient generation of all non-isomorphic connected cubic graphs. Our implementation of this algorithm is more than 4 times faster than previous generators. The generation can also be efficiently restricted to cubic graphs with girth at least 4 or 5.
Sturmian Sequences and Invertible Substitutions
Authors: Peng Li , Tan Bo
Published: August 2021

Combinatorics

It is known that a Sturmian sequence S can be defined as a coding of the orbit of rho (called the intercept of S) under a rotation of irrational angle alpha (called the slope). On the other hand, a fixed point of an invertible substitution is Sturmian. Naturally, there are two interrelated questions: (1) Given an invertible substitution, we know that its fixed point is Sturmian. What is the slope and intercept? (2) Which kind of Sturmian sequences can be fixed by certain non-trivial invertible substitutions? In this paper we give a unified treatment to the two questions. We remark that though the results are known, our proof is very elementary and concise.
On the minimal distance of a polynomial code
Authors: Pach Peter Pal , Szabo Csaba
Published: August 2021

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity

For a polynomial f(x) is an element of Z(2)[x] it is natural to consider the near-ring code generated by the polynomials f circle x, f circle x(2) ,..., f circle x(k) as a vectorspace. It is a 19 year old conjecture of Gunter Pilz that for the polynomial f (x) - x(n) broken vertical bar x(n-1) broken vertical bar ... broken vertical bar x the minimal distance of this code is n. The conjecture is equivalent to the following purely number theoretical problem. Let (m) under bar = \1, 2 ,..., m\ and A subset of N be an arbitrary finite subset of N. Show that the number of products that occur odd many times in (n) under bar. A is at least n. Pilz also formulated the conjecture for the special case when A = (k) under bar. We show that for A = (k) under bar the conjecture holds and that the minimal distance of the code is at least n/(log n)(0.223). While proving the case A = (k) under bar we use different number theoretical methods depending on the size of k (respect to n). Furthermore, we apply several estimates on the distribution of primes.
Bounds for the minimum oriented diameter
Authors: Kurz Sascha , Laetsch Martin
Published: August 2021

Graphs and Algorithms

We consider the problem of determining an orientation with minimum diameter MOD(G) of a connected and bridge-less graph G. In 2001 Fomin et al. discovered the relation MOD(G) <= 9 gamma(G) - 5 between the minimum oriented diameter and the size gamma(G) of a minimum dominating set. We improve their upper bound to MOD(G) <= 4 gamma(G).
alpha-Labelings and the Structure of Trees with Nonzero alpha-Deficit
Authors: Brinkmann Gunnar , Crevals Simon , Melot Hadrien , Rylands Leanne , Steffen Eckhard
Published: August 2021

Graph Theory

We present theoretical and computational results on alpha-labelings of trees. The theorems proved in this paper were inspired by the results of a computer investigation of alpha-labelings of all trees with up to 26 vertices, all trees with maximum degree 3 and up to 36 vertices, all trees with maximum degree 4 and up to 32 vertices and all trees with maximum degree 5 and up to 31 vertices. We generalise a criterion for trees to have nonzero alpha-deficit, and prove an unexpected result on the alpha-deficit of trees with a vertex of large degree compared to the order of the tree.
On neighbour-distinguishing colourings from lists
Authors: Horňák Mirko , WoźniaK Mariusz
Published: August 2021

Graphs and Algorithms

An edge colouring of a graph is said to be neighbour-distinguishing if any two adjacent vertices have distinct sets of colours of their incident edges. In this paper the list version of the problem of determining the minimum number of colours in a neighbour-distinguishing colouring of a given graph is considered.
Some results on stable sets for k-colorable P₆-free graphs and generalizations
Authors: Mosca Raffaele
Published: August 2021

Graphs and Algorithms

This article deals with the Maximum Weight Stable Set (MWS) problem (and some other related NP-hard problems) and the class of P-6-free graphs. The complexity status of MWS is open for P-6-free graphs and is open even for P-5-free graphs (as a long standing open problem). Several results are known for MWS on subclasses of P-5-free: in particular, MWS can be solved for k-colorable P-5-free graphs in polynomial time for every k (depending on k) and more generally for (P-5, K-p)-free graphs (depending on p), which is a useful result since for every graph G one can easily compute a k-coloring of G, with k not necessarily minimum. This article studies the MWS problem for k-colorable P-6-free graphs and more generally for (P-6, K-p)-free graphs. Though we were not able to define a polynomial time algorithm for this problem for every k, this article introduces: (i) some structure properties of P-6-free graphs with respect to stable sets, (ii) two reductions for MWS on (P-6; K-p)-free graphs for every p, (iii) three polynomial time algorithms to solve MWS respectively for 3-colorable P-6-free, for 4-colorable P-6-free, and for (P-6, K-4)-free graphs (the latter allows one to state, together with other known results, that MWS can be solved for (P-6, F)-free graphs in polynomial time where F is any four vertex graph).
Immersion containment and connectivity in color-critical graphs
Authors: Abu-Khzam Faisal N. , Langston Michael A.
Published: August 2021

Graph Theory

The relationship between graph coloring and the immersion order is considered. Vertex connectivity, edge connectivity and related issues are explored. It is shown that a t-chromatic graph G contains either an immersed Kt or an immersed t-chromatic subgraph that is both 4-vertex-connected and t-edge-connected. This gives supporting evidence of our conjecture that if G requires at least t colors, then Kt is immersed in G.
Acyclic chromatic index of fully subdivided graphs and Halin graphs
Authors: Basavaraju Manu
Published: August 2021

Graph Theory

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). A graph G is called fully subdivided if it is obtained from another graph H by replacing every edge by a path of length at least two. Fully subdivided graphs are known to be acyclically edge colorable using Δ+1 colors since they are properly contained in 2-degenerate graphs which are acyclically edge colorable using Δ+1 colors. Muthu, Narayanan and Subramanian gave a simple direct proof of this fact for the fully subdivided graphs. Fiamcik has shown that if we subdivide every edge in a cubic graph with at most two exceptions to get a graph G, then a'(G)=3. In this paper we generalise the bound to Δ for all fully subdivided graphs improving the result of Muthu et al. In particular, we prove that if G is a fully subdivided graph and Δ(G) ≥3, then a'(G)=Δ(G). Consider a graph G=(V,E), with E=E(T) ∪E(C) where T is a rooted tree on the vertex set V and C is a simple cycle on the leaves of T. Such a graph G is called a Halin graph if G has a planar embedding and T has no vertices of degree 2. Let Kn denote a complete graph on n vertices. Let G be a Halin graph with maximum degree Δ. We prove that, a'(G) = 5 if G is K4, 4 if Δ = 3 and G is not K4, and Δ otherwise.
Operations on partially ordered sets and rational identities of type A
Authors: Boussicault Adrien
Published: August 2021

Combinatorics

We consider the family of rational functions ψw= ∏( xwi - xwi+1 )-1 indexed by words with no repetition. We study the combinatorics of the sums ΨP of the functions ψw when w describes the linear extensions of a given poset P. In particular, we point out the connexions between some transformations on posets and elementary operations on the fraction ΨP. We prove that the denominator of ΨP has a closed expression in terms of the Hasse diagram of P, and we compute its numerator in some special cases. We show that the computation of ΨP can be reduced to the case of bipartite posets. Finally, we compute the numerators associated to some special bipartite graphs as Schubert polynomials.
Fillings of skew shapes avoiding diagonal patterns
Authors: Jelínek Vít , Karpilovskij Mark
Published: August 2021

A skew shape is the difference of two top-left justified Ferrers shapes
sharing the same top-left corner. We study integer fillings of skew shapes. As
our first main result, we show that for a specific hereditary class of skew
shapes, which we call D-free shapes, the fillings that avoid a north-east chain
of size $k$ are in bijection with fillings that avoid a south-east chain of the
same size. Since Ferrers shapes are a subclass of D-free shapes, this result
can be seen as a generalization of previous analogous results for Ferrers
shapes.
As our second main result, we construct a bijection between 01-fillings of an
arbitrary skew shape that avoid a south-east chain of size 2, and the
01-fillings of the same shape that simultaneously avoid a north-east chain of
size 2 and a particular non-square subfilling. This generalizes a previous
result for transversal fillings.
Enumeration of Dumont permutations avoiding certain four-letter patterns
Authors: Burstein Alexander , Jones Opel
Published: August 2021

In this paper, we enumerate Dumont permutations of the fourth kind avoiding
or containing certain permutations of length 4. We also conjecture a
Wilf-equivalence of two 4-letter patterns on Dumont permutations of the first
kind.
Bounded affine permutations I. Pattern avoidance and enumeration
Authors: Madras Neal , Troyka Justin M.
Published: August 2021

We introduce a new boundedness condition for affine permutations, motivated
by the fruitful concept of periodic boundary conditions in statistical physics.
We study pattern avoidance in bounded affine permutations. In particular, we
show that if $\tau$ is one of the finite increasing oscillations, then every
$\tau$-avoiding affine permutation satisfies the boundedness condition. We also
explore the enumeration of pattern-avoiding affine permutations that can be
decomposed into blocks, using analytic methods to relate their exact and
asymptotic enumeration to that of the underlying ordinary permutations.
Finally, we perform exact and asymptotic enumeration of the set of all bounded
affine permutations of size $n$. A companion paper will focus on avoidance of
monotone decreasing patterns in bounded affine permutations.
The Magnus-Derek game in groups
Authors: Gerbner Dániel
Published: August 2021

Combinatorics

The Magnus-Derek game (also called the maximal variant of the vector game), introduced by Nedev and Muthukrishnan is the following: a token is moved around a table with n positions. In each round of the game Magnus chooses a number and then Derek chooses a direction (clockwise or counterclockwise), and the token moves that many positions into that direction. The goal of Magnus is to maximize the number of positions visited, the goal of Derek is the opposite. In the minimal variant of the game the goals of the two players are exchanged: Magnus wants to minimize the number of positions visited and Derek wants the opposite. Here we introduce a generalization of these games: the token is moved in a group, Magnus chooses an element of the group and Derek decides if the current position is multiplied or divided by that element.
On the complexity of distributed BFS in ad hoc networks with non-spontaneous wake-ups
Authors: Kowalski Dariusz , Krzywdziński Krzysztof
Published: August 2021

Distributed Computing and Networking

We study time and message complexity of the problem of building a BFS tree by a spontaneously awaken node in ad hoc network. Computation is in synchronous rounds, and messages are sent via point-to-point bi-directional links. Network topology is modeled by a graph. Each node knows only its own id and the id's of its neighbors in the network and no pre-processing is allowed; therefore the solutions to the problem of spanning a BFS tree in this setting must be distributed. We deliver a deterministic distributed solution that trades time for messages, mainly, with time complexity O(D . min(D; n=f(n)) . logD . log n) and with the number of point-to-point messages sent O(n. (min(D; n=f(n))+f(n)) . logD. log n), for any n-node network with diameter D and for any monotonically non-decreasing sub-linear integer function f. Function f in the above formulas come from the threshold value on node degrees used by our algorithms, in the sense that nodes with degree at most f(n) are treated differently that the other nodes. This yields the first BFS-finding deterministic distributed algorithm in ad hoc networks working in time o(n) and with o(n2) message complexity, for some suitable functions f(n) = o(n= log2 n), provided D = o(n= log4 n).
The Erdős-Sós conjecture for geometric graphs
Authors: Barba Luis , Fabila-Monroy Ruy , Lara Dolores , Leaños Jesús , Rodrıguez Cynthia , Salazar Gelasio , Zaragoza Francisco
Published: August 2021

Combinatorics

Let f(n,k) be the minimum number of edges that must be removed from some complete geometric graph G on n points, so that there exists a tree on k vertices that is no longer a planar subgraph of G. In this paper we show that ( 1 / 2 )n2 / k-1-n / 2≤f(n,k) ≤2 n(n-2) / k-2. For the case when k=n, we show that 2 ≤f(n,n) ≤3. For the case when k=n and G is a geometric graph on a set of points in convex position, we completely solve the problem and prove that at least three edges must be removed.
Automaticity of primitive words and irreducible polynomials
Authors: Lacroix Anne , Rampersad Narad
Published: August 2021

Automata, Logic and Semantics

If L is a language, the automaticity function A_L(n) (resp. N_L(n)) of L counts the number of states of a smallest deterministic (resp. non-deterministic) finite automaton that accepts a language that agrees with L on all inputs of length at most n. We provide bounds for the automaticity of the language of primitive words and the language of unbordered words over a k-letter alphabet. We also give a bound for the automaticity of the language of base-b representations of the irreducible polynomials over a finite field. This latter result is analogous to a result of Shallit concerning the base-k representations of the set of prime numbers.
Kraskiewicz-Pragacz modules and Pieri and dual Pieri rules for Schubert polynomials
Authors: Watanabe Masaki
Published: August 2021

In their 1987 paper Kraskiewicz and Pragacz defined certain modules, which we call KP modules, over the upper triangular Lie algebra whose characters are Schubert polynomials. In a previous work the author showed that the tensor product of Kraskiewicz-Pragacz modules always has KP filtration, i.e. a filtration whose each successive quotients are isomorphic to KP modules. In this paper we explicitly construct such filtrations for certain special cases of these tensor product modules, namely Sw Sd(Ki) and Sw Vd(Ki), corresponding to Pieri and dual Pieri rules for Schubert polynomials.
Asymptotic laws for knot diagrams
Authors: Chapman Harrison
Published: August 2021

We study random knotting by considering knot and link diagrams as decorated, (rooted) topological maps on spheres and sampling them with the counting measure on from sets of a fixed number of vertices n. We prove that random rooted knot diagrams are highly composite and hence almost surely knotted (this is the analogue of the Frisch-Wasserman-Delbruck conjecture) and extend this to unrooted knot diagrams by showing that almost all knot diagrams are asymmetric. The model is similar to one of Dunfield, et al.
A triple product formula for plane partitions derived from biorthogonal polynomials
Authors: Kamioka Shuhei
Published: August 2021

A new triple product formulae for plane partitions with bounded size of parts is derived from a combinato- rial interpretation of biorthogonal polynomials in terms of lattice paths. Biorthogonal polynomials which generalize the little q-Laguerre polynomials are introduced to derive a new triple product formula which recovers the classical generating function in a triple product by MacMahon and generalizes the trace-type generating functions in double products by Stanley and Gansner.
Asymptotics of Bivariate Analytic Functions with Algebraic Singularities
Authors: Greenwood Torin
Published: August 2021

In this paper, we use the multivariate analytic techniques of Pemantle and Wilson to find asymptotic for- mulae for the coefficients of a broad class of multivariate generating functions with algebraic singularities. Flajolet and Odlyzko (1990) analyzed the coefficients of a class of univariate generating functions with algebraic singularities. These results have been extended to classes of multivariate generating functions by Gao and Richmond (1992) and Hwang (1996, 1998), in both cases by immediately reducing the multivariate case to the univariate case. Pemantle and Wilson (2013) outlined new multivariate analytic techniques and used them to analyze the coefficients of rational generating functions.
Diagonally and antidiagonally symmetric alternating sign matrices of odd order
Authors: Behrend Roger , Fischer Ilse , Konvalinka Matjaz
Published: August 2021

We study the enumeration of diagonally and antidiagonally symmetric alternating sign matrices (DAS- ASMs) of fixed odd order by introducing a case of the six-vertex model whose configurations are in bijection with such matrices. The model involves a grid graph on a triangle, with bulk and boundary weights which satisfy the Yang– Baxter and reflection equations. We obtain a general expression for the partition function of this model as a sum of two determinantal terms, and show that at a certain point each of these terms reduces to a Schur function. We are then able to prove a conjecture of Robbins from the mid 1980's that the total number of (2n + 1) × (2n + 1) DASASMs is∏n (3i)! ,andaconjectureofStroganovfrom2008thattheratiobetweenthenumbersof(2n+1)×(2n+1) i=0 (n+i)! DASASMs with central entry −1 and 1 is n/(n + 1). Among the several product formulae for the enumeration of symmetric alternating sign matrices which were conjectured in the 1980's, that for odd-order DASASMs is the last to have been proved.
A dual approach to structure constants for K-theory of Grassmannians
Authors: Li Huilan , Morse Jennifer , Shields Pat
Published: August 2021

The problem of computing products of Schubert classes in the cohomology ring can be formulated as theproblem of expanding skew Schur polynomial into the basis of ordinary Schur polynomials. We reformulate theproblem of computing the structure constants of the Grothendieck ring of a Grassmannian variety with respect to itsbasis of Schubert structure sheaves in a similar way; we address the problem of expanding the generating functions forskew reverse-plane partitions into the basis of polynomials which are Hall-dual to stable Grothendieck polynomials. From this point of view, we produce a chain of bijections leading to Buch’s K-theoretic Littlewood-Richardson rule.
Elliptic rook and file numbers
Authors: Schlosser Michael J. , Yoo Meesue
Published: August 2021

In this work, we construct elliptic analogues of the rook numbers and file numbers by attaching elliptic weights to the cells in a board. We show that our elliptic rook and file numbers satisfy elliptic extensions of corre- sponding factorization theorems which in the classical case were established by Goldman, Joichi and White and by Garsia and Remmel in the file number case. This factorization theorem can be used to define elliptic analogues of various kinds of Stirling numbers of the first and second kind as well as Abel numbers. We also give analogous results for matchings of graphs, elliptically extending the result of Haglund and Remmel.
Strange Expectations and Simultaneous Cores
Authors: Thiel Marko , Williams Nathan
Published: August 2021

Let gcd(a, b) = 1. J. Olsson and D. Stanton proved that the maximum number of boxes in a simultaneous (a, b)-core is (a2 −1)(b2 −1) 24, and showed that this maximum is achieved by a unique core. P. Johnson combined Ehrhart theory with the polynomial method to prove D. Armstrong's conjecture that the expected number of boxes in a simultaneous (a, b)-core is (a−1)(b−1)(a+b+1) 24. We apply P. Johnson's method to compute the variance and third moment. By extending the definitions of “simultaneous cores” and “number of boxes” to affine Weyl groups, we give uniform generalizations of these formulae to simply-laced affine types. We further explain the appearance of the number 24 using the “strange formula” of H. Freudenthal and H. de Vries.
Noncrossing partitions, toggles, and homomesy
Authors: Einstein David , Farber Miriam , Gunawan Emily , Joseph Michael , Macauley Matthew , Propp James , Rubinstein-Salzedo Simon
Published: August 2021

We introduce n(n − 1)/2 natural involutions (“toggles”) on the set S of noncrossing partitions π of size n, along with certain composite operations obtained by composing these involutions. We show that for many operations T of this kind, a surprisingly large family of functions f on S (including the function that sends π to the number of blocks of π) exhibits the homomesy phenomenon: the average of f over the elements of a T -orbit is the same for all T -orbits. Our methods apply more broadly to toggle operations on independent sets of certain graphs.
On intervals of the consecutive pattern poset
Authors: Elizalde Sergi , McNamara Peter R. W.
Published: August 2021

The consecutive pattern poset is the infinite partially ordered set of all permutations where σ ≤ τ if τ has a subsequence of adjacent entries in the same relative order as the entries of σ. We study the structure of the intervals in this poset from topological, poset-theoretic, and enumerative perspectives. In particular, we prove that all intervals are rank-unimodal and strongly Sperner, and we characterize disconnected and shellable intervals. We also show that most intervals are not shellable and have Mo ̈bius function equal to zero.
The configuration space of a robotic arm in a tunnel of width 2
Authors: Ardila Federico , Bastidas Hanner , Ceballos Cesar , Guo John
Published: August 2021

We study the motion of a robotic arm inside a rectangular tunnel of width 2. We prove that the configuration space S of all possible positions of the robot is a CAT(0) cubical complex. Before this work, very few families of robots were known to have CAT(0) configuration spaces. This property allows us to move the arm optimally from one position to another.
Partitioning Harary graphs into connected subgraphs containing prescribed vertices
Authors: Baudon Olivier , Bensmail Julien , Sopena Eric
Published: August 2021

A graph G is arbitrarily partitionable (AP for short) if for every partition (n_1, n_2, ..., n_p) of |V(G)| there exists a partition (V_1, V_2, ..., V_p) of V(G) such that each V_i induces a connected subgraph of G with order n_i. If, additionally, k of these subgraphs (k <= p) each contains an arbitrary vertex of G prescribed beforehand, then G is arbitrarily partitionable under k prescriptions (AP+k for short). Every AP+k graph on n vertices is (k+1)-connected, and thus has at least ceil(n(k+1)/2) edges. We show that there exist AP+k graphs on n vertices and ceil(n(k+1)/2) edges for every k >= 1 and n >= k.
Continued Classification of 3D Lattice Models in the Positive Octant
Authors: Bacher Axel , Kauers Manuel , Yatchak Rika
Published: August 2021

We continue the investigations of lattice walks in the three-dimensional lattice restricted to the positive octant. We separate models which clearly have a D-finite generating function from models for which there is no reason to expect that their generating function is D-finite, and we isolate a small set of models whose nature remains unclear and requires further investigation. For these, we give some experimental results about their asymptotic behaviour, based on the inspection of a large number of initial terms. At least for some of them, the guessed asymptotic form seems to tip the balance towards non-D-finiteness.
On the number of vertices of each rank in phylogenetic trees and their generalizations
Authors: Bóna Miklós
Published: August 2021

We find surprisingly simple formulas for the limiting probability that the
rank of a randomly selected vertex in a randomly selected phylogenetic tree or
generalized phylogenetic tree is a given integer.