bluuebunny/crossref_metadata_2025 huggingface dataset:
Local-to-Global Principles for the Hitting Sequence of a Rotor Walk
Authors: Giacaglia Giuliano Pezzolo , Levine Lionel , Propp James , Zayas-Palmer Linda
Published: January 2020

In rotor walk on a finite directed graph, the exits from each vertex follow a prescribed periodic sequence. Here we consider the case of rotor walk where a particle starts from a designated source vertex and continues until it hits a designated target set, at which point the walk is restarted from the source. We show that the sequence of successively hit targets, which is easily seen to be eventually periodic, is in fact periodic. We show moreover that reversing the periodic patterns of all rotor sequences causes the periodic pattern of the hitting sequence to be reversed as well. The proofs involve a new notion of equivalence of rotor configurations, and an extension of rotor walk incorporating time-reversed particles.
Playing Nim on a Simplicial Complex
Authors: Ehrenborg Richard , Steingrímsson Einar
Published: January 2020

We introduce a generalization of the classical game of Nim by placing the piles on the vertices of a simplicial complex and allowing a move to affect the piles on any set of vertices that forms a face of the complex. Under certain conditions on the complex we present a winning strategy. These conditions are satisfied, for instance, when the simplicial complex consists of the independent sets of a binary matroid. Moreover, we study four operations on a simplicial complex under which games on the complex behave nicely. We also consider particular complexes that correspond to natural generalizations of classical Nim.
A New Construction for Cancellative Families of Sets
Authors: Shearer James B.
Published: January 2020

Following [2], we say a family, $H$, of subsets of a $n$-element set is cancellative if $A \cup B = A \cup C$ implies $B =C$ when $A, B, C \in H$. We show how to construct cancellative families of sets with $c 2^{.54797n}$ elements. This improves the previous best bound $c 2^{.52832n}$ and falsifies conjectures of Erdös and Katona [3] and Bollobás [1].
Clique-Width and the Speed of Hereditary Properties
Authors: Allen Peter , Lozin Vadim , Rao Michaël
Published: January 2020

In this paper, we study the relationship between the number of $n$-vertex graphs in a hereditary class $\cal X$, also known as the speed of the class $\cal X$, and boundedness of the clique-width in this class. We show that if the speed of $\cal X$ is faster than $n!c^n$ for any $c$, then the clique-width of graphs in $\cal X$ is unbounded, while if the speed does not exceed the Bell number $B_n$, then the clique-width is bounded by a constant. The situation in the range between these two extremes is more complicated. This area contains both classes of bounded and unbounded clique-width. Moreover, we show that classes of graphs of unbounded clique-width may have slower speed than classes where the clique-width is bounded.
A Generalization of Gosper's Algorithm to Bibasic Hypergeometric Summation
Authors: Riese Axel
Published: January 2020

An algebraically motivated generalization of Gosper's algorithm to indefinite bibasic hypergeometric summation is presented. In particular, it is shown how Paule's concept of greatest factorial factorization of polynomials can be extended to the bibasic case. It turns out that most of the bibasic hypergeometric summation identities from literature can be proved and even found this way. A Mathematica implementation of the algorithm is available from the author.
Ramseyan Properties of Graphs
Authors: DeLaVina Ermelinda , Fajtlowicz Siemion
Published: January 2020

Every graph of chromatic number $k$ with more than $k(r-1)(b-1)$ vertices has a $b$-element independent set of vertices such that if any two of them are joined by an edge then the chromatic number stays the same or a $r$-element independent set of vertices such that joining any two of them by an edge increases the chromatic number.
Descendants in heap ordered trees or a triumph of computer algebra
Authors: Prodinger Helmut
Published: January 2020

A heap ordered tree with $n$ nodes ("size $n$") is a planted plane tree together with a bijection from the nodes to the set $\{1,\dots,n\}$ which is monotonically increasing when going from the root to the leaves. We consider the number of descendants of the node $j$ in a (random) heap ordered tree of size $n\ge j$. Precise expressions are derived for the probability distribution and all (factorial) moments.
An Extension of the Exponential Formula in Enumerative Combinatorics
Authors: Labelle Gilbert , Leroux Pierre
Published: January 2020

Let $\alpha$ be a formal variable and $F_w$ be a weighted species of structures (class of structures closed under weight-preserving isomorphisms) of the form ${F}_{w} = E({F}_{w}^{c})$, where $E$ and $F_w^c$ respectively denote the species of sets and of connected $F_w$-structures. Multiplying by $\alpha$ the weight of each $F_w^c$-structure yields the species ${F}_{{w}^{( \alpha )}} = E({F}_{ \alpha w}^{c})$. We introduce a "universal" virtual weighted species, $\Lambda ^{(\alpha)}$, such that $F_{w^{(\alpha)}} = \Lambda^{( \alpha)}\, \circ \, F_w^+$, where $F_w^+$ denotes the species of non-empty $F_w$-structures. Using general properties of $\Lambda^{( \alpha)}$ , we compute the various enumerative power series $G(x)$, $\widetilde{G}(x)$, $\overline{G}(x)$, $G(x;q)$, $G\langle{x;q}\rangle$, ${Z}_{G}(x_1,x_2,x_3,\ldots)$, ${\Gamma }_{G}(x_1,x_2,x_3,\ldots)$, for $G = F_{w^{(\alpha)}}$, in terms of $F_w$. Special instances of our formulas include the exponential formula, ${F}_{{w}^{(\alpha )}}(x)=\exp(\alpha F_{w}(x))=({F}_{w}(x){)}^{\alpha }$, cyclotomic identities, and their $q$-analogues. The virtual weighted species, $\Lambda ^{(\alpha)}$, is, in fact, a new combinatorial lifting of the function ${(1+x)}^{\alpha }$.
A Graph-Theoretic Method for Choosing a Spanning Set for a Finite-Dimensional Vector Space, with Applications to the Grossman-Larson-Wright Module and the Jacobian Conjecture
Authors: Singer Dan
Published: January 2020

It is well known that a square zero pattern matrix guarantees non-singularity if and only if it is permutationally equivalent to a triangular pattern with nonzero diagonal entries. It is also well known that a nonnegative square pattern matrix with positive main diagonal is sign nonsingular if and only if its associated digraph does not have any directed cycles of even length. Any $m\times n$ matrix containing an $n\times n$ sub-matrix with either of these forms will have full rank. We translate this idea into a graph-theoretic method for finding a spanning set of vectors for a finite-dimensional vector space from among a set of vectors generated combinatorially. This method is particularly useful when there is no convenient ordering of vectors and no upper bound to the dimensions of the vector spaces we are dealing with. We use our method to prove three properties of the Grossman-Larson-Wright module originally described by David Wright: $\overline{\cal M}(3,\infty)_m=0$ for $m\ge 3$, $\overline{\cal M}(4,3)_m=0$ for $5\le m\le 8$, and $\overline{\cal M}(4,4)_8=0$. The first two properties yield combinatorial proofs of special cases of the homogeneous symmetric reduction of the Jacobian conjecture.
Generating Functions and Generalized Dedekind Sums
Authors: Gessel Ira
Published: January 2020

We study sums of the form $\sum_\zeta R(\zeta)$, where $R$ is a rational function and the sum is over all $n$th roots of unity $\zeta$ (often with $\zeta =1$ excluded). We call these generalized Dedekind sums, since the most well-known sums of this form are Dedekind sums. We discuss three methods for evaluating such sums: The method of factorization applies if we have an explicit formula for $\prod_\zeta (1-xR(\zeta))$. Multisection can be used to evaluate some simple, but important sums. Finally, the method of partial fractions reduces the evaluation of arbitrary generalized Dedekind sums to those of a very simple form.
Shape Tiling
Authors: Keating Kevin , King Jonathan L.
Published: January 2020

Given a list $1\times 1, 1\times a, 1\times b, \dots, 1\times c$ of rectangles, with $a,b,\dots,c$ non-negative, when can $1\times{t}$ be tiled by positive and negative copies of rectangles which are similar (uniform scaling) to those in the list? We prove that such a tiling exists iff $t$ is in the field $Q(a,b,\dots,c)$.
Multimatroids II. Orthogonality, minors and connectivity
Authors: Bouchet André
Published: January 2020

A multimatroid is a combinatorial structure that encompasses matroids, delta-matroids and isotropic systems. This structure has been introduced to unify a theorem of Edmonds on the coverings of a matroid by independent sets and a theorem of Jackson on the existence of pairwise compatible Euler tours in a 4-regular graph. Here we investigate some basic concepts and properties related with multimatroids: matroid orthogonality, minor operations and connectivity.
On Kissing Numbers in Dimensions 32 to 128
Authors: Edel Yves , Rains E. M. , Sloane N. J. A.
Published: January 2020

An elementary construction using binary codes gives new record kissing numbers in dimensions from 32 to 128.
The Average Order of a Permutation
Authors: Stong Richard
Published: January 2020

We show that the average order $\mu_n$ of a permutation in $S_n$ satisfies $$ \log\mu_n\ =\ C\sqrt{\frac n{\log n}} + O\left(\frac{\sqrt n\log\log n}{\log n}\right), $$ which refines earlier results of Erdős and Turán, Schmutz, and Goh and Schmutz.
On the Theory of Pfaffian Orientations. II. $T$-joins, $k$-cuts, and Duality of Enumeration
Authors: Galluccio Anna , Loebl Martin
Published: January 2020

This is a continuation of our paper "A Theory of Pfaffian Orientations I: Perfect Matchings and Permanents". We present a new combinatorial way to compute the generating functions of $T$-joins and $k$-cuts of graphs. As a consequence, we show that the computational problem to find the maximum weight of an edge-cut is polynomially solvable for the instances $(G,w)$ where $G$ is a graph embedded on an arbitrary fixed orientable surface and the weight function $w$ has only a bounded number of different values. We also survey the related results concerning a duality of the Tutte polynomial, and present an application for the weight enumerator of a binary code. In a continuation of this paper which is in preparation we present an application to the Ising problem of three-dimensional crystal structures.
Permutation Patterns and Continued Fractions
Authors: Robertson Aaron , Wilf Herbert S. , Zeilberger Doron
Published: January 2020

We find, in the form of a continued fraction, the generating function for the number of $(132)$-avoiding permutations that have a given number of $(123)$ patterns, and show how to extend this to permutations that have exactly one $(132)$ pattern. We also find some properties of the continued fraction, which is similar to, though more general than, those that were studied by Ramanujan.
Restricted permutations, continued fractions, and Chebyshev polynomials
Authors: Mansour Toufik , Vainshtein Alek
Published: January 2020

Let $f_n^r(k)$ be the number of 132-avoiding permutations on $n$ letters that contain exactly $r$ occurrences of $12\dots k$, and let $F_r(x;k)$ and $F(x,y;k)$ be the generating functions defined by $F_r(x;k)=\sum_{n\ge 0} f_n^r(k)x^n$ and $F(x,y;k)=\sum_{r\ge 0}F_r(x;k)y^r$. We find an explicit expression for $F(x,y;k)$ in the form of a continued fraction. This allows us to express $F_r(x;k)$ for $1\le r\le k$ via Chebyshev polynomials of the second kind.
Graceful Tree Conjecture for Infinite Trees
Authors: Chan Tsz Lung , Cheung Wai Shun , Ng Tuen Wai
Published: January 2020

One of the most famous open problems in graph theory is the Graceful Tree Conjecture, which states that every finite tree has a graceful labeling. In this paper, we define graceful labelings for countably infinite graphs, and state and verify a Graceful Tree Conjecture for countably infinite trees.
A Construction Method for Complete Sets of Mutually Orthogonal Frequency Squares
Authors: Mavron V C
Published: January 2020

A construction is described for combining affine designs with complete sets of mutually orthogonal frequency squares to produce other complete sets.
Values of Domination Numbers of the Queen's Graph
Authors: Östergård Patric R. J. , Weakley William D.
Published: January 2020

The queen's graph $Q_{n}$ has the squares of the $n \times n$ chessboard as its vertices; two squares are adjacent if they are in the same row, column, or diagonal. Let $\gamma (Q_{n})$ and $i(Q_{n})$ be the minimum sizes of a dominating set and an independent dominating set of $Q_{n}$, respectively. Recent results, the Parallelogram Law, and a search algorithm adapted from Knuth are used to find dominating sets. New values and bounds:(A) $\gamma (Q_n) = \lceil n/2 \rceil$ is shown for 17 values of $n$ (in particular, the set of values for which the conjecture $\gamma (Q_{4k+1}) = 2k + 1$ is known to hold is extended to $k \leq 32$);(B) $i(Q_n) = \lceil n/2 \rceil$ is shown for 11 values of $n$, including 5 of those from (A);(C) One or both of $\gamma (Q_n)$ and $i(Q_n)$ is shown to lie in $\{ \lceil n/2 \rceil $, $\lceil n/2 \rceil + 1 \}$ for 85 values of $n$ distinct from those in (A) and (B).Combined with previously published work, these results imply that for $n \leq 120$, each of $\gamma (Q_n)$ and $i(Q_n)$ is either known, or known to have one of two values.Also, the general bounds $\gamma (Q_n) \leq 69n/133 + O(1)$ and $i(Q_n) \leq 61n/111 + O(1)$ are established. Comment added August 25th 2003.Corrigendum added October 5th 2017.
All Regular Multigraphs of Even Order and High Degree Are 1-factorable
Authors: Plantholt Michael J. , Tipnis Shailesh K.
Published: January 2020

Plantholt and Tipnis (1991) proved that for any even integer $r$, a regular multigraph $G$ with even order $n$, multiplicity $\mu(G) \leq r$ and degree high relative to $n$ and $r$ is 1-factorable. Here we extend this result to include the case when $r$ is any odd integer. Häggkvist and Perković and Reed (1997) proved that the One-factorization Conjecture for simple graphs is asymptotically true. Our techniques yield an extension of this asymptotic result on simple graphs to a corresponding asymptotic result on multigraphs.
A Note on the Ranks of Set-Inclusion Matrices
Authors: De Caen D.
Published: January 2020

A recurrence relation is derived for the rank (over most fields) of the set-inclusion matrices on a finite ground set.
On Packing Densities of Permutations
Authors: Albert M. H. , Atkinson M. D. , Handley C. C. , Holton D. A. , Stromquist W.
Published: January 2020

The density of a permutation pattern $\pi$ in a permutation $\sigma$ is the proportion of subsequences of $\sigma$ of length $|\pi|$ that are isomorphic to $\pi$. The maximal value of the density is found for several patterns $\pi$, and asymptotic upper and lower bounds for the maximal density are found in several other cases. The results are generalised to sets of patterns and the maximum density is found for all sets of length $3$ patterns.
Certificates of Factorisation for a Class of Triangle-Free Graphs
Authors: Morgan Kerri , Farr Graham
Published: January 2020

The chromatic polynomial $P(G,\lambda)$ gives the number of $\lambda$-colourings of a graph. If $P(G,\lambda)=P(H_{1},\lambda)P(H_{2},\lambda)/P(K_{r},\lambda)$, then the graph $G$ is said to have a chromatic factorisation with chromatic factors $H_{1}$ and $H_{2}$. It is known that the chromatic polynomial of any clique-separable graph has a chromatic factorisation. In this paper we construct an infinite family of graphs that have chromatic factorisations, but have chromatic polynomials that are not the chromatic polynomial of any clique-separable graph. A certificate of factorisation, that is, a sequence of rewritings based on identities for the chromatic polynomial, is given that explains the chromatic factorisations of graphs from this family. We show that the graphs in this infinite family are the only graphs that have a chromatic factorisation satisfying this certificate and having the odd cycle $C_{2n+1}$, $n\geq2$, as a chromatic factor.
Generalizing the Ramsey Problem through Diameter
Authors: Mubayi Dhruv
Published: January 2020

Given a graph $G$ and positive integers $d,k$, let $f_d^k(G)$ be the maximum $t$ such that every $k$-coloring of $E(G)$ yields a monochromatic subgraph with diameter at most $d$ on at least $t$ vertices. Determining $f_1^k(K_n)$ is equivalent to determining classical Ramsey numbers for multicolorings. Our results include $\bullet$ determining $f_d^k(K_{a,b})$ within 1 for all $d,k,a,b$ $\bullet$ for $d \ge 4$, $f_d^3(K_n)=\lceil n/2 \rceil +1$ or $\lceil n/2 \rceil$ depending on whether $n \equiv 2 (mod 4)$ or not $\bullet$ $f_3^k(K_n) > {{n}\over {k-1+1/k}}$ The third result is almost sharp, since a construction due to Calkin implies that $f_3^k(K_n) \le {{n}\over {k-1}} +k-1$ when $k-1$ is a prime power. The asymptotics for $f_d^k(K_n)$ remain open when $d=k=3$ and when $d\ge 3, k \ge 4$ are fixed.
The Number of Labeled 2-Connected Planar Graphs
Authors: Bender Edward A. , Gao Zhicheng , Wormald Nicholas C.
Published: January 2020

We derive the asymptotic expression for the number of labeled 2-connected planar graphs with respect to vertices and edges. We also show that almost all such graphs with $n$ vertices contain many copies of any fixed planar graph, and this implies that almost all such graphs have large automorphism groups.
A Small Trivalent Graph of Girth 14
Authors: Exoo Geoffrey
Published: January 2020

We construct a graph of order 384, the smallest known trivalent graph of girth 14.
Permutations Which Avoid 1243 and 2143, Continued Fractions, and Chebyshev Polynomials
Authors: Egge Eric S. , Mansour Toufik
Published: January 2020

Several authors have examined connections between permutations which avoid 132, continued fractions, and Chebyshev polynomials of the second kind. In this paper we prove analogues of some of these results for permutations which avoid 1243 and 2143. Using tools developed to prove these analogues, we give enumerations and generating functions for permutations which avoid 1243, 2143, and certain additional patterns. We also give generating functions for permutations which avoid 1243 and 2143 and contain certain additional patterns exactly once. In all cases we express these generating functions in terms of Chebyshev polynomials of the second kind.
Sorting with a Forklift
Authors: Albert M. H. , Atkinson M. D.
Published: January 2020

A fork stack is a generalised stack which allows pushes and pops of several items at a time. We consider the problem of determining which input streams can be sorted using a single forkstack, or dually, which permutations of a fixed input stream can be produced using a single forkstack. An algorithm is given to solve the sorting problem and the minimal unsortable sequences are found. The results are extended to fork stacks where there are bounds on how many items can be pushed and popped at one time. In this context we also establish how to enumerate the collection of sortable sequences.
A Survey of Stack-Sorting Disciplines
Authors: Bóna Miklós
Published: January 2020

We review the various ways that stacks, their variations and their combinations, have been used as sorting devices. In particular, we show that they have been a key motivator for the study of permutation patterns. We also show that they have connections to other areas in combinatorics such as Young tableau, planar graph theory, and simplicial complexes.
Anti-Codes in Terms of Berlekamp's Switching Game
Authors: Schauz Uwe
Published: January 2020

We view a linear code (subspace) $C\leq\mathbb{F}_{q}^n$ as a light pattern on the \(n\)-dimensional Berlekamp Board $\mathbb{F}_{q}^n$ with $q^n$ light bulbs. The lights corresponding to elements of $C$ are ON, the others are OFF. Then we allow axis-parallel switches of complete rows, columns, etc. We show that the dual code $C^\perp$ contains a vector $v$ of full weight, i.e. $v_1,v_2,\dots,v_n\neq0$, if and only if the light pattern $C$ cannot be switched off. Generalizations of this allow us to describe anti-codes with maximal weight $\delta$ in a similar way, or, alternatively, in terms of a switching game in projective space. We provide convenient bases and normal forms to the modules of all light patterns of the generalized games. All our proofs are purely combinatorial and simpler than the algebraic ones used for similar results about anti-codes in $\mathbb{Z}_k^n$.  Aside from coding theory, the game is also of interest in the study of nowhere-zero points of matrices and nowhere-zero flows and colorings of graphs.
A Discontinuity in the Distribution of Fixed Point Sums
Authors: Bender Edward A. , Canfield E. Rodney , Richmond L. Bruce , Wilf Herbert S.
Published: January 2020

The quantity $f(n,r)$, defined as the number of permutations of the set $[n]=\{1,2,\dots n\}$ whose fixed points sum to $r$, shows a sharp discontinuity in the neighborhood of $r=n$. We explain this discontinuity and study the possible existence of other discontinuities in $f(n,r)$ for permutations. We generalize our results to other families of structures that exhibit the same kind of discontinuities, by studying $f(n,r)$ when "fixed points" is replaced by "components of size 1" in a suitable graph of the structure. Among the objects considered are permutations, all functions and set partitions.
Graphic and Protographic Lists of Integers
Authors: Fon-Der-Flaass Dmitry , West Douglas B.
Published: January 2020

A positive list (list of positive integers) is protographic if its merger with all but finitely many positive graphic lists is graphic. Define the family ${\cal P}_s$ of $s$-protogaphic lists by letting ${\cal P}_0$ be the family of positive graphic lists and letting ${\cal P}_s$ for $s>0$ be the family of positive lists whose merger with all but finitely many lists in ${\cal P}_{s-1}$ is in ${\cal P}_{s-1}$. The main result is that $X\in{\cal P}_s$ if and only if $t(X)\in {\cal P}_{s-1}$, where $t(X)$ is the list obtained from $X$ by subtracting one from each term of $X$ (deleting those that become $0$) and appending a 1 for each term of $X$. A corollary is that the maximum number of iterations to reach a graphic list from an $n$-term even list with sum $2k$ is $k-n+1$ (when $k\ge n$), achieved by the unique such list having one term larger than 1.
Fans and Bundles in the Graph of Pairwise Sums and Products
Authors: Halbeisen Lorenz
Published: January 2020

Let $G^{\times}_{+}$ be the graph on the vertex-set the positive integers ${\Bbb{N}}$, with $n$ joined to $m$ if $n\neq m$ and for some $x,y\in{\Bbb{N}}$ we have $x+y=n$ and $x\cdot y=m$. A pair of triangles sharing an edge (i.e., a $K_4$ with an edge deleted) and containing three consecutive numbers is called a $2$-fan, and three triangles on five numbers having one number in common and containing four consecutive numbers is called a $3$-fan. It will be shown that $G^{\times}_{+}$ contains $3$-fans, infinitely many $2$-fans and even arbitrarily large "bundles" of triangles sharing an edge. Finally, it will be shown that $\chi\big(G^{\times}_{+}\big)\ge 4$.
On Feasible Sets of Mixed Hypergraphs
Authors: Král Daniel
Published: January 2020

A mixed hypergraph $H$ is a triple $(V,{\cal C},{\cal D})$ where $V$ is the vertex set and ${\cal C}$ and ${\cal D}$ are families of subsets of $V$, called ${\cal C}$-edges and ${\cal D}$-edges. A vertex coloring of $H$ is proper if each ${\cal C}$-edge contains two vertices with the same color and each ${\cal D}$-edge contains two vertices with different colors. The spectrum of $H$ is a vector $(r_1,\ldots,r_m)$ such that there exist exactly $r_i$ different colorings using exactly $i$ colors, $r_m\ge 1$ and there is no coloring using more than $m$ colors. The feasible set of $H$ is the set of all $i$'s such that $r_i\ne 0$. We construct a mixed hypergraph with $O(\sum_i\log r_i)$ vertices whose spectrum is equal to $(r_1,\ldots,r_m)$ for each vector of non-negative integers with $r_1=0$. We further prove that for any fixed finite sets of positive integers $A_1\subset A_2$ ($1\notin A_2$), it is NP-hard to decide whether the feasible set of a given mixed hypergraph is equal to $A_2$ even if it is promised that it is either $A_1$ or $A_2$. This fact has several interesting corollaries, e.g., that deciding whether a feasible set of a mixed hypergraph is gap-free is both NP-hard and coNP-hard.
Steiner Triple Systems Intersecting in Pairwise Disjoint Blocks
Authors: Chee Yeow Meng
Published: January 2020

Two Steiner triple systems $(X,{\cal A})$ and $(X,{\cal B})$ are said to intersect in $m$ pairwise disjoint blocks if $|{\cal A}\cap{\cal B}|=m$ and all blocks in ${\cal A}\cap{\cal B}$ are pairwise disjoint. For each $v$, we completely determine the possible values of $m$ such that there exist two Steiner triple systems of order $v$ intersecting in $m$ pairwise disjoint blocks.
Weighted Aztec Diamond Graphs and the Weyl Character Formula
Authors: Benkart Georgia , Eng Oliver
Published: January 2020

Special weight labelings on Aztec diamond graphs lead to sum-product identities through a recursive formula of Kuo. The weight assigned to each perfect matching of the graph is a Laurent monomial, and the identities in these monomials combine to give Weyl's character formula for the representation with highest weight $\rho$ (the half sum of the positive roots) for the classical Lie algebras.
Sur une Généralisation des Coefficients Binomiaux
Authors: Jouhet Frédéric , Lass Bodo , Zeng Jiang
Published: January 2020

We prove a recent conjecture of Lassalle about positivity and integrality of coefficients in some polynomial expansions. We also give a combinatorial interpretation of those numbers. Finally, we show that this question is closely related to the fundamental problem of calculating the linearization coefficients for binomial coefficients.
Random Cayley Graphs are Expanders: a Simple Proof of the Alon–Roichman Theorem
Authors: Landau Zeph , Russell Alexander
Published: January 2020

We give a simple proof of the Alon–Roichman theorem, which asserts that the Cayley graph obtained by selecting $c_\varepsilon \log |G|$ elements, independently and uniformly at random, from a finite group $G$ has expected second eigenvalue no more than $\varepsilon$; here $c_\varepsilon$ is a constant that depends only on $\varepsilon$. In particular, such a graph is an expander with constant probability. Our new proof has three advantages over the original proof: (i.) it is extremely simple, relying only on the decomposition of the group algebra and tail bounds for operator-valued random variables, (ii.) it shows that the $\log |G|$ term may be replaced with $\log D$, where $D \leq |G|$ is the sum of the dimensions of the irreducible representations of $G$, and (iii.) it establishes the result above with a smaller constant $c_\varepsilon$.
Standard Paths in Another Composition Poset
Authors: Snellman Jan
Published: January 2020

Bergeron, Bousquet-Mélou and Dulucq [Ann. Sci. Math. Québec 19 (1995), 139–151] enumerated paths in the Hasse diagram of the following poset: the underlying set is that of all compositions, and a composition $\mu$ covers another composition $\lambda$ if $\mu$ can be obtained from $\lambda$ by adding $1$ to one of the parts of $\lambda$, or by inserting a part of size $1$ into $\lambda$. We employ the methods they developed in order to study the same problem for the following poset, which is of interest because of its relation to non-commutative term orders : the underlying set is the same, but $\mu$ covers $\lambda$ if $\mu$ can be obtained from $\lambda$ by adding $1$ to one of the parts of $\lambda$, or by inserting a part of size $1$ at the left or at the right of $\lambda$. We calculate generating functions for standard paths of fixed width and for standard paths of height $\le 2$.
A Uniformly Distributed Statistic on a Class of Lattice Paths
Authors: Callan David
Published: January 2020

Let ${\cal G}_n$ denote the set of lattice paths from $(0,0)$ to $(n,n)$ with steps of the form $(i,j)$ where $i$ and $j$ are nonnegative integers, not both zero. Let ${\cal D}_n$ denote the set of paths in ${\cal G}_n$ with steps restricted to $(1,0),(0,1),(1,1)$, the so-called Delannoy paths. Stanley has shown that $| {\cal G}_n | =2^{n-1}|{\cal D}_n|$ and Sulanke has given a bijective proof. Here we give a simple statistic on ${\cal G}_n$ that is uniformly distributed over the $2^{n-1}$ subsets of $[n-1]=\{1,2,\ldots,n\}$ and takes the value $[n-1]$ precisely on the Delannoy paths.
Bonferroni-Galambos Inequalities for Partition Lattices
Authors: Dohmen Klaus , Tittmann Peter
Published: January 2020

In this paper, we establish a new analogue of the classical Bonferroni inequalities and their improvements by Galambos for sums of type $\sum_{\pi\in {\Bbb P}(U)} (-1)^{|\pi|-1} (|\pi|-1)! f(\pi)$ where $U$ is a finite set, ${\Bbb P}(U)$ is the partition lattice of $U$ and $f:{\Bbb P}(U)\rightarrow{\Bbb R}$ is some suitable non-negative function. Applications of this new analogue are given to counting connected $k$-uniform hypergraphs, network reliability, and cumulants.
Enumerative Formulae for Unrooted Planar Maps: a Pattern
Authors: Liskovets Valery A.
Published: January 2020

We present uniformly available simple enumerative formulae for unrooted planar $n$-edge maps (counted up to orientation-preserving isomorphism) of numerous classes including arbitrary, loopless, non-separable, eulerian maps and plane trees. All the formulae conform to a certain pattern with respect to the terms of the sum over $t\mid n,\,t\! < \!n.$ Namely, these terms, which correspond to non-trivial automorphisms of the maps, prove to be of the form $\phi\left({n\over t}\right)\alpha\,r^t {k\,t\choose t}$, where $\phi(m)$ is the Euler function, $k$ and $r$ are integer constants and $\alpha$ is a constant or takes only two rational values. On the contrary, the main, "rooted" summand corresponding to $t=n$ contains an additional factor which is a rational function of $n$. Two simple new enumerative results are deduced for bicolored eulerian maps. A collateral aim is to briefly survey recent and old results of unrooted planar map enumeration.
Nonexistence Results for Hadamard-like Matrices
Authors: Christian Justin D. , Shader Bryan L.
Published: January 2020

The class of square $(0,1,-1)$-matrices whose rows are nonzero and mutually orthogonal is studied. This class generalizes the classes of Hadamard and Weighing matrices. We prove that if there exists an $n$ by $n$ $(0,1,-1)$-matrix whose rows are nonzero, mutually orthogonal and whose first row has no zeros, then $n$ is not of the form $p^k$, $2p^k$ or $3p$ where $p$ is an odd prime, and $k$ is a positive integer.
Colored Prüfer Codes for $k$-Edge Colored Trees
Authors: Cho Manwon , Kim Dongsu , Seo Seunghyun , Shin Heesung
Published: January 2020

A combinatorial bijection between $k$-edge colored trees and colored Prüfer codes for labelled trees is established. This bijection gives a simple combinatorial proof for the number $k(n-2)!{nk-n\choose n-2}$ of $k$-edge colored trees with $n$ vertices.
Propagation of Mean Degrees
Authors: Rautenbach Dieter
Published: January 2020

We propose two alternative measures of the local irregularity of a graph in terms of its vertex degrees and relate these measures to the order and the global irregularity of the graph measured by the difference of its maximum and minimum vertex degree.
The Local Theorem for Monotypic Tilings
Authors: Dolbilin Nikolai , Schulte Egon
Published: January 2020

A locally finite face-to-face tiling $\cal T$ of euclidean $d$-space ${\Bbb E}^d$ is monotypic if each tile of $\cal T$ is a convex polytope combinatorially equivalent to a given polytope, the combinatorial prototile of $\cal T$. The paper describes a local characterization of combinatorial tile-transitivity of monotypic tilings in ${\Bbb E}^d$; the result is the Local Theorem for Monotypic Tilings. The characterization is expressed in terms of combinatorial symmetry properties of large enough neighborhood complexes of tiles. The theorem sits between the Local Theorem for Tilings, which describes a local characterization of isohedrality (tile-transitivity) of monohedral tilings (with a single isometric prototile) in ${\Bbb E}^d$, and the Extension Theorem, which gives a criterion for a finite monohedral complex of polytopes to be extendable to a global isohedral tiling of space.
Some New Methods in the Theory of $m$-Quasi-Invariants
Authors: Bell J. , Garsia A. M. , Wallach N.
Published: January 2020

We introduce here a new approach to the study of $m$-quasi-invariants. This approach consists in representing $m$-quasi-invariants as $N^{tuples}$ of invariants. Then conditions are sought which characterize such $N^{tuples}$. We study here the case of $S_3$ $m$-quasi-invariants. This leads to an interesting free module of triplets of polynomials in the elementary symmetric functions $e_1,e_2,e_3$ which explains certain observed properties of $S_3$ $m$-quasi-invariants. We also use basic results on finitely generated graded algebras to derive some general facts about regular sequences of $S_n$ $m$-quasi-invariants
Signed Words and Permutations II; The Euler-Mahonian Polynomials
Authors: Foata Dominique , Han Guo-Niu
Published: January 2020

As for the symmetric group of ordinary permutations there is also a statistical study of the group of signed permutations, that consists of calculating multivariable generating functions for this group by statistics involving record values and the length function. Two approaches are here systematically explored, using the flag-major index on the one hand, and the flag-inversion number on the other hand. The MacMahon Verfahren appears as a powerful tool throughout.
Matroid Inequalities from Electrical Network Theory
Authors: Wagner David G.
Published: January 2020

In 1981, Stanley applied the Aleksandrov–Fenchel Inequalities to prove a logarithmic concavity theorem for regular matroids. Using ideas from electrical network theory we prove a generalization of this for the wider class of matroids with the "half–plane property". Then we explore a nest of inequalities for weighted basis–generating polynomials that are related to these ideas. As a first result from this investigation we find that every matroid of rank three or corank three satisfies a condition only slightly weaker than the conclusion of Stanley's theorem.
Chess Tableaux
Authors: Chow Timothy Y. , Eriksson Henrik , Fan C. Kenneth
Published: January 2020

A chess tableau is a standard Young tableau in which, for all $i$ and $j$, the parity of the entry in cell $(i,j)$ equals the parity of $i+j+1$. Chess tableaux were first defined by Jonas Sjöstrand in his study of the sign-imbalance of certain posets, and were independently rediscovered by the authors less than a year later in the completely different context of composing chess problems with interesting enumerative properties. We prove that the number of $3\times n$ chess tableaux equals the number of Baxter permutations of $n-1$, as a corollary of a more general correspondence between certain three-rowed chess tableaux and certain three-rowed Dulucq-Guibert nonconsecutive tableaux. The correspondence itself is proved by means of an explicit bijection. We also outline how lattice paths, or rat races, can be used to obtain generating functions for chess tableaux. We conclude by explaining the connection to chess problems, and raising some unanswered questions, e.g., there are striking numerical coincidences between chess tableaux and the Charney-Davis statistic; is there a combinatorial explanation?
One-Factorizations of Regular Graphs of Order 12
Authors: Kaski Petteri , Östergård Patric R. J.
Published: January 2020

Algorithms for classifying one-factorizations of regular graphs are studied. The smallest open case is currently graphs of order 12; one-factorizations of $r$-regular graphs of order 12 are here classified for $r\leq 6$ and $r=10,11$. Two different approaches are used for regular graphs of small degree; these proceed one-factor by one-factor and vertex by vertex, respectively. For degree $r=11$, we have one-factorizations of $K_{12}$. These have earlier been classified, but a new approach is presented which views these as certain triple systems on $4n-1$ points and utilizes an approach developed for classifying Steiner triple systems. Some properties of the classified one-factorizations are also tabulated.
Kaleidoscopical Configurations in $G$-Spaces
Authors: Banakh Taras , Petrenko Oleksandr , Protasov Igor , Slobodianiuk Sergiy
Published: January 2020

Let $G$ be a group and $X$ be a $G$-space with the action $G\times X\rightarrow X$, $(g,x)\mapsto gx$. A subset $F$ of $X$ is called a kaleidoscopical configuration if there exists a coloring $\chi:X\rightarrow C$ such that the restriction of $\chi$ on each subset $gF$, $g\in G$, is a bijection. We present a construction (called the splitting construction) of kaleidoscopical configurations in an arbitrary $G$-space, reduce the problem of characterization of kaleidoscopical configurations in a finite Abelian group $G$ to a factorization of $G$ into two subsets, and describe all kaleidoscopical configurations in isometrically homogeneous ultrametric spaces with finite distance scale. Also we construct $2^{\mathfrak c}$ (unsplittable) kaleidoscopical configurations of cardinality $\mathfrak c$ in the Euclidean space $\mathbb{R}^n$.
A Two-Dimensional Pictorial Presentation of Berele's Insertion Algorithm for Symplectic Tableaux
Authors: Roby Tom , Terada Itaru
Published: January 2020

We give the first two-dimensional pictorial presentation of Berele's correspondence, an analogue of the Robinson-Schensted (R-S) correspondence for the symplectic group $Sp(2n, {\Bbb C})$. From the standpoint of representation theory, the R-S correspondence combinatorially describes the irreducible decomposition of the tensor powers of the natural representation of $GL(n,{\Bbb C})$. Berele's insertion algorithm gives the bijection that describes the irreducible decomposition of the tensor powers of the natural representation of $Sp(2n,{\Bbb C})$. Two-dimensional pictorial presentations of the R-S correspondence via local rules (first given by S. Fomin) and its many variants have proven very useful in understanding their properties and creating new generalizations. We hope our new presentation will be similarly useful.
$(-1)$–Enumeration of Self–Complementary Plane Partitions
Authors: Eisenkölbl Theresia
Published: January 2020

We prove a product formula for the remaining cases of the weighted enumeration of self–complementary plane partitions contained in a given box where adding one half of an orbit of cubes and removing the other half of the orbit changes the sign of the weight. We use nonintersecting lattice path families to express this enumeration as a Pfaffian which can be expressed in terms of the known ordinary enumeration of self–complementary plane partitions.
Counting Set Systems by Weight
Authors: Klazar Martin
Published: January 2020

Applying enumeration of sparse set partitions, we show that the number of set systems $H\subset\exp(\{1,2,\dots,n\})$ such that $\emptyset\notin H$, $\sum_{E\in H} |E|=n$ and $\bigcup_{E\in H} E=\{1,2,\dots,m\}$, $m\le n$, equals $(1/\log(2)+o(1))^nb_n$ where $b_n$ is the $n$-th Bell number. The same asymptotics holds if $H$ may be a multiset. If the vertex degrees in $H$ are restricted to be at most $k$, the asymptotics is $(1/\alpha_k+o(1))^nb_n$ where $\alpha_k$ is the unique root of $\sum_{i=1}^k x^i/i!-1$ in $(0,1]$.
The Hook Fusion Procedure
Authors: Grime James
Published: January 2020

We derive a new expression for the diagonal matrix elements of irreducible representations of the symmetric group. We obtain this new expression using Cherednik's fusion procedure. However, instead of splitting Young diagrams into their rows or columns, we consider their principal hooks. This minimises the number of auxiliary parameters needed in the fusion procedure.
On Biembeddings of Latin Squares
Authors: Grannell M. J. , Griggs T. S. , Knor M.
Published: January 2020

A known construction for face 2-colourable triangular embeddings of complete regular tripartite graphs is re-examined from the viewpoint of the underlying Latin squares. This facilitates biembeddings of a wide variety of Latin squares, including those formed from the Cayley tables of the elementary Abelian 2-groups $C_2^k$ ($k\ne 2$). In turn, these biembeddings enable us to increase the best known lower bound for the number of face 2-colourable triangular embeddings of $K_{n,n,n}$ for an infinite class of values of $n$.
Asymptotics of Generating the Symmetric and Alternating Groups
Authors: Dixon John D.
Published: January 2020

The probability that a random pair of elements from the alternating group $A_{n}$ generates all of $A_{n}$ is shown to have an asymptotic expansion of the form $1-1/n-1/n^{2}-4/n^{3}-23/n^{4}-171/n^{5}-... $. This same asymptotic expansion is valid for the probability that a random pair of elements from the symmetric group $S_{n}$ generates either $A_{n}$ or $S_{n}$. Similar results hold for the case of $r$ generators ($r>2$).
Pattern Avoidance Classes and Subpermutations
Authors: Atkinson M. D. , Murphy M. M. , Ruškuc N.
Published: January 2020

Pattern avoidance classes of permutations that cannot be expressed as unions of proper subclasses can be described as the set of subpermutations of a single bijection. In the case that this bijection is a permutation of the natural numbers a structure theorem is given. The structure theorem shows that the class is almost closed under direct sums or has a rational generating function.
Degree Sequences of $F$-Free Graphs
Authors: Pikhurko Oleg , Taraz Anusch
Published: January 2020

Let $F$ be a fixed graph of chromatic number $r+1$. We prove that for all large $n$ the degree sequence of any $F$-free graph of order $n$ is, in a sense, close to being dominated by the degree sequence of some $r$-partite graph. We present two different proofs: one goes via the Regularity Lemma and the other uses a more direct counting argument. Although the latter proof is longer, it gives better estimates and allows $F$ to grow with $n$. As an application of our theorem, we present new results on the generalization of the Turán problem introduced by Caro and Yuster [Electronic J. Combin. 7 (2000)].
Permanents of Hessenberg (0,1)-matrices
Authors: Olesky D. D. , Shader Bryan , Van den Driessche P.
Published: January 2020

Let $P\left( m,n\right) $ denote the maximum permanent of an $n$-by-$n$ lower Hessenberg $(0,1) $-matrix with $m$ entries equal to 1. A "staircased" structure for some matrices achieving this maximum is obtained, and recursive formulas for computing $P\left( m,n\right) $ are given. This structure and results about permanents are used to determine the exact values of $P\left( m,n\right) $ for $n \leq m \leq 8n/3$ and for all $\hbox{nnz}(H_n)-\hbox{nnz}(H_{\lfloor n/2 \rfloor}) \leq m \leq \hbox{nnz}(H_n)$, where $\hbox{nnz}(H_n)=(n^2+3n-2)/2$ is the maximum number of ones in an $n$-by-$n$ Hessenberg $(0,1)$-matrix.
Integer Partitions with Fixed Subsums
Authors: Yakubovich Yu.
Published: January 2020

Given two positive integers $m\le n$, we consider the set of partitions $\lambda=(\lambda_1,\dots,\lambda_\ell,0,\dots)$, $\lambda_1\ge\lambda_2\ge\dots$, of $n$ such that the sum of its parts over a fixed increasing subsequence $(a_j)$ is $m$: $\lambda_{a_1}+\lambda_{a_2}+\dots=m$. We show that the number of such partitions does not depend on $n$ if $m$ is either constant and small relatively to $n$ or depend on $n$ but is close to its largest possible value: $n-ma_1=k$ for fixed $k$ (in the latter case some additional requirements on the sequence $(a_j)$ are needed). This number is equal to the number of so-called colored partitions of $m$ (respectively $k$). It is proved by constructing bijections between these objects.
Vizing-like Conjecture for the Upper Domination of Cartesian Products of Graphs – The Proof
Authors: Brešar Boštjan
Published: January 2020

In this note we prove the following conjecture of Nowakowski and Rall: For arbitrary graphs $G$ and $H$ the upper domination number of the Cartesian product $G \,\square \, H$ is at least the product of their upper domination numbers, in symbols: $\Gamma(G \,\square \, H)\ge \Gamma(G)\Gamma(H).$
Tiling Tripartite Graphs with $3$-Colorable Graphs
Authors: Martin Ryan , Zhao Yi
Published: January 2020

For any positive real number $\gamma$ and any positive integer $h$, there is $N_0$ such that the following holds. Let $N\ge N_0$ be such that $N$ is divisible by $h$. If $G$ is a tripartite graph with $N$ vertices in each vertex class such that every vertex is adjacent to at least $(2/3+ \gamma) N$ vertices in each of the other classes, then $G$ can be tiled perfectly by copies of $K_{h,h,h}$. This extends the work in [Discrete Math. 254 (2002), 289–308] and also gives a sufficient condition for tiling by any fixed 3-colorable graph. Furthermore, we show that the minimum-degree $(2/3+ \gamma) N$ in our result cannot be replaced by $2N/3+ h-2$.
New Lower Bound for Multicolor Ramsey Numbers for Even Cycles
Authors: Dzido Tomasz , Nowik Andrzej , Szuca Piotr
Published: January 2020

For given finite family of graphs $G_{1}, G_{2}, \ldots , G_{k}, k \geq 2$, the multicolor Ramsey number $R(G_{1}, G_{2}, \ldots , G_{k})$ is the smallest integer $n$ such that if we arbitrarily color the edges of the complete graph on $n$ vertices with $k$ colors then there is always a monochromatic copy of $G_{i}$ colored with $i$, for some $1 \leq i \leq k$. We give a lower bound for $k-$color Ramsey number $R(C_{m}, C_{m}, \ldots , C_{m})$, where $m \geq 4$ is even and $C_{m}$ is the cycle on $m$ vertices.
Triangulations and the Hajós Conjecture
Authors: Mohar Bojan
Published: January 2020

The Hajós Conjecture was disproved in 1979 by Catlin. Recently, Thomassen showed that there are many ways that Hajós conjecture can go wrong. On the other hand, he observed that locally planar graphs and triangulations of the projective plane and the torus satisfy Hajós Conjecture, and he conjectured that the same holds for arbitrary triangulations of closed surfaces. In this note we disprove the conjecture and show that there are different reasons why the Hajós Conjecture fails also for triangulations.
A Simple Proof for the Existence of Exponentially Balanced Gray Codes
Authors: Suparta I Nengah
Published: January 2020

A Gray code of length $n$ is a circular list of all $2^n$ bitstrings or binary codewords of length $n$ such that successive codewords differ in only one bit position. The frequencies of the positions where these differences occur are called transition counts. An exponentially balanced Gray code is a Gray code the transition counts of which are all the same power of two, or are two successive powers of two. A proof for the existence of exponentially balanced Gray codes is derived. The proof is much simpler than an earlier proof presented by van Zanten and Suparta (Discrete Analysis and Operation Research, 11 (2004) 81-98 (Russian Journal)).
Using Homological Duality in Consecutive Pattern Avoidance
Authors: Khoroshkin Anton , Shapiro Boris
Published: January 2020

Using an approach suggested by Dotsenko and Khoroshkin we present a sufficient condition guaranteeing that two collections of patterns of permutations have the same exponential generating functions for the number of permutations avoiding elements of these collections as consecutive patterns. In short, the coincidence of the latter generating functions is guaranteed by a length-preserving bijection of patterns in these collections which is identical on the overlappings of pairs of patterns where the overlappings are considered as unordered sets. Our proof is based on a direct algorithm for the computation of the inverse generating functions. As an application we present a large class of patterns where this algorithm is fast and, in particular, allows us to obtain a linear ordinary differential equation with polynomial coefficients satisfied by the inverse generating function.
Polynomial Generalizations of Two-Variable Ramanujan Type Identities
Authors: McLaughlin James , Sills Andrew V.
Published: January 2020

We provide finite analogs of a pair of two-variable $q$-series identities from Ramanujan's lost notebook and a companion identity.