bluuebunny/crossref_metadata_2025 huggingface dataset:
Even Bonds of Prescribed Directed Parity
Authors: Hartmann Sven , Little C.H.C.
Published: January 2020

Given a set $S$ of vertices in a graph, the cocycle determined by $S$ is the set of edges joining a vertex in $S$ to a vertex not in $S$. A bond is a minimal non-empty cocycle. We characterise graphs that admit an orientation under which every bond of even cardinality has a prescribed directed parity.
Sunflowers in Lattices
Authors: McKenna Geoffrey
Published: January 2020

A Sunflower is a subset $S$ of a lattice, with the property that the meet of any two elements in $S$ coincides with the meet of all of $S$. The Sunflower Lemma of Erdös and Rado asserts that a set of size at least $1 + k!(t-1)^k$ of elements of rank $k$ in a Boolean Lattice contains a sunflower of size $t$. We develop counterparts of the Sunflower Lemma for distributive lattices, graphic matroids, and matroids representable over a fixed finite field. We also show that there is no counterpart for arbitrary matroids.
Locally Restricted Compositions II. General Restrictions and Infinite Matrices
Authors: Bender Edward A. , Canfield E. Rodney
Published: January 2020

We study compositions $\vec{\bf c}=(c_1,\dots,c_k)$ of the integer $n$ in which the value $c_i$ of the $i$th part is constrained based on previous parts within a fixed distance of $c_i$. The constraints may depend on $i$ modulo some fixed integer $m$. Periodic constraints arise naturally when $m$-rowed compositions are written in a single row. We show that the number of compositions of $n$ is asymptotic to $Ar^{-n}$ for some $A$ and $r$ and that many counts can be expected to have a joint normal distribution with means vector and covariance matrix asymptotically proportional to $n$. Our method of proof relies on infinite matrices and does not readily lead to methods for accurate estimation of the various parameters. We obtain information about the longest run. In many cases, we obtain almost sure asymptotic estimates for the maximum part and number of distinct parts.
Rank–Three Matroids are Rayleigh
Authors: Wagner David G.
Published: January 2020

A Rayleigh matroid is one which satisfies a set of inequalities analogous to the Rayleigh monotonicity property of linear resistive electrical networks. We show that every matroid of rank three satisfies these inequalities.
A Sperner-Type Theorem for Set-Partition Systems
Authors: Meagher Karen , Moura Lucia , Stevens Brett
Published: January 2020

A Sperner partition system is a system of set partitions such that any two set partitions $P$ and $Q$ in the system have the property that for all classes $A$ of $P$ and all classes $B$ of $Q$, $A \not\subseteq B$ and $B \not\subseteq A$. A $k$-partition is a set partition with $k$ classes and a $k$-partition is said to be uniform if every class has the same cardinality $c=n/k$. In this paper, we prove a higher order generalization of Sperner's Theorem. In particular, we show that if $k$ divides $n$ the largest Sperner $k$-partition system on an $n$-set has cardinality ${n-1 \choose n/k-1}$ and is a uniform partition system. We give a bound on the cardinality of a Sperner $k$-partition system of an $n$-set for any $k$ and $n$.
The Cover Pebbling Theorem
Authors: Sjöstrand Jonas
Published: January 2020

For any configuration of pebbles on the nodes of a graph, a pebbling move replaces two pebbles on one node by one pebble on an adjacent node. A cover pebbling is a move sequence ending with no empty nodes. The number of pebbles needed for a cover pebbling starting with all pebbles on one node is trivial to compute and it was conjectured that the maximum of these simple cover pebbling numbers is indeed the general cover pebbling number of the graph. That is, for any configuration of this size, there exists a cover pebbling. In this note, we prove a generalization of the conjecture. All previously published results about cover pebbling numbers for special graphs (trees, hypercubes et cetera) are direct consequences of this theorem. We also prove that the cover pebbling number of a product of two graphs equals the product of the cover pebbling numbers of the graphs.
On Zeilberger's Constant Term for Andrews' TSSCPP Theorem
Authors: Xin Guoce
Published: January 2020

This paper studies Zeilberger's two prized constant term identities. For one of the identities, Zeilberger asked for a simple proof that may give rise to a simple proof of Andrews theorem for the number of totally symmetric self complementary plane partitions. We obtain an identity reducing a constant term in $2k$ variables to a constant term in $k$ variables. As applications, Zeilberger's constant terms are converted to single determinants. The result extends for two classes of matrices, the sum of all of whose full rank minors is converted to a single determinant. One of the prized constant term problems is solved, and we give a seemingly new approach to Macdonald's constant term for root system of type BC.
Combinatorics of Tripartite Boundary Connections for Trees and Dimers
Authors: Kenyon Richard W. , Wilson David B.
Published: January 2020

A grove is a spanning forest of a planar graph in which every component tree contains at least one of a special subset of vertices on the outer face called nodes. For the natural probability measure on groves, we compute various connection probabilities for the nodes in a random grove. In particular, for "tripartite" pairings of the nodes, the probability can be computed as a Pfaffian in the entries of the Dirichlet-to-Neumann matrix (discrete Hilbert transform) of the graph. These formulas generalize the determinant formulas given by Curtis, Ingerman, and Morrow, and by Fomin, for parallel pairings. These Pfaffian formulas are used to give exact expressions for reconstruction: reconstructing the conductances of a planar graph from boundary measurements. We prove similar theorems for the double-dimer model on bipartite planar graphs.
Combinatorial and Automated Proofs of Certain Identities
Authors: Brereton Justin , Farid Amelia , Karnib Maryam , Marple Gary , Quenon Alex , Tefera Akalu
Published: January 2020

This paper focuses on two binomial identities. The proofs illustrate the power and elegance in enumerative/algebraic combinatorial arguments, modern machine-assisted techniques of Wilf-Zeilberger and the classical tools of generatingfunctionology.
Two Remarks on Skew Tableaux
Authors: Stanley Richard P.
Published: January 2020

This paper contains two results on the number $f^{\sigma/\tau}$ of standard skew Young tableaux of shape $\sigma/\tau$. The first concerns generating functions for certain classes of "periodic" shapes related to work of Gessel-Viennot and Baryshnikov-Romik. The second result gives an evaluation of the skew Schur function $s_{\lambda/\mu}(x)$ at $x=(1,1/2^{2k},1/3^{2k}, \dots)$ for $k=1,2,3$ in terms of $f^{\sigma/\tau}$ for a certain skew shape $\sigma/\tau$ depending on $\lambda/\mu$.
Enumeration of Standard Young Tableaux of certain Truncated Shapes
Authors: Adin Ron M. , King Ronald C. , Roichman Yuval
Published: January 2020

Unexpected product formulas for the number of standard Young tableaux of certain truncated shapes are found and proved. These include shifted staircase shapes minus a square in the NE corner, rectangular shapes minus a square in the NE corner, and some variations.
On the Zeros of Plane Partition Polynomials
Authors: Boyer Robert P. , Parry Daniel T.
Published: January 2020

Let $PL(n)$ be the number of all plane partitions of $n$ while $pp_k(n)$ be the number of plane partitions of $n$ whose trace is exactly $k$. We study the zeros of polynomial versions $Q_n(x)$ of plane partitions where $Q_n(x) = \sum pp_k(n) x^k$. Based on the asymptotics we have developed for $Q_n(x)$ and computational evidence, we determine the limiting behavior of the zeros of $Q_n(x)$ as $n\to\infty$. The distribution of the zeros has a two-scale behavior which has order $n^{2/3}$ inside the unit disk while has order $n$ on the unit circle.
Another Product Construction for Large Sets of Resolvable Directed Triple Systems
Authors: Zhao Hongtao
Published: January 2020

A large set of resolvable directed triple systems of order $v$, denoted by LRDTS$(v)$, is a collection of $3(v-2)$ RDTS$(v)$s based on $v$-set $X$, such that every transitive triple of $X$ occurs as a block in exactly one of the $3(v-2)$ RDTS$(v)$s. In this paper, we use DTRIQ and LR-design to present a new product construction for LRDTS$(v)$s. This provides some new infinite families of LRDTS$(v)$s.
Susceptibility in Inhomogeneous Random Graphs
Authors: Janson Svante , Riordan Oliver
Published: January 2020

We study the susceptibility, i.e., the mean size of the component containing a random vertex, in a general model of inhomogeneous random graphs. This is one of the fundamental quantities associated to (percolation) phase transitions; in practice one of its main uses is that it often gives a way of determining the critical point by solving certain linear equations. Here we relate the susceptibility of suitable random graphs to a quantity associated to the corresponding branching process, and study both quantities in various natural examples.
Plactic relations for $r$-domino tableaux
Authors: Taşkin Müge
Published: January 2020

The work of C. Bonnafé, M.Geck, L. Iancu and T. Lam shows through two conjectures that $r$-domino tableaux have an important role in Kazhdan-Lusztig theory of type $B$ with unequal parameters. In this paper we provide plactic relations on signed permutations which determine whether two given signed permutations have the same insertion $r$-domino tableaux in Garfinkle's algorithm. Moreover, we show that a particular extension of these relations can describe Garfinkle's equivalence relation on $r$-domino tableaux which is given through the notion of open cycles. With these results we enunciate the conjectures of Bonnafé et al. and provide necessary tools for their proofs.
Shi Threshold Arrangement
Authors: Seo Seunghyun
Published: January 2020

Richard Stanley suggested the problem of finding the number of regions and the characteristic polynomial of a certain hyperplane arrangement defined by $x_i + x_j=0,1$, which is called the Shi threshold arrangement. We present the answer of the problem, using the finite field method.
Rainbow Hamilton Cycles in Uniform Hypergraphs
Authors: Dudek Andrzej , Frieze Alan , Ruciński Andrzej
Published: January 2020

Let $K_n^{(k)}$ be the complete $k$-uniform hypergraph, $k\ge3$, and let $\ell$ be an integer such that $1\le \ell\le k-1$ and $k-\ell$ divides $n$. An $\ell$-overlapping Hamilton cycle in $K_n^{(k)}$ is a spanning subhypergraph $C$ of  $K_n^{(k)}$  with $n/(k-\ell)$ edges and such that for some cyclic ordering of the vertices each edge of $C$ consists of $k$ consecutive vertices and every pair of adjacent edges in $C$ intersects in precisely $\ell$ vertices.We show that, for some constant $c=c(k,\ell)$ and sufficiently large $n$, for every coloring (partition) of the edges of $K_n^{(k)}$ which uses arbitrarily many colors but no color appears more than $cn^{k-\ell}$ times, there exists a rainbow $\ell$-overlapping Hamilton cycle $C$, that is every edge of $C$ receives a different color. We also prove that, for some constant $c'=c'(k,\ell)$ and sufficiently large $n$, for every coloring of the edges of $K_n^{(k)}$ in which the maximum degree of the subhypergraph induced by any single color is bounded by $c'n^{k-\ell}$,  there exists a properly colored $\ell$-overlapping Hamilton cycle $C$, that is every two adjacent edges receive different colors. For $\ell=1$, both results are (trivially) best possible up to the constants. It is an open question if our results are also optimal for $2\le\ell\le k-1$.The proofs  rely on a version of the Lovász Local Lemma and incorporate some ideas from Albert, Frieze, and Reed.
Random Subgraphs in Cartesian Powers of Regular Graphs
Authors: Joos Felix
Published: January 2020

Let $G$ be a connected $d$-regular graph with $k$ vertices. We investigate the behaviour of a spanning random subgraph $G^n_p$ of $G^n$, the $n$-th Cartesian power of $G$, which is constructed by deleting each edge independently with probability $1-p$. We prove that $\lim\limits_{n \rightarrow \infty} \mathbb{P}[G^n_p {\rm \ is \ connected}]=e^{-\lambda}$, if $p=p(n)=1-\left(\frac{\lambda_n^{1/n}}{k}\right)^{1/d}$ and $\lambda_n \rightarrow \lambda>0$ as $n \rightarrow \infty$. This extends a result of L. Clark, Random subgraphs of certain graph powers, Int. J. Math. Math. Sci., 32(5):285-292, 2002.
Preface
Authors: Hultman Axel , Linusson Svante , Ziegler Günter M.
Published: January 2020

Preface to the Special Volume in honor of Anders Björner on the occasion of his 60th birthday.
A Dice Rolling Game on a Set of Tori
Authors: Kang Jeehoon , Kim Suh-Ryung , Park Boram
Published: January 2020

Some linear algebraic and combinatorial problems are widely studied in connection with $\sigma$-games. One particularissue is to characterize whether or not a given vector lies in the submodule generated by the rows of a given matrix over a commutative ring. In general, one can solve this problem easily and algorithmically using the linear algebra over commutative ring. However, if the matrix has some combinatorial structure, one may expect that some more can be asserted instead of merely giving an algorithm. A recent outstanding example appeared in this line of research is the paper by Florence and Meunier published in Journal of Algebraic Combinatorics in 2010. In the same spirit, we consider a matrix over  $\mathbb{Z}_n$ to completely characterize the submodule generated by its rows and give a constructive proof. The main idea for the characterization is to find certain good basic elements in the row space and then express a given element as the linear combination of them as well as some additional term.
The Chromatic Index of a Graph Whose Core has Maximum Degree $2$
Authors: Kano Mikio , Akbari Saieed , Ghanbari Maryam , Nikmehr Mohammad Javad
Published: January 2020

Let $G$ be a graph. The core of $G$, denoted by $G_{\Delta}$, is the subgraph of $G$ induced by the vertices of degree $\Delta(G)$, where $\Delta(G)$ denotes the maximum degree of $G$. A $k$-edge coloring of $G$ is a function $f:E(G)\rightarrow L$ such that $|L| = k$ and $f(e_1)\neq f(e_2)$ for all two adjacent edges  $e_1$ and $e_2$ of $G$. The chromatic index of $G$, denoted by $\chi'(G)$, is the minimum number $k$ for which $G$ has a $k$-edge coloring.  A graph $G$ is said to be Class $1$ if $\chi'(G) = \Delta(G)$ and Class $2$ if $\chi'(G) = \Delta(G) + 1$. In this paper it is shown that every connected graph $G$ of even order and with $\Delta(G_{\Delta})\leq 2$ is Class $1$ if $|G_{\Delta}|\leq 9$ or $G_{\Delta}$ is a cycle of order $10$.
A Combinatorial Proof of the Recurrence for Rook Paths
Authors: Jin Emma Yu , Nebel Markus E.
Published: January 2020

Let $a_n$ count the number of $2$-dimensional rook paths $\mathcal{R}_{n,n}$ from $(0,0)$ to $(2n,0)$. Rook paths $\mathcal{R}_{m,n}$ are the lattice paths from $(0,0)$ to $(m+n,m-n)$ with allowed steps $(x,x)$ and $(y,-y)$ where $x,y\in\mathbb{N}^{+}$. In answer to the open question proposed by M. Erickson et al. (2010), we shall present a combinatorial proof for the recurrence of $a_n$, i.e., $(n+1)a_{n+1}+9(n-1)a_{n-1}=2(5n+2)a_n$ with initial conditions $a_0=1$ and $a_1=2$. Furthermore, our proof can be extended to show the recurrence for the number of multiple Dyck paths $d_n$, i.e., $(n+2)d_{n+1}+9(n-1)d_{n-1}=5(2n+1)d_n$ with $d_0=1$ and $d_1=1$, where $d_n=\mathcal{N}_n(4)$ and $\mathcal{N}_n(x)$ is Narayana polynomial.
Edge-Decomposition of Graphs into Copies of a Tree with Four Edges
Authors: Barát János , Gerbner Dániel
Published: January 2020

We study edge-decompositions of highly connected graphs into copies of a given tree. In particular we attack the following conjecture by Barát and Thomassen: for each tree $T$, there exists a natural number $k_T$ such that if $G$ is a $k_T$-edge-connected graph, and $|E(T)|$ divides $|E(G)|$, then $E(G)$ has a decomposition into copies of $T$. As one of our main results it is sufficient to prove the conjecture for bipartite graphs. The same result has been independently obtained by Carsten Thomassen (2013).Let $Y$ be the unique tree with degree sequence $(1,1,1,2,3)$. We prove that if $G$ is a $191$-edge-connected graph of size divisible by $4$, then $G$ has a $Y$-decomposition. This is the first instance of such a theorem, in which the tree is different from a path or a star. Recently Carsten Thomassen proved a more general decomposition theorem for bistars, which yields the same result with a worse constant.
Partition of Graphs and Hypergraphs into Monochromatic Connected Parts
Authors: Fujita Shinya , Furuya Michitaka , Gyárfás András , Tóth Ágnes
Published: January 2020

We show that two results on covering of edge colored graphs by monochromatic connected parts can be extended to partitioning. We prove that for any $2$-edge-colored non-trivial $r$-uniform hypergraph $H$, the vertex set can be partitioned into at most $\alpha (H)-r+2$ monochromatic connected parts, where $\alpha (H)$ is the maximum number of vertices that does not contain any edge. In particular, any $2$-edge-colored graph $G$ can be partitioned into $\alpha(G)$ monochromatic connected parts, where $\alpha (G)$ denotes the independence number of $G$. This extends König's theorem, a special case of Ryser's conjecture. Our second result is about Gallai-colorings, i.e. edge-colorings of graphs without $3$-edge-colored triangles. We show that for any Gallai-coloring of a graph $G$, the vertex set of $G$ can be partitioned into monochromatic connected parts, where the number of parts depends only on $\alpha(G)$. This extends its cover-version proved earlier by Simonyi and two of the authors.
A Note on Zero-Sum 5-Flows in Regular Graphs
Authors: Akbari Saieed , Ghareghani Narges , Khosrovshahi Gholamreza , Zare Sanaz
Published: January 2020

Let $G$ be a graph. A zero-sum flow of $G$ is an assignment of non-zero real numbers to the edges of $G$ such that the sum of the values of all edges incident with each vertex is zero. Let $k$ be a natural number. A zero-sum $k$-flow is a flow with values from the set $\{\pm 1,\ldots ,\pm(k-1)\}$. It has been conjectured that every $r$-regular graph, $r\geq 3$, admits a zero-sum $5$-flow. In this paper we provide an affirmative answer to this conjecture, except for  $r=5$.
A Combinatorial Proof of an Identity for the Divisor Generating Function
Authors: Ando Masanori
Published: January 2020

In this paper, we give combinatorial proofs and new generalizations of $q$-series identities of Dilcher and Uchimura related to divisor function. Some interesting combinatorial results related to partition and arm-length are also presented.
Three Color Ramsey Numbers for Graphs with at most 4 Vertices
Authors: Boza Luis , Dybizbański Janusz , Dzido Tomasz
Published: January 2020

For given graphs $H_{1}, H_{2}, H_{3}$, the 3-color Ramsey number $R(H_{1},$ $H_{2}, H_{3})$ is the smallest integer $n$ such that if we arbitrarily color the edges of the complete graph of order $n$ with $3$ colors, then it always contains a monochromatic copy of $H_{i}$ colored with $i$, for some $1 \leq i \leq 3$.We study the bounds on 3-color Ramsey numbers $R(H_1,H_2,H_3)$, where $H_i$ is an isolate-free graph different from $K_2$ with at most four vertices, establishing that $R(P_4,C_4,K_4)=14$, $R(C_4,K_3,K_4-e)=17$, $R(C_4,K_3+e,K_4-e)=17$, $R(C_4,K_4-e,K_4-e)=19$, $28\le R(C_4,K_4-e,K_4)\le36$, $R(K_3,K_4-e,K_4)\le41$, $R(K_4-e,K_4-e,K_4)\le59$ and $R(K_4-e,K_4,K_4)\le113$. Also, we prove that $R(K_3+e,K_4-e,K_4-e)=R(K_3,K_4-e,K_4-e)$, $R(C_4,K_3+e,K_4)\le\max\{R(C_4,K_3,K_4),29\}\le32$, $R(K_3+e,K_4-e,K_4)\le\max\{R(K_3,K_4-e,K_4),33\}\le41$ and $R(K_3+e,K_4,K_4)\le\max\{R(K_3,K_4,K_4),2R(K_3,K_3,K_4)+2\}\le79$.This paper is an extension of the article by Arste, Klamroth, Mengersen [Utilitas Mathematica, 1996].
The Tight Upper Bound for the Number of Matchings of Tricyclic Graphs
Authors: Dolati Ardeshir , Golalizadeh Somayyeh
Published: January 2020

In this paper, we determine the tight upper bound for the number of matchings of connected $n$-vertex tricyclic graphs. We show that this bound is $13 f_{n-4} + 16f_{n-5}$, where $f_n$ be the  $n$th Fibonacci number. We also  characterize the $n$-vertex simple connected tricyclic graph for which the bound is best  possible.A corrigendum was added to this paper on Jun 17, 2015.
Forbidden Submatrices: Some New Bounds and Constructions
Authors: Anstee R.P. , Chen Ruiyuan
Published: January 2020

We explore an extremal hypergraph problem for which both the vertices and edges are ordered. Given a hypergraph $F$ (not necessarily simple), we consider how many edges a simple hypergraph (no repeated edges) on $m$ vertices can have while forbidding $F$ as a subhypergraph where both hypergraphs have fixed vertex and edge orderings. A hypergraph of $n$ edges on $m$ vertices can be encoded as an $m\times n$ (0,1)-matrix. We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. Given a (0,1)-matrix $F$, we define ${\hbox{fs}}(m,F)$ as the maximum, over all simple matrices $A$ which do not have $F$ as a submatrix, of the number of columns in $A$. The row and column order matter. It is known that if $F$ is $k\times \ell$ then ${\hbox{fs}}(m,F)$ is $O(m^{2k-1-\epsilon})$ where $\epsilon=(k-1)/(13\log_2 \ell)$. Anstee, Frankl, Füredi and Pach have conjectured that if $F$ is $k$-rowed, then  ${\hbox{fs}}(m,F)$ is $O(m^k)$. We show ${\hbox{fs}}(m,F)$ is $O(m^2)$ for $F= \left[{1\,0\,1\,0\,1\atop 0\,1\,0\,1\,0}\cdots\right]$ and for $F= \left[{1\,0\,1\,0\,1\atop 1\,0\,1\,0\,1}\cdots\right]$. The proofs use a type of amortized analysis. We also give some constructions.
Covering n-Permutations with (n+1)-Permutations
Authors: Allison Taylor F , Godbole Anant P , Hawley Kathryn M , Kay Bill
Published: January 2020

Let $S_n$ be the set of all permutations on $[n]:=\{1,2,\ldots,n\}$. We denote by $\kappa_n$ the smallest cardinality of a subset ${\cal A}$ of $S_{n+1}$ that "covers" $S_n$, in the sense that each $\pi\in S_n$ may be found as an order-isomorphic subsequence of some $\pi'$ in ${\cal A}$.  What are general upper bounds on $\kappa_n$?  If we randomly select $\nu_n$ elements of $S_{n+1}$, when does the probability that they cover $S_n$ transition from 0 to 1?  Can we provide a fine-magnification analysis that provides the "probability of coverage"  when $\nu_n$ is around the level given by the phase transition?   In this paper we answer these questions and raise others.
Entrywise Bounds for Eigenvectors of Random Graphs
Authors: Mitra Pradipta
Published: January 2020

Let $G$ be a graph randomly selected from ${\bf G}_{n, p}$, the space of Erdős-Rényi Random graphs with parameters $n$ and $p$, where $p \geq {\log^6 n\over n}$. Also, let $A$ be the adjacency matrix of $G$, and $v_1$ be the first eigenvector of $A$. We provide two short proofs of the following statement: For all $i \in [n]$, for some constant $c>0$ $$\left|v_1(i) - {1\over\sqrt{n}}\right| \leq c {1\over\sqrt{n}} {\log n\over\log (np)} \sqrt{{\log n\over np}}$$ with probability $1 - o(1)$. This gives nearly optimal bounds on the entrywise stability of the first eigenvector of (Erdős-Rényi) Random graphs. This question about entrywise bounds was motivated by a problem in unsupervised spectral clustering. We make some progress towards solving that problem.
Multiranks for Partitions into Multi-Colors
Authors: Zhou Roberta Rui
Published: January 2020

We generalize Hammond-Lewis birank to multiranks for partitions into colors and give combinatorial interpretations for multipartitions such as $b(n)$ defined by H. Zhao and Z. Zhong and $Q_{p_1;p_2}(n)$ defined by Toh congruences modulo 3, 5, 7.
On the Length of a Partial Independent Transversal in a Matroidal Latin Square
Authors: Kotlar Daniel , Ziv Ran
Published: January 2020

We suggest and explore a matroidal version of the Brualdi-Ryser conjecture about Latin squares. We prove that any $n\times n$ matrix, whose rows and columns are bases of a matroid, has an independent partial transversal of length $\lceil2n/3\rceil$. We show that for any $n$, there exists such a matrix with a maximal independent partial transversal of length at most $n-1$.
Counting $1324$, $4231$-Avoiding Permutations
Authors: Albert Michael H. , Atkinson M. D. , Vatter Vincent
Published: January 2020

A complete structural description and enumeration is found for permutations that avoid both $1324$ and $4231$.
The Coin Exchange Problem and the Structure of Cube Tilings
Authors: Kisielewicz Andrzej Piotr , Przeslawski Krzysztof
Published: January 2020

It is shown that if $[0,1)^d+t$, $t\in T$, is a unit cube tiling of $\mathbb{R}^d$, then for every $x\in T$, $y\in \mathbb{R}^d$, and every positive integer $m$ the number $|T\cap (x+\mathbb{Z}^d)\cap([0,m)^d+ y)|$ is divisible by $m$. Furthermore, by a result of Coppersmith and Steinberger on cyclotomic arrays it is proven that for every finite discrete box $D=D_1\times\cdots\times D_d \subseteq x+\mathbb{Z}^d$ of size $m_1\times \cdots\times m_d$ the number $|D\cap T|$ is a linear combination of $m_1,\ldots, m_d$ with non-negative integer coefficients. Several consequences  are collected. A generalization is presented.
The Edit Distance Function and Symmetrization
Authors: Martin Ryan R.
Published: January 2020

The edit distance between two graphs on the same labeled vertex set is the size of the symmetric difference of the edge sets.  The distance between a graph, G, and a hereditary property, ℋ, is the minimum of the distance between G and each G'∈ℋ.  The edit distance function of ℋ is a function of p∈[0,1] and is the limit of the maximum normalized distance between a graph of density p and ℋ.This paper utilizes a method due to Sidorenko [Combinatorica 13(1), pp. 109-120], called "symmetrization", for computing the edit distance function of various hereditary properties.  For any graph H, Forb(H) denotes the property of not having an induced copy of H.  This paper gives some results regarding estimation of the function for an arbitrary hereditary property. This paper also gives the edit distance function for Forb(H), where H is a cycle on 9 or fewer vertices.
The Closed Knight Tour Problem in Higher Dimensions
Authors: Erde Joshua , Golénia Bruno , Golénia Sylvain
Published: January 2020

The problem of existence of closed knight tours for rectangular chessboards was solved by Schwenk in 1991. Last year, in 2011, DeMaio and Mathew provide an extension of this result for $3$-dimensional rectangular boards.  In this article, we give the solution for $n$-dimensional rectangular boards, for $n\geq 4$.
Finding a Princess in a Palace: a Pursuit-Evasion Problem
Authors: Britnell John R , Wildon Mark
Published: January 2020

This paper solves a pursuit-evasion problem in which a prince must find a princess who is constrained to move on each day from one vertex of a finite graph to another. Unlike the related and much studied `Cops and Robbers Game', the prince has no knowledge of the position of the princess; he may, however, visit any single room he wishes on each day. We characterize the graphs for which the prince has a winning strategy, and determine, for each such graph, the minimum number of days the prince requires to guarantee to find the princess.
Combinatorial Expansions in $K$-Theoretic Bases
Authors: Bandlow Jason , Morse Jennifer
Published: January 2020

We study the class $\mathcal C$ of symmetric functions whose coefficients in the Schur basis can be described by generating functions for sets of tableaux with fixed shape.  Included in this class are the Hall-Littlewood polynomials, $k$-Schur functions, and Stanley symmetric functions; functions whose Schur coefficients encode combinatorial, representation theoretic and geometric information. While Schur functions represent the cohomology of the Grassmannian variety of $GL_n$, Grothendieck functions $\{G_\lambda\}$ represent the $K$-theory of the same space.  In this paper, we give a combinatorial description of the coefficients when any element of $\mathcal C$ is expanded in the $G$-basis or the basis dual to $\{G_\lambda\}$.
Geometric Constructions for Symmetric 3-Configurations
Authors: Berman Leah Wrenn
Published: January 2020

A geometric 3-configuration is a collection of points and straight lines, typically in the Euclidean plane, in which every point has 3 lines passing through it and every line has 3 points lying on it, and we say that such configuration is symmetric if there are non-trivial isometries of the plane that map the configuration to itself. Many symmetric 3-configurations may be easily constructed with computer algebra systems using algebraic techniques: e.g., constructing a number of symmetry classes of points and lines, by various means, and then determining the position of a final class of points or lines by solving some polynomial equation. In contrast, this paper presents a number of ruler-and-compass-type constructions for exactly constructing various types of symmetric 3-configurations, as long as the vertices of an initial regular m-gon are explicitly provided. In addition, it provides methods for constructing chirally symmetric 3-configurations given an underlying unlabelled reduced Levi graph, for extending these constructions to produce dihedrally symmetric 3-configurations, and for constructing 3-configurations corresponding to all 3-orbit and 4-orbit reduced Levi graphs that contain a pair of parallel arcs. Notably, most of the configurations described are movable: that is, they have at least one continuous parameter.
Münchhausen Matrices
Authors: Brand Michael
Published: January 2020

"The Baron's omni-sequence", $B(n)$, first defined by Khovanova and Lewis (2011), is a sequence that gives for each $n$ the minimum number of weighings on balance scales that can verify the correct labeling of $n$ identically-looking coins with distinct integer weights between $1$ gram and $n$ grams.A trivial lower bound on $B(n)$ is $\log_3 n$, and it has been shown that $B(n)$ is $\text{O}(\log n)$.We introduce new theoretical tools for the study of this problem, and show that $B(n)$ is $\log_3 n + \text{O}(\log \log n)$, thus settling in the affirmative a conjecture by Khovanova and Lewis that the true growth rate of the sequence is very close to the natural lower bound.
Properties of Random Difference Graphs
Authors: Ross Christopher
Published: January 2020

Generate a bipartite graph on a partitioned set of vertices by randomly assigning to each vertex $v$ some weight $w(v) \in [0,1]$ and adding an edge between vertices $u$ and $v$ (in distinct parts) if and only if $w(v) + w(v) > 1$; the results of such processes are known as difference graphs.Random difference graphs of a given size can be produced either by uniformly random generation of weights or by choosing a graph uniformly at random from the set of all such graphs. We prove that these two methods give rise to the same distribution, and use this equivalence to find exact results for the likelihood of connectivity and Hamiltonicity. We also find the distribution of other properties, such as matching number and degeneracy.
New Proofs of Determinant Evaluations Related to Plane Partitions
Authors: Rosengren Hjalmar
Published: January 2020

We give a new proof of a determinant evaluation due to Andrews, which has been used to enumerate cyclically symmetric and descending plane partitions. We also prove some related results, including a $q$-analogue of Andrews's determinant.
A Plethysm Formula on the Characteristic Map of Induced Linear Characters from $U_n(\mathbb F_q)$ to $GL(\mathbb F_q)$
Authors: Chen Zhi
Published: January 2020

This paper gives a plethysm formula on the characteristic map of the induced linear characters from the unipotent upper-triangular matrices $U_n(\mathbb F_q)$ to $GL_n(\mathbb F_q)$, the general linear group over finite field $\mathbb F_q$. The result turns out to be a multiple of a twisted version of the Hall-Littlewood symmetric functions $\tilde{P}_n[Y;q]$. A recurrence relation is also given which makes it easy to carry out the computation.
Repetition Threshold for Circular Words
Authors: Gorbunova Irina A.
Published: January 2020

We find the threshold between avoidable and unavoidable repetitions in circular words over $k$ letters for any $k\ge6$. Namely, we show that the number $CRT(k)=\frac{\left\lceil {k/2}\right\rceil{+}1}{\left\lceil {k/2}\right\rceil}$ satisfies the following properties.  For any $n$ there exists a $k$-ary circular word of length $n$ containing no repetition of exponent greater than $CRT(k)$. On the other hand, $k$-ary circular words of some lengths must have a repetition of exponent at least $CRT(k)$.
On ${\rm STD}_6[18,3]$'s and ${\rm STD}_7[21,3]$'s Admitting a Semiregular Automorphism Group of Order 9
Authors: Akiyama Kenzi , Ogawa Masayuki , Suetake Chihiro
Published: January 2020

We characterize symmetric transversal designs ${\rm STD}_{\lambda}[k,u]$'s which have a semiregular automorphism group $G$ on both points and blocks containing an elation group of order $u$ using the group ring ${\bf Z}[G]$. Let $n_\lambda$ be the number of nonisomorphic ${\rm STD}_{\lambda}[3\lambda,3]$'s. It is known that $n_1=1,\ n_2=1,\ n_3=4, n_4=1$, and $n_5=0$. We classify ${\rm STD}_6[18,3]$'s and ${\rm STD}_7[21,3]$'s which have a semiregular noncyclic automorphism group of order 9 on both points and blocks containing an elation of order 3 using this characterization. The former case yields exactly twenty nonisomorphic ${\rm STD}_6[18,3]$'s and the latter case yields exactly three nonisomorphic ${\rm STD}_7[21,3]$'s. These yield $n_6\geq20$ and $n_7\geq 5$, because B. Brock and A. Murray constructed two other ${\rm STD}_7[21,3]$'s in 1991. We used a computer for our research.
Classification of Cubic Symmetric Tricirculants
Authors: Kovacs Istvan , Kutnar Klavdija , Marusic Dragan , Wilson Steve
Published: January 2020

A tricirculant is a graph admitting a non-identity automorphism having three cycles of equal length in its cycle decomposition. A graph is said to be symmetric if its automorphism group acts transitively on the set of its arcs. In this paper it is shown that the complete bipartite graph $K_{3,3}$, the Pappus graph, Tutte's 8-cage and the unique cubic symmetric graph of order 54 are the only connected cubic symmetric tricirculants.
Automorphism groups of Cayley digraphs of ${\Bbb Z}_p^3$
Authors: Dobson Edward , Kovács István
Published: January 2020

We calculate the full automorphism group of Cayley digraphs of ${\Bbb Z}_p^3$, $p$ an odd prime, as well as determine the $2$-closed subgroups of $S_m \wr S_p$ with the product action.
An Improvement to Mathon's Cyclotomic Ramsey Colorings
Authors: Xu Xiaodong , Radziszowski Stanisław P.
Published: January 2020

In this note we show how to extend Mathon's cyclotomic colorings of the edges of some complete graphs without increasing the maximum order of monochromatic complete subgraphs. This improves the well known lower bound construction for multicolor Ramsey numbers, in particular we obtain $R_3(7) \ge 3214$.
Spectral Properties of Unitary Cayley Graphs of Finite Commutative Rings
Authors: Liu Xiaogang , Zhou Sanming
Published: January 2020

Let $R$ be a finite commutative ring. The unitary Cayley graph of $R$, denoted $G_R$, is the graph with vertex set $R$ and edge set $\left\{\{a,b\}:a,b\in R, a-b\in R^\times\right\}$, where $R^\times$ is the set of units of $R$. An $r$-regular graph is Ramanujan if the absolute value of every eigenvalue of it other than $\pm r$ is at most $2\sqrt{r-1}$. In this paper we give a necessary and sufficient condition for $G_R$ to be Ramanujan, and a necessary and sufficient condition for the complement of $G_R$ to be Ramanujan. We also determine the energy of the line graph of $G_R$, and compute the spectral moments of $G_R$ and its line graph.
On the Size of Minimal Unsatisfiable Formulas
Authors: Lee Choongbum
Published: January 2020

An unsatisfiable formula is called minimal if it becomes satisfiable whenever any of its clauses are removed. We construct minimal unsatisfiable $k$-SAT formulas with $\Omega(n^k)$ clauses for $k \geq 3$, thereby negatively answering a question of Rosenfeld. This should be compared to the result of Lovász [Studia Scientiarum Mathematicarum Hungarica 11, 1974, p113-114] which asserts that a critically 3-chromatic $k$-uniform hypergraph can have at most ${n\choose k-1}$ edges.
The Cyclic Sieving Phenomenon for Non-Crossing Forests
Authors: Kluge Stefan
Published: January 2020

In this paper we prove that the set of non-crossing forests together with a cyclic group acting on it by rotation and a natural q-analogue of the formula for their number exhibits the cyclic sieving phenomenon, as conjectured by Alan Guo.
Non-Classical Hyperplanes of $DW(5,q)$
Authors: De Bruyn Bart
Published: January 2020

The hyperplanes of the symplectic dual polar space $DW(5,q)$ arising from embedding, the so-called classical hyperplanes of $DW(5,q)$, have been determined earlier in the literature. In the present paper, we classify non-classical hyperplanes of $DW(5,q)$. If $q$ is even, then we prove that every such hyperplane is the extension of a non-classical ovoid of a quad of $DW(5,q)$. If $q$ is odd, then we prove that every non-classical ovoid of $DW(5,q)$ is either a semi-singular hyperplane or the extension of a non-classical ovoid of a quad of $DW(5,q)$. If $DW(5,q)$, $q$ odd, has a semi-singular hyperplane, then $q$ is not a prime number.
Vertex Isoperimetric Inequalities for a Family of Graphs on $\mathbb{Z}^k$
Authors: Veomett Ellen , Radcliffe Andrew John
Published: January 2020

We consider the family of graphs whose vertex set is $\mathbb{Z}^k$ where two vertices are connected by an edge when their $\ell_\infty$-distance is 1.  We prove the optimal vertex isoperimetric inequality for this family of graphs.  That is, given a positive integer $n$, we find a set $A\subset \mathbb{Z}^k$ of size $n$ such that the number of vertices who share an edge with some vertex in $A$ is minimized.  These sets of minimal boundary  are nested, and the proof uses the technique of compression.We also show a method of calculating the vertex boundary for certain subsets in  this family of graphs.  This calculation and the isoperimetric inequality allow us to indirectly find the sets which minimize the function calculating the boundary.
A Short Proof, Based on Mixed Volumes, of Liggett's Theorem on the Convolution of Ultra-Logconcave Sequences
Authors: Gurvits Leonid
Published: January 2020

R. Pemantle conjectured, and T.M. Liggett proved in 1997, that the convolution of two ultra-logconcave is ultra-logconcave. Liggett's proof is elementary but long. We present here a short proof, based on the mixed volume of convex sets.
A Duality Based Proof of the Combinatorial Nullstellensatz
Authors: Kouba Omran
Published: January 2020

In this note we present a proof of the combinatorial nullstellensatz using simple arguments from linear algebra.
Enumerating Lattice Paths Touching or Crossing the Diagonal at a Given Number of Lattice Points
Authors: Spivey Michael Z.
Published: January 2020

We give bijective proofs that, when combined with one of the combinatorial proofs of the general ballot formula, constitute a combinatorial argument yielding the number of lattice paths from $(0,0)$ to $(n,rn)$ that touch or cross the diagonal $y = rx$ at exactly $k$ lattice points.  This enumeration partitions all lattice paths from $(0,0)$ to $(n,rn)$.  While the resulting formula can be derived using results from Niederhausen, the bijections and combinatorial proof are new.
A Note on Divisibility of the Number of Matchings of a Family of Graphs
Authors: Hwang Kyung-Won , Sheikh Naeem N. , Hartke Stephen G.
Published: January 2020

For a certain graph obtained by adding extra vertices and edges to the triangular lattice graph, Propp conjectured that the number of perfect matchings of such a graph is always divisible by $3$. In this note we prove this conjecture.
On the Spanning Trees of the Hypercube and other Products of Graphs
Authors: Bernardi Olivier
Published: January 2020

We give two combinatorial proofs of a product formula for the number of spanning trees of the $n$-dimensional hypercube. The first proof is based on the assertion that if one chooses a uniformly random rooted spanning tree of the hypercube and orient each edge from parent to child, then the parallel edges of the hypercube get orientations which are independent of one another. This independence property actually holds in a more general context and has intriguing consequences. The second proof uses some "killing involutions'' in order to identify the factors in the product formula. It leads to an enumerative formula for the spanning trees of the $n$-dimensional hypercube augmented with diagonals edges, counted according to the number of edges of each type. We also discuss more general formulas, obtained using a matrix-tree approach, for the number of spanning trees of the Cartesian product of complete graphs.
Perfectly Balanced Partitions of Smoothed Graphs
Authors: Ben-Eliezer Ido , Krivelevich Michael
Published: January 2020

For a graph $G=(V,E)$ of even order, a partition $(V_1,V_2)$ of the vertices is said to be perfectly balanced if $|V_1|=|V_2|$ and the numbers of edges in the subgraphs induced by $V_1$ and $V_2$ are equal. For a base graph $H$ define a random graph $G(H,p)$ by turning every non-edge of $H$ into an edge and every edge of $H$ into a non-edge independently with probability $p$. We show that for any constant $\epsilon$ there is a constant $\alpha$, such that for any even $n$ and a graph $H$ on $n$ vertices that satisfies $\Delta(H)-\delta(H) \leq \alpha n$, a graph $G$ distributed according to $G(H,p)$, with ${\epsilon\over n} \leq p \leq 1-{\epsilon\over n}$, admits a perfectly balanced partition with probability exponentially close to $1$. As a direct consequence we get that for every $p$, a random graph from $G(n,p)$ admits a perfectly balanced partition with probability tending to $1$.
Non-Repetitive 3-Coloring of Subdivided Graphs
Authors: Pezarski Andrzej , Zmarz Michał
Published: January 2020

We show that every graph can be subdivided in a way that the resulting graph can be colored without repetitions on paths using only 3 colors. This extends the result of Thue asserting the existence of arbitrarily long nonrepetitive strings over a 3-letter alphabet.
Viewing Determinants as Nonintersecting Lattice Paths yields Classical Determinantal Identities Bijectively
Authors: Fulmek Markus
Published: January 2020

In this paper, we show how general determinants may be viewed as generating functions of nonintersecting lattice paths, using the Lindström-Gessel-Viennot-method and the Jacobi Trudi identity together with elementary observations.After some preparations, this point of view provides "graphical proofs'' for classical determinantal identities like the Cauchy-Binet formula, Dodgson's condensation formula, the Plücker relations, Laplace's expansion and Turnbull's identity. Also, a determinantal identity generalizing Dodgson's condensation formula is presented, which might be new.
Affine Primitive Groups and Semisymmetric Graphs
Authors: Han Hua , Lu Zaiping
Published: January 2020

In this paper, we investigate semisymmetric graphs which arise from affine primitive permutation groups. We give a characterization of such graphs, and then construct an infinite family of semisymmetric graphs which contains the Gray graph as the third smallest member. Then, as a consequence, we obtain a factorization,of the complete bipartite graph $K_{p^{sp^t},p^{sp^t}}$ into connected semisymmetric graphs, where $p$ is an prime, $1\le t\le s$ with $s\ge2$ while $p=2$.
On the Number of Partition Weights with Kostka Multiplicity One
Authors: Gates Zachary , Goldman Brian , Vinroot C. Ryan
Published: January 2020

Given a positive integer $n$, and partitions $\lambda$ and $\mu$ of $n$, let $K_{\lambda \mu}$ denote the Kostka number, which is the number of semistandard Young tableaux of shape $\lambda$ and weight $\mu$.  Let $J(\lambda)$ denote the number of $\mu$ such that $K_{\lambda \mu} = 1$.  By applying a result of Berenshtein and Zelevinskii, we obtain a formula for $J(\lambda)$ in terms of restricted partition functions, which is recursive in the number of distinct part sizes of $\lambda$.  We use this to classify all partitions $\lambda$ such that $J(\lambda) = 1$ and all $\lambda$ such that $J(\lambda) = 2$.  We then consider signed tableaux, where a semistandard signed tableau of shape $\lambda$ has entries from the ordered set $\{0 < \bar{1} < 1 < \bar{2} < 2 < \cdots \}$, and such that $i$ and $\bar{i}$ contribute equally to the weight.  For a weight $(w_0, \mu)$ with $\mu$ a partition, the signed Kostka number $K^{\pm}_{\lambda,(w_0, \mu)}$ is defined as the number of semistandard signed tableaux of shape $\lambda$ and weight $(w_0, \mu)$, and $J^{\pm}(\lambda)$ is then defined to be the number of weights $(w_0, \mu)$ such that $K^{\pm}_{\lambda, (w_0, \mu)} = 1$.  Using different methods than in the unsigned case, we find that the only nonzero value which $J^{\pm}(\lambda)$ can take is $1$, and we find all sequences of partitions with this property.  We conclude with an application of these results on signed tableaux to the character theory of finite unitary groups.
Resolving Sets and Semi-Resolving Sets in Finite Projective Planes
Authors: Héger Tamás , Takáts Marcella
Published: January 2020

In a graph $\Gamma=(V,E)$ a vertex $v$ is resolved by a vertex-set $S=\{v_1,\ldots,v_n\}$ if its (ordered) distance list with respect to $S$, $(d(v,v_1),\ldots,d(v,v_n))$, is unique. A set $A\subset V$ is resolved by $S$ if all its elements are resolved by $S$. $S$ is a resolving set in $\Gamma$ if it resolves $V$. The metric dimension of $\Gamma$ is the size of the smallest resolving set in it. In a bipartite graph a semi-resolving set is a set of vertices in one of the vertex classes that resolves the other class.We show that the metric dimension of the incidence graph of a finite projective plane of order $q\geq 23$ is $4q-4$, and describe all resolving sets of that size. Let $\tau_2$ denote the size of the smallest double blocking set in PG$(2,q)$, the Desarguesian projective plane of order $q$. We prove that for a semi-resolving set $S$ in the incidence graph of PG$(2,q)$, $|S|\geq \min \{2q+q/4-3, \tau_2-2\}$ holds. In particular, if $q\geq9$ is a square, then the smallest semi-resolving set in PG$(2,q)$ has size $2q+2\sqrt{q}$. As a corollary, we get that a blocking semioval in PG$(2, q)$, $q\geq 4$, has at least $9q/4-3$ points. A corrigendum was added to this paper on March 3, 2017.
Involutions on Standard Young Tableaux and Divisors on Metric Graphs
Authors: Agrawal Rohit , Musiker Gregg , Sotirov Vladimir , Wei Fan
Published: January 2020

We elaborate upon a bijection discovered by Cools, Draisma, Payne, and Robeva (2012) between the set of rectangular standard Young tableaux and the set of equivalence classes of chip configurations on certain metric graphs under the relation of linear equivalence. We present an explicit formula for computing the $v_0$-reduced divisors (representatives of the equivalence classes) associated to given tableaux, and use this formula to prove (i) evacuation of tableaux corresponds (under the bijection) to reflecting the metric graph, and (ii) conjugation of the tableaux corresponds to taking the Riemann-Roch dual of the divisor.
Paths and Stability Number in Digraphs
Authors: Fox Jacob , Sudakov Benny
Published: January 2020

The Gallai-Milgram theorem says that the vertex set of any digraph with stability number $k$ can be partitioned into $k$ directed paths. In 1990, Hahn and Jackson conjectured that this theorem is best possible in the following strong sense. For each positive integer $k$, there is a digraph $D$ with stability number $k$ such that deleting the vertices of any $k-1$ directed paths in $D$ leaves a digraph with stability number $k$. In this note, we prove this conjecture.
Properties of the Corolla Polynomial of a 3-regular Graph
Authors: Kreimer Dirk , Yeats Karen
Published: January 2020

We investigate combinatorial properties of a graph polynomial indexed by half-edges of a graph which was introduced recently to understand the connection between Feynman rules for scalar field theory and Feynman rules for gauge theory. We investigate the new graph polynomial as a stand-alone object.