bluuebunny/crossref_metadata_2025 huggingface dataset:
A Simple Algorithm for Constructing Szemerédi's Regularity Partition
Authors: Frieze Alan , Kannan Ravi
Published: January 2020

We give a simple constructive version of Szemerédi's Regularity Lemma, based on the computation of singular values of matrices.
On Highly Closed Cellular Algebras and Highly Closed Isomorphisms
Authors: Evdokimov Sergei , Ponomarenko Ilia
Published: January 2020

We define and study $m$-closed cellular algebras (coherent configurations) and $m$-isomorphisms of cellular algebras which can be regarded as $m$th approximations of Schurian algebras (i.e. the centralizer algebras of permutation groups) and of strong isomorphisms (i.e. bijections of the point sets taking one algebra to the other) respectively. If $m=1$ we come to arbitrary cellular algebras and their weak isomorphisms (i.e. matrix algebra isomorphisms preserving the Hadamard multiplication). On the other hand, the algebras which are $m$-closed for all $m\ge 1$ are exactly Schurian ones whereas the weak isomorphisms which are $m$-isomorphisms for all $m\ge 1$ are exactly ones induced by strong isomorphisms. We show that for any $m$ there exist $m$-closed algebras on $O(m)$ points which are not Schurian and $m$-isomorphisms of cellular algebras on $O(m)$ points which are not induced by strong isomorphisms. This enables us to find for any $m$ an edge colored graph with $O(m)$ vertices satisfying the $m$-vertex condition and having non-Schurian adjacency algebra. On the other hand, we rediscover and explain from the algebraic point of view the Cai-Fürer-Immerman phenomenon that the $m$-dimensional Weisfeiler-Lehman method fails to recognize the isomorphism of graphs in an efficient way.
Deformation of Chains via a Local Symmetric Group Action
Authors: Hersh Patricia
Published: January 2020

A symmetric group action on the maximal chains in a finite, ranked poset is local if the adjacent transpositions act in such a way that $(i,i+1)$ sends each maximal chain either to itself or to one differing only at rank $i$. We prove that when $S_n$ acts locally on a lattice, each orbit considered as a subposet is a product of chains. We also show that all posets with local actions induced by labellings known as $R^* S$-labellings have symmetric chain decompositions and provide $R^* S$-labellings for the type B and D noncrossing partition lattices, answering a question of Stanley.
Maximum Degree Growth of the Iterated Line Graph
Authors: Hartke Stephen G. , Higgins Aparna W.
Published: January 2020

Let $\Delta_k$ denote the maximum degree of the $k^{\rm th}$ iterated line graph $L^k(G)$. For any connected graph $G$ that is not a path, the inequality $\Delta_{k+1}\leq 2\Delta_k-2$ holds. Niepel, Knor, and Šoltés have conjectured that there exists an integer $K$ such that, for all $k\geq K$, equality holds; that is, the maximum degree $\Delta_k$ attains the greatest possible growth. We prove this conjecture using induced subgraphs of maximum degree vertices and locally maximum vertices.
On the Structure and Classification of SOMAs: Generalizations of Mutually Orthogonal Latin Squares
Authors: Soicher Leonard H.
Published: January 2020

Let $k\ge0$ and $n\ge2$ be integers. A SOMA, or more specifically a SOMA$(k,n)$, is an $n\times n$ array $A$, whose entries are $k$-subsets of a $kn$-set $\Omega$, such that each element of $\Omega$ occurs exactly once in each row and exactly once in each column of $A$, and no 2-subset of $\Omega$ is contained in more than one entry of $A$. A SOMA$(k,n)$ can be constructed by superposing $k$ mutually orthogonal Latin squares of order $n$ with pairwise disjoint symbol-sets, and so a SOMA$(k,n)$ can be seen as a generalization of $k$ mutually orthogonal Latin squares of order $n$. In this paper we first study the structure of SOMAs, concentrating on how SOMAs can decompose. We then report on the use of computational group theory and graph theory in the discovery and classification of SOMAs. In particular, we discover and classify SOMA$(3,10)$s with certain properties, and discover two SOMA$(4,14)$s (SOMAs with these parameters were previously unknown to exist). Some of the newly discovered SOMA$(3,10)$s come from superposing a Latin square of order 10 on a SOMA$(2,10)$.
Zero Capacity Region of Multidimensional Run Length Constraints
Authors: Ito Hisashi , Kato Akiko , Nagy Zsigmond , Zeger Kenneth
Published: January 2020

For integers $d$ and $k$ satisfying $0 \le d \le k$, a binary sequence is said to satisfy a one-dimensional $(d,k)$ run length constraint if there are never more than $k$ zeros in a row, and if between any two ones there are at least $d$ zeros. For $n\geq 1$, the $n$-dimensional $(d,k)$-constrained capacity is defined as $$C^{n}_{d,k} = \lim_{m_1,m_2,\ldots,m_n\rightarrow\infty} {{\log_2 N_{m_1,m_2,\ldots ,m_n}^{(n; d,k)}} \over {m_1 m_2\cdots m_n}} $$ where $N_{m_1,m_2,\ldots ,m_n}^{(n; d,k)}$ denotes the number of $m_1\times m_2\times\cdots\times m_n$ $n$-dimensional binary rectangular patterns that satisfy the one-dimensional $(d,k)$ run length constraint in the direction of every coordinate axis. It is proven for all $n\ge 2$, $d\ge1$, and $k>d$ that $C^{n}_{d,k}=0$ if and only if $k=d+1$. Also, it is proven for every $d\geq 0$ and $k\geq d$ that $\lim_{n\rightarrow\infty}C^{n}_{d,k}=0$ if and only if $k\le 2d$.
Critical Subgraphs of a Random Graph
Authors: Molloy Michael , Reed Bruce
Published: January 2020

We prove that the threshold for a random graph to have a $k$-core is equal to the threshold for having a subgraph which meets a necessary condition of Gallai for being $k$-critical.
Intersections of Randomly Embedded Sparse Graphs are Poisson
Authors: Bender Edward A. , Canfield E. Rodney
Published: January 2020

Suppose that $t \ge 2$ is an integer, and randomly label $t$ graphs with the integers $1 \dots n$. We give sufficient conditions for the number of edges common to all $t$ of the labelings to be asymptotically Poisson as $n \to \infty$. We show by example that our theorem is, in a sense, best possible. For $G_n$ a sequence of graphs of bounded degree, each having at most $n$ vertices, Tomescu has shown that the number of spanning trees of $K_n$ having $k$ edges in common with $G_n$ is asymptotically $e^{-2s/n}(2s/n)^k/k! \times n^{n-2}$, where $s=s(n)$ is the number of edges in $G_n$. As an application of our Poisson-intersection theorem, we extend this result to the case in which maximum degree is only restricted to be ${\scriptstyle\cal O}(n \log\log n/\log n)$. We give an inversion theorem for falling moments, which we use to prove our Poisson-intersection theorem.
On the Stanley-Wilf Conjecture for the Number of Permutations Avoiding a Given Pattern
Authors: Arratia Richard
Published: January 2020

Consider, for a permutation $\sigma \in {\cal S}_k$, the number $F(n,\sigma)$ of permutations in ${\cal S}_n$ which avoid $\sigma$ as a subpattern. The conjecture of Stanley and Wilf is that for every $\sigma$ there is a constant $c(\sigma) < \infty$ such that for all $n$, $F(n,\sigma) \leq c(\sigma)^n$. All the recent work on this problem also mentions the "stronger conjecture" that for every $\sigma$, the limit of $F(n,\sigma)^{1/n}$ exists and is finite. In this short note we prove that the two versions of the conjecture are equivalent, with a simple argument involving subadditivity We also discuss $n$-permutations, containing all $\sigma \in {\cal S}_k$ as subpatterns. We prove that this can be achieved with $n=k^2$, we conjecture that asymptotically $n \sim (k/e)^2$ is the best achievable, and we present Noga Alon's conjecture that $n \sim (k/2)^2$ is the threshold for random permutations.
Linear Codes over Finite Chain Rings
Authors: Honold Thomas , Landjev Ivan
Published: January 2020

The aim of this paper is to develop a theory of linear codes over finite chain rings from a geometric viewpoint. Generalizing a well-known result for linear codes over fields, we prove that there exists a one-to-one correspondence between so-called fat linear codes over chain rings and multisets of points in projective Hjelmslev geometries, in the sense that semilinearly isomorphic codes correspond to equivalent multisets and vice versa. Using a selected class of multisets we show that certain MacDonald codes are linearly representable over nontrivial chain rings.
Interchangeability of Relevant Cycles in Graphs
Authors: Gleiss Petra M. , Leydold Josef , Stadler Peter F.
Published: January 2020

The set ${\cal R}$ of relevant cycles of a graph $G$ is the union of its minimum cycle bases. We introduce a partition of ${\cal R}$ such that each cycle in a class ${\cal W}$ can be expressed as a sum of other cycles in ${\cal W}$ and shorter cycles. It is shown that each minimum cycle basis contains the same number of representatives of a given class ${\cal W}$. This result is used to derive upper and lower bounds on the number of distinct minimum cycle bases. Finally, we give a polynomial-time algorithm to compute this partition.
Improved Upper Bounds for Self-Avoiding Walks in ${\bf Z}^{d}$
Authors: Pönitz André , Tittmann Peter
Published: January 2020

New upper bounds for the connective constant of self-avoiding walks in a hypercubic lattice are obtained by automatic generation of finite automata for counting walks with finite memory. The upper bound in dimension two is 2.679192495.
Min-Wise Independent Linear Permutations
Authors: Bohman Tom , Cooper Colin , Frieze Alan
Published: January 2020

A set of permutations ${\cal F} \subseteq S_n$ is min-wise independent if for any set $X \subseteq [n]$ and any $x \in X$, when $\pi$ is chosen at random in ${\cal F}$ we have ${\bf P} \left(\min\{\pi(X)\} = \pi(x)\right) = {{1}\over {|X|}}$. This notion was introduced by Broder, Charikar, Frieze and Mitzenmacher and is motivated by an algorithm for filtering near-duplicate web documents. Linear permutations are an important class of permutations. Let $p$ be a (large) prime and let ${\cal F}_p=\{p_{a,b}:\;1\leq a\leq p-1,\,0\leq b\leq p-1\}$ where for $x\in [p]=\{0,1,\ldots,p-1\}$, $p_{a,b}(x)=ax+b\pmod p$. For $X\subseteq [p]$ we let $F(X)=\max_{x\in X}\left\{{\bf P}_{a,b}(\min\{p(X)\}=p(x))\right\}$ where ${\bf P}_{a,b}$ is over $p$ chosen uniformly at random from ${\cal F}_p$. We show that as $k,p \to\infty$, ${\bf E}_X[F(X)]={{1}\over {k}}+O\left({(\log k)^3}\over {k^{3/2}}\right)$ confirming that a simply chosen random linear permutation will suffice for an average set from the point of view of approximate min-wise independence.
A Note on the Number of $(k,l)$-Sum-Free Sets
Authors: Schoen Tomasz
Published: January 2020

A set $A\subseteq {\bf N}$ is $(k,\ell)$-sum-free, for $k,\ell\in {\bf N}$, $k>\ell$, if it contains no solutions to the equation $x_1+\dots+x_k=y_1+\dots+y_{\ell}$. Let $\rho=\rho (k-\ell)$ be the smallest natural number not dividing $k-\ell$, and let $r=r_n$, $0\le r < \rho$, be such that $r\equiv n \pmod {\rho }$. The main result of this note says that if $(k-\ell)/\ell$ is small in terms of $\rho$, then the number of $(k,\ell)$-sum-free subsets of $[1,n]$ is equal to $(\varphi(\rho)+\varphi_r(\rho)+o(1)) 2^{\lfloor n/\rho \rfloor}$, where $\varphi_r(x)$ denotes the number of positive integers $m\le r$ relatively prime to $x$ and $\varphi(x)=\varphi_x(x)$.
Separability Number and Schurity Number of Coherent Configurations
Authors: Evdokimov Sergei , Ponomarenko Ilia
Published: January 2020

To each coherent configuration (scheme) ${\cal C}$ and positive integer $m$ we associate a natural scheme $\widehat{\cal C}^{(m)}$ on the $m$-fold Cartesian product of the point set of ${\cal C}$ having the same automorphism group as ${\cal C}$. Using this construction we define and study two positive integers: the separability number $s({\cal C})$ and the Schurity number $t({\cal C})$ of ${\cal C}$. It turns out that $s({\cal C})\le m$ iff ${\cal C}$ is uniquely determined up to isomorphism by the intersection numbers of the scheme $\widehat{\cal C}^{(m)}$. Similarly, $t({\cal C})\le m$ iff the diagonal subscheme of $\widehat{\cal C}^{(m)}$ is an orbital one. In particular, if ${\cal C}$ is the scheme of a distance-regular graph $\Gamma$, then $s({\cal C})=1$ iff $\Gamma$ is uniquely determined by its parameters whereas $t({\cal C})=1$ iff $\Gamma$ is distance-transitive. We show that if ${\cal C}$ is a Johnson, Hamming or Grassmann scheme, then $s({\cal C})\le 2$ and $t({\cal C})=1$. Moreover, we find the exact values of $s({\cal C})$ and $t({\cal C})$ for the scheme ${\cal C}$ associated with any distance-regular graph having the same parameters as some Johnson or Hamming graph. In particular, $s({\cal C})=t({\cal C})=2$ if ${\cal C}$ is the scheme of a Doob graph. In addition, we prove that $s({\cal C})\le 2$ and $t({\cal C})\le 2$ for any imprimitive 3/2-homogeneous scheme. Finally, we show that $s({\cal C})\le 4$, whenever ${\cal C}$ is a cyclotomic scheme on a prime number of points.
Counting Pattern-free Set Partitions II: Noncrossing and Other Hypergraphs
Authors: Klazar Martin
Published: January 2020

A (multi)hypergraph ${\cal H}$ with vertices in ${\bf N}$ contains a permutation $p=a_1a_2\ldots a_k$ of $1, 2, \ldots, k$ if one can reduce ${\cal H}$ by omitting vertices from the edges so that the resulting hypergraph is isomorphic, via an increasing mapping, to ${\cal H}_p=(\{i, k+a_i\}:\ i=1, \ldots, k)$. We formulate six conjectures stating that if ${\cal H}$ has $n$ vertices and does not contain $p$ then the size of ${\cal H}$ is $O(n)$ and the number of such ${\cal H}$s is $O(c^n)$. The latter part generalizes the Stanley–Wilf conjecture on permutations. Using generalized Davenport–Schinzel sequences, we prove the conjectures with weaker bounds $O(n\beta(n))$ and $O(\beta(n)^n)$, where $\beta(n)\rightarrow\infty$ very slowly. We prove the conjectures fully if $p$ first increases and then decreases or if $p^{-1}$ decreases and then increases. For the cases $p=12$ (noncrossing structures) and $p=21$ (nonnested structures) we give many precise enumerative and extremal results, both for graphs and hypergraphs.
When Structures Are Almost Surely Connected
Authors: Bell Jason P.
Published: January 2020

Let $A_n$ denote the number of objects of some type of"size" $n$, and let $C_n$ denote the number of these objects which are connected. It is often the case that there is a relation between a generating function of the $C_n$'s and a generating function of the $A_n$'s. Wright showed that if $\lim_{n\rightarrow\infty} C_n/A_n =1$, then the radius of convergence of these generating functions must be zero. In this paper we prove that if the radius of convergence of the generating functions is zero, then $\limsup_{n\rightarrow \infty} C_n/A_n =1$, proving a conjecture of Compton; moreover, we show that $\liminf_{n\rightarrow\infty} C_n/A_n$ can assume any value between $0$ and $1$.
An Asymptotic Expansion for the Number of Permutations with a Certain Number of Inversions
Authors: Clark Lane
Published: January 2020

Let $b(n,k)$ denote the number of permutations of $\{1,\ldots,n\}$ with precisely $k$ inversions. We represent $b(n,k)$ as a real trigonometric integral and then use the method of Laplace to give a complete asymptotic expansion of the integral. Among the consequences, we have a complete asymptotic expansion for $b(n,k)/n!$ for a range of $k$ including the maximum of the $b(n,k)/n!$.
Frequency Squares and Affine Designs
Authors: Mavron V C
Published: January 2020

The known methods for constructing complete sets of mutually orthogonal frequency squares all yield one of two parameter sets. We show that almost all these constructions can be derived from one basic design theory construction.
On the Number of Perfect Matchings and Hamilton Cycles in $\epsilon$-Regular Non-bipartite Graphs
Authors: Frieze Alan
Published: January 2020

A graph $G=(V,E)$ on $n$ vertices is super $\epsilon$-regular if (i) all vertices have degree in the range $[(d-\epsilon)n,(d+\epsilon)n]$, $dn$ being the average degree, and (ii) for every pair of disjoint sets $S,T\subseteq V,\,|S|,|T|\geq \epsilon n$, $e(S,T)$ is in the range $[(d-\epsilon)|S||T|,(d+\epsilon)|S||T|]$. We show that the number of perfect matchings lies in the range $$[((d-2\epsilon)^\nu {{n!}\over {\nu !2^\nu}},(d+2\epsilon)^\nu {{n!}\over {\nu !2^\nu}}],$$ where $\nu ={{n}\over {2}}$, and the number of Hamilton cycles lies in the range $[(d-2\epsilon)^nn!,(d+2\epsilon)^nn!]$.
Inequality Related to Vizing's Conjecture
Authors: Clark W. Edwin , Suen Stephen
Published: January 2020

Let $\gamma(G)$ denote the domination number of a graph $G$ and let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \le 2 \gamma(G\square H)$ for all simple graphs $G$ and $H$.
A Unified View of Determinantal Expansions for Jack Polynomials
Authors: Roberts Leigh
Published: January 2020

Recently Lapointe et. al. [3] have expressed Jack Polynomials as determinants in monomial symmetric functions $m_\lambda$. We express these polynomials as determinants in elementary symmetric functions $e_\lambda$, showing a fundamental symmetry between these two expansions. Moreover, both expansions are obtained indifferently by applying the Calogero-Sutherland operator in physics or quasi Laplace Beltrami operators arising from differential geometry and statistics. Examples are given, and comments on the sparseness of the determinants so obtained conclude the paper.
Product of Integers in an Interval, Modulo Squares
Authors: Granville Andrew , Selfridge J. L.
Published: January 2020

We prove a conjecture of Irving Kaplansky which asserts that between any pair of consecutive positive squares there is a set of distinct integers whose product is twice a square. Along similar lines, our main theorem asserts that if prime $p$ divides some integer in $[z,z+3\sqrt{z/2}+1)$ (with $z\geq 11$) then there is a set of integers in the interval whose product is $p$ times a square. This is probably best possible, because it seems likely that there are arbitrarily large counterexamples if we shorten the interval to $[z,z+3\sqrt{z/2})$.
How to Find Overfull Subgraphs in Graphs with Large Maximum Degree, II
Authors: Niessen Thomas
Published: January 2020

Let $G$ be a simple graph with $3\Delta (G) > |V|$. The Overfull Graph Conjecture states that the chromatic index of $G$ is equal to $\Delta (G)$, if $G$ does not contain an induced overfull subgraph $H$ with $\Delta (H) = \Delta (G)$, and otherwise it is equal to $\Delta (G) +1$. We present an algorithm that determines these subgraphs in $O(n^{5/3}m)$ time, in general, and in $O(n^3)$ time, if $G$ is regular. Moreover, it is shown that $G$ can have at most three of these subgraphs. If $2\Delta (G) \geq |V|$, then $G$ contains at most one of these subgraphs, and our former algorithm for this situation is improved to run in linear time.
On Edge Colorings with at Least q Colors in Every Subset of p Vertices
Authors: Sárközy Gábor N. , Selkow Stanley
Published: January 2020

For fixed integers $p$ and $q$, an edge coloring of $K_n$ is called a $(p, q)$-coloring if the edges of $K_n$ in every subset of $p$ vertices are colored with at least $q$ distinct colors. Let $f(n, p, q)$ be the smallest number of colors needed for a $(p, q)$-coloring of $K_n$. In [3] Erdős and Gyárfás studied this function if $p$ and $q$ are fixed and $n$ tends to infinity. They determined for every $p$ the smallest $q$ ($= {p \choose 2} - p + 3$) for which $f(n,p,q)$ is linear in $n$ and the smallest $q$ for which $f(n,p,q)$ is quadratic in $n$. They raised the question whether perhaps this is the only $q$ value which results in a linear $f(n,p,q)$. In this paper we study the behavior of $f(n,p,q)$ between the linear and quadratic orders of magnitude. In particular we show that that we can have at most $\log p$ values of $q$ which give a linear $f(n,p,q)$.
Meet and Join within the Lattice of Set Partitions
Authors: Canfield E. Rodney
Published: January 2020

We build on work of Boris Pittel [5] concerning the number of $t$-tuples of partitions whose meet (join) is the minimal (maximal) element in the lattice of set partitions.
The Rectilinear Crossing Number of $K_{10}$ is $62$
Authors: Brodsky Alex , Durocher Stephane , Gethner Ellen
Published: January 2020

The rectilinear crossing number of a graph $G$ is the minimum number of edge crossings that can occur in any drawing of $G$ in which the edges are straight line segments and no three vertices are collinear. This number has been known for $G=K_n$ if $n \leq 9$. Using a combinatorial argument we show that for $n=10$ the number is 62.
An Analogue of Covering Space Theory for Ranked Posets
Authors: Hoffman Michael E.
Published: January 2020

Suppose $P$ is a partially ordered set that is locally finite, has a least element, and admits a rank function. We call $P$ a weighted-relation poset if all the covering relations of $P$ are assigned a positive integer weight. We develop a theory of covering maps for weighted-relation posets, and in particular show that any weighted-relation poset $P$ has a universal cover $\tilde P\to P$, unique up to isomorphism, so that 1. $\tilde P\to P$ factors through any other covering map $P'\to P$; 2. every principal order ideal of $\tilde P$ is a chain; and 3. the weight assigned to each covering relation of $\tilde P$ is 1. If $P$ is a poset of "natural" combinatorial objects, the elements of its universal cover $\tilde P$ often have a simple description as well. For example, if $P$ is the poset of partitions ordered by inclusion of their Young diagrams, then the universal cover $\tilde P$ is the poset of standard Young tableaux; if $P$ is the poset of rooted trees ordered by inclusion, then $\tilde P$ consists of permutations. We discuss several other examples, including the posets of necklaces, bracket arrangements, and compositions.
Spanning Trees of Bounded Degree
Authors: Czygrinow Andrzej , Fan Genghua , Hurlbert Glenn , Kierstead H. A. , Trotter William T.
Published: January 2020

Dirac's classic theorem asserts that if ${\bf G}$ is a graph on $n$ vertices, and $\delta({\bf G})\ge n/2$, then ${\bf G}$ has a hamilton cycle. As is well known, the proof also shows that if $\deg(x)+\deg(y)\ge(n-1)$, for every pair $x$, $y$ of independent vertices in ${\bf G}$, then ${\bf G}$ has a hamilton path. More generally, S. Win has shown that if $k\ge 2$, ${\bf G}$ is connected and $\sum_{x\in I}\deg(x)\ge n-1$ whenever $I$ is a $k$-element independent set, then ${\bf G}$ has a spanning tree ${\bf T}$ with $\Delta({\bf T})\le k$. Here we are interested in the structure of spanning trees under the additional assumption that ${\bf G}$ does not have a spanning tree with maximum degree less than $k$. We show that apart from a single exceptional class of graphs, if $\sum_{x\in I}\deg(x)\ge n-1$ for every $k$-element independent set, then ${\bf G}$ has a spanning caterpillar ${\bf T}$ with maximum degree $k$. Furthermore, given a maximum path $P$ in ${\bf G}$, we may require that $P$ is the spine of ${\bf T}$ and that the set of all vertices whose degree in ${\bf T}$ is $3$ or larger is independent in ${\bf T}$.
A Lower Bound for the Number of Edges in a Graph Containing No Two Cycles of the Same Length
Authors: Lai Chunhui
Published: January 2020

In 1975, P. Erdős proposed the problem of determining the maximum number $f(n)$ of edges in a simple graph of $n$ vertices in which any two cycles are of different lengths. In this paper, it is proved that $$f(n)\geq n+32t-1$$ for $t=27720r+169 \,\ (r\geq 1)$ and $n\geq {{6911}\over {16}}t^{2}+{{514441}\over {8}}t-{{3309665}\over {16}}$. Consequently, $\liminf _{n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 + {2562 \over 6911}}.$
The ${1/k}$-Eulerian Polynomials
Authors: Savage Carla D. , Viswanathan Gopal
Published: January 2020

We use the theory of lecture hall partitions to define a generalization of the Eulerian polynomials, for each positive integer $k$.  We show that these ${1}/{k}$-Eulerian polynomials have a simple combinatorial interpretation in terms of a single statistic on generalized inversion sequences. The theory provides a geometric realization of the polynomials as the $h^*$-polynomials of $k$-lecture hall polytopes. Many of the defining relations of the Eulerian polynomials have natural ${1}/{k}$-generalizations.  In fact,  these properties extend to a bivariate generalization obtained by replacing  ${1}/{k}$ by a  continuous variable. The bivariate polynomials have appeared in the work of Carlitz, Dillon, and Roselle on Eulerian numbers of higher order and, more recently, in the theory of rook polynomials.
The Game of End-Nim
Authors: Albert Michael H. , Nowakowski Richard J.
Published: January 2020

In the game of End-Nim two players take turns in removing one or more boxes from a string of non-empty stacks. At each move boxes may only be taken from the two stacks which form the ends of the string (unless only one stack remains!). We give a solution for both impartial and partizan versions of the game and explain the significance of the mystic hieroglyphs: $$ \begin{array}{|cc|} \hline \uparrow & \downarrow \\ \downarrow & \uparrow \\ \hline \end{array} $$
Optimal Token Allocations in Solitaire Knock 'm Down
Authors: Benjamin Arthur T. , Fluet Matthew T. , Huber Mark L.
Published: January 2020

In the game Knock 'm Down, tokens are placed in $N$ bins. At each step of the game, a bin is chosen at random according to a fixed probability distribution. If a token remains in that bin, it is removed. When all the tokens have been removed, the player is done. In the solitaire version of this game, the goal is to minimize the expected number of moves needed to remove all the tokens. Here we present necessary conditions on the number of tokens needed for each bin in an optimal solution, leading to an asymptotic solution.
The Hexad Game
Authors: Kahane Joseph , Ryba Alexander J.
Published: January 2020

We give a non-enumerative proof that the $P$-positions of the hexad game give the Steiner system $S(5,6,12)$. We show that the distributions of nim sums and Welter values of these $P$-positions have simple and surprising regularities.
On the Oriented Game Chromatic Number
Authors: Nešetřil J. , Sopena E.
Published: January 2020

We consider the oriented version of a coloring game introduced by Bodlaender [On the complexity of some coloring games, Internat. J. Found. Comput. Sci. 2 (1991), 133–147]. We prove that every oriented path has oriented game chromatic number at most 7 (and this bound is tight), that every oriented tree has oriented game chromatic number at most 19 and that there exists a constant $t$ such that every oriented outerplanar graph has oriented game chromatic number at most $t$.
The Tenacity of Zero-One Laws
Authors: Spencer Joel H. , St. John Katherine
Published: January 2020

The Ehrenfeucht-Fraisse game is a two-person game of perfect information which is connected to the Zero-One Laws of first order logic. We give bounds for roughly how quickly the Zero-One Laws converge for random bit strings and random circular bit sequences. We measure the tenaciousness of the second player ("Duplicator") in playing the Ehrenfeucht-Fraisse game, by bounding the numbers of moves Duplicator can play and win with probability $1-\epsilon$. We show that for random bit strings and random circular sequences of length $n$ generated with a low probability ($p\ll n^{-1}$), the number of moves, $T_{\epsilon}(n)$, is $\Theta(\log_2 n)$. For random bit strings and circular sequences with isolated ones ($n^{-1}\ll p \ll n^{-1/2}$), $T_{\epsilon}(n) = O(\min(\log_2 np, -\log_2 np^2))$. For $n^{-1/2}\ll p$ and $(1-p) \ll n^{-1/2}$, we show that $T_{\epsilon}(n) = O(\log^* n)$ for random circular sequences, where $\log^* n$ has the usual definition– the least number of times you iteratively apply the logarithm to get a value less than one.
Set-Systems with Restricted Multiple Intersections
Authors: Grolmusz Vince
Published: January 2020

We give a generalization for the Deza-Frankl-Singhi Theorem in case of multiple intersections. More exactly, we prove, that if ${\cal H}$ is a set-system, which satisfies that for some $k$, the $k$-wise intersections occupy only $\ell$ residue-classes modulo a $p$ prime, while the sizes of the members of ${\cal H}$ are not in these residue classes, then the size of ${\cal H}$ is at most $$(k-1)\sum_{i=0}^{\ell}{n\choose i}$$ This result considerably strengthens an upper bound of Füredi (1983), and gives partial answer to a question of T. Sós (1976). As an application, we give a direct, explicit construction for coloring the $k$-subsets of an $n$ element set with $t$ colors, such that no monochromatic complete hypergraph on $$\exp{(c(\log m)^{1/t}(\log \log m)^{1/(t-1)})}$$ vertices exists.
Generating a Random Sink-free Orientation in Quadratic Time
Authors: Cohn Henry , Pemantle Robin , Propp James
Published: January 2020

A sink-free orientation of a finite undirected graph is a choice of orientation for each edge such that every vertex has out-degree at least 1. Bubley and Dyer (1997) use Markov Chain Monte Carlo to sample approximately from the uniform distribution on sink-free orientations in time $O(m^3 \log (1 / \varepsilon))$, where $m$ is the number of edges and $\varepsilon$ the degree of approximation. Huber (1998) uses coupling from the past to obtain an exact sample in time $O(m^4)$. We present a simple randomized algorithm inspired by Wilson's cycle popping method which obtains an exact sample in mean time at most $O(nm)$, where $n$ is the number of vertices.
A Generalisation of Transversals for Latin Squares
Authors: Wanless Ian M.
Published: January 2020

We define a $k$-plex to be a partial latin square of order $n$ containing $kn$ entries such that exactly $k$ entries lie in each row and column and each of $n$ symbols occurs exactly $k$ times. A transversal of a latin square corresponds to the case $k=1$. For $k>n/4$ we prove that not all $k$-plexes are completable to latin squares. Certain latin squares, including the Cayley tables of many groups, are shown to contain no $(2c+1)$-plex for any integer $c$. However, Cayley tables of soluble groups have a $2c$-plex for each possible $c$. We conjecture that this is true for all latin squares and confirm this for orders $n\leq8$. Finally, we demonstrate the existence of indivisible $k$-plexes, meaning that they contain no $c$-plex for $1\leq c < k$.
Efficient Packing of Unit Squares in a Square
Authors: Kearney Michael J , Shiu Peter
Published: January 2020

Let $s(N)$ denote the edge length of the smallest square in which one can pack $N$ unit squares. A duality method is introduced to prove that $s(6)=s(7)=3$. Let $n_r$ be the smallest integer $n$ such that $s(n^2+1)\le n+{1/r}$. We use an explicit construction to show that $n_r\le 27r^3/2+O(r^2)$, and also that $n_2\le43$.
On the Number of Distributive Lattices
Authors: Erné Marcel , Heitzig Jobst , Reinhold Jürgen
Published: January 2020

We investigate the numbers $d_k$ of all (isomorphism classes of) distributive lattices with $k$ elements, or, equivalently, of (unlabeled) posets with $k$ antichains. Closely related and useful for combinatorial identities and inequalities are the numbers $v_k$ of vertically indecomposable distributive lattices of size $k$. We present the explicit values of the numbers $d_k$ and $v_k$ for $k < 50$ and prove the following exponential bounds: $$ 1.67^k < v_k < 2.33^k\;\;\; {\rm and}\;\;\; 1.84^k < d_k < 2.39^k\;(k\ge k_0).$$ Important tools are (i) an algorithm coding all unlabeled distributive lattices of height $n$ and size $k$ by certain integer sequences $0=z_1\le\cdots\le z_n\le k-2$, and (ii) a "canonical 2-decomposition" of ordinally indecomposable posets into "2-indecomposable" canonical summands.
Kasteleyn Cokernels
Authors: Kuperberg Greg
Published: January 2020

We consider Kasteleyn and Kasteleyn-Percus matrices, which arise in enumerating matchings of planar graphs, up to matrix operations on their rows and columns. If such a matrix is defined over a principal ideal domain, this is equivalent to considering its Smith normal form or its cokernel. Many variations of the enumeration methods result in equivalent matrices. In particular, Gessel-Viennot matrices are equivalent to Kasteleyn-Percus matrices. We apply these ideas to plane partitions and related planar of tilings. We list a number of conjectures, supported by experiments in Maple, about the forms of matrices associated to enumerations of plane partitions and other lozenge tilings of planar regions and their symmetry classes. We focus on the case where the enumerations are round or $q$-round, and we conjecture that cokernels remain round or $q$-round for related "impossible enumerations" in which there are no tilings. Our conjectures provide a new view of the topic of enumerating symmetry classes of plane partitions and their generalizations. In particular we conjecture that a $q$-specialization of a Jacobi-Trudi matrix has a Smith normal form. If so it could be an interesting structure associated to the corresponding irreducible representation of SL$(n,C)$. Finally we find, with proof, the normal form of the matrix that appears in the enumeration of domino tilings of an Aztec diamond.
Distinguishing Chromatic Numbers of Bipartite Graphs
Authors: Laflamme C. , Seyffarth K.
Published: January 2020

Extending the work of K.L. Collins and A.N. Trenk, we characterize connected bipartite graphs with large distinguishing chromatic number. In particular, if $G$ is a connected bipartite graph with maximum degree $\Delta \geq 3$, then $\chi_D(G)\leq 2\Delta -2$ whenever $G\not\cong K_{\Delta-1,\Delta}$, $K_{\Delta,\Delta}$.
Sum List Coloring $2 \times n$ Arrays
Authors: Isaak Garth
Published: January 2020

A graph is $f$-choosable if for every collection of lists with list sizes specified by $f$ there is a proper coloring using colors from the lists. The sum choice number is the minimum over all choosable functions $f$ of the sum of the sizes in $f$. We show that the sum choice number of a $2 \times n$ array (equivalent to list edge coloring $K_{2,n}$ and to list vertex coloring the cartesian product $K_2 \square K_n$) is $n^2 + \lceil 5n/3 \rceil$.
Irreducible Coverings by Cliques and Sperner's Theorem
Authors: Tomescu Ioan
Published: January 2020

In this note it is proved that if a graph $G$ of order $n$ has an irreducible covering of its vertex set by $n-k$ cliques, then its clique number $\omega (G)\leq k+1$ if $k=2$ or 3 and $\omega (G)\leq { {k} \choose {\lfloor k/2\rfloor }}$ if $k\geq 4$. These bounds are sharp if $n\geq k+1$ (for $k=2$ or 3) and $n\geq k+ { {k} \choose {\lfloor k/2\rfloor }}$ (for $k\geq 4$).
Homogeneous Permutations
Authors: Cameron Peter J.
Published: January 2020

There are just five Fraïssé classes of permutations (apart from the trivial class of permutations of a singleton set); these are the identity permutations, reversing permutations, composites (in either order) of these two classes, and all permutations. The paper also discusses infinite generalisations of permutations, and the connection with Fraïssé's theory of countable homogeneous structures, and states a few open problems. Links with enumeration results, and the analogous result for circular permutations, are also described.
Combinatorial Necklace Splitting
Authors: Pálvölgyi Dömötör
Published: January 2020

We give a new, combinatorial proof for the necklace splitting problem for two thieves using only Tucker's lemma (a combinatorial version of the Borsuk-Ulam theorem). We show how this method can be applied to obtain a related recent result of Simonyi and even generalize it.
Prefix Exchanging and Pattern Avoidance by Involutions
Authors: Jaggard Aaron D.
Published: January 2020

Let $I_n(\pi)$ denote the number of involutions in the symmetric group ${\cal S}_{n}$ which avoid the permutation $\pi$. We say that two permutations $\alpha,\beta\in{\cal S}_{j}$ may be exchanged if for every $n$, $k$, and ordering $\tau$ of $j+1,\ldots,k$, we have $I_n(\alpha\tau)=I_n(\beta\tau)$. Here we prove that $12$ and $21$ may be exchanged and that $123$ and $321$ may be exchanged. The ability to exchange $123$ and $321$ implies a conjecture of Guibert, thus completing the classification of ${\cal S}_{4}$ with respect to pattern avoidance by involutions; both of these results also have consequences for longer patterns. Pattern avoidance by involutions may be generalized to rook placements on Ferrers boards which satisfy certain symmetry conditions. Here we provide sufficient conditions for the corresponding generalization of the ability to exchange two prefixes and show that these conditions are satisfied by $12$ and $21$ and by $123$ and $321$. Our results and approach parallel work by Babson and West on analogous problems for pattern avoidance by general (not necessarily involutive) permutations, with some modifications required by the symmetry of the current problem.
The Laplacian Spread of Tricyclic Graphs
Authors: Chen Yanqing , Wang Ligong
Published: January 2020

The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second smallest eigenvalue of the Laplacian matrix of the graph. In this paper, we investigate Laplacian spread of graphs, and prove that there exist exactly five types of tricyclic graphs with maximum Laplacian spread among all tricyclic graphs of fixed order.
Optimal Double-Loop Networks with Non-Unit Steps
Authors: Aguiló F. , Simó E. , Zaragozá M.
Published: January 2020

A double-loop digraph $G(N;s_1,s_2)=G(V,E)$ is defined by $V={\bf Z}_N$ and $E=\{(i,i+s_1), (i,i+s_2)|\; i\in V\}$, for some fixed steps $1\leq s_1 < s_2 < N$ with $\gcd(N,s_1,s_2)=1$. Let $D(N;s_1,s_2)$ be the diameter of $G$ and let us define $$ D(N)=\min_{\scriptstyle1\leq s_1 < s_2 < N,\atop\scriptstyle\gcd(N,s_1,s_2)=1}D(N;s_1,s_2),\quad D_1(N)=\min_{1 < s < N}D(N;1,s). $$ Some early works about the diameter of these digraphs studied the minimization of $D(N;1,s)$, for a fixed value $N$, with $1 < s < N$. Although the identity $D(N)=D_1(N)$ holds for infinite values of $N$, there are also another infinite set of integers with $D(N) < D_1(N)$. These other integral values of $N$ are called non-unit step integers or nus integers. In this work we give a characterization of nus integers and a method for finding infinite families of nus integers is developed. Also the tight nus integers are classified. As a consequence of these results, some errata and some flaws in the bibliography are corrected.
The Cube Polynomial and its Derivatives: the Case of Median Graphs
Authors: Brešar Boštjan , Klavžar Sandi , Škrekovski Riste
Published: January 2020

For $i\geq 0$, the $i$-cube $Q_i$ is the graph on $2^i$ vertices representing $0/1$ tuples of length $i$, where two vertices are adjacent whenever the tuples differ in exactly one position. (In particular, $Q_0 = K_1$.) Let $\alpha_i(G)$ be the number of induced $i$-cubes of a graph $G$. Then the cube polynomial $c(G,x)$ of $G$ is introduced as $\sum_{i\geq 0} \alpha_i(G) x^i$. It is shown that any function $f$ with two related, natural properties, is up to the factor $f(Q_0,x)$ the cube polynomial. The derivation $\partial\, G$ of a median graph $G$ is introduced and it is proved that the cube polynomial is the only function $f$ with the property $f'(G,x)= f(\partial\, G, x)$ provided that $f(G,0)=|V(G)|$. As the main application of the new concept, several relations that widely generalize previous such results for median graphs are proved. For instance, it is shown that for any $s\geq 0$ we have $c^{(s)}(G,x+1) = \sum_{i\geq s}\, {{c^{(i)}(G,x)}\over {(i-s)!}}\,,$ where certain derivatives of the cube polynomial coincide with well-known invariants of median graphs.
Packing 10 or 11 Unit Squares in a Square
Authors: Stromquist Walter
Published: January 2020

Let $s(n)$ be the side of the smallest square into which it is possible pack $n$ unit squares. We show that $s(10)=3+\sqrt{1\over 2}\approx3.707$ and that $s(11)\geq2+2\sqrt{4\over 5}\approx3.789$. We also show that an optimal packing of $11$ unit squares with orientations limited to $0$ degrees or $45$ degrees has side $2+2\sqrt{8\over 9}\approx3.886$. These results prove Martin Gardner's conjecture that $n=11$ is the first case in which an optimal result requires a non-$45$ degree packing.
How Many Square Occurrences Must a Binary Sequence Contain?
Authors: Kucherov Gregory , Ochem Pascal , Rao Michaël
Published: January 2020

Every binary word with at least four letters contains a square. A. Fraenkel and J. Simpson showed that three distinct squares are necessary and sufficient to construct an infinite binary word. We study the following complementary question: how many square occurrences must a binary word contain? We show that this quantity is, in the limit, a constant fraction of the word length, and prove that this constant is $0.55080...$.
On Hypergraphs of Girth Five
Authors: Lazebnik Felix , Verstraëte Jacques
Published: January 2020

In this paper, we study $r$-uniform hypergraphs ${\cal H}$ without cycles of length less than five, employing the definition of a hypergraph cycle due to Berge. In particular, for $r = 3$, we show that if ${\cal H}$ has $n$ vertices and a maximum number of edges, then $$|{\cal H}|={\textstyle 1\over6}n^{3/2} + o(n^{3/2}).$$ This also asymptotically determines the generalized Turán number $T_{3}(n,8,4)$. Some results are based on our bounds for the maximum size of Sidon-type sets in $\Bbb{Z}_{n}$.
Binary Gray Codes with Long Bit Runs
Authors: Goddyn Luis , Gvozdjak Pavol
Published: January 2020

We show that there exists an $n$-bit cyclic binary Gray code all of whose bit runs have length at least $n - 3\log_2 n$. That is, there exists a cyclic ordering of $\{0,1\}^n$ such that adjacent words differ in exactly one (coordinate) bit, and such that no bit changes its value twice in any subsequence of $n-3\log_2 n$ consecutive words. Such Gray codes are 'locally distance preserving' in that Hamming distance equals index separation for nearby words in the sequence.
Monochrome Symmetric Subsets in 2-Colorings of Groups
Authors: Gryshko Yuliya
Published: January 2020

A subset $A$ of a group $G$ is called symmetric with respect to the element $g\in G$ if $A=gA^{-1}g$. It is proved that in any 2-coloring, every infinite group $G$ contains monochrome symmetric subsets of arbitrarily large cardinality $ < |G|$.
Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice
Authors: Griggs Jerrold , Killian Charles E. , Savage Carla D.
Published: January 2020

We show that symmetric Venn diagrams for $n$ sets exist for every prime $n$, settling an open question. Until this time, $n=11$ was the largest prime for which the existence of such diagrams had been proven, a result of Peter Hamburger. We show that the problem can be reduced to finding a symmetric chain decomposition, satisfying a certain cover property, in a subposet of the Boolean lattice ${\cal B}_n$, and prove that such decompositions exist for all prime $n$. A consequence of the approach is a constructive proof that the quotient poset of ${\cal B}_n$, under the relation "equivalence under rotation", has a symmetric chain decomposition whenever $n$ is prime. We also show how symmetric chain decompositions can be used to construct, for all $n$, monotone Venn diagrams with the minimum number of vertices, giving a simpler existence proof.
Discrepancy of Cartesian Products of Arithmetic Progressions
Authors: Doerr Benjamin , Srivastav Anand , Wehr Petra
Published: January 2020

We determine the combinatorial discrepancy of the hypergraph ${\cal H}$ of cartesian products of $d$ arithmetic progressions in the $[N]^d$–lattice ($[N] = \{0,1,\ldots,N-1\}$). The study of such higher dimensional arithmetic progressions is motivated by a multi-dimensional version of van der Waerden's theorem, namely the Gallai-theorem (1933). We solve the discrepancy problem for $d$–dimensional arithmetic progressions by proving ${\rm disc}({\cal H}) = \Theta(N^{d/4})$ for every fixed integer $d \ge 1$. This extends the famous lower bound of $\Omega(N^{1/4})$ of Roth (1964) and the matching upper bound $O(N^{1/4})$ of Matoušek and Spencer (1996) from $d=1$ to arbitrary, fixed $d$. To establish the lower bound we use harmonic analysis on locally compact abelian groups. For the upper bound a product coloring arising from the theorem of Matoušek and Spencer is sufficient. We also regard some special cases, e.g., symmetric arithmetic progressions and infinite arithmetic progressions.
A Combinatorial Proof of the Sum of $q$-Cubes
Authors: Garrett Kristina C. , Hummel Kristen
Published: January 2020

We give a combinatorial proof of a $q$-analogue of the classical formula for the sum of cubes.
On the Counting of Fully Packed Loop Configurations: Some New Conjectures
Authors: Zuber J.-B.
Published: January 2020

New conjectures are proposed on the numbers of FPL configurations pertaining to certain types of link patterns. Making use of the Razumov and Stroganov Ansatz, these conjectures are based on the analysis of the ground state of the Temperley-Lieb chain, for periodic boundary conditions and so-called "identified connectivities", up to size $2n=22$.
Lattice Structures from Planar Graphs
Authors: Felsner Stefan
Published: January 2020

The set of all orientations of a planar graph with prescribed outdegrees carries the structure of a distributive lattice. This general theorem is proven in the first part of the paper. In the second part the theorem is applied to show that interesting combinatorial sets related to a planar graph have lattice structure: Eulerian orientations, spanning trees and Schnyder woods. For the Schnyder wood application some additional theory has to be developed. In particular it is shown that a Schnyder wood for a planar graph induces a Schnyder wood for the dual.
Cyclic Labellings with Constraints at Two Distances
Authors: Leese R. A. , Noble S. D.
Published: January 2020

Motivated by problems in radio channel assignment, we consider the vertex-labelling of graphs with nonnegative integers. The objective is to minimize the span of the labelling, subject to constraints imposed at graph distances one and two. We show that the minimum span is (up to rounding) a piecewise linear function of the constraints, and give a complete specification, together with the associated optimal assignments, for trees and cycles.
Dense Packings of Equal Spheres in a Cube
Authors: Gensane Th.
Published: January 2020

We describe an adaptation of the billiard algorithm for finding dense packings of equal spheres inside a domain of the euclidean space. In order to improve the convergence of this stochastic algorithm, we introduce systematic perturbations in it. We apply this perturbed billiard algorithm in the case of $n$ spheres in a cube and display all the optimal and best known packings up to $n=32$. We improve the previous record packings for all $11\leq n\leq 26$ except $n=13,14,18$. We prove the existence of the displayed packings for $n=11,12,15,17,20,21,22,26,32$, by constructing them explicitly. For example, the graph of the conjectured optimal packing of twenty-two spheres is composed of five octahedrons and four isolated points. We also conjecture that the minimum distance $d_n$ between spheres centers of the optimal packings is constant in the range $29\leq n \leq 32$.
Airy Phenomena and Analytic Combinatorics of Connected Graphs
Authors: Flajolet Philippe , Salvy Bruno , Schaeffer Gilles
Published: January 2020

Until now, the enumeration of connected graphs has been dealt with by probabilistic methods, by special combinatorial decompositions or by somewhat indirect formal series manipulations. We show here that it is possible to make analytic sense of the divergent series that expresses the generating function of connected graphs. As a consequence, it becomes possible to derive analytically known enumeration results using only first principles of combinatorial analysis and straight asymptotic analysis—specifically, the saddle-point method. In this perspective, the enumeration of connected graphs by excess (of number of edges over number of vertices) derives from a simple saddle-point analysis. Furthermore, a refined analysis based on coalescent saddle points yields complete asymptotic expansions for the number of graphs of fixed excess, through an explicit connection with Airy functions.