bluuebunny/crossref_metadata_2025 huggingface dataset:
Domination of the Rectangular Queen's Graph
Authors: Bozóki Sándor , Gál Péter , Marosi István , Weakley William D.
Published: January 2020

The queens graph $Q_{m \times n}$ has the squares of the $m \times n$ chessboard as its vertices; two squares are adjacent if they are in the same row, column, or diagonal of the board. A set $D$ of squares of $Q_{m \times n}$ is a dominating set for $Q_{m \times n}$ if every square of $Q_{m \times n}$ is either in $D$ or adjacent to a square in $D$. The minimum size of a dominating set of $Q_{m \times n}$ is the domination number, denoted by $\gamma(Q_{m \times n})$.

Values of $\gamma(Q_{m \times n}), \, 4 \leq m \leq n \leq 18,\,$ are given here, in each case with a file of minimum dominating sets (often all of them, up to symmetry) in an online appendix. In these ranges for $m$ and $n$, monotonicity fails once: $\gamma(Q_{8\times 11}) = 6 > 5 = \gamma(Q_{9 \times 11}) = \gamma(Q_{10 \times 11}) = \gamma(Q_{11 \times 11})$.

Let $g(m)$ [respectively $g^{*}(m)$] be the largest integer such that $m$ queens suffice to dominate the $(m+1) \times g(m)$ board [respectively, to dominate the $(m+1) \times g^{*}(m)$ board with no two queens in a row]. Starting from the elementary bound $g(m) \leq 3m$, domination when the board is far from square is investigated. It is shown (Theorem 2) that $g(m) = 3m$ can only occur when $m \equiv 0, 1, 2, 3, \mbox{or } 4 \mbox{ (mod 9)}$, with an online appendix showing that this does occur for $m \leq 40, m \neq 3$. Also (Theorem 4), if $m \equiv 5, 6, \mbox{or } 7 \mbox{ (mod 9)}$ then $g^{*}(m) \leq 3m-2$, and if $m \equiv 8 \mbox{ (mod 9)}$ then $g^{*}(m) \leq 3m-4$. It is shown that equality holds in these bounds for $m \leq 40 $.

Lower bounds on $\gamma(Q_{m \times n})$ are given. In particular, if $m \leq n$ then $\gamma(Q_{m \times n}) \geq \min \{ m,\lceil (m+n-2)/4 \rceil \}$.

Two types of dominating sets (orthodox covers and centrally strong sets) are developed; each type is shown to give good upper bounds of $\gamma(Q_{m \times n})$ in several cases.

Three questions are posed: whether monotonicity of $\gamma(Q_{m \times n})$ holds (other than from $(m, n) = (8, 11)$ to $(9, 11)$), whether $\gamma(Q_{m \times n}) = (m+n-2)/4$ occurs with $m \leq n < 3m+2$ (other than for $(m, n) = (3, 3)$ and $(11, 11)$), and whether the lower bound given above can be improved.

A set of squares is independent if no two of its squares are adjacent. The minimum size of an independent dominating set of $Q_{m \times n}$ is the independent domination number, denoted by $i(Q_{m \times n})$. Values of $i(Q_{m \times n}), \, 4 \leq m \leq n \leq 18, \,$ are given here, in each case with some minimum dominating sets. In these ranges for $m$ and $n$, monotonicity fails twice: $i(Q_{8\times 11}) = 6 > 5 = i(Q_{9 \times 11}) = i(Q_{10 \times 11}) = i(Q_{11 \times 11})$, and $i(Q_{11 \times 18}) = 9 > 8 = i(Q_{12\times 18})$.
Rigged Configurations for all Symmetrizable Types
Authors: Salisbury Ben , Scrimshaw Travis
Published: January 2020

In an earlier work, the authors developed a rigged configuration model for the crystal $B(\infty)$ (which also descends to a model for irreducible highest weight crystals via a cutting procedure). However, the result obtained was only valid in finite types, affine types, and simply-laced indefinite types. In this paper, we show that the rigged configuration model proposed does indeed hold for all symmetrizable types. As an application, we give an easy combinatorial condition that gives a Littlewood-Richardson rule using rigged configurations which is valid in all symmetrizable Kac-Moody types.
Adaptive Identification in Torii in the King Lattice
Authors: Ben-Haim Yael , Gravier Sylvain , Lobstein Antoine , Moncel Julien
Published: January 2020

Given a connected graph $G=(V,E)$, Let $r\geq1$ be an integer and $B_r(v)$ denote the ball of radius $r$ centered at $v\in V$, i.e., the set of all vertices within distance $r$ from $v$. A subset of vertices $C \subseteq V$ is an $r$-identifying code of $G$ (for a given nonzero constant $r\in \mathbb{N}$) if and only if all the sets $B_r(v)\cap C$ are nonempty and pairwise distinct. These codes were introduced in [M. G. Karpovsky, K. Chakrabarty, L. B. Levitin, On a New Class of Codes for Identifying Vertices in Graphs, IEEE Transactions on Information Theory 44(2) (1998), 599–611] to model a fault-detection problem in multiprocessor systems. They are also used to devise location-detection schemes in the framework of wireless sensor networks. These codes enable one to locate a malfunctioning device in these networks, provided one scans all the vertices of the code. We study here an adaptive version of identifying codes, which enables to perform tests dynamically. The main feature of such codes is that they may require significantly fewer tests, compared to usual static identifying codes. In this paper we study adaptive identifying codes in torii in the king lattice. In this framework, adaptive identification can be closely related to a Rényi-type search problem studied by M. Ruszinkó [M. Ruszinkó, On a 2-dimensional Search Problem, Journal of Statistical Planning and Inference 37(3) (1993), 371–383].
On KM-Arcs in Small Desarguesian Planes
Authors: Vandendriessche Peter
Published: January 2020

In this paper we study the existence problem for KM-arcs in small Desarguesian planes. We establish a full classification of KM$_{q,t}$-arcs for $q\le 32$, up to projective equivalence. We also construct a KM$_{64,4}$-arc; as $t=4$ was the only value for which the existence of a KM$_{64,t}$-arc was unknown, this fully settles the existence problem for $q\le 64$.
Topological Infinite Gammoids, and a New Menger-Type Theorem for Infinite Graphs
Authors: Carmesin Johannes
Published: January 2020

Answering a question of Diestel, we develop a topological notion of gammoids in infinite graphs which, unlike traditional infinite gammoids, always define a matroid.As our main tool, we prove for any infinite graph $G$ with vertex-sets $A$ and $B$, if every finite subset of $A$ is linked to $B$ by disjoint paths, then the whole of $A$ can be linked to the closure of $B$ by disjoint paths or rays in a natural topology on $G$ and its ends.This latter theorem implies the topological Menger theorem of Diestel for locally finite graphs. It also implies a special case of the infinite Menger theorem of Aharoni and Berger.
Flag Bicolorings, Pseudo-Orientations, and Double Covers of Maps
Authors: Koike Hiroki , Pellicer Daniel , Raggi Miguel , Wilson Steve
Published: January 2020

This paper discusses consistent flag bicolorings of maps, in their own right and as generalizations of orientations and pseudo-orientations. Furthermore, a related doubling concept is introduced, and relationships between these ideas are explored.
Quantum State Transfer in Coronas
Authors: Ackelsberg Ethan , Brehm Zachary , Chan Ada , Mundinger Joshua , Tamon Christino
Published: January 2020

We study state transfer in quantum walks on graphs relative to the adjacency matrix. Our motivation is to understand how the addition of pendant subgraphs affect state transfer. For two graphs $G$ and $H$, the Frucht-Harary corona product $G \circ H$ is obtained by taking $|G|$ copies of the cone $K_{1} + H$ and by identifying the conical vertices according to $G$. Our work explores conditions under which the corona $G \circ H$ exhibits state transfer. We also describe new families of graphs with state transfer based on the corona product. Some of these constructions provide a generalization of related known results.
Colorful Subhypergraphs in Uniform Hypergraphs
Authors: Alishahi Meysam
Published: January 2020

There are several topological results ensuring in any properly colored graph the existence of a colorful complete bipartite subgraph, whose order is bounded from below by some topological invariants of some topological spaces associated to the graph. Meunier [Colorful subhypergraphs in Kneser hypergraphs, The Electronic Journal of Combinatorics, 2014] presented the first colorful type result for uniform hypergraphs. In this paper, we give some new generalizations of the $\mathbb{Z}_p$-Tucker lemma and by use of them, we improve Meunier's result and some other colorful results by Simonyi, Tardif, and Zsbán [Colourful theorems and indices of homomorphism complexes, The Electronic Journal of Combinatorics, 2014] and by Simonyi and Tardos [Colorful subgraphs in Kneser-like graphs, European Journal of Combinatorics, 2007] to uniform hypergraphs. Also, we introduce some new lower bounds for the chromatic number and local chromatic number of uniform hypergraphs. A hierarchy between these lower bounds is presented as well.
Matching Polytons
Authors: Doležal Martin , Hladký Jan
Published: January 2020

Hladký, Hu, and Piguet [Tilings in graphons, preprint] introduced the notions of matching and fractional vertex covers in graphons. These are counterparts to the corresponding notions in finite graphs. 

Combinatorial optimization studies the structure of the matching polytope and the fractional vertex cover polytope of a graph. Here, in analogy, we initiate the study of the structure of the set of all matchings and of all fractional vertex covers in a graphon. We call these sets the matching polyton and the fractional vertex cover polyton.

We also study properties of matching polytons and fractional vertex cover polytons along convergent sequences of graphons.

 As an auxiliary tool of independent interest, we prove that a graphon is $r$-partite if and only if it contains no graph of chromatic number $r+1$. This in turn gives a characterization of bipartite graphons as those having a symmetric spectrum.
Orthogonal Trades in Complete Sets of MOLS
Authors: Cavenagh Nicholas , Donovan Diane , Demirkale Fatih
Published: January 2020

Let $B_p$ be the Latin square given by the addition table for the integers modulo an odd prime $p$. Here we consider the properties of Latin trades in $B_p$ which preserve orthogonality with one of the $p-1$ MOLS given by the finite field construction. We show that for certain choices of the orthogonal mate, there is a lower bound logarithmic in $p$ for the number of times each symbol occurs in such a trade, with an overall lower bound of $(\log{p})^2/\log\log{p}$ for the size of such a trade. Such trades imply the existence of orthomorphisms of the cyclic group which differ from a linear orthomorphism by a small amount. We also show that any transversal in $B_p$ hits the main diagonal either $p$ or at most $p-\log_2{p}-1$ times. Finally, if $p\equiv 1\pmod{6}$ we show the existence of a Latin square which is orthogonal to $B_p$ and which contains a $2\times 2$ subsquare.
All or Nothing at All
Authors: D'Arco Paolo , Esfahani Navid Nasr , Stinson Douglas R.
Published: January 2020

We continue a study of unconditionally secure all-or-nothing transforms (AONT) begun by Stinson (2001). An AONT is a bijective mapping that constructs $s$ outputs from $s$ inputs. We consider the security of $t$ inputs, when $s-t$ outputs are known. Previous work concerned the case $t=1$; here we consider the problem for general $t$, focussing on the case $t=2$. We investigate constructions of binary matrices for which the desired  properties hold with the maximum probability. Upper bounds on these probabilities are obtained via a quadratic programming approach, while lower bounds can be obtained from combinatorial constructions based on symmetric BIBDs and cyclotomy. We also report some results on  exhaustive searches and random constructions for small values of $s$.
Longest Monotone Subsequences and Rare Regions of Pattern-Avoiding Permutations
Authors: Madras Neal , Yıldırım Gökhan
Published: January 2020

We consider the distributions of the lengths of the longest monotone and alternating subsequences in classes of permutations of size $n$ that avoid a specific pattern or set of patterns, with respect to the uniform distribution on each such class. We obtain exact results for any class that avoids two patterns of length 3, as well as results for some classes that avoid one pattern of length 4 or more. In our results, the longest monotone subsequences have expected length proportional to $n$ for pattern-avoiding classes, in contrast with the $\sqrt n$ behaviour that holds for unrestricted permutations.  In addition, for a pattern $\tau$ of length $k$, we scale the plot of a random $\tau$-avoiding permutation down to the unit square and study the "rare region", which is the part of the square that is exponentially unlikely to contain any points. We prove that when $\tau_1>\tau_k$, the complement of the rare region is a closed set that contains the main diagonal of the unit square. For the case $\tau_1=k,$ we also show that the lower boundary of the part of the rare region above the main diagonal is a curve that is Lipschitz continuous and strictly increasing on $[0,1]$.
Cubic Edge-Transitive Bi-$p$-Metacirculants
Authors: Qin Yan-Li , Zhou Jin-Xin
Published: January 2020

A graph is said to be a bi-Cayley graph over a group $H$ if it admits $H$ as a group of automorphisms acting semiregularly on its vertices with two orbits. For a prime $p$, we call a bi-Cayley graph over a metacyclic $p$-group a bi-$p$-metacirculant. In this paper, the automorphism group of a connected cubic edge-transitive bi-$p$-metacirculant is characterized for an odd prime $p$, and the result reveals that a connected cubic edge-transitive bi-$p$-metacirculant exists only when $p=3$. Using this, a classification is given of connected cubic edge-transitive bi-Cayley graphs over an inner-abelian metacyclic $3$-group. As a result, we construct the first known infinite family of cubic semisymmetric graphs of order twice a $3$-power.
On Spherical Designs of Some Harmonic Indices
Authors: Zhu Yan , Bannai Eiichi , Bannai Etsuko , Kim Kyoung-Tark , Yu Wei-Hsuan
Published: January 2020

A finite subset $Y$ on the unit sphere $S^{n-1} \subseteq \mathbb{R}^n$ is called a spherical design of harmonic index $t$, if the following condition is satisfied: $\sum_{\mathbf{x}\in Y}f(\mathbf{x})=0$ for all real homogeneous harmonic polynomials $f(x_1,\ldots,x_n)$ of degree $t$. Also, for a subset $T$ of $\mathbb{N} = \{1,2,\cdots \}$, a finite subset $Y \subseteq S^{n-1}$ is called a spherical design of harmonic index $T,$ if $\sum_{\mathbf{x}\in Y}f(\mathbf{x})=0$ is satisfied for all real homogeneous harmonic polynomials $f(x_1,\ldots,x_n)$ of degree $k$ with $k\in T$.In the present paper we first study Fisher type lower bounds for the sizes of spherical designs of harmonic index $t$ (or for harmonic index $T$). We also study `tight' spherical designs of harmonic index $t$ or index $T$. Here `tight' means that the size of $Y$ attains the lower bound for this Fisher type inequality. The classification problem of tight spherical designs of harmonic index $t$ was started by Bannai-Okuda-Tagami (2015), and the case $t = 4$ was completed by Okuda-Yu (2016). In this paper we show the classification (non-existence) of tight spherical designs of harmonic index 6 and 8, as well as the asymptotic non-existence of tight spherical designs of harmonic index $2e$ for general $e\geq 3$. We also study the existence problem for tight spherical designs of harmonic index $T$ for some $T$, in particular, including index $T = \{8,4\}$.
Enumeration of Standard Young Tableaux of Shifted Strips with Constant Width
Authors: Sun Ping
Published: January 2020

Let $g_{n_1,n_2}$ be the number of standard Young tableau of truncated shifted shape with $n_1$ rows and $n_2$ boxes in each row. By using the integral method this paper derives the recurrence relations of $g_{3,n}$, $g_{n,4}$ and $g_{n,5}$ respectively. Specifically, $g_{n,4}$ is the $(2n-1)$-st Pell number.
Forbidden Berge Hypergraphs
Authors: Anstee R. P. , Salazar Santiago
Published: January 2020

A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix $F$, we say that a (0,1)-matrix $A$ has $F$ as a Berge hypergraph if there is a submatrix $B$ of $A$ and some row and column permutation of $F$, say $G$, with $G\le B$. Letting $\|A\|$ denote the number of columns in $A$, we define the extremal function $\mathrm{Bh}(m,{ F})=\max\{\|A\|\,:\, A \hbox{ }m\hbox{-rowed simple matrix and no Berge hypergraph }F\}$. We determine the asymptotics of $\mathrm{Bh}(m,F)$ for all $3$- and $4$-rowed $F$ and most $5$-rowed $F$. For certain $F$, this becomes the problem of determining the maximum number of copies of $K_r$ in a $m$-vertex graph that has no $K_{s,t}$ subgraph, a problem studied by Alon and Shikhelman.
Vertex-Addition Strategy for Domination-Like Invariants
Authors: Furuya Michitaka , Matsumoto Naoki
Published: January 2020

In [J. Graph Theory 13 (1989) 749—762], McCuaig and Shepherd gave an upper bound of the domination number for connected graphs with minimum degree at least two. In this paper, we propose a simple strategy which, together with the McCuaig-Shepherd theorem, gives a sharp upper bound of the domination number via the number of leaves. We also apply the same strategy to other domination-like invariants, and find a relationship between such invariants and the number of leaves.
Inversion Generating Functions for Signed Pattern Avoiding Permutations
Authors: Cameron Naiomi T. , Killpatrick Kendra
Published: January 2020

We consider the classical Mahonian statistics on the set $B_n(\Sigma)$ of signed permutations in the hyperoctahedral group $B_n$ which avoid all patterns in $\Sigma$, where $\Sigma$ is a set of patterns of length two.  In 2000, Simion gave the cardinality of $B_n(\Sigma)$ in the cases where $\Sigma$ contains either one or two patterns of length two and showed that $\left|B_n(\Sigma)\right|$ is constant whenever $\left|\Sigma\right|=1$, whereas in most but not all instances where $\left|\Sigma\right|=2$, $\left|B_n(\Sigma)\right|=(n+1)!$.  We answer an open question of Simion by providing bijections from $B_n(\Sigma)$ to $S_{n+1}$ in these cases where $\left|B_n(\Sigma)\right|=(n+1)!$.  In addition, we extend Simion's work by providing a combinatorial proof in the language of signed permutations for the major index on $B_n(21, \bar{2}\bar{1})$ and by giving the major index on $D_n(\Sigma)$ for $\Sigma =\{21, \bar{2}\bar{1}\}$ and $\Sigma=\{12,21\}$.  The main result of this paper is to give the inversion generating functions for $B_n(\Sigma)$ for almost all sets $\Sigma$ with $\left|\Sigma\right|\leq2.$
Kazhdan-Lusztig Polynomials of Thagomizer Matroids
Authors: Gedeon Katie R.
Published: January 2020

We introduce thagomizer matroids and compute the Kazhdan-Lusztig polynomial of a rank $n+1$ thagomizer matroid by showing that the coefficient of $t^k$ is equal to the number of Dyck paths of semilength $n$ with $k$ long ascents. We also give a conjecture for the $S_n$-equivariant Kazhdan-Lusztig polynomial of a thagomizer matroid.
Quantum $A_r$ $Q$-System Solutions as q-Multinomial Series
Authors: Francesco Philippe Di
Published: January 2020

We derive explicit expressions for the generating series of the fundamental solutions of the $A_r$ quantum $Q$-system of Di Francesco and Kedem [ Non-commutative integrability, paths and quasi-determinants, Adv. in Math. 228(1) (2011) 97–152], expressed in terms of any admissible initial data. These involve products of quantum multinomial coefficients, coded by the initial data structure.
An Arithmetic Property of Moments of the $\beta$-Hermite Ensemble and Certain Map Enumerators
Authors: Aggarwal Amol
Published: January 2020

Moments of the $\beta$-Hermite ensemble are known to be related to the enumerative theory of topological maps. When $\beta \in \{ 1, 2 \}$, asymptotic information about these moments has been used to deduce asymptotics on the number of maps of given genus, and arithmetic information about these moments can sometimes be explained by underlying group actions on the set of maps. In this paper we establish a new arithmetic property about the $2q$-th moment of the $\beta$-Hermite ensemble, for any prime $q \ge 3$ and real number $\beta > 0$, that has a combinatorial interpretation in terms of maps but no known combinatorial explanation. In the process, we derive several additional results that might be of independent interest, including a general integrality statement and an efficient algorithm for evaluating expectations of multi-part elementary symmetric polynomials of bounded length.
Arbitrary Orientations of Hamilton Cycles in Oriented Graphs
Authors: Kelly Luke
Published: January 2020

We use a randomised embedding method to prove that for all $\alpha>0$ any sufficiently large oriented graph $G$ with minimum in-degree and out-degree $\delta^+(G),\delta^-(G)\geq (3/8+\alpha)|G|$ contains every possible orientation of a Hamilton cycle. This confirms a conjecture of Häggkvist and Thomason.
A $q$-Robinson-Schensted-Knuth Algorithm and a $q$-Polymer
Authors: Pei Yuchen
Published: January 2020

In Matveev-Petrov (2017) a $q$-deformed Robinson-Schensted-Knuth algorithm ($q$RSK) was introduced.In this article we give reformulations of this algorithm in terms of the Noumi-Yamada description, growth diagrams and local moves. We show that the algorithm is symmetric, namely the output tableaux pairs are swapped in a sense of distribution when the input matrix is transposed. We also formulate a $q$-polymer model based on the $q$RSK, prove the corresponding Burke property, which we use to show a strong law of large numbers for the partition function given stationary boundary conditions and $q$-geometric weights.We use the $q$-local moves to define a generalisation of the $q$RSK taking a Young diagram-shape of array as the input. We write down the joint distribution of partition functions in the space-like direction of the $q$-polymer in $q$-geometric environment, formulate a $q$-version of the multilayer polynuclear growth model ($q$PNG) and write down the joint distribution of the $q$-polymer partition functions at a fixed time.
Some Properties of the Fibonacci Sequence on an Infinite Alphabet
Authors: Zhang Jiemeng , Wen Zhixiong , Wu Wen
Published: January 2020

The infinite Fibonacci sequence $\mathbf{F}$, which is an extension of the classic Fibonacci sequence to the infinite alphabet $\mathbb{N}$, is the fixed point of the morphism $\phi$: $(2i)\mapsto (2i)(2i+1)$ and $(2i+1)\mapsto (2i+2)$ for all $i\in\mathbb{N}$. In this paper, we study the growth order and digit sum of $\mathbf{F}$ and give several decompositions of $\mathbf{F}$ using singular words.
An Inductive Construction for Hamilton Cycles in Kneser Graphs
Authors: Johnson J. Robert
Published: January 2020

The Kneser graph $K(n,r)$ has as vertices all $r$-subsets of an $n$-set with two vertices adjacent if the corresponding subsets are disjoint. It is conjectured that, except for $K(5,2)$, these graphs are Hamiltonian for all $n\geq 2r+1$. In this note we describe an inductive construction which relates Hamiltonicity of $K(2r+2s,r)$ to Hamiltonicity of $K(2r'+s,r')$. This shows (among other things) that Hamiltonicity of $K(2r+1,r)$ for all $3\leq r\leq k$ implies Hamiltonicity of $K(2r+2,r)$ for all $r\leq 2k+1$. Applying this result extends the range of values for which Hamiltonicity of $K(n,r)$ is known. Another consequence is that certain families of Kneser graphs ($K(\frac{27}{13}r,r)$ for instance) contain infinitely many Hamiltonian graphs.
Sorting via Chip-Firing
Authors: Hopkins Sam , McConville Thomas , Propp James
Published: January 2020

We investigate a variant of the chip-firing process on the infinite path graph $\mathbb{Z}$: rather than treating the chips as indistinguishable, we label them with positive integers. To fire an unstable vertex, i.e. a vertex with more than one chip, we choose any two chips at that vertex and move the lesser-labeled chip to the left and the greater-labeled chip to the right. This labeled version of the chip-firing process exhibits a remarkable confluence property, similar to but subtler than the confluence that prevails for unlabeled chip-firing: when all chips start at the origin and the number of chips is even, the chips always end up in sorted order. Our proof of sorting relies upon an independently interesting lemma concerning unlabeled chip-firing which says that stabilization preserves a natural partial order on configurations. We also discuss some extensions of this sorting phenomenon to other graphs (variants of the infinite path), to other initial configurations, and to other Cartan-Killing types.
A Major-Index Preserving Map on Fillings
Authors: Alexandersson Per , Sawhney Mehtaab
Published: January 2020

We generalize a map by S. Mason regarding two combinatorial models for key polynomials, in a way that accounts for the major index. Furthermore we define a similar variant of this map, that regards alternative models for the modified Macdonald polynomials at t=0, and thus partially answers a question by J. Haglund. These maps together imply a certain uniqueness property regarding inversion–and coinversion-free fillings. These uniqueness properties allow us to generalize the notion of charge to a non-symmetric setting, thus answering a question by A. Lascoux and the analogous question in the symmetric setting proves a conjecture by K. Nelson.
Forbidden Families of Minimal Quadratic and Cubic Configurations
Authors: Sali Attila , Spiro Sam
Published: January 2020

A matrix is simple if it is a (0,1)-matrix and there are no repeated columns. Given a (0,1)-matrix $F$, we say a matrix $A$ has $F$ as a configuration, denoted $F\prec A$, if there is a submatrix of $A$ which is a row and column permutation of $F$. Let $|A|$ denote the number of columns of $A$. Let $\mathcal{F}$ be a family of matrices. We define the extremal function $\text{forb}(m, \mathcal{F}) = \max\{|A|\colon A \text{ is an }m-\text{rowed simple matrix and has no configuration } F\in\mathcal{F}\}$. We consider pairs $\mathcal{F}=\{F_1,F_2\}$ such that $F_1$ and $F_2$ have no common extremal construction and derive that individually each $\text{forb}(m, F_i)$ has greater asymptotic growth than $\text{forb}(m, \mathcal{F})$, extending research started by Anstee and Koch.
Core Partitions with Distinct Parts
Authors: Xiong Huan
Published: January 2020

Simultaneous core partitions have attracted much attention since Anderson's work on the number of $(t_1,t_2)$-core partitions. In this paper we focus on simultaneous core partitions with distinct parts. The generating function of $t$-core partitions with distinct parts is obtained. We also prove results on the number, the largest size and the average size of $(t, t + 1)$-core partitions with distinct parts. This gives a complete answer to a conjecture of Amdeberhan, which is partly and independently proved by Straub, Nath and Sellers, and Zaleski recently.
Extending Perfect Matchings to Gray Codes with Prescribed Ends
Authors: Gregor Petr , Novotný Tomáš , Škrekovski Riste
Published: January 2020

A binary (cyclic) Gray code is a (cyclic) ordering of all binary strings of the same length such that any two consecutive strings differ in a single bit. This corresponds to a Hamiltonian path (cycle) in the hypercube. Fink showed that every perfect matching in the $n$-dimensional hypercube $Q_n$ can be extended to a Hamiltonian cycle, confirming a conjecture of Kreweras. In this paper, we study the "path version" of this problem. Namely, we characterize when a perfect matching in $Q_n$ extends to a Hamiltonian path between two prescribed vertices of opposite parity. Furthermore, we characterize when a perfect matching in $Q_n$ with two faulty vertices extends to a Hamiltonian cycle. In both cases we show that for all dimensions $n\ge 5$ the only forbidden configurations are so-called half-layers, which are certain natural obstacles. These results thus extend Kreweras' conjecture with an additional edge, or with two faulty vertices. The proof for the case $n=5$ is computer-assisted.
Crystal Analysis of type C Stanley Symmetric Functions
Authors: Hawkes Graham , Paramonov Kirill , Schilling Anne
Published: January 2020

Combining results of T.K. Lam and J. Stembridge, the type $C$ Stanley symmetric function $F_w^C(\mathbf{x})$, indexed by an element $w$ in the type $C$ Coxeter group, has a nonnegative integer expansion in terms of Schur functions. We provide a crystal theoretic explanation of this fact and give an explicit combinatorial description of the coefficients in the Schur expansion in terms of highest weight crystal elements.
Unimodal Permutations and Almost-Increasing Cycles
Authors: Archer Kassie , Lauderdale L.-K.
Published: January 2020

In this paper, we establish a natural bijection between the almost-increasing cyclic permutations of length $n$ and unimodal permutations of length $n-1$. This map is used to give a new characterization, in terms of pattern avoidance, of almost-increasing cycles. Additionally, we use this bijection to enumerate several statistics on almost-increasing cycles. Such statistics include descents, inversions, peaks and excedances, as well as the newly defined statistic called low non-inversions. Furthermore, we refine the enumeration of unimodal permutations by descents, inversions and inverse valleys. We conclude this paper with a theorem that characterizes the standard cycle notation of almost-increasing permutations.
A Note on the Expected Length of the Longest Common Subsequences of two i.i.d. Random Permutations
Authors: Houdré Christian , Xu Chen
Published: January 2020

We address a question and a conjecture on the expected length of the longest common subsequences of two i.i.d. random permutations of $[n]:=\{1,2,...,n\}$. The question is resolved by showing that the minimal expectation is not attained in the uniform case. The conjecture asserts that $\sqrt{n}$ is a lower bound on this expectation, but we only obtain $\sqrt[3]{n}$ for it.
The Isoperimetric Number of the Incidence Graph of $PG(n,q)$
Authors: Elvey Price Andrew , Surani Muhammad Adib , Zhou Sanming
Published: January 2020

Let $\Gamma_{n,q}$ be the point-hyperplane incidence graph of the projective space $\operatorname{PG}(n,q)$, where $n \ge 2$ is an integer and $q$ a prime power. We determine the order of magnitude of $1-i_V(\Gamma_{n,q})$, where $i_V(\Gamma_{n,q})$ is the vertex-isoperimetric number of $\Gamma_{n,q}$. We also obtain the exact values of $i_V(\Gamma_{2,q})$ and the related incidence-free number of $\Gamma_{2,q}$ for $q \le 16$.
An Algebra Associated with a Flag in a Subspace Lattice over a Finite Field and the Quantum Affine Algebra
Authors: Watanabe Yuta
Published: January 2020

In this paper, we introduce an algebra $\mathcal{H}$ from a subspace lattice with respect to a fixed flag which contains its incidence algebra as a proper subalgebra. We then establish a relation between the algebra $\mathcal{H}$ and the quantum affine algebra $U_{q^{1/2}}(\widehat{\mathfrak{sl}}_2)$, where $q$ denotes the cardinality of the base field. It is an extension of the well-known relation between the incidence algebra of a subspace lattice and the quantum algebra $U_{q^{1/2}}(\mathfrak{sl}_2)$. We show that there exists an algebra homomorphism from $U_{q^{1/2}}(\widehat{\mathfrak{sl}}_2)$ to $\mathcal{H}$ and that any irreducible module for $\mathcal{H}$ is irreducible as an $U_{q^{1/2}}(\widehat{\mathfrak{sl}}_2)$-module.
Large Monochromatic Components in Edge Colored Graphs with a Minimum Degree Condition
Authors: Gyárfás András , Sárközy Gábor
Published: January 2020

It is well-known that in every $k$-coloring of the edges of the complete graph $K_n$ there is a monochromatic connected component of order at least ${n\over k-1}$. In this paper we study an extension of this problem by replacing complete graphs by graphs of large minimum degree. For $k=2$ the authors proved that $\delta(G)\ge{3n\over 4}$ ensures a monochromatic connected component with at least $\delta(G)+1$ vertices in every $2$-coloring of the edges of a graph $G$ with $n$ vertices. This result is sharp, thus for $k=2$ we really need a complete graph to guarantee that one of the colors has a monochromatic connected spanning subgraph. Our main result here is  that for larger values of $k$ the situation is different, graphs of minimum degree $(1-\epsilon_k)n$ can replace complete graphs and still there is a monochromatic connected component of order at least ${n\over k-1}$, in fact $$\delta(G)\ge \left(1 - \frac{1}{1000(k-1)^9}\right)n$$ suffices.Our second result is an improvement of this bound for $k=3$. If the edges of $G$ with  $\delta(G)\geq {9n\over 10}$ are $3$-colored, then there is a monochromatic component of order at least ${n\over 2}$. We conjecture that this can be improved to ${7n\over 9}$ and for general $k$ we conjecture the following: if $k\geq 3$ and  $G$ is a graph of order $n$ such that $\delta(G)\geq \left( 1 - \frac{k-1}{k^2}\right)n$, then in any $k$-coloring of the edges of $G$ there is a monochromatic connected component of order at least ${n\over k-1}$.
Some Variations on a Theme of Irina Mel'nichuk Concerning the Avoidability of Patterns in Strings of Symbols
Authors: McNulty George F.
Published: January 2020

The set of all doubled patterns on $n$ or fewer letters can be avoided on an alphabet with $k$ letters, where $k$ is the least even integer strictly greater than $n+1$, with the exception of $n=4$. The set of all doubled patterns on $4$ or fewer letters can be avoided on the $8$-letter alphabet. The set of all avoidable patterns on $n$ or fewer letters can be avoided on an alphabet with $2(n+2)$ letters.
A Euclidean Ramsey Result in the Plane
Authors: Tsaturian Sergei
Published: January 2020

An old question in Euclidean Ramsey theory asks, if the points in the plane are red-blue coloured, does there always exist a red pair of points at unit distance or five blue points in line separated by unit distances? An elementary proof answers this question in the affirmative.
Smaller Subgraphs of Minimum Degree $k$
Authors: Mousset Frank , Noever Andreas , Škorić Nemanja
Published: January 2020

In 1990 Erdős, Faudree, Rousseau and Schelp proved that for $k \ge 2$, every graph with $n \ge k+1$ vertices and $(k-1)(n-k+2)+\binom{k-2}{2}+1$ edges contains a subgraph of minimum degree $k$ on at most $n-\sqrt{n/6k^3}$ vertices. They conjectured that it is possible to remove at least $\epsilon_k n$ many vertices and remain with a subgraph of minimum degree $k$, for some $\epsilon_k>0$. We make progress towards their conjecture by showing that one can remove at least order of $\Omega(n/\log n)$ many vertices.
Perfect Matching Covers of Cubic Graphs of Oddness 2
Authors: Sun Wuyang , Wang Fan
Published: January 2020

A perfect matching cover of a graph $G$ is a set of perfect matchings of $G$ such that each edge of $G$ is contained in at least one member of it. Berge conjectured that every bridgeless cubic graph has a perfect matching cover of order at most 5. The Berge Conjecture is largely open and it is even unknown whether a constant integer $c$ does exist such that every bridgeless cubic graph has a perfect matching cover of order at most $c$. In this paper, we show that a bridgeless cubic graph $G$ has a perfect matching cover of order at most 11 if $G$ has a 2-factor in which the number of odd circuits is 2.
On the Stability and Instability of Finite Dynamical Systems with Prescribed Interaction Graphs
Authors: Gadouleau Maximilien
Published: January 2020

The dynamical properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding, and in the context of hat games, such as the guessing game and Winkler's hat game. The instability of an FDS is the minimum Hamming distance between a state and its image under the FDS, while the stability is the minimum of the reciprocal of the Hamming distance; they are both directly related to Winkler's hat game. In this paper, we study the value of the (in)stability of FDSs with prescribed interaction graphs. The first main contribution of this paper is the study of the maximum stability for interaction graphs with a loop on each vertex. We determine the maximum (in)stability for large enough alphabets and also prove some lower bounds for the Boolean alphabet. We also compare the maximum stability for arbitrary functions compared to monotone functions only. The second main contribution of the paper is the study of the average (in)stability of FDSs with a given interaction graph. We show that the average stability tends to zero with high alphabets, and we then investigate the average instability. In that study, we give bounds on the number of FDSs with positive instability (i.e fixed point free functions). We then conjecture that all non-acyclic graphs will have an average instability which does not tend to zero when the alphabet is large. We prove this conjecture for some classes of graphs, including cycles.
The Cycle Polynomial of a Permutation Group
Authors: Cameron Peter J. , Semeraro Jason
Published: January 2020

The cycle polynomial of a finite permutation group $G$ is the generating function for the number of elements of $G$ with a given number of cycles:\[F_G(x) = \sum_{g\in G}x^{c(g)},\] where $c(g)$ is the number of cycles of $g$ on $\Omega$. In the first part of the paper, we develop basic properties of this polynomial, and give a number of examples. In the 1970s, Richard Stanley introduced the notion of reciprocity for pairs of combinatorial polynomials. We show that, in a considerable number of cases, there is a polynomial in the reciprocal relation to the cycle polynomial of $G$; this is the orbital chromatic polynomial of $\Gamma$ and $G$, where $\Gamma$ is a $G$-invariant graph, introduced by the first author, Jackson and Rudd. We pose the general problem of finding all such reciprocal pairs, and give a number of examples and characterisations: the latter include the cases where $\Gamma$ is a complete or null graph or a tree. The paper concludes with some comments on other polynomials associated with a permutation group.
A Note on Not-4-List Colorable Planar Graphs
Authors: Voigt Margit , Kemnitz Arnfried
Published: January 2020

The Four Color Theorem states that every planar graph is properly 4-colorable. Moreover, it is well known that there are planar graphs that are non-$4$-list colorable. In this paper we investigate a problem combining proper colorings and list colorings. We ask whether the vertex set of every planar graph can be partitioned into two subsets where one subset induces a bipartite graph and the other subset induces a $2$-list colorable graph. We answer this question in the negative strengthening the result on non-$4$-list colorable planar graphs.
Random Enriched Trees with Applications to Random Graphs
Authors: Stufler Benedikt
Published: January 2020

We establish limit theorems that describe the asymptotic local and global geometric behaviour of random enriched trees considered up to symmetry. We apply these general results to random unlabelled weighted rooted graphs and uniform random unlabelled $k$-trees that are rooted at a $k$-clique of distinguishable vertices. For both models we establish a Gromov–Hausdorff scaling limit, a Benjamini–Schramm limit, and a local weak limit that describes the asymptotic shape near the fixed root.
A Note on the Linear Cycle Cover Conjecture of Gyárfás and Sárközy
Authors: Ergemlidze Beka , Győri Ervin , Methuku Abhishek
Published: January 2020

A linear cycle in a $3$-uniform hypergraph $H$ is a cyclic sequence of hyperedges such that any two consecutive hyperedges intersect in exactly one element and non-consecutive hyperedges are disjoint. Let $\alpha(H)$ denote the size of a largest independent set of $H$.We show that the vertex set of every $3$-uniform hypergraph $H$ can be covered by at most $\alpha(H)$ edge-disjoint linear cycles (where we accept a vertex and a hyperedge as a linear cycle), proving a weaker version of a conjecture of Gyárfás and Sárközy.
A Family of Partially Ordered Sets with Small Balance Constant
Authors: Chen Evan
Published: January 2020

Given a finite poset $\mathcal P$ and two distinct elements $x$ and $y$, we let $\operatorname{pr}_{\mathcal P}(x \prec y)$ denote the fraction of linear extensions of $\mathcal P$ in which $x$ precedes $y$. The balance constant $\delta(\mathcal P)$ of $\mathcal P$ is then defined by \[ \delta(\mathcal P) = \max_{x \neq y \in \mathcal P} \min \left\{ \operatorname{pr}_{\mathcal P}(x \prec y), \operatorname{pr}_{\mathcal P}(y \prec x) \right\}. \] The $1/3$-$2/3$ conjecture asserts that $\delta(\mathcal P) \ge \frac13$ whenever $\mathcal P$ is not a chain, but except from certain trivial examples it is not known when equality occurs, or even if balance constants can approach $1/3$.In this paper we make some progress on the conjecture by exhibiting a sequence of posets with balance constants approaching $\frac{1}{32}(93-\sqrt{6697}) \approx 0.3488999$, answering a question of Brightwell. These provide smaller balance constants than any other known nontrivial family.
Non-Classical Hyperplanes of Finite Thick Dual Polar Spaces
Authors: De Bruyn Bart
Published: January 2020

We obtain a classification of the nonclassical hyperplanes of all finite thick dual polar spaces of rank at least 3 under the assumption that there are no ovoidal and semi-singular hex intersections. In view of the absence of known examples of ovoids and semi-singular hyperplanes in finite thick dual polar spaces of rank 3, the condition on the nonexistence of these hex intersections can be regarded as not very restrictive. As a corollary, we also obtain a classification of the nonclassical hyperplanes of $DW(2n-1,q)$, $q$ even. In particular, we obtain a complete classification of all nonclassical hyperplanes of $DW(2n-1,q)$ if $q \in \{ 8,32 \}$.
An Orthosymplectic Pieri Rule
Authors: Stokke Anna
Published: January 2020

The classical Pieri formula gives a combinatorial rule for decomposing the product of a Schur function and a complete homogeneous symmetric polynomial as a linear combination of Schur functions with integer coefficients. We give a Pieri rule for describing the product of an orthosymplectic character and an orthosymplectic character arising from a one-row partition. We establish that the orthosymplectic Pieri rule coincides with Sundaram's Pieri rule for symplectic characters and that orthosymplectic characters and symplectic characters obey the same product rule.
Defective and Clustered Graph Colouring
Authors: Wood David R.
Published: January 2020

Consider the following two ways to colour the vertices of a graph where the requirement that adjacent vertices get distinct colours is relaxed. A colouring has defect $d$ if each monochromatic component has maximum degree at most $d$. A colouring has clustering $c$ if each monochromatic component has at most $c$ vertices. This paper surveys research on these types of colourings, where the first priority is to minimise the number of colours, with small defect or small clustering as a secondary goal. List colouring variants are also considered. The following graph classes are studied: outerplanar graphs, planar graphs, graphs embeddable in surfaces, graphs with given maximum degree, graphs with given maximum average degree, graphs excluding a given subgraph, graphs with linear crossing number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, graphs with given circumference, graphs excluding a given immersion, graphs with given thickness, graphs with given stack- or queue-number, graphs excluding $K_t$ as a minor, graphs excluding $K_{s,t}$ as a minor, and graphs excluding an arbitrary graph $H$ as a minor. Several open problems are discussed.
Symmetries of Shamrocks II: Axial Shamrocks
Authors: Ciucu Mihai
Published: January 2020

The first paper in this series presented the enumeration of cyclically symmetric, and cyclically symmetric and transpose complementary lozenge tilings of a hexagon with a shamrock removed from its center. In this article we address the transpose complementary case. The results we prove are in fact more general and allow us to give an extension of the symmetric case of the original hexagonal regions with shamrocks removed from their center, to what we call axial shamrocks. For the latter, the transpose complementary case is the only symmetry class besides the one requiring no symmetries. The enumeration of both of these follows from our results.
Hamilton Cycles in Sparse Robustly Expanding Digraphs
Authors: Lo Allan , Patel Viresh
Published: January 2020

The notion of robust expansion has played a central role in the solution of several conjectures involving the packing of Hamilton cycles in graphs and directed graphs. These and other results usually rely on the fact that every robustly expanding (di)graph with suitably large minimum degree contains a Hamilton cycle. Previous proofs of this require Szemerédi's Regularity Lemma and so this fact can only be applied to dense, sufficiently large robust expanders. We give a proof that does not use the Regularity Lemma and, indeed, we can apply our result to sparser robustly expanding digraphs.
On the Number of Connected Sets in Bounded Degree Graphs
Authors: Kangas Kustaa , Kaski Petteri , Korhonen Janne H. , Koivisto Mikko
Published: January 2020

A set of vertices in a graph is connected if it induces a connected subgraph. Using Shearer's entropy lemma and a computer search, we show that the number of connected sets in a graph with $n$ vertices and maximum vertex degree $d$ is at most $O(1.9351^n)$ for $d=3$, $O(1.9812^n)$ for $d=4$, and $O(1.9940^n)$ for $d=5$. Dually, we construct infinite families of graphs where the number of connected sets is at least $\Omega(1.7651^n)$ for $d=3$, $\Omega(1.8925^n)$ for $d=4$, and $\Omega(1.9375^n)$ for $d=5$.
Centroidal Localization Game
Authors: Bosek Bartłomiej , Gordinowicz Przemysław , Grytczuk Jarosław , Nisse Nicolas , Sokół Joanna , Śleszyńska-Nowak Małgorzata
Published: January 2020

One important problem in a network $G$ is to locate an (invisible) moving entity by using distance-detectors placed at strategical locations in $G$. For instance, the famous metric dimension of a graph $G$ is the minimum number $k$ of detectors placed in some vertices $\{v_1,\cdots,v_k\}$ such that the vector $(d_1,\cdots,d_k)$ of the distances $d(v_i,r)$ between the detectors and the entity's location $r$ allows to uniquely determine $r$ for every $r \in V(G)$. In a more realistic setting, each device does not get the exact distance to the entity's location. Rather, given locating devices placed in $\{v_1,\cdots,v_k\}$, we get only relative distances between the moving entity's location $r$ and the devices (roughly, for every $1\leq i,j\leq k$, it is provided whether $d(v_i,r) >$, $<$, or $=$ to $d(v_j,r)$). The centroidal dimension of a graph $G$ is the minimum number of devices required to locate the entity, in one step, in this setting.In this paper, we consider the natural generalization of the latter problem, where vertices may be probed sequentially (i.e., in several steps) until the moving entity is located. Roughly, at every turn, a set $\{v_1,\cdots,v_k\}$ of vertices are probed and then the relative order of the distances between the vertices $v_i$ and the current location $r$ of the moving entity is given. If it not located, the moving entity may move along one edge. Let $\zeta^* (G)$ be the minimum $k$ such that the entity is eventually located, whatever it does, in the graph $G$. We first prove that $\zeta^* (T)\leq 2$ for every tree $T$ and give an upper bound on $\zeta^*(G\square H)$ for the cartesian product of graphs $G$ and $H$. Our main result is that $\zeta^* (G)\leq 3$ for any outerplanar graph $G$. We then prove that $\zeta^* (G)$ is bounded by the pathwidth of $G$ plus 1 and that the optimization problem of determining $\zeta^* (G)$ is NP-hard in general graphs. Finally, we show that approximating (up to a small constant distance) the location of the robber in the Euclidean plane requires at most two vertices per turn.
Bounds for Matchings in Nonabelian Groups
Authors: Sawin Will
Published: January 2020

We give upper bounds for triples of subsets of a finite group such that the triples of elements that multiply to $1$ form a perfect matching. Our bounds are the first to give exponential savings in powers of an arbitrary finite group. Previously, Blasiak, Church, Cohn, Grochow, Naslund, Sawin, and Umans (2017) gave similar bounds in abelian groups of bounded exponent, and Petrov (2016) gave exponential bounds in certain $p$-groups.