bluuebunny/crossref_metadata_2025 huggingface dataset:
Note on the Subgraph Component Polynomial
Authors: Liao Yunhua , Hou Yaoping
Published: January 2020

Tittmann, Averbouch and Makowsky [The enumeration of vertex induced subgraphs with respect to the number of components, European J. Combin. 32 (2011) 954-974] introduced the subgraph component polynomial $Q(G;x,y)$ of a graph $G$, which counts the number of connected components in vertex induced subgraphs. This polynomial encodes a large amount of combinatorial information about the underlying graph, such as the order, the size, and the independence number. We show that several other graph invariants, such as the connectivity and the number of cycles of length four in a regular bipartite graph are also determined by the subgraph component polynomial. Then, we prove that several well-known families of graphs are determined by the polynomial $Q(G;x,y).$ Moreover, we study the distinguishing power and find simple graphs which are not distinguished by the subgraph component polynomial but distinguished by the characteristic polynomial, the matching polynomial and the Tutte polynomial. These are partial answers to three open problems proposed by Tittmann et al.
Extending Cycles Locally to Hamilton Cycles
Authors: Hamann Matthias , Lehner Florian , Pott Julian
Published: January 2020

A Hamilton circle in an infinite graph is a homeomorphic copy of the  unit circle $S^1$ that contains all vertices and all ends precisely once. We prove that every connected, locally connected, locally finite, claw-free graph has such a Hamilton circle, extending a result of Oberly and Sumner to infinite graphs. Furthermore, we show that such graphs are Hamilton-connected if and only if they are $3$-connected, extending a result of Asratian. Hamilton-connected means that between any two vertices there is a Hamilton arc, a homeomorphic copy of the unit interval $[0,1]$ that contains all vertices and all ends precisely once.
Enumerating Pattern Avoidance for Affine Permutations
Authors: Crites Andrew
Published: January 2020

In this paper we study pattern avoidance for affine permutations. In particular, we show that for a given pattern $p$, there are only finitely many affine permutations in $\widetilde{S}_n$ that avoid $p$ if and only if $p$ avoids the pattern 321. We then count the number of affine permutations that avoid a given pattern $p$ for each $p$ in $S_3$, as well as give some conjectures for the patterns in $S_4$.
The Weak Order on Pattern-Avoiding Permutations
Authors: Drake Brian
Published: January 2020

The weak order on the symmetric group is a well-known partial order which is also a lattice. We consider subposets of the weak order consisting of permutations avoiding a single pattern, characterizing the patterns for which the subposet is a lattice. These patterns have only a single small ascent or descent. We prove that all patterns for which the subposet is a sublattice have length at most three.
Decomposing Complete Equipartite Graphs into Short Odd Cycles
Authors: Smith Benjamin R. , Cavenagh Nicholas J.
Published: January 2020

In this paper we examine the problem of decomposing the lexicographic product of a cycle with an empty graph into cycles of uniform length. We determine necessary and sufficient conditions for a solution to this problem when the cycles are of odd length. We apply this result to find necessary and sufficient conditions to decompose a complete equipartite graph into cycles of uniform length, in the case that the length is both odd and short relative to the number of parts.
Trivial Meet and Join within the Lattice of Monotone Triangles
Authors: Engbers John , Hammett Adam
Published: January 2020

The lattice of monotone triangles $(\mathfrak{M}_n,\leq)$ ordered by entry-wise comparisons is studied. Let $\tau_{\min}$ denote the unique minimal element in this lattice, and $\tau_{\max}$ the unique maximum. The number of $r$-tuples of monotone triangles $(\tau_1,\ldots,\tau_r)$ with minimal infimum $\tau_{\min}$ (maximal supremum $\tau_{\max}$, resp.) is shown to asymptotically approach $r|\mathfrak{M}_n|^{r-1}$ as $n \to \infty$. Thus, with high probability this event implies that one of the $\tau_i$ is $\tau_{\min}$ ($\tau_{\max}$, resp.). Higher-order error terms are also discussed.
Order Polynomials and Pólya's Enumeration Theorem
Authors: Jochemko Katharina
Published: January 2020

Pólya’s enumeration theorem states that the number of labelings of a finite set up to symmetry is given by a polynomial in the number of labels. We give a new perspective on this theorem by generalizing it to partially ordered sets and order preserving maps. Further we prove a reciprocity statement in terms of strictly order preserving maps generalizing a classical result by Stanley (1970). We apply our results to counting graph colorings up to symmetry.
Pairs of Quadratic Forms over Finite Fields
Authors: Pott Alexander , Schmidt Kai-Uwe , Zhou Yue
Published: January 2020

Let $\mathbb{F}_q$ be a finite field with $q$ elements and let $X$ be a set of matrices over $\mathbb{F}_q$. The main results of this paper are explicit expressions for the number of pairs $(A,B)$ of matrices in $X$ such that $A$ has rank $r$, $B$ has rank $s$, and $A+B$ has rank $k$ in the cases that (i) $X$ is the set of alternating matrices over $\mathbb{F}_q$ and (ii) $X$ is the set of symmetric matrices over $\mathbb{F}_q$ for odd $q$. Our motivation to study these sets comes from their relationships to quadratic forms. As one application, we obtain the number of quadratic Boolean functions that are simultaneously bent and negabent, which solves a problem due to Parker and Pott.
Modular Statistics for Subgraph Counts in Sparse Random Graphs
Authors: DeMarco Bobby , Kahn Jeff , Redlich Amanda
Published: January 2020

Answering a question of Kolaitis and Kopparty, we show that, for given integer $q>1$ and pairwise nonisomorphic connected graphs $G_1,\dots, G_k$, if $p=p(n) $ is such that $\Pr(G_{n,p}\supseteq G_i)\rightarrow 1$ $\forall i$, then, with $\xi_i$ the number of copies of $G_i$ in $G_{n,p}$, $(\xi_1,\dots, \xi_k)$ is asymptotically uniformly distributed on ${\bf Z}_q^k$.
Graph Homomorphisms between Trees
Authors: Csikvári Péter , Lin Zhicong
Published: January 2020

In this paper we study several problems concerning the number of homomorphisms of trees. We begin with an algorithm for the number of homomorphisms from a tree to any graph. By using this algorithm and some transformations on trees, we study various extremal problems about the number of homomorphisms of trees. These applications include a far reaching generalization and a dual of Bollobás and Tyomkyn's result concerning the number of walks in trees.Some other main results of the paper are the following. Denote by $\hom(H,G)$ the number of homomorphisms from a graph $H$ to a graph $G$. For any tree $T_m$ on $m$ vertices we give a general lower bound for $\hom(T_m,G)$ by certain entropies of Markov chains defined on the graph $G$. As a particular case, we show that for any graph $G$, $$\exp(H_{\lambda}(G))\lambda^{m-1}\leq\hom(T_m,G),$$ where $\lambda$ is the largest eigenvalue of the adjacency matrix of $G$ and $H_{\lambda}(G)$ is a certain constant depending only on $G$ which we call the spectral entropy of $G$. We also show that if $T_m$ is any fixed tree and$$\hom(T_m,P_n)>\hom(T_m,T_n),$$for some tree $T_n$ on $n$ vertices, then $T_n$ must be the tree obtained from a path $P_{n-1}$ by attaching a pendant vertex to the second vertex of $P_{n-1}$.All the results together enable us to show that among all trees with fixed number of vertices, the path graph has the fewest number of endomorphisms while the star graph has the most.
Covering a Graph with Cycles of Length at Least 4
Authors: Wang Hong
Published: January 2020

Let $G$ be a graph of order $n\geq 4k$, where $k$ is a positive integer. Suppose that the minimum degree of $G$ is at least $\lceil n/2\rceil$. We show that $G$ contains $k$ vertex-disjoint cycles covering all the vertices of $G$ such that $k-1$ of them are quadrilaterals.
A Survey of Minimum Saturated Graphs
Authors: Faudree Jill R. , Faudree Ralph J. , Schmitt John R.
Published: January 2020

Given a family of (hyper)graphs $\mathcal{F}$ a (hyper)graph $G$ is said to be $\mathcal{F}$-saturated if $G$ is $F$-free for any $F \in\mathcal{F}$ but for any edge e in the complement of $G$ the (hyper)graph $G + e$ contains some $F\in\mathcal{F}$. We survey the problem of determining the minimum size of an $\mathcal{F}$-saturated (hyper)graph and collect many open problems and conjectures.
Nordhaus-Gaddum Type Inequalities for Laplacian and Signless Laplacian Eigenvalues
Authors: Ashraf F. , Tayfeh-Rezaie B.
Published: January 2020

Let $G$ be a graph with $n$ vertices. We denote the largest signless Laplacian eigenvalue of $G$ by $q_1(G)$ and Laplacian eigenvalues of $G$ by $\mu_1(G)\ge\cdots\ge\mu_{n-1}(G)\ge\mu_n(G)=0$. It is a conjecture on Laplacian spread of graphs that $\mu_1(G)-\mu_{n-1}(G)\le n-1$ or equivalently $\mu_1(G)+\mu_1(\overline G)\le2n-1$. We prove the conjecture for bipartite graphs. Also we show that for any bipartite graph $G$, $\mu_1(G)\mu_1(\overline G)\le n(n-1)$. Aouchiche and Hansen [Discrete Appl. Math. 2013] conjectured that $q_1(G)+q_1(\overline G)\le3n-4$ and $q_1(G)q_1(\overline G)\le2n(n-2)$. We prove the former and disprove the latter by constructing a family of graphs $H_n$ where $q_1(H_n)q_1(\overline{H_n})$ is about $2.15n^2+O(n)$.
A Note on Covering Edge Colored Hypergraphs by Monochromatic Components
Authors: Fujita Shinya , Furuya Michitaka , Gyárfás András , Tóth Ágnes
Published: January 2020

For $r\geq 2$, $\alpha \geq r-1$ and $k\geq 1$, let $c(r,\alpha ,k)$ be the smallest integer $c$ such that the vertex set of any non-trivial $r$-uniform $k$-edge-colored hypergraph ${\cal H}$ with $\alpha ({\cal H})=\alpha$ can be covered by $c$ monochromatic connected components. Here $\alpha({\cal{H}})$ is the maximum cardinality of a subset $A$ of vertices in $\cal{H}$ such that $A$ does not contain any edges. An old conjecture of Ryser is equivalent to $c(2,\alpha,k)=\alpha (r-1)$ and a recent result of Z. Király states that $c(r,r-1,k)=\lceil \frac{k}{r}\rceil$ for any $r\ge 3$.Here we make the first step to treat non-complete hypergraphs, showing that $c(r,r,r)=2$ for $r\ge 2$ and $c(r,r,r+1)=3$ for $r\ge 3$.
On the most Weight $w$ Vectors in a Dimension $k$ Binary Code
Authors: Kramer Joshua Brown
Published: January 2020

Ahlswede, Aydinian, and Khachatrian posed the following problem: what is the maximum number of Hamming weight $w$ vectors in a $k$-dimensional subspace of $\mathbb{F}_2^n$? The answer to this question could be relevant to coding theory, since it sheds light on the weight distributions of binary linear codes. We give some partial results. We also provide a conjecture for the complete solution when $w$ is odd as well as for the case $k \geq 2w$ and $w$ even. One tool used to study this problem is a linear map that decreases the weight of nonzero vectors by a constant. We characterize such maps.
Thin Edges in Braces
Authors: Lucchesi Cláudio L. , De Carvalho Marcelo H. , Murty U. S. R.
Published: January 2020

The bicontraction of a vertex $v$ of degree two in a graph, with precisely two neighbours $v_1$ and $v_2$, consists of shrinking the set $\{v_1,v,v_2\}$ to a single vertex.  The retract of a matching covered graph $G$, denoted by $\widehat{G}$, is the graph obtained from $G$ by repeatedly bicontracting vertices of degree two.  Up to isomorphism, the retract of a matching covered graph $G$ is unique. If $G$ is a brace on six or more vertices, an edge $e$ of $G$ is thin if $\widehat{G-e}$ is a brace.  A thin edge $e$ in a simple brace $G$ is strictly thin if $\widehat{G-e}$ is a simple brace. Theorems concerning the existence of strictly thin edges have been used (implicitly by McCuaig (Pólya's Permanent Problem, Electron. J. of Combin., 11, 2004) and explicitly by the authors (On the Number of Perfect Matchings in a Bipartite Graph, SIAM J. Discrete Math., 27, 940-958, 2013)) as inductive tools for establishing properties of braces.Let $G$ and $J$ be two distinct braces, where $G$ is of order six or more and $J$ is a simple matching minor of $G$.  It follows from a theorem of McCuaig (Brace Generation, J. Graph Theory, 38, 124-169, 2001) that $G$ has a thin edge $e$ such that $J$ is a matching minor of $G-e$.  In Section 2, we give an alternative, and simpler proof, of this assertion. Our method of proof lends itself to proving stronger results concerning thin edges.Let ${\cal G}^+$ denote the family of braces consisting of all prisms, all Möbius ladders, all biwheels, and all extended biwheels.  Strengthening another result of McCuaig on brace generation, we show that every simple brace of order six or more which is not a member of ${\cal G}^+$ has at least two strictly thin edges. We also give examples to show that this result is best possible.
Multiple Coverings with Closed Polygons
Authors: Kovács István , Tóth Géza
Published: January 2020

A planar set $P$ is said to be cover-decomposable if there is a constant $k=k(P)$ such that every $k$-fold covering of the plane with translates of $P$ can be decomposed into two coverings. It is known that open convex polygons are cover-decomposable. Here we show that closed, centrally symmetric convex polygons are also cover-decomposable. We also show that an infinite-fold covering of the plane with translates of $P$ can be decomposed into two infinite-fold coverings. Both results hold for coverings of any subset of the plane.
On Groups all of whose Undirected Cayley Graphs of Bounded Valency are Integral
Authors: Estélyi István , Kovács István
Published: January 2020

A finite group $G$ is called Cayley integral if all undirected Cayley graphs over $G$ are integral, i.e., all eigenvalues of the graphs are integers. The Cayley integral groups have been determined by Kloster and Sander in the abelian case, and by Abdollahi and Jazaeri, and independently by Ahmady, Bell and Mohar in the non-abelian case. In this paper we generalize this class of groups by introducing the class $\mathcal{G}_k$ of finite groups $G$ for which all graphs $\mathrm{Cay}(G,S)$ are integral if $|S| \le k$. It will be proved that $\mathcal{G}_k$ consists of the Cayley integral groups if $k \ge 6;$ and the classes $\mathcal{G}_4$ and $\mathcal{G}_5$ are equal, and consist of: (1) the Cayley integral groups, (2) the generalized dicyclic groups $Dic(E_{3^n} \times \mathbb{Z}_6),$ where $n \ge 1$.
Matchings and Partial Patterns
Authors: Jelínek Vít , Mansour Toufik
Published: January 2020

A matching of size $2n$ is a partition of the set $[2n]=\{1,2,\dotsc,2n\}$ into $n$ disjoint pairs. A matching may be identified with a canonical sequence, which is a sequence of integers in which each integer $i\in[n]$ occurs exactly twice, and the first occurrence of $i$ precedes the first occurrence of $i+1$. A partial pattern with $k$ symbols is a sequence of integers from the set $[k]$, in which each $i\in[k]$ appears at least once and at most twice, and the first occurrence of $i$ always precedes the first occurrence of $i+1$. Given a partial pattern $\sigma$ and a matching $\mu$, we say that $\mu$ avoids $\sigma$ if the canonical sequence of $\mu$ has no subsequence order-isomorphic to $\sigma$. Two partial patterns $\tau$ and $\sigma$ are equivalent if there is a size-preserving bijection between $\tau$-avoiding and $\sigma$-avoiding matchings. In this paper, we describe several families of equivalent pairs of patterns, most of them involving infinitely many equivalent pairs. We verify by computer enumeration that these families contain all the equivalences among patterns of length at most six. Many of our arguments exploit a close connection between partial patterns and fillings of diagrams.
On Obstacle Numbers
Authors: Dujmović Vida , Morin Pat
Published: January 2020

The obstacle number is a new graph parameter introduced by Alpert, Koch, and Laison (2010). Mukkamala et al. (2012) show that there exist graphs with $n$ vertices having obstacle number in $\Omega(n/\log n)$. In this note, we up this lower bound to $\Omega(n/(\log\log n)^2)$. Our proof makes use of an upper bound of Mukkamala et al. on the number of graphs having obstacle number at most $h$ in such a way that any subsequent improvements to their upper bound will improve our lower bound.
A Combinatorial Approach to Ebert's Hat Game with Many Colors
Authors: Tantipongpipat Uthaipon
Published: January 2020

This paper proves an optimal strategy for Ebert's hat game with three players and more than two hat colors. In general, for $n$ players and $k$ hat colours, we construct a strategy that is asymptotically optimal as $k\rightarrow \infty$. Computer calculation for particular values of $n$ and $k$ suggests that, as long as $n$ is linear with $k$, the strategy is asymptotically optimal. We conclude by comparing our strategy with the strategy of Lenstra and Seroussi and with the bound of Alon, and suggest our strategy is better when $2k \geq n \geq 7$.
Completing Partial Proper Colorings using Hall's Condition
Authors: Holliday Sarah , Vandenbussche Jennifer , Westlund Erik E
Published: January 2020

In the context of list-coloring the vertices of a graph, Hall's condition is a generalization of Hall's Marriage Theorem and is necessary (but not sufficient) for a graph to admit a proper list-coloring. The graph $G$ with list assignment $L$ satisfies Hall's condition if for each subgraph $H$ of $G$, the inequality $|V(H)| \leq \sum_{\sigma \in \mathcal{C}} \alpha(H(\sigma, L))$ is satisfied, where $\mathcal{C}$ is the set of colors and $\alpha(H(\sigma, L))$ is the independence number of the subgraph of $H$ induced on the set of vertices having color $\sigma$ in their lists. A list assignment $L$ to a graph $G$ is called Hall if $(G,L)$ satisfies Hall's condition. A graph $G$ is Hall $m$-completable for some $m \geq \chi(G)$ if every partial proper $m$-coloring of $G$ whose corresponding list assignment is Hall can be extended to a proper coloring of $G$. In 2011, Bobga et al. posed the following questions: (1) Are there examples of graphs that are Hall $m$-completable, but not Hall $(m+1)$-completable for some $m \geq 3$? (2) If $G$ is neither complete nor an odd cycle, is $G$ Hall $\Delta(G)$-completable? This paper establishes that for every $m \geq 3$, there exists a graph that is Hall $m$-completable but not Hall $(m+1)$-completable and also that every bipartite planar graph $G$ is Hall $\Delta(G)$-completable.
A Probabilistic Approach to the Asymptotics of the Length of the Longest Alternating Subsequence
Authors: Houdré Christian , Restrepo Ricardo
Published: January 2020

Let $LA_{n}(\tau)$ be the length of the longest alternating subsequence of a uniform random permutation $\tau\in\left[ n\right] $. Classical probabilistic arguments are used to rederive the asymptotic mean, variance and limiting law of $LA_{n}\left( \tau\right) $. Our methodology is robust enough to tackle similar problems for finite alphabet random words or even Markovian sequences in which case our results are mainly original. A sketch of how some cases of pattern restricted permutations can also be tackled with probabilistic methods is finally presented.
$\lambda$-Factorials of $n$
Authors: Sun Yidong , Zhuang Jujuan
Published: January 2020

Recently, by the Riordan identity related to tree enumerations, \begin{align*} \sum_{k=0}^{n}\binom{n}{k}(k+1)!(n+1)^{n-k} = (n+1)^{n+1}, \end{align*} Sun and Xu have derived another analogous one, \begin{align*} \sum_{k=0}^{n}\binom{n}{k}D_{k+1}(n+1)^{n-k} = n^{n+1}, \end{align*} where $D_{k}$ is the number of permutations with no fixed points on $\{1,2,\dots, k\}$. In the paper, we utilize the $\lambda$-factorials of $n$, defined by Eriksen, Freij and W$\ddot{a}$stlund, to give a unified generalization of these two identities. We provide for it a combinatorial proof by the functional digraph theory and two algebraic proofs. Using the umbral representation of our generalized identity and Abel's binomial formula, we deduce several properties for $\lambda$-factorials of $n$ and establish interesting relations between the generating functions of general and exponential types for any sequence of numbers or polynomials.
Chromatic Bounds on Orbital Chromatic Roots
Authors: Kim Dae Hyun , Mun Alexander H. , Omar Mohamed
Published: January 2020

Given a group $G$ of automorphisms of a graph $\Gamma$, the orbital chromatic polynomial $OP_{\Gamma,G}(x)$ is the polynomial whose value at a positive integer $k$ is the number of orbits of $G$ on proper $k$-colorings of $\Gamma.$ Cameron and Kayibi introduced this polynomial as a means of understanding roots of chromatic polynomials. In this light, they posed a problem asking whether the real roots of the orbital chromatic polynomial of any graph are bounded above by the largest real root of its chromatic polynomial. We resolve this problem in a resounding negative by not only constructing a counterexample, but by providing a process for generating families of counterexamples. We additionally begin the program of finding classes of graphs whose orbital chromatic polynomials have real roots bounded above by the largest real root of their chromatic polynomials; in particular establishing this for many outerplanar graphs.
Sphere Representations, Stacked Polytopes, and the Colin de Verdière Number of a Graph
Authors: Mitchell Lon , Yengulalp Lynne
Published: January 2020

We prove that a $k$-tree can be viewed as a subgraph of a special type of $(k+1)$-tree that corresponds to a stacked polytope and that these "stacked'' $(k+1)$-trees admit representations by orthogonal spheres in $\mathbb{R}^{k+1}$. As a result, we derive lower bounds for Colin de Verdière's $\mu$ of complements of partial $k$-trees and prove that $\mu(G) + \mu(\overline{G}) \geq |G| - 2$ for all chordal $G$.
Flows in Signed Graphs with Two Negative Edges
Authors: Rollová Edita , Schubert Michael , Steffen Eckhard
Published: January 2020

The presented paper studies the flow number $F(G,\sigma)$ of flow-admissible signed graphs $(G,\sigma)$ with two negative edges. We restrict our study to cubic graphs, because for each non-cubic signed graph $(G,\sigma)$ there is a set of cubic graphs obtained from $(G,\sigma)$ such that the flow number of $(G,\sigma)$ does not exceed the flow number of any of the cubic graphs. We prove that $F(G,\sigma) \leq 6$ if $(G,\sigma)$ contains a bridge, and $F(G,\sigma) \leq 7$ in general. We prove better bounds, if there is a cubic graph $(H,\sigma_H)$ obtained from $(G,\sigma)$ which satisfies some additional conditions. In particular, if $H$ is bipartite, then $F(G,\sigma) \leq 4$ and the bound is tight. If $H$ is $3$-edge-colorable or critical or if it has a sufficient cyclic edge-connectivity, then $F(G,\sigma) \leq 6$. Furthermore, if Tutte's $5$-Flow Conjecture is true, then $(G,\sigma)$ admits a nowhere-zero $6$-flow endowed with some strong properties.
Extensions of Infinite Partition Regular Systems
Authors: Hindman Neil , Leader Imre , Strauss Dona
Published: January 2020

A finite or infinite matrix $A$ with rational entries (and only finitely many non-zero entries in each row) is called image partition regular if, whenever the natural numbers are finitely coloured, there is a vector $x$, with entries in the natural numbers, such that $Ax$ is monochromatic. Many of the classicial results of Ramsey theory are naturally stated in terms of image partition regularity.Our aim in this paper is to investigate maximality questions for image partition regular matrices.  When is it possible to add rows on to $A$ and remain image partition regular? When can one add rows but `nothing new is produced'? What about adding rows and also new variables? We prove some results about extensions of the most interesting infinite systems, and make several conjectures.Our most surprising positive result is a compatibility result for Milliken-Taylor systems, stating that (in many cases) one may adjoin one Milliken-Taylor system to a translate of another and remain image partition regular. This is in contrast to earlier results, which had suggested a strong inconsistency between different Milliken-Taylor systems. Our main tools for this are some algebraic properties of $\beta {\mathbb N}$, the Stone-Čech compactification of the natural numbers.
Invariant Tensors and the Cyclic Sieving Phenomenon
Authors: Westbury Bruce W.
Published: January 2020

We construct a large class of examples of the cyclic sieving phenomenon by exploiting the representation theory of semi-simple Lie algebras. Let $M$ be a finite dimensional representation of a semi-simple Lie algebra and let $B$ be the associated Kashiwara crystal. For $r\ge 0$, the triple $(X,c,P)$ which exhibits the cyclic sieving phenomenon is constructed as follows: the set $X$ is the set of isolated vertices in the crystal $\otimes^rB$; the map $c\colon X\rightarrow X$ is a generalisation of promotion acting on standard tableaux of rectangular shape and the polynomial $P$ is the fake degree of the Frobenius character of a representation of $\mathfrak{S}_r$ related to the natural action of $\mathfrak{S}_r$ on the subspace of invariant tensors in $\otimes^rM$. Taking $M$ to be the defining representation of $\mathrm{SL}(n)$ gives the cyclic sieving phenomenon for rectangular tableaux.
A Note on Circuit Graphs
Authors: Cui Qing
Published: January 2020

We give a short proof of Gao and Richter's theorem that every circuit graph contains a closed walk visiting each vertex once or twice.
Classification of ($p,q,n$)-Dipoles on Nonorientable Surfaces
Authors: Yang Yan , Liu Yanpei
Published: January 2020

A type of rooted map called $(p,q,n)$-dipole, whose numbers on surfaces have some applications in string theory, are defined and the numbers of $(p,q,n)$-dipoles on orientable surfaces of genus 1 and 2 are given by Visentin and Wieler (The Electronic Journal of Combinatorics 14 (2007),#R12). In this paper, we study the classification of $(p,q,n)$-dipoles on nonorientable surfaces and obtain the numbers of $(p,q,n)$-dipoles on the projective plane and Klein bottle.
Zeros of Jones Polynomials of Graphs
Authors: Dong Fengming , Jin Xian'an
Published: January 2020

In this paper, we introduce the Jones polynomial of a graph $G=(V,E)$ with $k$  components as the following specialization of the Tutte polynomial:$$J_G(t)=(-1)^{|V|-k}t^{|E|-|V|+k}T_G(-t,-t^{-1}).$$We first study its basic properties and determine certain extreme coefficients. Then we prove that $(-\infty, 0]$ is a zero-free interval of Jones polynomials of connected bridgeless graphs while for any small $\epsilon>0$ or large $M>0$, there is a zero of the Jones polynomial of a plane graph in $(0,\epsilon)$, $(1-\epsilon,1)$, $(1,1+\epsilon)$ or $(M,+\infty)$. Let $r(G)$ be the maximum moduli of zeros of $J_G(t)$. By applying Sokal's result on zeros of Potts model partition functions and Lucas's theorem, we prove that\begin{eqnarray*}{q_s-|V|+1\over |E|}\leq r(G)<1+6.907652\Delta_G\end{eqnarray*}for any connected bridgeless and loopless graph $G=(V,E)$ of maximum degree $\Delta_G$ with $q_s$ parallel classes. As a consequence of the upper bound, X.-S. Lin's conjecture holds if the positive checkerboard graph of a connected alternating link has a fixed maximum degree and a sufficiently large number of edges.
Subspaces Intersecting Each Element of a Regulus in One Point, André-Bruck-Bose Representation and Clubs
Authors: Lavrauw Michel , Zanella Corrado
Published: January 2020

In this paper results are proved with applications to the orbits of $(n-1)$-dimensional subspaces disjoint from a regulus $\mathcal{R}$ of $(n-1)$-subspaces in $\mathrm{PG}(2n-1,q)$, with respect to the subgroup of $\mathrm{PGL}(2n,q)$ fixing $\mathcal{R}$. Such results have consequences on several aspects of finite geometry. First of all, a necessary condition for an $(n-1)$-subspace $U$ and a regulus $\mathcal{R}$ of $(n-1)$-subspaces to be extendable to a Desarguesian spread is given. The description also allows to improve results of Barwick and Jackson on the André -Bruck-Bose representation of a $q$-subline in $\mathrm{PG}(2,q^n)$. Furthermore, the results in this paper are applied to the classification of linear sets, in particular clubs.
On the Density of Certain Languages with $p^2$ Letters
Authors: Segovia Carlos , Winklmeier Monika
Published: January 2020

The sequence $(x_n)_{n\in\mathbb N} = (2,5,15,51,187,\ldots)$ given by the rule $x_n=(2^n+1)(2^{n-1}+1)/3$ appears in several seemingly unrelated areas of mathematics. For example, $x_n$ is the density of a language of words of length $n$ with four different letters. It is also the cardinality of the quotient of $(\mathbb Z_2\times \mathbb Z_2)^n$ under the left action of the special linear group $\mathrm{SL}(2,\mathbb Z)$. In this paper we show how these two interpretations of $x_n$ are related to each other. More generally, for prime numbers $p$ we show a correspondence between a quotient of $(\mathbb Z_p\times\mathbb Z_p)^n$ and a language with $p^2$ letters and words of length $n$.
Enumeration of Hybrid Domino-Lozenge Tilings II: Quasi-Octagonal Regions
Authors: Lai Tri
Published: January 2020

We use the subgraph replacement method to prove a simple product formula for the tilings of an  8-vertex counterpart of Propp's quasi-hexagons (Problem 16 in New Perspectives in Geometric Combinatorics, Cambridge University Press, 1999), called quasi-octagon.
Crystal Structure on Rigged Configurations and the Filling Map
Authors: Schilling Anne , Scrimshaw Travis
Published: January 2020

In this paper, we extend work of the first author on a crystal structure on rigged configurations of simply-laced type to all non-exceptional affine types using the technology of virtual rigged configurations and crystals. Under the bijection between rigged configurations and tensor products of Kirillov--Reshetikhin crystals specialized to a single tensor factor, we obtain a new tableaux model for Kirillov--Reshetikhin crystals. This is related to the model in terms of Kashiwara--Nakashima tableaux via a filling map, generalizing the recently discovered filling map in type $D_n^{(1)}$.
Colored Trees and Noncommutative Symmetric Functions
Authors: Szczesny Matt
Published: January 2020

Let ${\cal CRF}_S$ denote the category of $S$-colored rooted forests, and H$_{{\cal CRF}_S}$ denote its Ringel-Hall algebra as introduced by Kremnizer and Szczesny. We construct a homomorphism from a $K^+_0({\cal CRF}_S)$–graded version of the Hopf algebra of noncommutative symmetric functions to H$_{{\cal CRF}_S}$. Dualizing, we obtain a homomorphism from the Connes-Kreimer Hopf algebra to a $K^+_0({\cal CRF}_S)$–graded version of the algebra of quasisymmetric functions. This homomorphism is a refinement of one considered by W. Zhao.
A Generalization of Tokuyama's Formula to the Hall-Littlewood Polynomials
Authors: Gupta Vineet , Roy Uma , Van Peski Roger
Published: January 2020

A theorem due to Tokuyama expresses Schur polynomials in terms of Gelfand-Tsetlin patterns, providing a deformation of the Weyl character formula and two other classical results, Stanley's formula for the Schur $q$-polynomials and Gelfand's parametrization for the Schur polynomials. We generalize Tokuyama's formula to the Hall-Littlewood polynomials by extending Tokuyama's statistics. Our result, in addition to specializing to Tokuyama's result and the aforementioned classical results, also yields connections to the monomial symmetric function and a new deformation of Stanley's formula.
Rainbow Matching in Edge-Colored Graphs
Authors: LeSaulnier Timothy D. , Stocker Christopher , Wenger Paul S. , West Douglas B.
Published: January 2020

A rainbow subgraph of an edge-colored graph is a subgraph whose edges have distinct colors. The color degree of a vertex $v$ is the number of different colors on edges incident to $v$. Wang and Li conjectured that for $k\geq 4$, every edge-colored graph with minimum color degree at least $k$ contains a rainbow matching of size at least $\left\lceil k/2 \right\rceil$. We prove the slightly weaker statement that a rainbow matching of size at least $\left\lfloor k/2 \right\rfloor$ is guaranteed. We also give sufficient conditions for a rainbow matching of size at least $\left\lceil k/2 \right\rceil$ that fail to hold only for finitely many exceptions (for each odd $k$).
Bijection Between Bigrassmannian Permutations Maximal below a Permutation and its Essential Set
Authors: Kobayashi Masato
Published: January 2020

Bigrassmannian permutations are known as permutations which have precisely one left descent and one right descent. They play an important role in the study of Bruhat order. Fulton introduced the essential set of a permutation and studied its combinatorics. As a consequence of his work, it turns out that the essential set of bigrassmannian permutations consists of precisely one element. In this article, we generalize this observation for essential sets of arbitrary permutations. Our main theorem says that there exists a bijection between bigrassmanian permutations maximal below a permutation and its essential set. For the proof, we make use of two equivalent characterizations of bigrassmannian permutations by Lascoux-Schützenberger and Reading.
A Relationship Between Generalized Davenport-Schinzel Sequences and Interval Chains
Authors: Geneson Jesse
Published: January 2020

Let an $(r, s)$-formation be a concatenation of $s$ permutations of $r$ distinct letters, and let a block of a sequence be a subsequence of consecutive distinct letters. A $k$-chain on $[1, m]$ is a sequence of $k$ consecutive, disjoint, nonempty intervals of the form $[a_{0}, a_{1}] [a_{1}+1, a_{2}] \ldots [a_{k-1}+1, a_{k}]$ for integers $1 \leq a_{0} \leq a_{1} < \ldots < a_{k} \leq m$, and an $s$-tuple is a set of $s$ distinct integers. An $s$-tuple stabs an interval chain if each element of the $s$-tuple is in a different interval of the chain. Alon et al. (2008) observed similarities between bounds for interval chains and Davenport-Schinzel sequences, but did not identify the cause.We show for all $r \geq 1$ and $1 \leq s \leq k \leq m$ that the maximum number of distinct letters in any sequence $S$ on $m+1$ blocks avoiding every $(r, s+1)$-formation such that every letter in $S$ occurs at least $k+1$ times is the same as the maximum size of a collection $X$ of (not necessarily distinct) $k$-chains on $[1, m]$ so that there do not exist $r$ elements of $X$ all stabbed by the same $s$-tuple.Let $D_{s,k}(m)$ be the maximum number of distinct letters in any sequence which can be partitioned into $m$  blocks, has at least $k$ occurrences of every letter, and has no subsequence forming an alternation of length $s$. Nivasch (2010) proved that $D_{5, 2d+1}(m) = \Theta( m \alpha_{d}(m))$ for all fixed $d \geq 2$. We show that $D_{s+1, s}(m) = \binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}$ for all $s \geq 2$. We also prove new lower bounds which imply that $D_{5, 6}(m) = \Theta(m \log \log m)$ and $D_{5, 2d+2}(m) = \Theta(m \alpha_{d}(m))$ for all fixed $d \geq 3$.
On Periodicity of Generalized Pseudostandard Words
Authors: Florian Josef , Dvořáková L'ubomíra
Published: January 2020

Generalized pseudostandard words were introduced by de Luca and De Luca in 2006. In comparison to the palindromic and pseudopalindromic closure, only little is known about the generalized pseudopalindromic closure and the associated generalized pseudostandard words. In this paper we provide a necessary and sufficient condition for their periodicity over a binary and a ternary alphabet. More precisely, we describe how the directive bi-sequence of a generalized pseudostandard word has to look like in order to correspond to a periodic word. We state moreover a conjecture concerning a necessary and sufficient condition for periodicity over any alphabet.
Containment Game Played on Random Graphs: Another Zig-Zag Theorem
Authors: Prałat Paweł
Published: January 2020

We consider a variant of the game of Cops and Robbers, called Containment, in which cops move from edge to adjacent edge, the robber moves from vertex to adjacent vertex (but cannot move along an edge occupied by a cop). The cops win by "containing'' the robber, that is, by occupying all edges incident with a vertex occupied by the robber. The minimum number of cops, $\xi(G)$, required to contain a robber played on a graph $G$ is called the containability number, a natural counterpart of the well-known cop number $c(G)$. This variant of the game was recently introduced by Komarov and Mackey, who proved that for every graph $G$, $c(G) \le \xi(G) \le \gamma(G) \Delta(G)$, where $\gamma(G)$ and $\Delta(G)$ are the domination number and the maximum degree of $G$, respectively. They conjecture that an upper bound can be improved and, in fact, $\xi(G) \le c(G) \Delta(G)$. (Observe that, trivially, $c(G) \le \gamma(G)$.) This seems to be the main question for this game at the moment. By investigating expansion properties, we provide asymptotically almost sure bounds on the containability number of binomial random graphs $\mathcal{G}(n,p)$ for a wide range of $p=p(n)$, showing that it forms an intriguing zigzag shape. This result also proves that the conjecture holds for some range of $p$ (or holds up to a constant or an $O(\log n)$ multiplicative factors for some other ranges).
Equipopularity Classes in the Separable Permutations
Authors: Albert Michael , Homberger Cheyne , Pantone Jay
Published: January 2020

When two patterns occur equally often in a set of permutations, we say that these patterns are equipopular. Using both structural and analytic tools, we classify the equipopular patterns in the set of separable permutations. In particular, we show that the number of equipopularity classes for length $n$ patterns in the separable permutations is equal to the number of partitions of $n-1$.
K-Knuth Equivalence for Increasing Tableaux
Authors: Gaetz Christian , Mastrianni Michelle , Patrias Rebecca , Peck Hailee , Robichaux Colleen , Schwein David , Tam Ka Yu
Published: January 2020

A $K$-theoretic analogue of RSK insertion and the Knuth equivalence relations were introduced by Buch, Kresch, Shimozono, Tamvakis, and Yong (2006) and Buch and Samuel (2013), respectively. The resulting $K$-Knuth equivalence relations on words and increasing tableaux on $[n]$ has prompted investigation into the equivalence classes of tableaux arising from these relations. Of particular interest are the tableaux that are unique in their class, which we refer to as unique rectification targets (URTs). In this paper, we give several new families of URTs and a bound on the length of intermediate words connecting two $K$-Knuth equivalent words. In addition, we describe an algorithm to determine if two words are $K$-Knuth equivalent and to compute all $K$-Knuth equivalence classes of tableaux on $[n]$.
Hyperbinary Expansions and Stern Polynomials
Authors: Dilcher Karl , Ericksen Larry
Published: January 2020

We introduce an infinite class of polynomial sequences $a_t(n;z)$ with integer parameter $t\geq 1$, which reduce to the well-known Stern (diatomic) sequence when $z=1$ and are $(0,1)$-polynomials when $t\geq 2$. Using these polynomial sequences, we derive two different characterizations of all hyperbinary expansions of an integer $n\geq 1$. Furthermore, we study the polynomials $a_t(n;z)$ as objects in their own right, obtaining a generating function and some consequences. We also prove results on the structure of these sequences, and determine expressions for the degrees of the polynomials.
A Construction of Uniquely $n$-Colorable Digraphs with Arbitrarily Large Digirth
Authors: Severino Michael
Published: January 2020

A natural digraph analogue of the graph-theoretic concept of an `independent set' is that of an `acyclic set', namely a set of vertices not spanning a directed cycle. Hence a digraph analogue of a graph coloring is a decomposition of the vertex set into acyclic sets and we say a digraph is uniquely $n$-colorable when this decomposition is unique up to relabeling. It was shown probabilistically in [A. Harutyunyan et al., Uniquely $D$-colorable digraphs with large girth, Canad. J. Math., 64(6): 1310-1328, 2012] that there exist uniquely $n$-colorable digraphs with arbitrarily large girth. Here we give a construction of such digraphs and prove that they have circular chromatic number $n$. The graph-theoretic notion of `homomorphism' also gives rise to a digraph analogue. An acyclic homomorphism from a digraph $D$ to a digraph $H$ is a mapping $\varphi: V(D) \rightarrow V(H)$ such that $uv \in A(D)$ implies that either $\varphi(u)\varphi(v) \in A(H)$ or $\varphi(u)=\varphi(v)$, and all the `fibers' $\varphi^{-1}(v)$, for $v \in V(H)$, of $\varphi$ are acyclic. In this language, a core is a digraph $D$ for which there does not exist an acyclic homomorphism  from $D$ to a proper subdigraph of itself. Here we prove some basic results about digraph cores and construct highly chromatic cores without short cycles.
Semiregular Automorphisms of Cubic Vertex-Transitive Graphs and the Abelian Normal Quotient Method
Authors: Morris Joy , Spiga Pablo , Verret Gabriel
Published: January 2020

We characterise connected cubic graphs admitting a vertex-transitive group of automorphisms with an abelian normal subgroup that is not semiregular. We illustrate the utility of this result by using it to prove that the order of a semiregular subgroup of maximum order in a vertex-transitive group of automorphisms of a connected cubic graph grows with the order of the graph.
Counting Points of Slope Varieties over Finite Fields
Authors: Enkosky Thomas
Published: January 2020

The slope variety of a graph is an algebraic set whose points correspond to drawings of that graph. A complement-reducible graph (or cograph) is a graph without an induced four-vertex path. We construct a bijection between the zeroes of the slope variety of the complete graph on $n$ vertices over $\mathbb{F}_2$, and the complement-reducible graphs on $n$ vertices.
Mutually Unbiased Bush-type Hadamard Matrices and Association Schemes
Authors: Kharaghani Hadi , Sasani Sara , Suda Sho
Published: January 2020

It was shown by LeCompte, Martin, and Owens in 2010 that the existence of mutually unbiased Hadamard matrices and the identity matrix, which coincide with mutually unbiased bases, is equivalent to that of a $Q$-polynomial association scheme of class four which is both $Q$-antipodal and $Q$-bipartite.  We prove that the existence of a set of mutually unbiased Bush-type Hadamard matrices is equivalent to that of an association scheme of class five. As an application of this equivalence, we obtain an upper bound of the number of mutually unbiased Bush-type Hadamard matrices of order $4n^2$ to be $2n-1$. This is in contrast to the fact that the best general upper bound for the mutually unbiased Hadamard matrices of order $4n^2$ is $2n^2$. We also discuss a relation of our scheme to some fusion schemes which are $Q$-antipodal and $Q$-bipartite $Q$-polynomial of class $4$.
Generating Functions Attached to some Infinite Matrices
Authors: Monsky Paul
Published: January 2020

Let $V$ be an infinite matrix with rows and columns indexed by the positive integers, and entries in a field $F$. Suppose that $v_{i,j}$ only depends on $i-j$ and is 0 for $|i-j|$ large. Then $V^{n}$ is defined for all $n$, and one has a "generating function" $G=\sum a_{1,1}(V^{n})z^{n}$. Ira Gessel has shown that $G$ is algebraic over $F(z)$. We extend his result, allowing $v_{i,j}$ for fixed $i-j$ to be eventually periodic in $i$ rather than constant. This result and some variants of it that we prove will have applications to Hilbert-Kunz theory.
Distance-Regular Graphs
Authors: Van Dam Edwin R. , Koolen Jack H. , Tanaka Hajime
Published: January 2020

This is a survey of distance-regular graphs. We present an introduction to distance-regular graphs for the reader who is unfamiliar with the subject, and then give an overview of some developments in the area of distance-regular graphs since the monograph 'BCN' [Brouwer, A.E., Cohen, A.M., Neumaier, A., Distance-Regular Graphs, Springer-Verlag, Berlin, 1989] was written.
SB-Labelings, Distributivity, and Bruhat Order on Sortable Elements
Authors: Mühle Henri
Published: January 2020

In this article, we investigate the set of $\gamma$-sortable elements, associated with a Coxeter group $W$ and a Coxeter element $\gamma\in W$, under Bruhat order, and we denote this poset by $\mathcal{B}_{\gamma}$. We show that this poset belongs to the class of SB-lattices recently introduced by Hersh and Mészáros, by proving a more general statement, namely that all join-distributive lattices are SB-lattices. The observation that $\mathcal{B}_{\gamma}$ is join-distributive is due to Armstrong. Subsequently, we investigate for which finite Coxeter groups $W$ and which Coxeter elements $\gamma\in W$ the lattice $\mathcal{B}_{\gamma}$ is in fact distributive. It turns out that this is the case for the "coincidental" Coxeter groups, namely the groups $A_{n},B_{n},H_{3}$ and $I_{2}(k)$. We conclude this article with a conjectural characteriziation of the Coxeter elements $\gamma$ of said groups for which $\mathcal{B}_{\gamma}$ is distributive in terms of forbidden orientations of the Coxeter diagram.
Tokuyama's Identity for Factorial Schur $P$ and $Q$ Functions
Authors: Hamel Angèle M. , King Ronald C.
Published: January 2020

A recent paper of Bump, McNamara and Nakasuji introduced a factorial version of Tokuyama's identity, expressing the partition function of  six vertex model as the product of a $t$-deformed Vandermonde and a Schur function. Here we provide an extension of their result by exploiting the language of primed shifted tableaux, with its proof based on the use of non-interesecting lattice paths.
Clustered Planarity Testing Revisited
Authors: Fulek Radoslav , Kynčl Jan , Malinović Igor , Pálvölgyi Dömötör
Published: January 2020

The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani–Tutte theorem in the case when each cluster induces a connected subgraph.Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident with at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.
Spectrally Extremal Vertices, Strong Cospectrality, and State Transfer
Authors: Coutinho Gabriel
Published: January 2020

In order to obtain perfect state transfer between two sites in a network of interacting qubits, their corresponding vertices in the underlying graph must satisfy a property called strong cospectrality. Here we determine the structure of graphs containing pairs of vertices which are strongly cospectral and satisfy a certain extremal property related to the spectrum of the graph. If the graph satisfies this property globally and is regular, we also show that the existence of a partition of the vertex set into pairs of vertices at maximum distance admitting perfect state transfer forces the graph to be distance-regular. Finally, we present some new examples of perfect state transfer in simple graphs constructed with our technology. In particular, for odd distances, we improve the known trade-off between the distance perfect state transfer occurs in simple graphs and the size of the graph.
Promotion and Evacuation on Standard Young Tableaux of Rectangle and Staircase Shape
Authors: Pon Steven , Wang Qiang
Published: January 2020

(Dual-)promotion and (dual-)evacuation are bijections on $SYT(\lambda)$ for any partition $\lambda$. Let $c^r$ denote the rectangular partition $(c,\ldots,c)$ of height $r$, and let $sc_k$ ($k>2$) denote the staircase partition $(k,k-1,\ldots,1)$. We demonstrate a promotion- and evacuation-preserving embedding of $SYT(sc_k)$ into $SYT(k^{k+1})$. We hope that this result, together with results by Rhoades on rectangular tableaux, can help to demonstrate the cyclic sieving phenomenon of promotion action on $SYT(sc_k)$.