bluuebunny/crossref_metadata_2025 huggingface dataset:
Improved Coverings of a Square with Six and Eight Equal Circles
Authors: Melissen J. B. M. , Schuur P. C.
Published: January 2020

In a recent article, Tarnai and Gáspár used computer simulations to find thin coverings of a square with up to ten equal circles. We will give improved coverings with six and eight circles and a new, thin covering with eleven circles, found by the use of simulated annealing. Furthermore, we present a combinatorial method for constructing lower bounds for the optimal covering radius.
Affine Permutations of Type $A$
Authors: Björner Anders , Brenti Francesco
Published: January 2020

We study combinatorial properties, such as inversion table, weak order and Bruhat order, for certain infinite permutations that realize the affine Coxeter group $\tilde{A}_{n}$.
Some Equidistributed Statistics on Genocchi Permutations
Authors: Randrianarivony Arthur , Zeng Jiang
Published: January 2020

A Genocchi permutation $\sigma $ of $[2n]$ is a permutation such that $\sigma (2i-1)>2i-1,\quad \sigma (2i)\leq 2i$ for all $i\in \{1, 2, \ldots, 2n\}$. The purpose of this paper is to investigate the equidistribution of several bivariate statistics on the Genocchi permutations.
Affine Permutations and Inversion Multigraphs
Authors: Papi Paolo
Published: January 2020

In this paper we solve the problem of characterizing inversion multigraphs associated to affine permutations.
On Random Greedy Triangle Packing
Authors: Grable David A.
Published: January 2020

The behaviour of the random greedy algorithm for constructing a maximal packing of edge-disjoint triangles on $n$ points (a maximal partial triple system) is analysed with particular emphasis on the final number of unused edges. It is shown that this number is at most $n^{7/4+o(1)}$, "halfway" from the previous best-known upper bound $o(n^2)$ to the conjectured value $n^{3/2+o(1)}$. The more general problem of random greedy packing in hypergraphs is also considered.
Near Threshold Graphs
Authors: Kirkland Steve
Published: January 2020

A conjecture of Grone and Merris states that for any graph $G$, its Laplacian spectrum, $\Lambda(G)$, is majorized by its conjugate degree sequence, $D^*(G)$. That conjecture prompts an investigation of the relationship between $\Lambda(G)$ and $D^*(G),$ and Merris has characterized the graphs $G$ for which the multisets $\Lambda(G)$ and $D^*(G)$ are equal. In this paper, we provide a constructive characterization of the graphs $G$ for which $\Lambda(G)$ and $D^*(G)$ share all but two elements.
Combinatorial Approaches and Conjectures for 2-Divisibility Problems Concerning Domino Tilings of Polyominoes
Authors: Pachter Lior
Published: January 2020

We give the first complete combinatorial proof of the fact that the number of domino tilings of the $2n \times 2n$ square grid is of the form $2^n(2k+1)^2$, thus settling a question raised by John, Sachs, and Zernitz. The proof lends itself naturally to some interesting generalizations, and leads to a number of new conjectures.
Dodgson's Determinant-Evaluation Rule Proved by Two-Timing Men and Women
Authors: Zeilberger Doron
Published: January 2020

I give a bijective proof of the Reverend Charles Lutwidge Dodgson's Rule: $$ \det \left [ (a_{i,j})_{ {1 \leq i \leq n } \atop {1 \leq j \leq n }} \right ] \cdot \det \left [ (a_{i,j})_{ {2 \leq i \leq n-1 } \atop {2 \leq j \leq n-1 }} \right ] \, = $$ $$ \det \left [ (a_{i,j})_{ {1 \leq i \leq n-1 } \atop {1 \leq j \leq n-1 }} \right ] \cdot \det \left [ (a_{i,j})_{ {2 \leq i \leq n } \atop {2 \leq j \leq n }} \right ] \,-\, \det \left [ (a_{i,j})_{ {1 \leq i \leq n-1 } \atop {2 \leq j \leq n }} \right ] \cdot \det \left [ (a_{i,j})_{ {2 \leq i \leq n } \atop {1 \leq j \leq n-1 }} \right ]\quad . $$
Extremal Infinite Overlap-Free Binary Words
Authors: Allouche Jean-Paul , Currie James , Shallit Jeffrey
Published: January 2020

Let $\overline{\bf t}$ be the infinite fixed point, starting with $1$, of the morphism $\mu: 0 \rightarrow 01$, $1 \rightarrow 10$. An infinite word over $\lbrace 0, 1 \rbrace$ is said to be overlap-free if it contains no factor of the form $axaxa$, where $a \in \lbrace 0,1 \rbrace$ and $x \in \lbrace 0,1 \rbrace^*$. We prove that the lexicographically least infinite overlap-free binary word beginning with any specified prefix, if it exists, has a suffix which is a suffix of $\overline{\bf t}$. In particular, the lexicographically least infinite overlap-free binary word is $001001 \overline{\bf t}$.
Some New Ramsey Colorings
Authors: Exoo Geoffrey
Published: January 2020

New lower bounds for 15 classical Ramsey numbers are established. Several of the colorings are found using a new variation of local search heuristics. Several others are found using known colorings as building blocks.
A Multivariate Lagrange Inversion Formula for Asymptotic Calculations
Authors: Bender Edward A. , Richmond L. Bruce
Published: January 2020

The determinant that is present in traditional formulations of multivariate Lagrange inversion causes difficulties when one attempts to obtain asymptotic information. We obtain an alternate formulation as a sum of terms, thereby avoiding this difficulty.
Combinatorial Aspects of Multiple Zeta Values
Authors: Borwein Jonathan M. , Bradley David M. , Broadhurst David J. , Lisoněk Petr
Published: January 2020

Multiple zeta values (MZVs, also called Euler sums or multiple harmonic series) are nested generalizations of the classical Riemann zeta function evaluated at integer values. The fact that an integral representation of MZVs obeys a shuffle product rule allows the possibility of a combinatorial approach to them. Using this approach we prove a longstanding conjecture of Don Zagier about MZVs with certain repeated arguments. We also prove a similar cyclic sum identity. Finally, we present extensive computational evidence supporting an infinite family of conjectured MZV identities that simultaneously generalize the Zagier identity.
On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents
Authors: Galluccio Anna , Loebl Martin
Published: January 2020

Kasteleyn stated that the generating function of the perfect matchings of a graph of genus $g$ may be written as a linear combination of $4^g$ Pfaffians. Here we prove this statement. As a consequence we present a combinatorial way to compute the permanent of a square matrix.
Rhombus Tilings of a Hexagon with Two Triangles Missing on the Symmetry Axis
Authors: Eisenkölbl Theresia
Published: January 2020

We compute the number of rhombus tilings of a hexagon with sides $n$, $n$, $N$, $n$, $n$, $N$, where two triangles on the symmetry axis touching in one vertex are removed. The case of the common vertex being the center of the hexagon solves a problem posed by Propp.
A Closer Look at Lattice Points in Rational Simplices
Authors: Beck Matthias
Published: January 2020

We generalize Ehrhart's idea of counting lattice points in dilated rational polytopes: Given a rational simplex, that is, an $n$-dimensional polytope with $n+1$ rational vertices, we use its description as the intersection of $n+1$ halfspaces, which determine the facets of the simplex. Instead of just a single dilation factor, we allow different dilation factors for each of these facets. We give an elementary proof that the lattice point counts in the interior and closure of such a vector-dilated simplex are quasipolynomials satisfying an Ehrhart-type reciprocity law. This generalizes the classical reciprocity law for rational polytopes. As an example, we derive a lattice point count formula for a rectangular rational triangle, which enables us to compute the number of lattice points inside any rational polygon.
Small Maximal Sum-Free Sets
Authors: Giudici Michael , Hart Sarah
Published: January 2020

Let $G$ be a group and $S$ a non-empty subset of $G$. If $ab \notin S$ for any $a, b \in S$, then $S$ is called sum-free. We show that if $S$ is maximal by inclusion and no proper subset generates $\langle S\rangle$ then $|S|\leq 2$. We determine all groups with a maximal (by inclusion) sum-free set of size at most 2 and all of size 3 where there exists $a \in S$ such that $a \notin \langle S \setminus \{a\}\rangle$.
Where the Typical Set Partitions Meet and Join
Authors: Pittel Boris
Published: January 2020

The lattice of the set partitions of $[n]$ ordered by refinement is studied. Suppose $r$ partitions $p_1,\dots,p_r$ are chosen independently and uniformly at random. The probability that the coarsest refinement of all $p_i$'s is the finest partition $\bigl\{\{1\},\dots,\{n\}\bigr\}$ is shown to approach $0$ for $r=2$, and $1$ for $r\ge 3$. The probability that the finest coarsening of all $p_i$'s is the one-block partition is shown to approach $1$ for every $r\ge 2$.
The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted subgraphs and their complements
Authors: Hagos Elias M.
Published: January 2020

The question of whether the characteristic polynomial of a simple graph is uniquely determined by the characteristic polynomials of its vertex-deleted subgraphs is one of the many unresolved problems in graph reconstruction. In this paper we prove that the characteristic polynomial of a graph is reconstructible from the characteristic polynomials of the vertex-deleted subgraphs of the graph and its complement.
Tournament Sequences and Meeussen Sequences
Authors: Cook Matthew , Kleber Michael
Published: January 2020

A tournament sequence is an increasing sequence of positive integers $(t_1,t_2,\ldots)$ such that $t_1=1$ and $t_{i+1} \leq 2t_i$. A Meeussen sequence is an increasing sequence of positive integers $(m_1,m_2,\ldots)$ such that $m_1=1$, every nonnegative integer is the sum of a subset of the $\{m_i\}$, and each integer $m_i-1$ is the sum of a unique such subset. We show that these two properties are isomorphic. That is, we present a bijection between tournament and Meeussen sequences which respects the natural tree structure on each set. We also present an efficient technique for counting the number of tournament sequences of length $n$, and discuss the asymptotic growth of this number. The counting technique we introduce is suitable for application to other well-behaved counting problems of the same sort where a closed form or generating function cannot be found.
A Turán Type Problem Concerning the Powers of the Degrees of a Graph
Authors: Caro Yair , Yuster Raphael
Published: January 2020

For a graph $G$ whose degree sequence is $d_{1},\ldots ,d_{n}$, and for a positive integer $p$, let $e_{p}(G)=\sum_{i=1}^{n}d_{i}^{p}$. For a fixed graph $H$, let $t_{p}(n,H)$ denote the maximum value of $e_{p}(G)$ taken over all graphs with $n$ vertices that do not contain $H$ as a subgraph. Clearly, $t_{1}(n,H)$ is twice the Turán number of $H$. In this paper we consider the case $p>1$. For some graphs $H$ we obtain exact results, for some others we can obtain asymptotically tight upper and lower bounds, and many interesting cases remain open.
Hadamard Matrices and Strongly Regular Graphs with the $3$-e.c. Adjacency Property
Authors: Bonato Anthony , Holzmann W. H. , Kharaghani Hadi
Published: January 2020

A graph is $3$-e.c. if for every $3$-element subset $S$ of the vertices, and for every subset $T$ of $S$, there is a vertex not in $S$ which is joined to every vertex in $T$ and to no vertex in $S\setminus T$. Although almost all graphs are $3$-e.c., the only known examples of strongly regular $3$-e.c. graphs are Paley graphs with at least $29$ vertices. We construct a new infinite family of $3$-e.c. graphs, based on certain Hadamard matrices, that are strongly regular but not Paley graphs. Specifically, we show that Bush-type Hadamard matrices of order $16n^2$ give rise to strongly regular $3$-e.c. graphs, for each odd $n$ for which $4n$ is the order of a Hadamard matrix.
On Catalan Trees and the Jacobian Conjecture
Authors: Singer Dan
Published: January 2020

New combinatorial properties of Catalan trees are established and used to prove a number of algebraic results related to the Jacobian conjecture. Let $F=(x_1+H_1,x_2+H_2,\dots,x_n+H_n)$ be a system of $n$ polynomials in $C[x_1,x_2,\dots,x_n]$, the ring of polynomials in the variables $x_1,x_2, \dots, x_n$ over the field of complex numbers. Let $H=(H_1,H_2,\dots,H_n)$. Our principal algebraic result is that if the Jacobian of $F$ is equal to 1, the polynomials $H_i$ are each homogeneous of total degree 2, and $({{\partial H_i}\over {\partial x_j}})^3=0$, then $H\circ H\circ H=0$ and $F$ has an inverse of the form $G=(G_1,G_2,\dots,G_n)$, where each $G_i$ is a polynomial of total degree $\le6$. We prove this by showing that the sum of weights of Catalan trees over certain equivalence classes is equal to zero. We also show that if all of the polynomials $H_i$ are homogeneous of the same total degree $d\ge2$ and $({{\partial H_i}\over {\partial x_j}})^2=0$, then $H\circ H=0$ and the inverse of $F$ is $G=(x_1-H_1,\dots,x_n-H_n)$.
A Note on the Glauber Dynamics for Sampling Independent Sets
Authors: Vigoda Eric
Published: January 2020

This note considers the problem of sampling from the set of weighted independent sets of a graph with maximum degree $\Delta$. For a positive fugacity $\lambda$, the weight of an independent set $\sigma$ is $\lambda^{|\sigma|}$. Luby and Vigoda proved that the Glauber dynamics, which only changes the configuration at a randomly chosen vertex in each step, has mixing time $O(n\log{n})$ when $\lambda < {{2}\over {\Delta-2}}$ for triangle-free graphs. We extend their approach to general graphs.
Circular Chromatic Number of Planar Graphs of Large Odd Girth
Authors: Zhu Xuding
Published: January 2020

It was conjectured by Jaeger that $4k$-edge connected graphs admit a $(2k+1, k)$-flow. The restriction of this conjecture to planar graphs is equivalent to the statement that planar graphs of girth at least $4k$ have circular chromatic number at most $2+ {{1}\over {k}}$. Even this restricted version of Jaeger's conjecture is largely open. The $k=1$ case is the well-known Grötzsch 3-colour theorem. This paper proves that for $k \geq 2$, planar graphs of odd girth at least $8k-3$ have circular chromatic number at most $2+{{1}\over {k}}$.
The Well-Rounded Linear Function
Authors: Eggleton Roger B.
Published: January 2020

The generic linear function $ax+b$ of a real variable, with $a, b, x \in {\bf R}$, is usually evaluated as a scale function (product) followed by a translation (sum). Our main result shows that when such a function is variously combined with rounding functions (floor and ceiling), exactly 67 inequivalent rounded generic linear functions result, of which 38 are integer-valued and 29 are not. Several related results are also established, with elucidation of the relevant equivalence class structures.
Exchange Symmetries in Motzkin Path and Bargraph Models of Copolymer Adsorption
Authors: Janse van Rensburg E. J. , Rechnitzer A.
Published: January 2020

In a previous work [26], by considering paths that are partially weighted, the generating function of Dyck paths was shown to possess a type of symmetry, called an exchange relation, derived from the exchange of a portion of the path between weighted and unweighted halves. This relation is particularly useful in solving for the generating functions of certain models of vertex-coloured Dyck paths; this is a directed model of copolymer adsorption, and in a particular case it is possible to find an asymptotic expression for the adsorption critical point of the model as a function of the colouring. In this paper we examine Motzkin path and partially directed walk models of the same adsorbing directed copolymer problem. These problems are an interesting generalisation of previous results since the colouring can be of either the edges, or the vertices, of the paths. We are able to find asymptotic expressions for the adsorption critical point in the Motzkin path model for both edge and vertex colourings, and for the partially directed walk only for edge colourings. The vertex colouring problem in partially directed walks seems to be beyond the scope of the methods of this paper, and remains an open question. In both these cases we first find exchange relations for the generating functions, and use those to find the asymptotic expression for the adsorption critical point.
Compositions of Random Functions on a Finite Set
Authors: Dalal Avinash , Schmutz Eric
Published: January 2020

If we compose sufficiently many random functions on a finite set, then the composite function will be constant. We determine the number of compositions that are needed, on average. Choose random functions $f_1, f_2,f_3,\dots $ independently and uniformly from among the $n^n$ functions from $[n]$ into $[n]$. For $t>1$, let $g_t=f_t\circ f_{t-1}\circ \cdots \circ f_1$ be the composition of the first $t$ functions. Let $T$ be the smallest $t$ for which $g_t$ is constant(i.e. $g_t(i)=g_t(j)$ for all $i,j$). We prove that $E(T)\sim 2n$ as $n\rightarrow\infty$, where $E(T)$ denotes the expected value of $T$.
Spanning Trees and Function Classes
Authors: Remmel Jeffery B. , Williamson S. Gill
Published: January 2020

If $G=K_n$ is the complete graph, the classical Prüffer correspondence gives a natural bijection between all spanning trees of $G$ (i.e., all Cayley trees) and all functions from a set of $n-2$ elements to a set of $n$ elements. If $G$ is a complete multipartite graph, then such bijections have been studied by Eğecioğlu and Remmel. In this paper, we define a class of directed graphs, called filtered digraphs, and describe a natural class of bijections between oriented spanning forests of these digraphs and associated classes of functions. We derive multivariate generating functions for the oriented spanning forests which arise in this context, and we link basic properties of these spanning forests to properties of the functions to which they correspond. This approach yields a number of new results for directed graphs. Moreover, in the undirected case, various specializations of our multivariate generating function not only include various known results but also give a number of new results.
Thue-like Sequences and Rainbow Arithmetic Progressions
Authors: Grytczuk Jaroslaw
Published: January 2020

A sequence $u=u_{1}u_{2}...u_{n}$ is said to be nonrepetitive if no two adjacent blocks of $u$ are exactly the same. For instance, the sequence $a{\bf bcbc}ba$ contains a repetition $bcbc$, while $abcacbabcbac$ is nonrepetitive. A well known theorem of Thue asserts that there are arbitrarily long nonrepetitive sequences over the set $\{a,b,c\}$. This fact implies, via König's Infinity Lemma, the existence of an infinite ternary sequence without repetitions of any length. In this paper we consider a stronger property defined as follows. Let $k\geq 2$ be a fixed integer and let $C$ denote a set of colors (or symbols). A coloring $f:{\bf N}\rightarrow C$ of positive integers is said to be $k$-nonrepetitive if for every $r\geq 1$ each segment of $kr$ consecutive numbers contains a $k$-term rainbow arithmetic progression of difference $r$. In particular, among any $k$ consecutive blocks of the sequence $f=f(1)f(2)f(3)...$ no two are identical. By an application of the Lovász Local Lemma we show that the minimum number of colors in a $k$-nonrepetitive coloring is at most $2^{-1}e^{k(2k-1)/(k-1)^{2}}k^{2}(k-1)+1$. Clearly at least $k+1$ colors are needed but whether $O(k)$ suffices remains open. This and other types of nonrepetitiveness can be studied on other structures like graphs, lattices, Euclidean spaces, etc., as well. Unlike for the classical Thue sequences, in most of these situations non-constructive arguments seem to be unavoidable. A few of a range of open problems appearing in this area are presented at the end of the paper.
The Minimum Number of Monotone Subsequences
Authors: Myers Joseph Samuel
Published: January 2020

Erdős and Szekeres showed that any permutation of length $n \geq k^2+1$ contains a monotone subsequence of length $k+1$. A simple example shows that there need be no more than $(n \bmod k){{\lceil n/k \rceil}\choose {k+1}} + (k - (n \bmod k)){{\lfloor n/k \rfloor}\choose {k+1}}$ such subsequences; we conjecture that this is the minimum number of such subsequences. We prove this for $k=2$, with a complete characterisation of the extremal permutations. For $k > 2$ and $n \geq k(2k-1)$, we characterise the permutations containing the minimum number of monotone subsequences of length $k+1$ subject to the additional constraint that all such subsequences go in the same direction (all ascending or all descending); we show that there are $2 {{k}\choose {n \bmod k}} C_k^{2k-2}$ such extremal permutations, where $C_k = {{1}\over {k+1}}{{2k}\choose {k}}$ is the $k^{{\rm th}}$ Catalan number. We conjecture, with some supporting computational evidence, that permutations with a minimum number of monotone $(k+1)$-subsequences must have all such subsequences in the same direction if $n \geq k(2k-1)$, except for the case of $k = 3$ and $n = 16$.
Permutations Avoiding Two Patterns of Length Three
Authors: Vatter Vincent R.
Published: January 2020

We study permutations that avoid two distinct patterns of length three and any additional set of patterns. We begin by showing how to enumerate these permutations using generating trees, generalizing the work of Mansour [13]. We then find sufficient conditions for when the number of such permutations is given by a polynomial and answer a question of Egge [6]. Afterwards, we show how to use these computations to count permutations that avoid two distinct patterns of length three and contain other patterns a prescribed number of times.
Colouring the Petals of a Graph
Authors: Cariolaro David , Cariolaro Gianfranco
Published: January 2020

A petal graph is a connected graph $G$ with maximum degree three, minimum degree two, and such that the set of vertices of degree three induces a $2$–regular graph and the set of vertices of degree two induces an empty graph. We prove here that, with the single exception of the graph obtained from the Petersen graph by deleting one vertex, all petal graphs are Class $1$. This settles a particular case of a conjecture of Hilton and Zhao.
The Neighborhood Characteristic Parameter for Graphs
Authors: McKee Terry A.
Published: January 2020

Define the neighborhood characteristic of a graph to be $s_1 - s_2 + s_3 - \cdots$, where $s_i$ counts subsets of $i$ vertices that are all adjacent to some vertex outside the subset. This amounts to replacing cliques by neighborhoods in the traditional 'Euler characteristic' (the number of vertices, minus the number of edges, plus the number of triangles, etc.). The neighborhood characteristic can also be calculated by knowing, for all $i,j \ge 2$, how many $K_{i,j}$ subgraphs there are or, through an Euler-Poincaré-type theorem, by knowing how those subgraphs are arranged. Chordal bipartite graphs are precisely the graphs for which every nontrivial connected induced subgraph has neighborhood characteristic 2.
A Note on Graph Coloring Extensions and List-Colorings
Authors: Axenovich Maria
Published: January 2020

Let $G$ be a graph with maximum degree $\Delta \geq 3$ not equal to $K_{\Delta +1}$ and let $P$ be a subset of vertices with pairwise distance, $d(P)$, between them at least $8$. Let each vertex $x$ be assigned a list of colors of size $\Delta$ if $x\in V\setminus P$ and $1$ if $x\in P$. We prove that it is possible to color $V(G)$ such that adjacent vertices receive different colors and each vertex has a color from its list. We show that $d(P)$ cannot be improved. This generalization of Brooks' theorem answers the following question of Albertson positively: If $G$ and $P$ are objects described above, can any coloring of $P$ in at most $\Delta$ colors be extended to a proper coloring of $G$ in at most $\Delta$ colors?
Minuscule Heaps over Dynkin Diagrams of Type $\tilde{A}$
Authors: Hagiwara Manabu
Published: January 2020

A minuscule heap is a partially ordered set, together with a labeling of its elements by the nodes of a Dynkin diagram, satisfying certain conditions derived by J. Stembridge. This paper classifies the minuscule heaps over the Dynkin diagram of type $\tilde{A}$.
Chromatically Unique Multibridge Graphs
Authors: Dong F. M. , Teo K. L. , Little C. H. C. , Hendy M. , Koh K. M.
Published: January 2020

Let $\theta(a_1,a_2,\cdots,a_k)$ denote the graph obtained by connecting two distinct vertices with $k$ independent paths of lengths $a_1,a_2,$ $\cdots,a_k$ respectively. Assume that $2\le a_1\le a_2\le \cdots \le a_k$. We prove that the graph $\theta(a_1,a_2, \cdots,a_k)$ is chromatically unique if $a_k < a_1+a_2$, and find examples showing that $\theta(a_1,a_2, \cdots,a_k)$ may not be chromatically unique if $a_k=a_1+a_2$.
Improved Bounds on the Length of Maximal Abelian Square-Free Words
Authors: Bullock Evan M.
Published: January 2020

A word is abelian square-free if it does not contain two adjacent subwords which are permutations of each other. Over an alphabet $\Sigma_k$ on $k$ letters, an abelian square-free word is maximal if it cannot be extended to the left or right by letters from $\Sigma_k$ and remain abelian square-free. Michael Korn proved that the length $\ell (k)$ of a shortest maximal abelian square-free word satisfies $4k-7\leq \ell(k)\leq 6k-10$ for $k\geq 6$. In this paper, we refine Korn's methods to show that $6k-29\leq \ell(k)\leq 6k-12$ for $k\geq 8$.
Equilateral Triangles in Finite Metric Spaces
Authors: Mascioni Vania
Published: January 2020

In the context of finite metric spaces with integer distances, we investigate the new Ramsey-type question of how many points can a space contain and yet be free of equilateral triangles. In particular, for finite metric spaces with distances in the set $\{1,\ldots,n\}$, the number $D_n$ is defined as the least number of points the space must contain in order to be sure that there will be an equilateral triangle in it. Several issues related to these numbers are studied, mostly focusing on low values of $n$. Apart from the trivial $D_1=3$, $D_2=6$, we prove that $D_3=12$, $D_4=33$ and $81\leq D_5 \leq 95$.
On a Combinatorial Problem of Asmus Schmidt
Authors: Zudilin W.
Published: January 2020

For any integer $r\ge2$, define a sequence of numbers $\{c_k^{(r)}\}_{k=0,1,\dots}$, independent of the parameter $n$, by $$ \sum_{k=0}^n{n\choose k}^r{n+k\choose k}^r =\sum_{k=0}^n{n\choose k}{n+k\choose k}c_k^{(r)}, \qquad n=0,1,2,\dots. $$ We prove that all the numbers $c_k^{(r)}$ are integers.
Permutations Avoiding Arithmetic Patterns
Authors: Hegarty Peter
Published: January 2020

A permutation $\pi$ of an abelian group $G$ (that is, a bijection from $G$ to itself) will be said to avoid arithmetic progressions if there does not exist any triple $(a,b,c)$ of elements of $G$, not all equal, such that $c-b=b-a$ and $\pi(c)-\pi(b)=\pi(b)- \pi(a)$. The basic question is, which abelian groups possess such a permutation? This and problems of a similar nature will be considered.
Antichains on Three Levels
Authors: Lieby Paulette
Published: January 2020

An antichain is a collection of sets in which no two sets are comparable under set inclusion. An antichain ${\cal A}$ is flat if there exists an integer $k\geq 0$ such that every set in ${\cal A}$ has cardinality either $k$ or $k+1$. The size of ${\cal A}$ is $|{\cal A}|$ and the volume of ${\cal A}$ is $\sum_{A\in{\cal A}}|A|$. The flat antichain theorem states that for any antichain ${\cal A}$ on $[n]=\{1,2,\ldots,n\}$ there exists a flat antichain on $[n]$ with the same size and volume as ${\cal A}$. In this paper we present a key part of the proof of the flat antichain theorem, namely we show that the theorem holds for antichains on three consecutive levels; that is, in which every set has cardinality $k+1$, $k$ or $k-1$ for some integer $k\geq 1$. In fact we prove a stronger result which should be of independent interest. Using the fact that the flat antichain theorem holds for antichains on three consecutive levels, together with an unpublished result by the author and A. Woods showing that the theorem also holds for antichains on four consecutive levels, Á. Kisvölcsey completed the proof of the flat antichain theorem. This proof is to appear in Combinatorica. The squashed (or colex) order on sets is the set ordering with the property that the number of subsets of a collection of sets of size $k$ is minimised when the collection consists of an initial segment of sets of size $k$ in squashed order. Let $p$ be a positive integer, and let ${\cal A}$ consist of $p$ subsets of $[n]$ of size $k+1$ such that, in the squashed order, these subsets are consecutive. Let ${\cal B}$ consist of any $p$ subsets of $[n]$ of size $k-1$. Let $|\triangle_N{\cal A}|$ be the number of subsets of size $k$ of the sets in ${\cal A}$ which are not subsets of any set of size $k+1$ preceding the sets in ${\cal A}$ in the squashed order. Let $|{\bigtriangledown}{\cal B}|$ be the number of supersets of size $k$ of the sets in ${\cal B}$. We show that $|\triangle_N{\cal A}| + |{\bigtriangledown}{\cal B}| > 2 p$. We call this result the 3-levels result. The 3-levels result implies that the flat antichain theorem is true for antichains on at most three, consecutive, levels.
Multiple Pattern Avoidance with respect to Fixed Points and Excedances
Authors: Elizalde Sergi
Published: January 2020

We study the distribution of the statistics 'number of fixed points' and 'number of excedances' in permutations avoiding subsets of patterns of length 3. We solve all the cases of simultaneous avoidance of more than one pattern, giving generating functions enumerating these two statistics. Some cases are generalized to patterns of arbitrary length. For avoidance of one single pattern we give partial results. We also describe the distribution of these statistics in involutions avoiding any subset of patterns of length 3. The main technique is to use bijections between pattern-avoiding permutations and certain kinds of Dyck paths, in such a way that the statistics in permutations that we study correspond to statistics on Dyck paths that are easy to enumerate.
A $\lambda$-ring Frobenius Characteristic for $G\wr S_n$
Authors: Mendes Anthony , Remmel Jeffrey , Wagner Jennifer
Published: January 2020

A $\lambda$-ring version of a Frobenius characteristic for groups of the form $G \wr S_n$ is given. Our methods provide natural analogs of classic results in the representation theory of the symmetric group. Included is a method decompose the Kronecker product of two irreducible representations of $G\wr S_n$ into its irreducible components along with generalizations of the Murnaghan-Nakayama rule, the Hall inner product, and the reproducing kernel for $G\wr S_n$.
On-line Ramsey Theory
Authors: Grytczuk J. A. , Hałuszczak M. , Kierstead H. A.
Published: January 2020

The Ramsey game we consider in this paper is played on an unbounded set of vertices by two players, called Builder and Painter. In one move Builder introduces a new edge and Painter paints it red or blue. The goal of Builder is to force Painter to create a monochromatic copy of a fixed target graph $H$, keeping the constructed graph in a prescribed class ${\cal G}$. The main problem is to recognize the winner for a given pair $H,{\cal G}$. In particular, we prove that Builder has a winning strategy for any $k$-colorable graph $H$ in the game played on $k$-colorable graphs. Another class of graphs with this strange self-unavoidability property is the class of forests. We show that the class of outerplanar graphs does not have this property. The question of whether planar graphs are self-unavoidable is left open. We also consider a multicolor version of Ramsey on-line game. To extend our main result for $3$-colorable graphs we introduce another Ramsey type game, which seems interesting in its own right.
Short Cycles in Random Regular Graphs
Authors: McKay Brendan D. , Wormald Nicholas C. , Wysocka Beata
Published: January 2020

Consider random regular graphs of order $n$ and degree $d=d(n)\ge 3$. Let $g=g(n)\ge 3$ satisfy $(d-1)^{2g-1}=o(n)$. Then the number of cycles of lengths up to $g$ have a distribution similar to that of independent Poisson variables. In particular, we find the asymptotic probability that there are no cycles with sizes in a given set, including the probability that the girth is greater than $g$. A corresponding result is given for random regular bipartite graphs.
On the $q$-Analogue of the Sum of Cubes
Authors: Warnaar S. Ole
Published: January 2020

A simple $q$-analogue of the sum of cubes is given. This answers a question posed in this journal by Garrett and Hummel.
A Binomial Coefficient Identity Associated with Beukers' Conjecture on Apéry numbers
Authors: Chu Wenchang
Published: January 2020

By means of partial fraction decomposition, an algebraic identity on rational function is established. Its limiting case leads us to a harmonic number identity, which in turn has been shown to imply Beukers' conjecture on the congruence of Apéry numbers.
On a Partition Function of Richard Stanley
Authors: Andrews George E.
Published: January 2020

In this paper, we examine partitions $\pi$ classified according to the number $r(\pi)$ of odd parts in $\pi$ and $s(\pi)$ the number of odd parts in $\pi\prime$, the conjugate of $\pi$. The generating function for such partitions is obtained when the parts of $\pi$ are all $\leq N$. From this a variety of corollaries follow including a Ramanujan type congruence for Stanley's partition function $t(n)$.
Asymptotics for the Distributions of Subtableaux in Young and Up-Down Tableaux
Authors: Grabiner David J.
Published: January 2020

Let $\mu$ be a partition of $k$, and $T$ a standard Young tableau of shape $\mu$. McKay, Morse, and Wilf show that the probability a randomly chosen Young tableau of $N$ cells contains $T$ as a subtableau is asymptotic to $f^\mu/k!$ as $N$ goes to infinity, where $f^\mu$ is the number of all tableaux of shape $\mu$. We use a random-walk argument to show that the analogous asymptotic probability for randomly chosen Young tableaux with at most $n$ rows is proportional to $\prod_{1\le i < j\le n}\bigl((\mu_i-i)-(\mu_j-j)\bigr)$; as $n$ goes to infinity, the probabilities approach $f^\mu/k!$ as expected. We have a similar formula for up-down tableaux; the probability approaches $f^\mu/k!$ if $\mu$ has $k$ cells and thus the up-down tableau is actually a standard tableau, and approaches 0 if $\mu$ has fewer than $k$ cells.
The Active Bijection between Regions and Simplices in Supersolvable Arrangements of Hyperplanes
Authors: Gioan Emeric , Las Vergnas Michel
Published: January 2020

Comparing two expressions of the Tutte polynomial of an ordered oriented matroid yields a remarkable numerical relation between the numbers of reorientations and bases with given activities. A natural activity preserving reorientation-to-basis mapping compatible with this relation is described in a series of papers by the present authors. This mapping, equivalent to a bijection between regions and no broken circuit subsets, provides a bijective version of several enumerative results due to Stanley, Winder, Zaslavsky, and Las Vergnas, expressing the number of acyclic orientations in graphs, or the number of regions in real arrangements of hyperplanes or pseudohyperplanes (i.e. oriented matroids), as evaluations of the Tutte polynomial. In the present paper, we consider in detail the supersolvable case – a notion introduced by Stanley – in the context of arrangements of hyperplanes. For linear orderings compatible with the supersolvable structure, special properties are available, yielding constructions significantly simpler than those in the general case. As an application, we completely carry out the computation of the active bijection for the Coxeter arrangements $A_n$ and $B_n$. It turns out that in both cases the active bijection is closely related to a classical bijection between permutations and increasing trees.
The Structure of Maximum Subsets of $\{1,\ldots,n\}$ with No Solutions to $a+b = kc$
Authors: Baltz Andreas , Hegarty Peter , Knape Jonas , Larsson Urban , Schoen Tomasz
Published: January 2020

If $k$ is a positive integer, we say that a set $A$ of positive integers is $k$-sum-free if there do not exist $a,b,c$ in $A$ such that $a + b = kc$. In particular we give a precise characterization of the structure of maximum sized $k$-sum-free sets in $\{1,\ldots,n\}$ for $k\ge 4$ and $n$ large.
How Different Can Two Intersecting Families Be?
Authors: Patkós Balázs
Published: January 2020

To measure the difference between two intersecting families ${\cal F},{\cal G} \subseteq 2^{[n]}$ we introduce the quantity $D({\cal F} ,{\cal G})=|\{ (F,G):F \in {\cal F}, G \in {\cal G}, F\cap G =\emptyset \}|$. We prove that if ${\cal F}$ is $k$-uniform and ${\cal G}$ is $l$-uniform, then for large enough $n$ and for any $i \neq j$ ${\cal F}_i=\{F \subseteq [n]: i \in F, |F|=k \}$ and ${\cal F}_j=\{F \subseteq [n]: j \in F, |F|=l\}$ form an optimal pair of families (that is $D({\cal F},{\cal G}) \leq D({\cal F}_i,{\cal F}_j)$ for all uniform and intersecting ${\cal F}$ and ${\cal G}$), while in the non-uniform case any pair of the form ${\cal F}_i=\{F \subseteq [n]: i \in F \}$ and ${\cal F}_j=\{F \subseteq [n]: j \in F\}$ is optimal for any $n$.
Faster Algorithms for Frobenius Numbers
Authors: Beihoffer Dale , Hendry Jemimah , Nijenhuis Albert , Wagon Stan
Published: January 2020

The Frobenius problem, also known as the postage-stamp problem or the money-changing problem, is an integer programming problem that seeks nonnegative integer solutions to $ x_1 a_1 +\cdots + x_n a_n =M$, where $ a_i $ and $M$ are positive integers. In particular, the Frobenius number $f(A)$, where $A=\{ a_i \}$, is the largest $M$ so that this equation fails to have a solution. A simple way to compute this number is to transform the problem to a shortest-path problem in a directed weighted graph; then Dijkstra's algorithm can be used. We show how one can use the additional symmetry properties of the graph in question to design algorithms that are very fast. For example, on a standard desktop computer, our methods can handle cases where $n=10$ and $ a_1 = 10^7$. We have two main new methods, one based on breadth-first search and another that uses the number theory and combinatorial structure inherent in the problem to speed up the Dijkstra approach. For both methods we conjecture that the average-case complexity is $O( a_1 \sqrt{n} )$. The previous best method is due to Böcker and Lipták and runs in time $O( a_1 n)$. These algorithms can also be used to solve auxiliary problems such as (1) find a solution to the main equation for a given value of $M$; or (2) eliminate all redundant entries from a basis. We then show how the graph theory model leads to a new upper bound on $f(A)$ that is significantly lower than existing upper bounds. We also present a conjecture, supported by many computations, that the expected value of $f(A)$ is a small constant multiple of $ \left({1\over2} \, n! \, \Pi A\right)^{1/(n-1)} -\Sigma A$.
Asymptotic Enumeration of Dense 0-1 Matrices with Equal Row Sums and Equal Column Sums
Authors: Canfield E. Rodney , McKay Brendan D.
Published: January 2020

Let $s,\,t,\,m$ and $n$ be positive integers such that $sm=tn$. Let $B(m,s;n,t)$ be the number of $m\times n$ matrices over $\{0,1\}$ with each row summing to $s$ and each column summing to $t$. Equivalently, $B(m,s;n,t)$ is the number of semiregular bipartite graphs with $m$ vertices of degree $s$ and $n$ vertices of degree $t$. Define the density $\lambda=s/n=t/m$. The asymptotic value of $B(m,s;n,t)$ has been much studied but the results are incomplete. McKay and Wang (2003) solved the sparse case $\lambda(1-\lambda)=o\big((mn)^{-1/2}\big)$ using combinatorial methods. In this paper, we use analytic methods to solve the problem for two additional ranges. In one range the matrix is relatively square and the density is not too close to 0 or 1. In the other range, the matrix is far from square and the density is arbitrary. Interestingly, the asymptotic value of $B(m,s;n,t)$ can be expressed by the same formula in all cases where it is known. Based on computation of the exact values for all $m,n\le 30$, we conjecture that the same formula holds whenever $m+n\to\infty$ regardless of the density.
A Triple Lacunary Generating Function for Hermite Polynomials
Authors: Gessel Ira M. , Jayawant Pallavi
Published: January 2020

Some of the classical orthogonal polynomials such as Hermite, Laguerre, Charlier, etc. have been shown to be the generating polynomials for certain combinatorial objects. These combinatorial interpretations are used to prove new identities and generating functions involving these polynomials. In this paper we apply Foata's approach to generating functions for the Hermite polynomials to obtain a triple lacunary generating function. We define renormalized Hermite polynomials $h_n(u)$ by $$\sum_{n= 0}^\infty h_n(u) {z^n\over n!}=e^{uz+{z^2\!/2}}.$$ and give a combinatorial proof of the following generating function: $$ \sum_{n= 0}^\infty h_{3n}(u) {{z^n\over n!}}= {e^{(w-u)(3u-w)/6}\over\sqrt{1-6wz}} \sum_{n= 0}^\infty {{(6n)!\over 2^{3n}(3n)!(1-6wz)^{3n}} {z^{2n}\over(2n)!}}, $$ where $w=(1-\sqrt{1-12uz})/6z=uC(3uz)$ and $C(x)=(1-\sqrt{1-4x})/(2x)$ is the Catalan generating function. We also give an umbral proof of this generating function.
A Determinant Identity that Implies Rogers-Ramanujan
Authors: Garrett Kristina C.
Published: January 2020

We give a combinatorial proof of a general determinant identity for associated polynomials. This determinant identity gives rise to new polynomial generalizations of known Rogers-Ramanujan type identities. Several examples of new Rogers-Ramanujan type identities are given.
The Insertion Encoding of Permutations
Authors: Albert Michael H. , Linton Steve , Ruškuc Nik
Published: January 2020

We introduce the insertion encoding, an encoding of finite permutations. Classes of permutations whose insertion encodings form a regular language are characterized. Some necessary conditions are provided for a class of permutations to have insertion encodings that form a context free language. Applications of the insertion encoding to the evaluation of generating functions for classes of permutations, construction of polynomial time algorithms for enumerating such classes, and the illustration of bijective equivalence between classes are demonstrated.
Bounds for the Average $L^p$-Extreme and the $L^\infty$-Extreme Discrepancy
Authors: Gnewuch Michael
Published: January 2020

The extreme or unanchored discrepancy is the geometric discrepancy of point sets in the $d$-dimensional unit cube with respect to the set system of axis-parallel boxes. For $2\leq p < \infty$ we provide upper bounds for the average $L^p$-extreme discrepancy. With these bounds we are able to derive upper bounds for the inverse of the $L^\infty$-extreme discrepancy with optimal dependence on the dimension $d$ and explicitly given constants.
Kocay's Lemma, Whitney's Theorem, and some Polynomial Invariant Reconstruction Problems
Authors: Thatte Bhalchandra D.
Published: January 2020

Given a graph $G$, an incidence matrix ${\cal N}(G)$ is defined on the set of distinct isomorphism types of induced subgraphs of $G$. It is proved that Ulam's conjecture is true if and only if the ${\cal N}$-matrix is a complete graph invariant. Several invariants of a graph are then shown to be reconstructible from its ${\cal N}$-matrix. The invariants include the characteristic polynomial, the rank polynomial, the number of spanning trees and the number of hamiltonian cycles in a graph. These results are stronger than the original results of Tutte in the sense that actual subgraphs are not used. It is also proved that the characteristic polynomial of a graph with minimum degree 1 can be computed from the characteristic polynomials of all its induced proper subgraphs. The ideas in Kocay's lemma play a crucial role in most proofs. Kocay's lemma is used to prove Whitney's subgraph expansion theorem in a simple manner. The reconstructibility of the characteristic polynomial is then demonstrated as a direct consequence of Whitney's theorem as formulated here.
Pan-Factorial Property in Regular Graphs
Authors: Kano M. , Yu Qinglin
Published: January 2020

Among other results, we show that if for any given edge $e$ of an $r$-regular graph $G$ of even order, $G$ has a 1-factor containing $e$, then $G$ has a $k$-factor containing $e$ and another one avoiding $e$ for all $k$, $1 \leq k \leq r-1$.
Flag $f$-Vectors of Three-Colored Complexes
Authors: Frohmader Andrew
Published: January 2020

The flag $f$-vectors of three-colored complexes are characterized.  This also characterizes the flag $h$-vectors of balanced Cohen-Macaulay complexes of dimension two, as well as the flag $h$-vectors of balanced shellable complexes of dimension two.
Aperiodic Subtraction Games
Authors: Fraenkel Aviezri S.
Published: January 2020

Periodicity is a fundamental property of many combinatorial games. It is sought vigorously, yet remains elusive in important cases, such as for some octal games, notably Grundy's game. Periodicity is important, because it provides poly-time winning strategies for many games. In particular, subtraction games, impartial and partizan, have been proved to be periodic. Our main purpose here is to exhibit constructively a class of subtraction games which is demonstratively aperiodic and yet is shown to have linear-time winning strategies.
The Existence of Strong Complete Mappings
Authors: Evans Anthony B.
Published: January 2020

A strong complete mapping of a group $G$ is a bijection $\theta\colon G\to G$ for which both mappings $x\mapsto x\theta(x)$ and $x\mapsto x^{-1}\theta(x)$ are bijections. We characterize finite abelian groups that admit strong complete mappings, thus solving a problem posed by Horton in 1990. We also prove the existence of strong complete mappings for countably infinite groups. A corrigendum for this paper was added on 2 October 2018.
Ehrhart $f^*$-Coefficients of Polytopal Complexes are Non-negative Integers
Authors: Breuer Felix
Published: January 2020

The Ehrhart polynomial $L_P$ of an integral polytope $P$ counts the number of integer points in integral dilates of $P$. Ehrhart polynomials of polytopes are often described in terms of their Ehrhart $h^*$-vector (aka Ehrhart $\delta$-vector), which is the vector of coefficients of $L_P$ with respect to a certain binomial basis and which coincides with the $h$-vector of a regular unimodular triangulation of $P$ (if one exists). One important result by Stanley about $h^*$-vectors of polytopes is that their entries are always non-negative. However, recent combinatorial applications of Ehrhart theory give rise to polytopal complexes with $h^*$-vectors that have negative entries.In this article we introduce the Ehrhart $f^*$-vector of polytopes or, more generally, of polytopal complexes $K$. These are again coefficient vectors of $L_K$ with respect to a certain binomial basis of the space of polynomials and they have the property that the $f^*$-vector of a unimodular simplicial complex coincides with its $f$-vector. The main result of this article is a counting interpretation for the $f^*$-coefficients which implies that $f^*$-coefficients of integral polytopal complexes are always non-negative integers. This holds even if the polytopal complex does not have a unimodular triangulation and if its $h^*$-vector does have negative entries. Our main technical tool is a new partition of the set of lattice points in a simplicial cone into discrete cones. Further results include a complete characterization of Ehrhart polynomials of integral partial polytopal complexes and a non-negativity theorem for the $f^*$-vectors of rational polytopal complexes.
Doubly Biased Maker-Breaker Connectivity Game
Authors: Hefetz Dan , Mikalački Mirjana , Stojaković Miloš
Published: January 2020

In this paper we study the (a:b) Maker-Breaker Connectivity game, played on the edge set of the complete graph on n vertices. We determine the winner for almost all values of a and b.
Orthogonal Systems in Vector Spaces over Finite Rings
Authors: Pham Thang Van , Le Anh Vinh
Published: January 2020

We prove that if a subset of the $d$-dimensional vector space over a finite ring is large enough, then the number of $k$-tuples of mutually orthogonal vectors in this set is close to its expected value.