bluuebunny/crossref_metadata_2025 huggingface dataset:
Permutation Statistics and $q$-Fibonacci Numbers
Authors: Goyt Adam M. , Mathisen David
Published: January 2020

In a recent paper, Goyt and Sagan studied distributions of certain set partition statistics over pattern restricted sets of set partitions that were counted by the Fibonacci numbers. Their study produced a class of $q$-Fibonacci numbers, which they related to $q$-Fibonacci numbers studied by Carlitz and Cigler. In this paper we will study the distributions of some Mahonian statistics over pattern restricted sets of permutations. We will give bijective proofs connecting some of our $q$-Fibonacci numbers to those of Carlitz, Cigler, Goyt and Sagan. We encode these permutations as words and use a weight to produce bijective proofs of $q$-Fibonacci identities. Finally, we study the distribution of some of these statistics on pattern restricted permutations that West showed were counted by even Fibonacci numbers.
Partitions, Rooks, and Symmetric Functions in Noncommuting Variables
Authors: Can Mahir Bilen , Sagan Bruce E.
Published: January 2020

Let $\Pi_n$ denote the set of all set partitions of $\{1,2,\ldots,n\}$. We consider two subsets of $\Pi_n$, one connected to rook theory and one associated with symmetric functions in noncommuting variables. Let ${\cal E}_n\subseteq\Pi_n$ be the subset of all partitions corresponding to an extendable rook (placement) on the upper-triangular board, ${\cal T}_{n-1}$. Given $\pi\in\Pi_m$ and $\sigma\in\Pi_n$, define their slash product to be $\pi|\sigma=\pi\cup(\sigma+m)\in\Pi_{m+n}$ where $\sigma+m$ is the partition obtained by adding $m$ to every element of every block of $\sigma$. Call $\tau$ atomic if it can not be written as a nontrivial slash product and let ${\cal A}_n\subseteq\Pi_n$ denote the subset of atomic partitions. Atomic partitions were first defined by Bergeron, Hohlweg, Rosas, and Zabrocki during their study of $NCSym$, the symmetric functions in noncommuting variables. We show that, despite their very different definitions, ${\cal E}_n={\cal A}_n$ for all $n\ge0$. Furthermore, we put an algebra structure on the formal vector space generated by all rook placements on upper triangular boards which makes it isomorphic to $NCSym$. We end with some remarks.
Fixed Points and Excedances in Restricted Permutations
Authors: Elizalde Sergi
Published: January 2020

Using an unprecedented technique involving diagonals of non-rational generating functions, we prove that among the permutations of length $n$ with $i$ fixed points and $j$ excedances, the number of 321-avoiding ones equals the number of 132-avoiding ones, for any given $i,j$. Our theorem generalizes a result of Robertson, Saracino and Zeilberger. Even though bijective proofs have later been found by the author jointly with Pak and with Deutsch, this paper contains the original analytic proof that was presented at FPSAC 2003.
The Vertical Profile of Embedded Trees
Authors: Bousquet-Mélou Mireille , Chapuy Guillaume
Published: January 2020

Consider a rooted binary tree with $n$ nodes. Assign with the root the abscissa 0, and with the left (resp. right) child of a node of abscissa $i$ the abscissa $i-1$ (resp. $i+1$). We prove that the number of binary trees of size $n$ having exactly $n_i$ nodes at abscissa $i$, for $l \leq i \leq r$ (with $n = \sum_i n_i$), is $$ \frac{n_0}{n_l n_r} {{n_{-1}+n_1} \choose {n_0-1}} \prod_{l\le i\le r \atop i\not = 0}{{n_{i-1}+n_{i+1}-1} \choose {n_i-1}}, $$ with $n_{l-1}=n_{r+1}=0$. The sequence $(n_l, \dots, n_{-1};n_0, \dots n_r)$ is called the vertical profile of the tree. The vertical profile of a uniform random tree of size $n$ is known to converge, in a certain sense and after normalization, to a random mesure called the integrated superbrownian excursion, which motivates our interest in the profile. We prove similar looking formulas for other families of trees whose nodes are embedded in $Z$. We also refine these formulas by taking into account the number of nodes at abscissa j whose parent lies at abscissa $i$, and/or the number of vertices at abscissa i having a prescribed number of children at abscissa $j$, for all $i$ and $j$. Our proofs are bijective.
On Matchings in Hypergraphs
Authors: Frankl Peter , Łuczak Tomasz , Mieczkowska Katarzyna
Published: January 2020

We show that if the largest matching in a $k$-uniform hypergraph $G$ on $n$ vertices has precisely $s$ edges, and $n>2k^2s/\log k$, then $H$ has at most $\binom n k - \binom {n-s} k $ edges and this upper bound is achieved only for hypergraphs in which the set of edges consists of all $k$-subsets which intersect a given set of $s$ vertices.
Some Gregarious Cycle Decompositions of Complete Equipartite Graphs
Authors: Smith Benjamin R.
Published: January 2020

A $k$-cycle decomposition of a multipartite graph $G$ is said to be gregarious if each $k$-cycle in the decomposition intersects $k$ distinct partite sets of $G$. In this paper we prove necessary and sufficient conditions for the existence of such a decomposition in the case where $G$ is the complete equipartite graph, having $n$ parts of size $m$, and either $n\equiv 0,1\pmod{k}$, or $k$ is odd and $m\equiv 0\pmod{k}$. As a consequence, we prove necessary and sufficient conditions for decomposing complete equipartite graphs into gregarious cycles of prime length.
The Existence of Near Generalized Balanced Tournament Designs
Authors: Wang Chengmin , Yan Jie
Published: January 2020

In this paper, we complete the existence of near generalized balanced tournament designs (NGBTDs) with block size 3 and 5. As an application, we obtain new classes of optimal constant composition codes.
Colourful Theorems and Indices of Homomorphism Complexes
Authors: Simonyi Gábor , Tardif Claude , Zsbán Ambrus
Published: January 2020

We extend the colourful complete bipartite subgraph theorems of [G. Simonyi, G. Tardos, Local chromatic number, Ky Fan's theorem,  and circular colorings, Combinatorica 26 (2006), 587--626] and [G. Simonyi, G. Tardos, Colorful subgraphs of Kneser-like graphs, European J. Combin. 28 (2007), 2188--2200] to more general topological settings. We give examples showing that the hypotheses are indeed more general. We use our results to show that the topological bounds on chromatic numbers of digraphs with tree duality are at most one better than the clique number. We investigate combinatorial and complexity-theoretic aspects of relevant order-theoretic maps.
Large 2-Coloured Matchings in 3-Coloured Complete Hypergraphs
Authors: Terpai Tamás
Published: January 2020

We prove the generalized Ramsey-type result on large $2$-coloured matchings in a $3$-coloured complete $3$-uniform hypergraph, supporting a conjecture by A. Gyárfás.
New Turán Densities for 3-Graphs
Authors: Baber Rahil , Talbot John
Published: January 2020

If $\mathcal{F}$ is a family of graphs then the Turán density of $\mathcal{F}$ is determined by the minimum chromatic number of the members of $\mathcal{F}$.The situation for Turán densities of 3-graphs is far more complex and still very unclear. Our aim in this paper is to present new exact Turán densities for individual and finite families of $3$-graphs, in many cases we are also able to give corresponding stability results. As well as providing new examples of individual $3$-graphs with Turán densities equal to $2/9,4/9,5/9$ and $3/4$ we also give examples of irrational Turán densities for finite families of 3-graphs, disproving a conjecture of Chung and Graham. (Pikhurko has independently disproved this conjecture by a very different method.)A central question in this area, known as Turán's problem, is to determine the Turán density of $K_4^{(3)}=\{123, 124, 134, 234\}$. Turán conjectured that this should be $5/9$. Razborov [On 3-hypergraphs with forbidden 4-vertex configurations in SIAM J. Disc. Math. 24 (2010), 946--963] showed that if we consider the induced Turán problem forbidding $K_4^{(3)}$ and $E_1$, the 3-graph with 4 vertices and a single edge, then the Turán density is indeed $5/9$. We give some new non-induced results of a similar nature, in particular we show that $\pi(K_4^{(3)},H)=5/9$ for a $3$-graph $H$ satisfying $\pi(H)=3/4$.We end with a number of open questions focusing mainly on the topic of which values can occur as Turán densities.Our work is mainly computational, making use of Razborov's flag algebra framework. However all proofs are exact in the sense that they can be verified without the use of any floating point operations. Indeed all verifying computations use only integer operations, working either over $\mathbb{Q}$ or in the case of irrational Turán densities over an appropriate quadratic extension of $\mathbb{Q}$.
Reflexive Polytopes of Higher Index and the Number 12
Authors: Kasprzyk Alexander M. , Nill Benjamin
Published: January 2020

We introduce reflexive polytopes of index $l$ as a natural generalisation of the notion of a reflexive polytope of index $1$. These $l$-reflexive polytopes also appear as dual pairs. In dimension two we show that they arise from reflexive polygons via a change of the underlying lattice. This allows us to efficiently classify all isomorphism classes of $l$-reflexive polygons up to index $200$. As another application, we show that any reflexive polygon of arbitrary index satisfies the famous "number $12$" property. This is a new, infinite class of lattice polygons possessing this property, and extends the previously known sixteen instances. The number $12$ property also holds more generally for $l$-reflexive non-convex or self-intersecting polygonal loops. We conclude by discussing higher-dimensional examples and open questions.
A Survey of Forbidden Configuration Results
Authors: Anstee Richard
Published: January 2020

Let $F$ be a $k\times \ell$ (0,1)-matrix. We say a (0,1)-matrix $A$ has $F$ as a configuration if there is a submatrix of $A$ which is a row and column permutation of $F$. In the language of sets, a configuration is a trace and in the language of hypergraphs a configuration is a subhypergraph.Let $F$ be a given $k\times \ell$ (0,1)-matrix. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. The matrix $F$ need not be simple. We define $\hbox{forb}(m,F)$ as the maximum number of columns of any simple $m$-rowed matrix $A$ which do not contain $F$ as a configuration. Thus if $A$ is an $m\times n$ simple matrix which has no submatrix which is a row and column permutation of $F$ then $n\le\hbox{forb}(m,F)$. Or alternatively if $A$ is an $m\times (\hbox{forb}(m,F)+1)$ simple matrix then $A$ has a submatrix which is a row and column permutation of $F$. We call $F$ a forbidden configuration. The fundamental result is due to Sauer, Perles and Shelah, Vapnik and Chervonenkis. For $K_k$ denoting the $k\times 2^k$ submatrix of all (0,1)-columns on $k$ rows, then $\hbox{forb}(m,K_k)=\binom{m}{k-1}+\binom{m}{k-2}+\cdots \binom{m}{0}$. We seek asymptotic results for $\hbox{forb}(m,F)$ for a fixed $F$ and as $m$ tends to infinity . A conjecture of Anstee and Sali predicts the asymptotically best constructions from which to derive the asymptotics of $\hbox{forb}(m,F)$. The conjecture has helped guide the research and has been verified for $k\times \ell$ $F$ with $k=1,2,3$ and for simple $F$ with $k=4$ as well as other cases including $\ell=1,2$. We also seek exact values for $\hbox{forb}(m,F)$.
On Some Partitions Related to ${\Bbb Q}(\sqrt{2})$
Authors: Patkowski Alexander E.
Published: January 2020

We offer some new identities for a bipartition function, which has a relation to a Hecke-type identity of Andrews. Further, we show this partition function is lacunary, and relate it to a real quadratic field.
Stability of Graphs
Authors: Demir Bünyamin , Deniz Ali , Koçak Şahin
Published: January 2020

Positively weighted graphs have a natural intrinsic metric. We consider finite, positively weighted graphs with a positive lower bound for their minimal weights and show that any two such graphs, which are close enough with respect to the Gromov-Hausdorff metric, are equivalent as graphs.
Oriented Matroids
Authors: Ziegler Günter M.
Published: January 2020

This dynamic survey offers an “entry point” for current research in oriented matroids. For this, it provides updates on the 1993 monograph “Oriented Matroids” by Bjö̈rner, Las Vergnas, Sturmfels, White & Ziegler [85], in three parts: 1. a sketch of a few “Frontiers of Research” in oriented matroid theory, 2. an update of corrections, comments and progress as compared to [85], and 3. an extensive, complete and up-to-date bibliography of oriented matroids, comprising and extending the bibliography of [85].
Extremal Graphs Having No Stable Cutset
Authors: Le Van Bang , Pfender Florian
Published: January 2020

A stable cutset in a graph is a stable set whose deletion disconnects the graph. It was conjectured by Caro and proved by Chen and Yu that any graph with $n$ vertices and at most $2n-4$ edges contains a stable cutset. The bound is tight, as we will show that all graphs with $n$ vertices and $2n-3$ edges without stable cutset arise recursively glueing together triangles and triangular prisms along an edge or triangle. As a by-product, an algorithmic implication of our result will be pointed out.
Γ-Species and the Enumeration of $k$-Trees
Authors: Gainer-Dewar Andrew
Published: January 2020

We study the class of graphs known as $k$-trees through the lens of Joyal’s theory of combinatorial species (and a extension known as 'Γ-species' which incorporates data about 'structural' group actions). This culminates in a system of recursive functional equations giving the generating function for unlabeled $k$-trees which allows for fast, efficient computation of their numbers. Enumerations up to $k = 10$ and $n = 30$ (for a k-tree with $n + k − 1$ vertices) are included in tables, and Sage code for the general computation is included in an appendix.
New Approach to the $k$-Independence Number of a Graph
Authors: Caro Yair , Hansberg Adriana
Published: January 2020

Let $G = (V,E)$ be a graph and $k \ge 0$ an integer. A $k$-independent set $S \subseteq V$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$. With $\alpha_k(G)$ we denote the maximum cardinality of a $k$-independent set of $G$. We prove that, for a graph $G$ on $n$ vertices and average degree $d$, $\alpha_k(G) \ge \frac{k+1}{\lceil d \rceil + k + 1} n$, improving the hitherto best general lower bound due to Caro and Tuza [Improved lower bounds on $k$-independence, J. Graph Theory 15 (1991), 99-107].
Depth Reduction of a Class of Witten Zeta Functions
Authors: Zhou Xia , Bradley David M. , Cai Tianxin
Published: January 2020

We show that if $a,b,c,d,f$ are positive integers such that $a+b+c+d+f$ is even, then the Witten zeta value $\zeta_{\mathfrak{sl}(4)} (a,b,c,d,0,f)$ is expressible in terms of Witten zeta functions with fewer arguments.
Skew Spectra of Oriented Graphs
Authors: Shader Bryan , So Wasin
Published: January 2020

An oriented graph $G^{\sigma}$ is a simple undirected graph $G$ with an orientation $\sigma$, which assigns to each edge a direction so that $G^{\sigma}$ becomes a directed graph. $G$ is called the underlying graph of $G^{\sigma}$, and we denote by $Sp(G)$ the adjacency spectrum of $G$. Skew-adjacency matrix $S( G^{\sigma} )$ of $G^{\sigma}$ is introduced, and its spectrum $Sp_S( G^{\sigma} )$ is called the skew-spectrum of $G^{\sigma}$. The relationship between $Sp_S( G^{\sigma} )$ and $Sp(G)$ is studied. In particular, we prove that (i) $Sp_S( G^{\sigma} ) = {\bf i} Sp(G)$ for some orientation $\sigma$ if and only if $G$ is bipartite, (ii) $Sp_S(G^{\sigma}) = {\bf i} Sp(G)$ for any orientation $\sigma$ if and only if $G$ is a forest, where ${\bf i}=\sqrt{-1}$.
The Graph Crossing Number and its Variants: A Survey
Authors: Schaefer Marcus
Published: January 2020

The crossing number is a popular tool in graph drawing and visualization, but there is not really just one crossing number; there is a large family of crossing number notions of which the crossing number is the best known. We survey the rich variety of crossing number variants that have been introduced in the literature for purposes that range from studying the theoretical underpinnings of the crossing number to crossing minimization for visualization problems.
Lindelöf Representations and (Non-)Holonomic Sequences
Authors: Flajolet Philippe , Gerhold Stefan , Salvy Bruno
Published: January 2020

Various sequences that possess explicit analytic expressions can be analysed asymptotically through integral representations due to Lindelöf, which belong to an attractive but somewhat neglected chapter of complex analysis. One of the outcomes of such analyses concerns the non-existence of linear recurrences with polynomial coefficients annihilating these sequences, and, accordingly, the non-existence of linear differential equations with polynomial coefficients annihilating their generating functions. In particular, the corresponding generating functions are transcendental. Asymptotic estimates of certain finite difference sequences come out as a byproduct of the Lindelöf approach.
A Combinatorial Proof of a Formula for Betti Numbers of a Stacked Polytope
Authors: Choi Suyoung , Kim Jang Soo
Published: January 2020

For a simplicial complex $\Delta$, the graded Betti number $\beta_{i,j}({\bf k}[\Delta])$ of the Stanley-Reisner ring ${\bf k}[\Delta]$ over a field ${\bf k}$ has a combinatorial interpretation due to Hochster. Terai and Hibi showed that if $\Delta$ is the boundary complex of a $d$-dimensional stacked polytope with $n$ vertices for $d\geq3$, then $\beta_{k-1,k}({\bf k}[\Delta])=(k-1){n-d\choose k}$. We prove this combinatorially.
Counting Subwords in a Partition of a Set
Authors: Mansour Toufik , Shattuck Mark , Yan Sherry H.F.
Published: January 2020

A partition $\pi$ of the set $[n]=\{1,\ldots,n\}$ is a collection $\{B_1,\ldots ,B_k\}$ of nonempty disjoint subsets of $[n]$ (called blocks) whose union equals $[n]$. In this paper, we find explicit formulas for the generating functions for the number of partitions of $[n]$ containing exactly $k$ blocks where $k$ is fixed according to the number of occurrences of a subword pattern $\tau$ for several classes of patterns, including all words of length 3. In addition, we find simple explicit formulas for the total number of occurrences of the patterns in question within all the partitions of $[n]$ containing $k$ blocks, providing both algebraic and combinatorial proofs.
Genus of the Cartesian Product of Triangles.
Authors: Kotrbčík Michal , Pisanski Tomaž
Published: January 2020

We investigate the orientable genus of $G_n$, the cartesian product of $n$ triangles, with a particular attention paid to the two smallest unsolved cases $n=4$ and $5$. Using a lifting method we present a general construction of a low-genus embedding of $G_n$ using a low-genus embedding of $G_{n-1}$. Combining this method with a computer search and a careful analysis of face structure we show that $30\le \gamma(G_4) \le 37$ and $133 \le\gamma(G_5) \le 190$. Moreover, our computer search resulted in more than $1300$ non-isomorphic minimum-genus embeddings of $G_3$. We also introduce genus range of a group and (strong) symmetric genus range of a Cayley graph and of a group. The (strong) symmetric genus range of irredundant Cayley graphs of $Z_p^n$ is calculated for all odd primes $p$.
Ramsey Properties of Permutations
Authors: Böttcher Julia , Foniok Jan
Published: January 2020

The age of each countable homogeneous permutation forms a Ramsey class.Thus, there are five countably infinite Ramsey classes of permutations.
Sequenceable Groups and Related Topics
Authors: Ollis M. A.
Published: January 2020

In 1980, about 20 years after sequenceable groups were introduced by Gordon to construct row-complete latin squares, Keedwell published a survey of all the available results concerning sequencings. This was updated (jointly with Dénes) in 1991 and a short overview, including results about complete mappings and R-sequencings, was given in the CRC Handbook of Combinatorial Designs in 1995. In Sections 1 and 2 we give a survey of the current situation concerning sequencings, including details of the most important constructions. In Section 3 we consider some concepts closely related to sequenceable groups: R-sequencings, harmonious groups, supersequenceable groups (also known as super P-groups), terraces and the Gordon game. We also look at constructions for row-complete latin squares that do not use sequencings.
The Toric Ideal of a Matroid of Rank 3 is Generated by Quadrics
Authors: Kashiwabara Kenji
Published: January 2020

White conjectured that the toric ideal associated with the basis of a matroid is generated by quadrics corresponding to symmetric exchanges. We present a combinatorial proof of White's conjecture for matroids of rank 3 by using a lemma proposed by Blasiak.
Permutations Destroying Arithmetic Structure
Authors: Jungić Veselin , Sahasrabudhe Julian
Published: January 2020

Given a linear form $C_1X_1 + \cdots + C_nX_n$, with coefficients in the integers, we characterize exactly the countably infinite abelian groups $G$ for which there exists a permutation $f$ that maps all solutions $(\alpha_1, \ldots , \alpha_n) \in G^n$ (with the $\alpha_i$ not all equal) to the equation $C_1X_1 + \cdots + C_nX_n = 0 $ to non-solutions. This generalises a result of Hegarty about permutations of an abelian group avoiding arithmetic progressions. We also study the finite version of the problem suggested by Hegarty. We show that the number of permutations of $\mathbb{Z}/p\mathbb{Z}$ that map all 4-term arithmetic progressions to non-progressions, is asymptotically $e^{-1}p!$.
Unique Sequences Containing No $k$-Term Arithmetic Progressions
Authors: Ahmed Tanbir , Dybizbánski Janusz , Snevily Hunter
Published: January 2020

In this paper, we are concerned with calculating $r(k, n)$, the length of the longest $k$-AP free subsequences in $1, 2, \ldots , n$. We prove the basic inequality $r(k, n) \le n − \lfloor m/2\rfloor$, where $n = m(k − 1) + r$ and $r < k − 1$. We also discuss a generalization of a famous conjecture of Szekeres (as appears in Erdős and Turán) and describe a simple greedy algorithm that appears to give an optimal $k$-AP free sequence infinitely often. We provide many exact values of $r(k, n)$ in the Appendix.
On Colorings Avoiding a Rainbow Cycle and a Fixed Monochromatic Subgraph
Authors: Axenovich Maria , Choi JiHyeok
Published: January 2020

Let $H$ and $G$ be two graphs on fixed number of vertices. An edge coloring of a complete graph is called $(H,G)$-good if there is no monochromatic copy of $G$ and no rainbow (totally multicolored) copy of $H$ in this coloring. As shown by Jamison and West, an $(H,G)$-good coloring of an arbitrarily large complete graph exists unless either $G$ is a star or $H$ is a forest. The largest number of colors in an $(H,G)$-good coloring of $K_n$ is denoted $maxR(n, G,H)$. For graphs $H$ which can not be vertex-partitioned into at most two induced forests, $maxR(n, G,H)$ has been determined asymptotically. Determining $maxR(n; G, H)$ is challenging for other graphs $H$, in particular for bipartite graphs or even for cycles. This manuscript treats the case when $H$ is a cycle. The value of $maxR(n, G, C_k)$ is determined for all graphs $G$ whose edges do not induce a star.
Bounding the Distinguishing Number of Infinite Graphs and Permutation Groups
Authors: Smith Simon M. , Watkins Mark E.
Published: January 2020

A group of permutations $G$ of a set $V$ is $k$-distinguishable if there exists a partition of $V$ into $k$ cells such that only the identity permutation in $G$ fixes setwise all of the cells of the partition. The least cardinal number $k$ such that $(G,V)$ is $k$-distinguishable is its distinguishing number $D(G,V)$. In particular, a graph $\Gamma$ is $k$-distinguishable if its automorphism group $\rm{Aut}(\Gamma)$ satisfies $D(\rm{Aut}(\Gamma),V\Gamma)\leq k$.Various results in the literature demonstrate that when an infinite graph fails to have some property, then often some finite subgraph is similarly deficient. In this paper we show that whenever an infinite connected graph $\Gamma$ is not $k$-distinguishable (for a given cardinal $k$), then it contains a ball of finite radius whose distinguishing number is at least $k$. Moreover, this lower bound cannot be sharpened, since for any integer $k \geq 3$ there exists an infinite, locally finite, connected graph $\Gamma$ that is not $k$-distinguishable but in which every ball of finite radius is $k$-distinguishable.In the second half of this paper we show that a large distinguishing number for an imprimitive group $G$ is traceable to a high distinguishing number either of a block of imprimitivity or of the induced action by $G$ on the corresponding system of imprimitivity. An immediate application is to automorphism groups of infinite imprimitive graphs. These results are companion to the study of the distinguishing number of infinite primitive groups and graphs in a previous paper by the authors together with T. W. Tucker.
Glossary of Signed and Gain Graphs
Authors: Zaslavsky Thomas
Published: January 2020

A glossary to accompany DS8.
On a Rado Type Problem for Homogeneous Second Order Linear Recurrences
Authors: Ardal Hayri , Dvořák Zdeněk , Jungić Veselin , Kaiser Tomáš
Published: January 2020

In this paper we introduce a Ramsey type function $S(r;a,b,c)$ as the maximum $s$ such that for any $r$-coloring of ${\Bbb N}$ there is a monochromatic sequence $x_1,x_2,\ldots,x_s$ satisfying a homogeneous second order linear recurrence $ax_i+bx_{i+1}+cx_{i+2}=0$, $1\leq i\leq s-2$. We investigate $S(2;a,b,c)$ and evaluate its values for a wide class of triples $(a,b,c)$.
On the Cayley Isomorphism Problem for Cayley Objects of Nilpotent Groups of Some Orders
Authors: Dobson Edward
Published: January 2020

We give a necessary condition to reduce the Cayley isomorphism problem for Cayley objects of a nilpotent or abelian group $G$ whose order satisfies certain arithmetic properties to the Cayley isomorphism problem of Cayley objects of the Sylow subgroups of $G$ in the case of nilpotent groups, and in the case of abelian groups to certain natural subgroups. As an application of this result, we show that ${\mathbb Z}_q\times{\mathbb Z}_p^2\times{\mathbb Z}_m$ is a CI-group with respect to digraphs, where $q$ and $p$ are primes with $p^2 < q$ and $m$ is a square-free integer satisfying certain arithmetic conditions (but there are no other restrictions on $q$ and $p$).
Crossings and Nestings in Colored Set Partitions
Authors: Marberg Eric
Published: January 2020

Chen, Deng, Du, Stanley, and Yan introduced the notion of $k$-crossings and $k$-nestings for set partitions, and proved that the sizes of the largest $k$-crossings and $k$-nestings in the partitions of an $n$-set possess a symmetric joint distribution. This work considers a generalization of these results to set partitions whose arcs are labeled by an $r$-element set (which we call $r$-colored set partitions). In this context, a $k$-crossing or $k$-nesting is a sequence of arcs, all with the same color, which form a $k$-crossing or $k$-nesting in the usual sense. After showing that the sizes of the largest crossings and nestings in colored set partitions likewise have a symmetric joint distribution, we consider several related enumeration problems. We prove that $r$-colored set partitions with no crossing arcs of the same color are in bijection with certain paths in $\mathbb{N}^r$, generalizing the correspondence between noncrossing (uncolored) set partitions and 2-Motzkin paths. Combining this with recent work of Bousquet-Mélou and Mishna affords a proof that the sequence counting noncrossing 2-colored set partitions is P-recursive. We also discuss how our methods extend to several variations of colored set partitions with analogous notions of crossings and nestings.
Facets of the Generalized Cluster Complex and Regions in the Extended Catalan Arrangement of Type $A$
Authors: Fishel Susanna , Kallipoliti Myrto , Tzanaki Eleni
Published: January 2020

In this paper we present a bijection between two well known families of Catalan objects: the set of facets of the $m$-generalized cluster complex $\Delta^m(A_n)$ and that of dominant regions in the $m$-Catalan arrangement ${\rm Cat}^m(A_n)$, where $m\in\mathbb{N}_{>0}$. In particular, the map which we define bijects facets containing the negative simple root $-\alpha$ to dominant regions having the hyperplane $\{v\in V\mid\left\langle v,\alpha \right\rangle=m\}$ as separating wall. As a result, it restricts to a bijection between the set of facets of the positive part of $\Delta^m(A_n)$ and the set of bounded dominant regions in ${\rm Cat}^m(A_n)$. Our map is a composition of two bijections in which integer partitions in an $m$-dilated $n$-staircase shape come into play.
Hamiltonicity of Cubic 3-Connected k-Halin Graphs
Authors: Malik Shabnam , Qureshi Ahmad Mahmood , Zamfirescu Tudor
Published: January 2020

We investigate here how far we can extend the notion of a Halin graph such that hamiltonicity is preserved. Let $H = T \cup C$ be a Halin graph, $T$ being a tree and $C$ the outer cycle. A $k$-Halin graph $G$ can be obtained from $H$ by adding edges while keeping planarity, joining vertices of $H - C$, such that $G - C$ has at most $k$ cycles. We prove that, in the class of cubic $3$-connected graphs, all $14$-Halin graphs are hamiltonian and all $7$-Halin graphs are $1$-edge hamiltonian. These results are best possible.
Doubly Even Orientable Closed 2-Cell Embeddings of the Complete Graph
Authors: Grannell Mike J , McCourt Thomas A
Published: January 2020

For all $m\geq 1$ and $k\geq 2$, we construct closed 2-cell embeddings of the complete graph $K_{8km+4k+1}$ with faces of size $4k$ in orientable surfaces. Moreover, we show that when $k\geq 3$ there are at least $(2m-1)!/2(2m+1)=2^{2m\text{log}_2m-\mathrm{O}(m)}$ nonisomorphic embeddings of this type. We also show that when $k=2$ there are at least $\frac14 \pi^{\frac12}m^{-\frac{5}{4}}\left(\frac{4m}{e^2}\right)^{\sqrt{m}}(1-\mathrm{o}(1))$ nonisomorphic embeddings of this type.
Intersecting $k$-Uniform Families Containing all the $k$-Subsets of a Given Set
Authors: Li Wei-Tian , Chen Bor-Liang , Huang Kuo-Ching , Lih Ko-Wei
Published: January 2020

Let $m, n$, and $k$ be integers satisfying $0 < k \leq n < 2k \leq m$. A family of sets $\mathcal{F}$ is called an $(m,n,k)$-intersecting family if $\binom{[n]}{k} \subseteq \mathcal{F} \subseteq \binom{[m]}{k}$ and any pair of members of $\mathcal{F}$ have nonempty intersection. Maximum $(m,k,k)$- and $(m,k+1,k)$-intersecting families are determined by the theorems of Erdős-Ko-Rado and Hilton-Milner, respectively. We determine the maximum families for the cases $n = 2k-1, 2k-2, 2k-3$, and $m$ sufficiently large.
Generalised Knight's Tours
Authors: Kamčev Nina
Published: January 2020

The problem of existence of closed knight's tours in $[n]^d$, where $[n]=\{0, 1, 2, \dots, n-1\}$, was recently solved by Erde, Golénia, and Golénia. They raised the same question for a generalised, $(a, b)$ knight, which is allowed to move along any two axes of $[n]^d$ by $a$ and $b$ unit lengths respectively.Given an even number $a$, we show that the $[n]^d$ grid admits an $(a, 1)$ knight's tour for sufficiently large even side length $n$.
Beyond Alternating Permutations: Pattern Avoidance in Young Diagrams and Tableaux
Authors: Gowravaram Nihal , Jagadeesan Ravi
Published: January 2020

We investigate pattern avoidance in alternating permutations and generalizations thereof. First, we study pattern avoidance in an alternating analogue of Young diagrams. In particular, we extend Babson-West's notion of shape-Wilf equivalence to apply to alternating permutations and so generalize results of Backelin-West-Xin and Ouchterlony to alternating permutations. Second, we study pattern avoidance in the more general context of permutations with restricted ascents and descents. We consider a question of Lewis regarding permutations that are the reading words of thickened staircase Young tableaux, that is, permutations that have $k-1$ ascents followed by a descent, followed by $k-1$ ascents, et cetera. We determine the relative sizes of the sets of pattern-avoiding $(k-1)$-ascent permutations in terms of the forbidden pattern. Furthermore, inequalities in the sizes of sets of pattern-avoiding permutations in this context arise from further extensions of shape-equivalence type enumerations. This paper is the first of a two-paper series presenting the work of Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux (arXiv:1301.6796v1). The second in the series is Ascent-descent Young diagrams and pattern avoidance in alternating permutations (by the second author, submitted).
Macaulay Posets
Authors: Bezrukov Sergei L. , Leck Uwe
Published: January 2020

Macaulay posets are posets for which there is an analogue of the classical Kruskal-Katona theorem for finite sets. These posets are of great importance in many branches of combinatorics and have numerous applications. We survey mostly new and also some old results on Macaulay posets, where the intention is to present them as pieces of a general theory. In particular, the classical examples of Macaulay posets are included as well as new ones. Emphasis is also put on the construction of Macaulay posets, and their relations to other discrete optimization problems.
A Bijective Proof of a Major Index Theorem of Garsia and Gessel
Authors: Novick Mordechai
Published: January 2020

In this paper we provide a bijective proof of a theorem of Garsia and Gessel describing the generating function of the major index over the set of all permutations of $[n]=\{1,...,n\}$ which are shuffles of given disjoint ordered sequences $\pi_1,...,\pi_k$ whose union is $[n]$. The proof is based on a result (an "insertion lemma") of Haglund, Loehr, and Remmel which describes the change in major index resulting from the insertion of a given new element in any place in a given permutation. Using this lemma we prove the theorem by establishing a bijection between shuffles of ordered sequences and a certain set of partitions. A special case of Garsia and Gessel's theorem provides a proof of the equidistribution of major index and inversion number over inverse descent classes, a result first proved bijectively by Foata and Schutzenberger in 1978. We provide, based on the method of our first proof, another bijective proof of this result.
A Generic Method for Bijections between Blossoming Trees and Planar Maps
Authors: Albenque Marie , Poulalhon Dominique
Published: January 2020

This article presents a unified bijective scheme between planar maps and blossoming trees, where a blossoming tree is defined as a spanning tree of the map decorated with some dangling half-edges that enable to reconstruct its faces. Our method generalizes a previous construction of Bernardi by loosening its conditions of application so as to include annular maps, that is maps embedded in the plane with a root face different from the outer face.The bijective construction presented here relies deeply on the theory of $\alpha$-orientations introduced by Felsner, and in particular on the existence of minimal and accessible orientations. Since most of the families of maps can be characterized by such orientations, our generic bijective method is proved to capture as special cases many previously known bijections involving blossoming trees: for example Eulerian maps, $m$-Eulerian maps, non-separable maps and simple triangulations and quadrangulations of a $k$-gon. Moreover, it also permits to obtain new bijective constructions for bipolar orientations and $d$-angulations of girth $d$ of a $k$-gon.As for applications, each specialization of the construction translates into enumerative by-products, either via a closed formula or via a recursive computational scheme. Besides, for every family of maps described in the paper, the construction can be implemented in linear time. It yields thus an effective way to encode or sample planar maps.In a recent work, Bernardi and Fusy introduced another unified bijective scheme; we adopt here a different strategy which allows us to capture different bijections. These two approaches should be seen as two complementary ways of unifying bijections between planar maps and decorated trees.
A Finite Calculus Approach to Ehrhart Polynomials
Authors: Sam Steven V. , Woods Kevin M.
Published: January 2020

A rational polytope is the convex hull of a finite set of points in ${\Bbb R}^d$ with rational coordinates. Given a rational polytope ${\cal P} \subseteq {\Bbb R}^d$, Ehrhart proved that, for $t\in{\Bbb Z}_{\ge 0}$, the function $\#(t{\cal P} \cap {\Bbb Z}^d)$ agrees with a quasi-polynomial $L_{\cal P}(t)$, called the Ehrhart quasi-polynomial. The Ehrhart quasi-polynomial can be regarded as a discrete version of the volume of a polytope. We use that analogy to derive a new proof of Ehrhart's theorem. This proof also allows us to quickly prove two other facts about Ehrhart quasi-polynomials: McMullen's theorem about the periodicity of the individual coefficients of the quasi-polynomial and the Ehrhart–Macdonald theorem on reciprocity.
On Restricted Unitary Cayley Graphs and Symplectic Transformations Modulo $n$
Authors: De Beaudrap Niel
Published: January 2020

We present some observations on a restricted variant of unitary Cayley graphs modulo $n$, and implications for a decomposition of elements of symplectic operators over the integers modulo $n$. We define quadratic unitary Cayley graphs $G_n$, whose vertex set is the ring ${\Bbb Z}_n$, and where residues $a,b$ modulo $n$ are adjacent if and only if their difference is a quadratic residue. By bounding the diameter of such graphs, we show an upper bound on the number of elementary operations (symplectic scalar multiplications, symplectic row swaps, and row additions or subtractions) required to decompose a symplectic matrix over ${\Bbb Z}_n$. We also characterize the conditions on $n$ for $G_n$ to be a perfect graph.
Equidimensionality of the Brauer Loop Scheme
Authors: Rothbach Brian
Published: January 2020

We give another description of certain subvarieties of the Brauer loop scheme of Knutson and Zinn-Justin. As a consequence, we show that the Brauer loop scheme is equidimensional.
Forcing $k$-Repetitions in Degree Sequences
Authors: Caro Yair , Shapira Asaf , Yuster Raphael
Published: January 2020

One of the most basic results in graph theory states that every graph with at least two vertices has two vertices with the same degree. Since there are graphs without $3$ vertices of the same degree, it is natural to ask if for any fixed $k$, every graph $G$ is "close" to a graph $G'$ with  $k$ vertices of the same degree. Our main result in this paper is that this is indeed the case. Specifically, we show that for any positive integer $k$, there is a constant $C=C(k)$, so that given any graph $G$, one can remove from $G$ at most $C$ vertices and thus obtain a new graph $G'$ that contains at least $\min\{k,|G|-C\}$ vertices of the same degree.Our main tool is a multidimensional zero-sum theorem for integer sequences, which we prove using an old geometric approach of Alon and Berman.
Locally 3-Arc-Transitive Regular Covers of Complete Bipartite Graphs
Authors: Swartz Eric
Published: January 2020

In this paper, locally $3$-arc-transitive regular covers of complete bipartite graphs are studied, and results are obtained that apply to arbitrary covering transformation groups. In particular, methods are obtained for classifying the locally $3$-arc-transitive graphs with a prescribed covering transformation group, and these results are applied to classify the locally $3$-arc-transitive regular covers of complete bipartite graphs with covering transformation group isomorphic to a cyclic group or an elementary abelian group of order $p^2$.
On the Subpartitions of the Ordinary Partitions, II
Authors: Kim Byungchan , Kim Eunmi
Published: January 2020

In this note, we provide a new proof for the number of partitions of $n$ having subpartitions of length $\ell$ with gap $d$. Moreover, by generalizing the definition of a subpartition, we show what is counted by $q$-expansion\[\prod_{n=1}^{\infty} \frac{1}{1-q^n} \sum_{n=0}^{\infty} (-1)^n q^{(an^2 + bn)/2}\]and how fast it grows. Moreover, we prove there is a special sign pattern for the coefficients of $q$-expansion\[\prod_{n=1}^{\infty} \frac{1}{1-q^n} \left( 1 - 2 \sum_{n=0}^{\infty} (-1)^n q^{(an^2 + bn)/2} \right).\]
Face-Width of Pfaffian Braces and Polyhex Graphs on Surfaces
Authors: Ye Dong , Zhang Heping
Published: January 2020

A graph $G$ with a perfect matching is Pfaffian if it admits an orientation $D$ such that every central cycle $C$ (i.e. $C$ is of even size and $G-V(C)$ has a perfect matching) has an odd number of edges oriented in either direction of the cycle. It is known that the number of perfect matchings of a Pfaffian graph can be computed in polynomial time. In this paper, we show that every embedding of a Pfaffian brace (i.e. 2-extendable bipartite graph)  on a surface with a positive genus has face-width at most 3.  Further, we study Pfaffian cubic braces and obtain a characterization of Pfaffian polyhex graphs: a polyhex graph is Pfaffian if and only if it is either non-bipartite or isomorphic to the cube, or the Heawood graph, or the Cartesian product $C_k\times K_2$ for even integers $k\ge 6$.
Homomesy in Products of Two Chains
Authors: Propp James , Roby Tom
Published: January 2020

Many invertible actions $\tau$ on a set $\mathcal{S}$ of combinatorial objects, along with a natural statistic $f$ on $\mathcal{S}$, exhibit the following property which we dub homomesy: the average of $f$ over each $\tau$-orbit in $\mathcal{S}$ is the same as the average of $f$ over the whole set $\mathcal{S}$. This phenomenon was first noticed by Panyushev in 2007 in the context of the rowmotion action on the set of antichains of a root poset; Armstrong, Stump, and Thomas proved Panyushev's conjecture in 2011. We describe a theoretical framework for results of this kind  that applies more broadly, giving examples in a variety of contexts. These include linear actions on vector spaces, sandpile dynamics, Suter's action on certain subposets of Young's Lattice, Lyness 5-cycles, promotion of rectangular semi-standard Young tableaux, and the rowmotion and promotion actions on certain posets. We give a detailed description of the latter situation for products of two chains.
Structure Coefficients of the Hecke Algebra of $(\mathcal{S}_{2n},\mathcal{B}_n)$
Authors: Tout Omar
Published: January 2020

The Hecke algebra of the pair $(\mathcal{S}_{2n},\mathcal{B}_n)$, where $\mathcal{B}_n$ is the hyperoctahedral subgroup of $\mathcal{S}_{2n}$, was introduced by James in 1961. It is a natural analogue of the center of the symmetric group algebra. In this paper, we give a polynomiality property of its structure coefficients. Our main tool is a combinatorial algebra which projects onto the Hecke algebra of $(\mathcal{S}_{2n},\mathcal{B}_n)$ for every $n$. To build it, by using partial bijections we introduce and study a new class of finite dimensional algebras.
Square-Free Words with Square-Free Self-Shuffles
Authors: Currie James D. , Saari Kalle
Published: January 2020

We answer a question of Harju: For every $n\ge 3$ there is a square-free ternary word of length $n$ with a square-free self-shuffle.
Switching in One-Factorisations of Complete Graphs
Authors: Kaski Petteri , Medeiros André de Souza , Östergård Patric R.J. , Wanless Ian M.
Published: January 2020

We define two types of switchings between one-factorisations of complete graphs, called factor-switching and vertex-switching. For each switching operation and for each $n\le 12$, we build a switching graph that records the transformations between isomorphism classes of one-factorisations of $K_{n}$.  We establish various parameters of our switching graphs, including order, size, degree sequence, clique number and the radius of each component.As well as computing data for $n\le12$, we demonstrate several properties that hold for one-factorisations of $K_{n}$ for general $n$. We show that such factorisations have a parity which is not changed by factor-switching, and this leads to disconnected switching graphs. We also characterise the isolated vertices that arise from an absence of switchings. For factor-switching the isolated vertices are perfect one-factorisations, while for vertex-switching the isolated vertices are closely related to atomic Latin squares.
An Optimal Strongly Identifying Code in the Infinite Triangular Grid
Authors: Honkala Iiro
Published: January 2020

Assume that $G = (V, E)$ is an undirected graph, and $C \subseteq V$. For every ${\bf v} \in V$, we denote by $I({\bf v})$ the set of all elements of $C$ that are within distance one from ${\bf v}$. If the sets $I({\bf v})\setminus \{{\bf v}\}$ for ${\bf v}\in V$ are all nonempty, and, moreover, the sets $\{ I({\bf v}), I({\bf v}) \setminus \{ {\bf v}\}\}$ for ${\bf v} \in V$ are disjoint, then $C$ is called a strongly identifying code. The smallest possible density of a strongly identifying code in the infinite triangular grid is shown to be $6/19$.
On Fractional Realizations of Graph Degree Sequences
Authors: Barrus Michael D.
Published: January 2020

We introduce fractional realizations of a graph degree sequence and a closely associated convex polytope. Simple graph realizations correspond to a subset of the vertices of this polytope; we characterize degree sequences for which each polytope vertex corresponds to a simple graph realization. These include the degree sequences of threshold and pseudo-split graphs, and we characterize their realizations both in terms of forbidden subgraphs and graph structure.
Some New Characterizations of Graph Colorability and of Blocking Sets of Projective Spaces
Authors: Schauz Uwe
Published: January 2020

Let $G=(V,E)$ be a graph and $q$ be an odd prime power. We prove that $G$ possess a proper vertex coloring with $q$ colors if and only if there exists an odd vertex labeling $x\in F_q^V$ of $G$. Here, $x$ is called odd if there is an odd number of partitions $\pi=\{V_1,V_2,\dotsc,V_t\}$ of $V$ whose blocks $V_i$ are \(G\)-bipartite and \(x\)-balanced, i.e., such that $G|_{V_i}$ is connected and bipartite, and $\sum_{v\in V_i}x_v=0$. Other new characterizations concern edge colorability of graphs and, on a more general level, blocking sets of projective spaces. Some of these characterizations are formulated in terms of a new switching game.
Records in Set Partitions
Authors: Knopfmacher Arnold , Mansour Toufik , Wagner Stephan
Published: January 2020

A partition of $[n]=\{1,2,\ldots,n\}$ is a decomposition of $[n]$ into nonempty subsets called blocks. We will make use of the canonical representation of a partition as a word over a finite alphabet, known as a restricted growth function. An element $a_i$ in such a word $\pi$ is a strong (weak) record if $a_i> a_j$ ($a_i\geq a_j$) for all $j=1,2,\ldots,i-1$. Furthermore, the position of this record is $i$. We derive generating functions for the total number of strong (weak) records in all words corresponding to partitions of $[n]$, as well as for the sum of the positions of the records. In addition we find the asymptotic mean values and variances for the number, and for the sum of positions, of strong (weak) records in all partitions of $[n]$.
Clique Trees of Infinite Locally Finite Chordal Graphs
Authors: Hofer-Temmel Christoph , Lehner Florian
Published: January 2020

We investigate clique trees of infinite locally finite chordal graphs. Our main contribution is a bijection between the set of clique trees and the product of local finite families of finite trees. Even more, the edges of a clique tree are in bijection with the edges of the corresponding collection of finite trees. This allows us to enumerate the clique trees of a chordal graph and extend various classic characterisations of clique trees to the infinite setting.
Lower Bounds for Identifying Codes in some Infinite Grids
Authors: Martin Ryan , Stanton Brendon
Published: January 2020

An $r$-identifying code on a graph $G$ is a set $C\subset V(G)$ such that for every vertex in $V(G)$, the intersection of the radius-$r$ closed neighborhood with $C$ is nonempty and unique. On a finite graph, the density of a code is $|C|/|V(G)|$, which naturally extends to a definition of density in certain infinite graphs which are locally finite. We present new lower bounds for densities of codes for some small values of $r$ in both the square and hexagonal grids.