bluuebunny/crossref_metadata_2025 huggingface dataset:
Pattern Popularity in 132-Avoiding Permutations
Authors: Rudolph Kate
Published: January 2020

The popularity of a pattern $p$ is the total number of copies of $p$ within all permutations of a set. We address popularity in the set of $132$-avoidng permutations. Bóna showed that in this set, all other non-monotone length-$3$ patterns are equipopular, and proved equipopularity relations between some length-$k$ patterns of a specific form. We prove equipopularity relations between general length-$k$ patterns, based on the structure of their corresponding binary plane trees. Our result explains all equipopularity relations for patterns of length up to $7$, and we conjecture that it provides a complete classification of equipopularity in $132$-avoiding permutations.
A Note on Coloring Line Arrangements
Authors: Ackerman Eyal , Pach János , Pinchasi Rom , Radoičić Radoš , Tóth Géza
Published: January 2020

We show that the lines of every arrangement of $n$ lines in the plane can be colored with $O(\sqrt{n/ \log n})$ colors such that no face of the arrangement is monochromatic. This improves a bound of Bose et al. by a $\Theta(\sqrt{\log n})$ factor. Any further improvement on this bound would also improve the best known lower bound on the following problem of Erdős: estimate the maximum number of points in general position within a set of $n$ points containing no four collinear points.
Cayley Graphs on the Symmetric Group Generated by Initial Reversals have Unit Spectral Gap
Authors: Cesi Filippo
Published: January 2020

In a recent paper Gunnells, Scott and Walden have determined the complete spectrum of the Schreier graph on the symmetric group corresponding to the Young subgroup $S_{n-2}\times S_2$ and generated by initial reversals. In particular they find that the first nonzero eigenvalue, or spectral gap, of the Laplacian is always 1, and report that "empirical evidence" suggests that this also holds for the corresponding Cayley graph. We provide a simple proof of this last assertion, based on the decomposition of the Laplacian of Cayley graphs, into a direct sum of irreducible representation matrices of the symmetric group.
Galkin Quandles, Pointed Abelian Groups, and Sequence A000712
Authors: Clark William E. , Hou Xiang-dong
Published: January 2020

For each pointed abelian group $(A,c)$, there is an associated Galkin quandle $G(A,c)$ which is an algebraic structure defined on $\Bbb Z_3\times A$ that can be used to construct knot invariants. It is known that two finite Galkin quandles are isomorphic if and only if their associated pointed abelian groups are isomorphic. In this paper we classify all finite pointed abelian groups. We show that the number of nonisomorphic pointed abelian groups of order $q^n$ ($q$ prime) is $\sum_{0\le m\le n}p(m)p(n-m)$, where $p(m)$ is the number of partitions of integer $m$.
Partitions and Compositions over Finite Fields
Authors: Muratovic-Ribic Amela , Wang Qiang
Published: January 2020

In this paper we  find an exact formula for the number of partitions of an element  $z$ into $m$ parts over a finite field,  i.e. we find the number of nonzero solutions of the equation $x_1+x_2+\cdots +x_m=z$ over a finite field when the order of terms does not matter. This is equivalent to counting the number of $m$-multi-subsets whose sum is $z$.  When the order of the terms in a solution does matter, such a solution is called a composition of $z$. The number of compositions is useful in the study of zeta functions of toric hypersurfaces over finite fields.  We also give an application in the study of polynomials of prescribed ranges over finite fields.
Generalized Pattern Frequency in Large Permutations
Authors: Cooper Joshua , Lundberg Erik , Nagle Brendan
Published: January 2020

In the study of permutations, generalized patterns extend classical patterns by adding the requirement that certain adjacent integers in a pattern must be adjacent in the permutation.For any generalized pattern $\pi_0^*$ of length $k$ with $1 \leq b \leq k$ blocks, we prove that for all $\mu > 0$, there exists $0 < c =c(k, \mu) < 1$ so that whenever $n \geq n_0(k, \mu, c)$, all but $c^n n!$ many $\pi \in S_n$ admit $(1 \pm \mu) \tfrac{1}{k!}\tbinom{n}{b}$ occurrences of $\pi_0^*$.  Up to the choice of $c$, this result is best possible for all $\pi_0^*$ with $k \geq 2$.We also give a lower bound on avoidance of the generalized pattern $12$-$34$, which answers a question of S. Elizalde (2006).
A Note on the Distance-Balanced Property of Generalized Petersen Graphs
Authors: Yang Rui , Hou Xinmin , Li Ning , Zhong Wei
Published: January 2020

A graph $G$ is said to be distance-balanced if for any edge $uv$ of $G$, the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$. Let $GP(n,k)$ be a generalized Petersen graph. Jerebic, Klavžar, and Rall [Distance-balanced graphs, Ann. Comb. 12 (2008) 71–79] conjectured that: For any integer $k\geq 2$, there exists a positive integer $n_0$ such that the $GP(n,k)$ is not distance-balanced for every integer $n\geq n_0$. In this note, we give a proof of this conjecture.
New Results in t-Tone Coloring of Graphs
Authors: Cranston Daniel , Kim Jaehoon , Kinnersley William
Published: January 2020

A $t$-tone $k$-coloring of $G$ assigns to each vertex of $G$ a set of $t$ colors from $\{1,\dots,k\}$ so that vertices at distance $d$ share fewer than $d$ common colors. The $t$-tone chromatic number of $G$, denoted $t(G)$, is the minimum $k$ such that $G$ has a $t$-tone $k$-coloring. Bickle and Phillips showed that always $\tau_2(G) \leq [\Delta(G)]^2 +\Delta(G)$, but conjectured that in fact $\tau_2(G) \leq 2\Delta(G) + 2$; we confirm this conjecture when $\Delta(G) \leq 3$ and also show that always $\tau_2(G) \leq \lceil (2 +\sqrt{2}) \Delta(G) \rceil$. For general $t$ we prove that $\tau_t(G) \leq (t^2+t) \Delta(G)$. Finally, for each $t \geq 2$ we show that there exist constants $c_1$ and $c_2$ such that for every tree $T$ we have $c_1 \sqrt{\Delta(T)} \leq \tau_t(T) \leq c_2\sqrt{\Delta(T)}$.
Dissimilarity Maps on Trees and the Representation Theory of $GL_n(\mathbb{C})$
Authors: Manon Christopher
Published: January 2020

We revisit representation theory in type $A,$ used previously to establish that the dissimilarity vectors of phylogenetic trees are points on the tropical Grassmannian variety. We use a different version of this construction to show that the space of phylogenetic trees $K_n$ maps to the tropical varieties of every flag variety of $GL_n(\mathbb{C}).$ Using this map, we find a tropical function on the space of phylogenetic trees for each semistandard tableaux, and we show that the functions satisfy the tropicalized equations which cut out $GL_n(\mathbb{C})$ flag varieties.
Generalized Balanced Tournament Designs with Block Size Four
Authors: Chee Yeow Meng , Kiah Han Mao , Wang Chengmin
Published: January 2020

In this paper, we remove the outstanding values $m$ for which the existence of a GBTD$(4,m)$ has not been decided previously. This leads to a complete solution to the existence problem regarding GBTD$(4,m)$s.
Nonconvexity of the Set of Hypergraph Degree Sequences
Authors: Liu Ricky Ini
Published: January 2020

It is well known that the set of possible degree sequences for a simple graph on $n$ vertices is the intersection of a lattice and a convex polytope. We show that the set of possible degree sequences for a simple $k$-uniform hypergraph on $n$ vertices is not the intersection of a lattice and a convex polytope for $k \geq 3$ and $n \geq k+13$. We also show an analogous nonconvexity result for the set of degree sequences of $k$-partite $k$-uniform hypergraphs and the generalized notion of $\lambda$-balanced $k$-uniform hypergraphs.
Bipartite Coverings and the Chromatic Number
Authors: Mubayi Dhruv , Vishwanathan Sundar
Published: January 2020

Consider a graph $G$ with chromatic number $k$ and a collection of complete bipartite graphs, or bicliques, that cover the edges of $G$. We prove the following two results: $\bullet$ If the bipartite graphs form a partition of the edges of $G$, then their number is at least $2^{\sqrt{\log_2 k}}$. This is the first improvement of the easy lower bound of $\log_2 k$, while the Alon-Saks-Seymour conjecture states that this can be improved to $k-1$. $\bullet$ The sum of the orders of the bipartite graphs in the cover is at least $(1-o(1))k\log_2 k$. This generalizes, in asymptotic form, a result of Katona and Szemerédi who proved that the minimum is $k\log_2 k$ when $G$ is a clique.
Independent Sets in Graphs with Given Minimum Degree
Authors: Alexander James , Cutler Jonathan , Mink Tim
Published: January 2020

The enumeration of independent sets in graphs with various restrictions has been a topic of much interest of late.  Let $i(G)$ be the number of independent sets in a graph $G$ and let $i_t(G)$ be the number of independent sets in $G$ of size $t$.  Kahn used entropy to show that if $G$ is an $r$-regular bipartite graph with $n$ vertices, then $i(G)\leq i(K_{r,r})^{n/2r}$.  Zhao used bipartite double covers to extend this bound to general $r$-regular graphs.  Galvin proved that if $G$ is a graph with $\delta(G)\geq \delta$ and $n$ large enough, then $i(G)\leq i(K_{\delta,n-\delta})$.  In this paper, we prove that if $G$ is a bipartite graph on $n$ vertices with $\delta(G)\geq\delta$ where $n\geq 2\delta$, then $i_t(G)\leq i_t(K_{\delta,n-\delta})$ when $t\geq 3$.  We note that this result cannot be extended to $t=2$ (and is trivial for $t=0,1$).  Also, we use Kahn's entropy argument and Zhao's extension to prove that if $G$ is a graph with $n$ vertices, $\delta(G)\geq\delta$, and $\Delta(G)\leq \Delta$, then $i(G)\leq i(K_{\delta,\Delta})^{n/2\delta}$.
Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs
Authors: Beck Matthias , Bogart Tristram , Pham Tu
Published: January 2020

A Golomb ruler is a sequence of distinct integers (the markings of the ruler) whose pairwise differences are distinct. Golomb rulers, also known as Sidon sets and $B_2$ sets, can be traced back to additive number theory in the 1930s and have attracted recent research activities on existence problems, such as the search for optimal Golomb rulers (those of minimal length given a fixed number of markings). Our goal is to enumerate Golomb rulers in a systematic way: we study$$g_m(t) := \# \left\{ {\bf x} \in {\bf Z}^{m+1} : \, 0 = x_0 < x_1 < \dots < x_m = t , \text{ all } x_j - x_k \text{ distinct} \right\} ,$$the number of Golomb rulers with $m+1$ markings and length $t$.Our main result is that $g_m(t)$ is a quasipolynomial in $t$ which satisfies a combinatorial reciprocity theorem: $(-1)^{m-1} g_m(-t)$ equals the number of rulers ${\bf x}$ of length $t$ with $m+1$ markings, each counted with its Golomb multiplicity, which measures how many combinatorially different Golomb rulers are in a small neighborhood of ${\bf x}$. Our reciprocity theorem can be interpreted in terms of certain mixed graphs associated to Golomb rulers; in this language, it is reminiscent of Stanley's reciprocity theorem for chromatic polynomials. Thus in the second part of the paper we develop an analogue of Stanley's theorem to mixed graphs, which connects their chromatic polynomials to acyclic orientations.
An Inhomogeneous Lambda-Determinant
Authors: Di Francesco Philippe
Published: January 2020

We introduce a multi-parameter generalization of the Lambda-determinant of Robbins and Rumsey, based on the cluster algebra with coefficients attached to a T-system recurrence. We express the result as a weighted sum over alternating sign matrices.
Multivariate Fuss-Narayana Polynomials and their Application to Random Matrices
Authors: Lenczewski Romuald , Salapata Rafal
Published: January 2020

It has been shown recently that the limit moments of $W(n)=B(n)B^{*}(n)$, where $B(n)$ is a product of $p$ independent rectangular random matrices, are certain homogeneous polynomials $P_{k}(d_0,d_1, \ldots , d_{p})$ in the asymptotic dimensions of these matrices. Using the combinatorics of noncrossing partitions, we explicitly determine these polynomials and show that they are closely related to polynomials which can be viewed as {\it multivariate Fuss-Narayana polynomials}. Using this result, we compute the moments of $\varrho_{t_1}\boxtimes \varrho_{t_2}\boxtimes\ldots \boxtimes \varrho_{t_m}$ for any positive $t_1,t_2, \ldots , t_m$, where $\boxtimes$ is the free multiplicative convolution in free probability and $\varrho_{t}$ is the Marchenko-Pastur distribution with shape parameter $t$.
Two Layer 3D Floor Planning
Authors: Horn Paul , Lippner Gabor
Published: January 2020

A 3D floorplan is a non-overlapping arrangement of blocks within a large box. Floor planning is a central notion in chip-design, and with recent advances in 3D integrated circuits, understanding 3D floorplans has become important. In this paper, we study so called mosaic 3D floorplans where the interior blocks partition the host box under a topological equivalence. We give representations which give an upper bound on the number of general 3D floorplans, and further consider the number of two layer mosaic floorplans. We prove that the number of two layer mosaic floorplans is $n^{(1+o(1))n/3}$. This contrasts with previous work which has studied 'corner free' mosaic floorplans, where the number is just exponential. The upper bound is by giving a representation, while the lower bound is a randomized construction.
Matroid and Tutte-Connectivity in Infinite Graphs
Authors: Bruhn Henning
Published: January 2020

We relate matroid connectivity to Tutte-connectivity in an infinite graph. Moreover, we show that the two cycle matroids, the finite-cycle matroid and the cycle matroid, in which also infinite cycles are taken into account, have the same connectivity function. As an application we re-prove that, also for infinite graphs, Tutte-connectivity is invariant under taking dual graphs.
Extremal Graphs for Blow-Ups of Cycles and Trees
Authors: Liu Hong
Published: January 2020

The blow-up of a graph H is the graph obtained from replacing each edge in H by a clique of the same size where the new vertices of the cliques are all different. Erdős et al. and Chen et al. determined the extremal number of blow-ups of stars. Glebov determined the extremal number and found all extremal graphs for blow-ups of paths. We determined the extremal number and found the extremal graphs for the blow-ups of cycles and a large class of trees, when n is sufficiently large. This generalizes their results. The additional aim of our note is to draw attention to a powerful tool, a classical decomposition theorem of Simonovits.
Permutations with Ascending and Descending Blocks
Authors: Steinhardt Jacob
Published: January 2020

We investigate permutations in terms of their cycle structure and descent set. To do this, we generalize the classical bijection of Gessel and Reutenauer to deal with permutations that have some ascending and some descending blocks. We then provide the first bijective proofs of some known results. We also extend the work of Eriksen, Freij, and Wästlund, who study derangements that descend in blocks of prescribed lengths. In particular, we solve some problems they posed and also obtain a new combinatorial sum for counting derangements with ascending and descending blocks.
Irreducible Cycles and Points in Special Position in Moduli Spaces for Tropical Curves
Authors: Gathmann Andreas , Schroeter Franziska
Published: January 2020

In the first part of this paper, we discuss the notion of irreducibility of cycles in the moduli spaces of $n$-marked rational tropical curves. We prove that Psi-classes and vital divisors are irreducible, and that locally irreducible divisors are also globally irreducible for $ n \le 6 $. In the second part of the paper, we show that the locus of point configurations in $({\mathbb R}^2)^n $ in special position for counting rational plane curves (defined in two different ways) can be given the structure a tropical cycle of codimension $1$. In addition, we compute explicitly the weights of this cycle.
The Tau Constant and the Edge Connectivity of a Metrized Graph
Authors: Cinkir Zubeyir
Published: January 2020

The tau constant is an important invariant of a metrized graph. It has connections to other graph invariants such as Kirchhoff index, and it has applications to arithmetic properties of algebraic curves. We show how the tau constant of a metrized graph changes under successive edge contractions and deletions. We prove identities which we call "contraction", "deletion", and "contraction-deletion" identities on a metrized graph. By establishing a lower bound for the tau constant in terms of the edge connectivity, we prove that Baker and Rumely's lower bound conjecture on the tau constant holds for metrized graphs with edge connectivity 5 or more. We show that proving this conjecture for 3-regular graphs is enough to prove it for all graphs.
Coloring the Cube with Rainbow Cycles
Authors: Mubayi Dhruv , Stading Randall
Published: January 2020

For every even positive integer $k\ge 4$ let $f(n,k)$ denote the minimim number of colors required to color the edges of the $n$-dimensional cube $Q_n$, so that the edges of every copy of the $k$-cycle $C_k$ receive $k$ distinct colors. Faudree, Gyárfás, Lesniak and Schelp proved that $f(n,4)=n$ for $n=4$ or $n>5$. We consider larger $k$ and prove that if $k \equiv 0$ (mod 4), then there are positive constants $c_1, c_2$ depending only on $k$ such that$$c_1n^{k/4} < f(n,k) < c_2 n^{k/4}.$$Our upper bound uses an old construction of Bose and Chowla of generalized Sidon sets. For $k \equiv 2$ (mod 4), the situation seems more complicated. For the smallest case $k=6$ we show that $$3n-2 \le f(n, 6) < n^{1+o(1)}$$ with the lower bound holding for $n \ge 3$. The upper bound is obtained from Behrend's construction of a subset of integers with no three term arithmetic progression.
A Combinatorial Proof of an Identity from Ramanujan's Lost Notebook
Authors: Lin Lishuang , Liu Jian , Wang Yezhou
Published: January 2020

In this note, we present a new combinatorial proof of an identity originally stated in Ramanujan's lost notebook by keeping track of an extra statistic in Yee's bijection for a special case of this identity.
The Combinatorics of Interval Vector Polytopes
Authors: Beck Matthias , De Silva Jessica , Dorfsman-Hopkins Gabriel , Pruitt Joseph , Ruiz Amanda
Published: January 2020

An interval vector is a $(0,1)$-vector in $\mathbb{R}^n$ for which all the $1$'s appear consecutively, and an interval vector polytope is the convex hull of a set of interval vectors in $\mathbb{R}^n$. We study three particular classes of interval vector polytopes which exhibit interesting geometric-combinatorial structures; e.g., one class has volumes equal to the Catalan numbers, whereas another class has face numbers given by the Pascal 3-triangle.
Near Packings of Graphs
Authors: Zak Andrzej
Published: January 2020

A packing of a graph $G$ is a set $\{G_1,G_2\}$ such that $G_1\cong G$, $G_2\cong G$, and $G_1$ and $G_2$ are edge disjoint subgraphs of $K_n$. Let $\mathcal{F}$ be a family of graphs. A near packing admitting $\mathcal{F}$ of a graph $G$ is a generalization of a packing. In a near packing admitting $\mathcal{F}$, the two copies of $G$ may overlap so the subgraph defined by the edges common to both copies is a member of $\mathcal{F}$. In the paper we study three families of graphs (1) $\mathcal{E}_k$ -- the family of all graphs  with at most $k$ edges, (2) $\mathcal{D}_k$ -- the family of all graphs with maximum degree at most $k$, and (3) $\mathcal{C}_k$ -- the family of all graphs that do not contain a subgraph of connectivity greater than or equal to $k+1$. By $m(n,\mathcal{F})$ we denote the maximum number $m$ such that each graph of order $n$ and size less than or equal to $m$ has a near-packing admitting $\mathcal{F}$. It is well known that $m(n,\mathcal{C}_0)=m(n,\mathcal{D}_0)=m(n,\mathcal{E}_0)=n-2$ because a near packing admitting $\mathcal{C}_0$, $\mathcal{D}_0$ or $\mathcal{E}_0$ is just a packing. We prove some generalization of this result, namely we prove that $ m(n,\mathcal{C}_k)\approx (k+1)n$, $ m(n,\mathcal{D}_1)\approx \frac{3}{2}n$, $ m(n,\mathcal{D}_2)\approx 2n$. We also present bounds on $m(n,\mathcal{E}_k)$. Finally, we prove that each graph of girth at least five has a near packing admitting $\mathcal{C}_1$ (i.e. a near packing admitting the family of the acyclic graphs).
A Simple Proof of an Identity of Lacasse
Authors: Sun Yidong
Published: January 2020

In this note, using the derangement polynomials and their umbral representation, we give another simple proof of an identity conjectured by Lacasse in the study of the PAC-Bayesian machine learning theory.
Cross-Intersecting Families of Labeled Sets
Authors: Zhang Huajun
Published: January 2020

For two positive integers $n$ and $p$, let $\mathcal{L}_{p}$ be the family of labeled $n$-sets given by $$\mathcal{L}_{p}=\big\{\{(1,\ell_1),(2,\ell_2),\ldots,(n,\ell_n)\}: \ell_i\in[p], i=1,2\ldots,n\big\}.$$ Families $\mathcal{A}$ and $\mathcal{B}$ are said to be cross-intersecting if $A\cap B\neq\emptyset$ for all $A\in \mathcal{A}$ and $B\in\mathcal{B}$. In this paper, we will prove that for $p\geq 4$,  if $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting subfamilies of $\mathcal{L}_{\mathfrak{p}}$, then $|\mathcal{A}||\mathcal{B}|\leq p^{2n-2}$, and equality holds if and only if $\mathcal{A}$ and $\mathcal{B}$ are an identical largest intersecting subfamily of $\mathcal{L}_{p}$.
Generating and Enumerating 321-Avoiding and Skew-Merged Simple Permutations
Authors: Albert Michael H. , Vatter Vincent
Published: January 2020

The simple permutations in two permutation classes --- the $321$-avoiding permutations and the skew-merged permutations --- are enumerated using a uniform method. In both cases, these enumerations were known implicitly, by working backwards from the enumeration of the class, but the simple permutations had not been enumerated explicitly. In particular, the enumeration of the simple skew-merged permutations leads to the first truly structural enumeration of this class as a whole. The extension of this method to a wider collection of classes namely grid classes of infinite paths is discussed.
Endomorphism Breaking in Graphs
Authors: Imrich Wilfried , Kalinowski Rafał , Lehner Florian , Pilśniak Monika
Published: January 2020

We introduce the endomorphism distinguishing number $D_e(G)$ of a graph $G$ as the least cardinal $d$ such that $G$ has a vertex coloring with $d$ colors that is only preserved by the trivial endomorphism. This generalizes the notion of the distinguishing number $D(G)$ of a graph $G$, which is defined for automorphisms instead of endomorphisms.As the number of endomorphisms can vastly exceed the number of automorphisms, the new concept opens challenging problems, several of which are presented here. In particular, we investigate relationships between $D_e(G)$ and the endomorphism motion of a graph $G$, that is, the least possible number of vertices moved by a nontrivial endomorphism of $G$. Moreover, we extend numerous results about the distinguishing number of finite and infinite graphs to the endomorphism distinguishing number.
Enumeration of Perfect Matchings of a Type of Quadratic Lattice on the Torus
Authors: Lu Fuliang , Zhang Lianzhu , Lin Fenggen
Published: January 2020

A quadrilateral cylinder of length $m$ and breadth $n$ is the Cartesian product of a $m$-cycle(with $m$ vertices) and a $n$-path(with $n$ vertices). Write the vertices of the two cycles on the boundary of the quadrilateral cylinder as $x_1,x_2,\cdots,x_m$ and $y_1,y_2,\cdots ,y_m$, respectively, where $x_i$ corresponds to $y_i(i=1,2,\dots, m)$. We denote by $Q_{m,n,r}$, the graph obtained from quadrilateral cylinder of length $m$ and breadth $n$ by adding edges $x_iy_{i+r}$ ($r$ is a integer, $0\leq r < m$ and $i+r$ is modulo $m$). Kasteleyn had derived explicit expressions of the number of perfect matchings for $Q_{m,n,0}$ [P.W. Kasteleyn, The statistics of dimers on a lattice I: The number of dimer arrangements on a quadratic lattice, Physica 27(1961), 1209–1225]. In this paper, we generalize the result of Kasteleyn, and obtain expressions of the number of perfect matchings for $Q_{m,n,r}$ by enumerating Pfaffians.
Minimal Covers of the Archimedean Tilings, Part II
Authors: Mixer Mark , Pellicer Daniel , Williams Gordon
Published: January 2020

In Part I of this paper the minimal regular covers of three Archimedean tilings were determined. However, the computations described in that work grow more complicated as the number of flag orbits of the tilings increases. In Part II, we develop a new technique in order to present the minimal regular covers of certain periodic abstract polytopes. We then use that technique to finish determining the minimal regular covers of the Archimedean tilings.
Separability of Density Matrices of Graphs for Multipartite Systems
Authors: Xie Chen , Zhao Hui , Wang Zhixi
Published: January 2020

We investigate separability of Laplacian matrices of graphs when seen as density matrices. This is a family of quantum states with many combinatorial properties. We firstly show that the well-known matrix realignment criterion can be used to test separability of this type of quantum states. The criterion can be interpreted as novel graph-theoretic idea. Then, we prove that the density matrix of the tensor product of N graphs is N-separable. However, the converse is not necessarily true. Additionally, we derive a sufficient condition for N-partite entanglement in star graphs and propose a necessary and sufficient condition for separability of nearest point graphs.
Greedy Trees, Subtrees and Antichains
Authors: Andriantiana Eric Ould Dadah , Wagner Stephan , Wang Hua
Published: January 2020

Greedy trees are constructed from a given degree sequence by a simple greedy algorithm that assigns the highest degree to the root, the second-, third-, ... highest degrees to the root's neighbors, and so on. They have been shown to maximize or minimize a number of different graph invariants among trees with a given degree sequence. In particular, the total number of subtrees of a tree is maximized by the greedy tree. In this work, we show that in fact a much stronger statement holds true: greedy trees maximize the number of subtrees of any given order. This parallels recent results on distance-based graph invariants. We obtain a number of corollaries from this fact and also prove analogous results for related invariants, most notably the number of antichains of given cardinality in a rooted tree.
$H$-Decompositions of $r$-graphs when $H$ is an $r$-graph with exactly 2 edges
Authors: Sousa Teresa
Published: January 2020

Given two $r$-graphs $G$ and $H$, an $H$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edge or forms a graph isomorphic to $H$. The minimum number of parts in an $H$-decomposition of $G$ is denoted by $\phi_H^r (G)$. By a $2$-edge-decomposition of an $r$-graph we mean an $H$-decomposition for any fixed $r$-graph $H$ with exactly 2 edges. In the special case where the two edges of $H$ intersect in exactly $1,2$ or $r-1$ vertices these 2-edge-decompositions will be called bowtie, domino and kite respectively. The value of the function $\phi_H^r(n)$ will be obtained for bowtie, domino and kite decompositons of $r$-graphs.
Cores of Vertex Transitive Graphs
Authors: Roberson David E.
Published: January 2020

A core of a graph X is a vertex minimal subgraph to which X admits a homomorphism. Hahn and Tardif have shown that for vertex transitive graphs, the size of the core must divide the size of the graph. This motivates the following question: when can the vertex set of a vertex transitive graph be partitioned into sets each of which induce a copy of its core? We show that normal Cayley graphs and vertex transitive graphs with cores half their size always admit such partitions. We also show that the vertex sets of vertex transitive graphs with cores less than half their size do not, in general, have such partitions.
Ramsey Properties of Countably Infinite Partial Orderings
Authors: Groszek Marcia J.
Published: January 2020

A partial ordering $\mathbb P$ is chain-Ramsey if, for every natural number $n$ and every coloring of the $n$-element chains from $\mathbb P$ in finitely many colors, there is a monochromatic subordering $\mathbb Q$ isomorphic to $\mathbb P$.  Chain-Ramsey partial orderings stratify naturally into levels.  We show that a countably infinite partial ordering with finite levels is chain-Ramsey if and only if it is biembeddable with one of a canonical collection of examples constructed from certain edge-Ramsey families of finite bipartite graphs.  A similar analysis applies to a large class of countably infinite partial orderings with infinite levels.
Value-Peaks of Permutations
Authors: Bouchard Pierre , Chang Hungyung , Ma Jun , Yeh Jean , Yeh Yeong-Nan
Published: January 2020

In this paper, we focus on a "local property" of permutations: value-peak. A permutation $\sigma$ has a value-peak $\sigma(i)$ if $\sigma(i-1) < \sigma(i)>\sigma(i+1)$ for some $i\in[2,n-1]$. Define $VP(\sigma)$ as the set of value-peaks of the permutation $\sigma$. For any $S\subseteq [3,n]$, define $VP_n(S)$ such that $VP(\sigma)=S$. Let ${\cal P}_n=\{S\mid VP_n(S)\neq\emptyset\}$. we make the set ${\cal P}_n$ into a poset $\mathfrak{ P}$$_n$ by defining $S\preceq T$ if $S\subseteq T$ as sets. We prove that the poset $\mathfrak{ P}$$_n$ is a simplicial complex on the set $[3,n]$ and study some of its properties. We give enumerative formulae of permutations in the set $VP_n(S)$.
New Aspects of Regions whose Tilings are Enumerated by Perfect Powers
Authors: Lai Tri
Published: January 2020

In 2003, Ciucu presented a unified way to enumerate tilings of lattice regions by using a certain Reduction Theorem (J. Algebraic Combin., 2003). In this paper we continue this line of work by investigating new families of lattice regions whose tilings are enumerated by perfect powers or products of several perfect powers. We prove a multi-parameter generalization of Bo-Yin Yang's theorem on fortresses (Ph.D. thesis, MIT, 1991).  On the square lattice with zigzag paths, we consider two particular families of regions whose numbers of tilings are always a power of 3 or twice a power of 3. The latter result provides a new proof for a conjecture of Matt Blum first proved by Ciucu. We also consider several new lattices obtained by periodically applying two simple subgraph replacement rules to the square lattice. On some of those lattices, we get new families of regions whose numbers of tilings  are given by products of several perfect powers. In addition, we prove a simple product formula for the number of tilings of a certain family of regions on a variant of the triangular lattice.
Long Paths and Cycles in Random Subgraphs of $\mathcal{H}$-Free Graphs
Authors: Krivelevich Michael , Samotij Wojciech
Published: January 2020

Let $\mathcal{H}$ be a given finite (possibly empty) family of connected graphs, each containing a cycle, and let $G$ be an arbitrary finite $\mathcal{H}$-free graph with minimum degree at least $k$. For $p \in [0,1]$, we form a $p$-random subgraph $G_p$ of $G$ by independently keeping each edge of $G$ with probability $p$. Extending a classical result of Ajtai, Komlós, and Szemerédi, we prove that for every positive $\varepsilon$, there exists a positive $\delta$ (depending only on $\varepsilon$) such that the following holds: If $p \geq \frac{1+\varepsilon}{k}$, then with probability tending to $1$ as $k \to \infty$, the random graph $G_p$ contains a cycle of length at least $n_{\mathcal{H}}(\delta k)$, where $n_\mathcal{H}(k)>k$ is the minimum number of vertices in an $\mathcal{H}$-free graph of average degree at least $k$. Thus in particular $G_p$ as above typically contains a cycle of length at least linear in $k$.
Consecutive Up-Down Patterns in Up-Down Permutations
Authors: Remmel Jeffrey B.
Published: January 2020

In this paper, we study the distribution of the number of consecutive pattern matches of the five up-down permutations of length four, $1324$, $2314$, $2413$, $1432$, and $3412$, in the set of up-down permutations. We show that for any such $\tau$, the generating function for the distribution of the number of consecutive pattern matches of $\tau$ in the set of up-down permutations can be expressed in terms of what we call the generalized maximum packing polynomials of $\tau$. We then provide some systematic methods to compute the generalized maximum packing polynomials for such $\tau$.
Ehrhart Clutters: Regularity and Max-Flow Min-Cut
Authors: Martínez-Bernal José , O'Shea Edwin , Villarreal Rafael H.
Published: January 2020

If $\mathcal{C}$ is a clutter with $n$ vertices and $q$ edges whose clutter matrix has column vectors ${\mathcal A} = \{v_1, \ldots, v_q\}$, we call $\mathcal{C}$ an Ehrhart clutter if $\{(v_1,1),\ldots,(v_q,1)\} \subset \{ 0,1 \}^{n+1}$ is a Hilbert basis. Letting $A(P)$ be the Ehrhart ring of $P={\rm conv}(\mathcal{A})$, we are able to show that if $\mathcal{C}$ is a uniform unmixed MFMC clutter, then $\mathcal{C}$ is an Ehrhart clutter and in this case we provide sharp upper bounds on the Castelnuovo-Mumford regularity and the $a$-invariant of $A(P)$. Motivated by the Conforti-Cornuéjols conjecture on packing problems, we conjecture that if $\mathcal{C}$ is both ideal and the clique clutter of a perfect graph, then $\mathcal{C}$ has the MFMC property. We prove this conjecture for Meyniel graphs by showing that the clique clutters of Meyniel graphs are Ehrhart clutters. In much the same spirit, we provide a simple proof of our conjecture when $\mathcal{C}$ is a uniform clique clutter of a perfect graph. We close with a generalization of Ehrhart clutters as it relates to total dual integrality.
A New Statistic on the Hyperoctahedral Groups
Authors: Stasinski Alexander , Voll Christopher
Published: January 2020

We introduce a new statistic on the hyperoctahedral groups (Coxeter groups of type B), and give a conjectural formula for its signed distributions over arbitrary descent classes.  The statistic is analogous to the classical Coxeter length function, and features a parity condition. For descent classes which are singletons the conjectured formula gives the Poincaré polynomials of the varieties of symmetric matrices of fixed rank.For several descent classes we prove the conjectural formula. For this we construct suitable supporting sets for the relevant generating functions. We prove cancellations on the complements of these supporting sets using suitably defined sign reversinginvolutions.
Orthogonal Vector Coloring
Authors: Haynes Gerald , Park Catherine , Schaeffer Amanda , Webster Jordan , Mitchell Lon H.
Published: January 2020

A vector coloring of a graph is an assignment of a vector to each vertex where the presence or absence of an edge between two vertices dictates the value of the inner product of the corresponding vectors. In this paper, we obtain results on orthogonal vector coloring, where adjacent vertices must be assigned orthogonal vectors. We introduce two vector analogues of list coloring along with their chromatic numbers and characterize all graphs that have (vector) chromatic number two in each case.
Packing Tree Factors in Random and Pseudo-Random Graphs
Authors: Bal Deepak , Frieze Alan , Krivelevich Michael , Loh Po-Shen
Published: January 2020

For a fixed graph $H$ with $t$ vertices, an $H$-factor of a graph $G$ with $n$ vertices, where $t$ divides $n$, is a collection of vertex disjoint (not necessarily induced) copies of $H$ in $G$ covering all vertices of $G$. We prove that for a fixed tree $T$ on $t$ vertices and $\epsilon>0$, the random graph $G_{n,p}$, with $n$ a multiple of $t$, with high probability contains a family of edge-disjoint $T$-factors covering all but an $\epsilon$-fraction of its edges, as long as $\epsilon^4 n p \gg \log^2 n$. Assuming stronger divisibility conditions, the edge probability can be taken down to $p>\frac{C\log n}{n}$. A similar packing result is proved also for pseudo-random graphs, defined in terms of their degrees and co-degrees.
An Identity Conjectured by Lacasse via the Tree Function
Authors: Prodinger Helmut
Published: January 2020

A. Lacasse conjectured a combinatorial identity in his study of learning theory. Various people found independent proofs. Here is another one that is based on the study of the tree function, with links to Lamberts $W$-function and Ramanujan's $Q$-function. It is particularly short.
The $t$-Stability Number of a Random Graph
Authors: Fountoulakis Nikolaos , Kang Ross J. , McDiarmid Colin
Published: January 2020

Given a graph $G = (V,E)$, a vertex subset $S \subseteq V$ is called $t$-stable (or $t$-dependent) if the subgraph $G[S]$ induced on $S$ has maximum degree at most $t$. The $t$-stability number $\alpha_t(G)$ of $G$ is the maximum order of a $t$-stable set in $G$. The theme of this paper is the typical values that this parameter takes on a random graph on $n$ vertices and edge probability equal to $p$. For any fixed $0 < p < 1$ and fixed non-negative integer $t$, we show that, with probability tending to $1$ as $n\to\infty$, the $t$-stability number takes on at most two values which we identify as functions of $t$, $p$ and $n$. The main tool we use is an asymptotic expression for the expected number of $t$-stable sets of order $k$. We derive this expression by performing a precise count of the number of graphs on $k$ vertices that have maximum degree at most $t$.
On Cross-Intersecting Uniform Sub-Families of Hereditary Families
Authors: Borg Peter
Published: January 2020

A family $\mathcal{H}$ of sets is hereditary if any subset of any set in $\mathcal{H}$ is in $\mathcal{H}$. If two families $\mathcal{A}$ and $\mathcal{B}$ are such that any set in $\mathcal{A}$ intersects any set in $\mathcal{B}$, then we say that $(\mathcal{A}, \mathcal{B})$ is a cross-intersection pair (cip). We say that a cip $(\mathcal{A}, \mathcal{B})$ is simple if at least one of $\mathcal{A}$ and $\mathcal{B}$ contains only one set. For a family $\mathcal{F}$, let $\mu(\mathcal{F})$ denote the size of a smallest set in $\mathcal{F}$ that is not a subset of any other set in $\mathcal{F}$. For any positive integer $r$, let $[r] := \{1, 2, ..., r\}$, $2^{[r]} := \{A \colon A \subseteq [r]\}$, $\mathcal{F}^{(r)} := \{F \in \mathcal{F} \colon |F| = r\}$. We show that if a hereditary family $\mathcal{H} \subseteq 2^{[n]}$ is compressed, $\mu(\mathcal{H}) \geq r+s$ with $r \leq s$, and $(\mathcal{A}, \mathcal{B})$ is a cip with $\emptyset \neq \mathcal{A} \subset \mathcal{H}^{(r)}$ and $\emptyset \neq \mathcal{B} \subset \mathcal{H}^{(s)}$, then $|\mathcal{A}| + |\mathcal{B}|$ is a maximum if $(\mathcal{A}, \mathcal{B})$ is the simple cip $\left( \{[r]\}, \{B \in \mathcal{H}^{(s)} \colon B \cap [r] \neq \emptyset\} \right)$; Frankl and Tokushige proved this for $\mathcal{H} = 2^{[n]}$. We also show that for any $2 \leq r \leq s$ and $m \geq r + s$ there exist (non-compressed) hereditary families $\mathcal{H}$ with $\mu(\mathcal{H}) = m$ such that no cip $(\mathcal{A}, \mathcal{B})$ with a maximum value of $|\mathcal{A}| + |\mathcal{B}|$ under the condition that $\emptyset \neq \mathcal{A} \subset \mathcal{H}^{(r)}$ and $\emptyset \neq \mathcal{B} \subset \mathcal{H}^{(s)}$ is simple (we prove that this is not the case for $r=1$), and we suggest two conjectures about the extremal structures in general.
A Note on the Acquaintance Time of Random Graphs
Authors: Kinnersley William B. , Mitsche Dieter , Prałat Paweł
Published: January 2020

In this short note, we prove the conjecture of Benjamini, Shinkar, and Tsur on the acquaintance time $\mathcal{AC}(G)$ of a random graph $G \in G(n,p)$. It is shown that asymptotically almost surely $\mathcal{AC}(G) = O(\log n / p)$ for $G \in G(n,p)$, provided that $pn > (1+\epsilon) \log n$ for some $\epsilon > 0$ (slightly above the threshold for connectivity). Moreover, we show a matching lower bound for dense random graphs, which also implies that asymptotically almost surely $K_n$ cannot be covered with $o(\log n / p)$ copies of a random graph $G \in G(n,p)$, provided that $pn > n^{1/2+\epsilon}$ and $p < 1-\epsilon$ for some $\epsilon>0$. We conclude the paper with a small improvement on the general upper bound showing that for any $n$-vertex graph $G$, we have $\mathcal{AC}(G) = O(n^2/\log n )$.
Remarks on a Conjecture of Barát and Tóth
Authors: Luiz Atílio G. , Richter R. Bruce
Published: January 2020

In 2010,  Barát and Tóth verified that any $r$-critical graph with at most $r+4$ vertices has a subdivision of $K_r$. Based in this result, the authors conjectured that, for every positive integer $c$, there exists a bound $r(c)$ such that for any $r$, where $r \geq r(c)$, any $r$-critical graph on $r+c$ vertices has a subdivision of $K_r$. In this note, we verify the validity of this conjecture for $c=5$, and show counterexamples for all $c \geq 6$.
Distinguishing Maps II: General Case
Authors: Tucker Thomas W.
Published: January 2020

A group $A$ acting faithfully on a set $X$ has  distinguishing number $k$, written $D(A,X)=k$, if there is a coloring of the elements of $X$ with $k$ colors such that no nonidentity element of $A$ is color-preserving, and no such coloring with fewer than $k$ colors exists.  Given a map $M$ with vertex set $V$ and automorphism group $Aut(M)$, let $D(M)=D(Aut(M),V)$. If $M$ is orientable, let $D^+(M)=D(Aut^+(M),V)$, where $Aut^+(M)$ is the group of orientation-preserving automorphisms.   In a previous paper, the author showed there are four maps $M$ with $D^+(M)>2$.  In this paper,  a complete classification is given for the graphs underlying maps with $D(M)>2$. There are $31$ such graphs, $22$ having no vertices of valence $1$ or $2$, and all have at most $10$ vertices.
New Results on Degree Sequences of Uniform Hypergraphs
Authors: Behrens Sarah , Erbes Catherine , Ferrara Michael , Hartke Stephen G. , Reiniger Benjamin , Spinoza Hannah , Tomlinson Charles
Published: January 2020

A sequence of nonnegative integers is $k$-graphic if it is the degree sequence of a $k$-uniform hypergraph. The only known characterization of $k$-graphic sequences is due to Dewdney in 1975. As this characterization does not yield an efficient algorithm, it is a fundamental open question to determine a more practical characterization. While several necessary conditions appear in the literature, there are few conditions that imply a sequence is $k$-graphic. In light of this, we present sharp sufficient conditions for $k$-graphicality based on a sequence's length and degree sum.Kocay and Li gave a family of edge exchanges (an extension of 2-switches) that could be used to transform one realization of a 3-graphic sequence into any other realization. We extend their result to $k$-graphic sequences for all $k \geq 3$. Finally we give several applications of edge exchanges in hypergraphs, including generalizing a result of Busch et al. on packing graphic sequences.
A Simple Proof for the Number of Tilings of Quartered Aztec Diamonds
Authors: Lai Tri
Published: January 2020

We get four quartered Aztec diamonds by dividing an Aztec diamond region by two zigzag cuts passing its center. W. Jockusch and J. Propp (in an unpublished work) found that the number of tilings of quartered Aztec diamonds is given by simple product formulas. In this paper we present a simple proof for this result.
Tree-like Tableaux
Authors: Aval Jean-Christophe , Boussicault Adrien , Nadeau Philippe
Published: January 2020

In this work we introduce and study tree-like tableaux, which are certain fillings of Ferrers diagrams in simple bijection with permutation tableaux and alternative tableaux. We exhibit an elementary insertion procedure on our tableaux which gives a clear proof that tree-like tableaux of size $n$ are counted by $n!$ and which moreover respects most of the well-known statistics studied originally on alternative and permutation tableaux. Our insertion procedure allows to define in particular two simple new bijections between tree-like tableaux and permutations: the first one is conceived specifically to respect the generalized pattern 2-31, while the second one respects the underlying tree of a tree-like tableau.
Tiling a Strip with Triangles
Authors: Bodeen John , Butler Steve , Kim Taekyoung , Sun Xiyuan , Wang Shenzhi
Published: January 2020

In this paper, we examine the tilings of a $2\times n$ "triangular strip" with triangles. These tilings have connections with Fibonacci numbers, Pell numbers, and other known sequences. We derive several different recurrences, establish some properties of these numbers, and give a refined count for these tilings (i.e., by the number and type of triangles used) and establish several properties of these refined counts.
Largest Minimal Percolating Sets in Hypercubes under $2$-Bootstrap Percolation
Authors: Riedl Eric
Published: January 2020

Consider the following process, known as $r$-bootstrap percolation, on a graph $G$. Designate some initial infected set $A$ and infect any vertex with at least $r$ infected neighbors, continuing until no new vertices can be infected. We say $A$ percolates if it eventually infects the entire graph. We say $A$ is a minimal percolating set if $A$ percolates, but no proper subset percolates. We compute the size of a largest minimal percolating set for $r=2$ in the $n$-dimensional hypercube.
Bell Numbers Modulo a Prime Number, Traces and Trinomials
Authors: Gallardo Luis H. , Rahavandrainy Olivier
Published: January 2020

Given a prime number $p$, we deduce from a formula of Barsky and Benzaghou and from a result of Coulter and Henderson on trinomials over finite fields, a simple necessary and sufficient condition $\beta(n) =k\beta(0)$ in $\mathbb{F}_{p^p}$ in order to resolve the congruence $B(n) \equiv k \pmod{p}$, where $B(n)$ is the $n$-th Bell number, and $k$ is any fixed integer. Several applications of the formula and of the condition are included, in particular we give equivalent forms of the conjecture of Kurepa that $B(p-1)$ is $\neq 1$ modulo $p$.
Constant Rank-Distance Sets of Hermitian Matrices and Partial Spreads in Hermitian Polar Spaces
Authors: Gow Rod , Lavrauw Michel , Sheekey John , Vanhove Frédéric
Published: January 2020

In this paper we investigate partial spreads of $H(2n-1,q^2)$ through the related notion of partial spread sets of hermitian matrices, and the more general notion of constant rank-distance sets. We prove a tight upper bound on the maximum size of a linear constant rank-distance set of hermitian matrices over finite fields, and as a consequence prove the maximality of extensions of symplectic semifield spreads as partial spreads of $H(2n-1,q^2)$. We prove upper bounds for constant rank-distance sets for even rank, construct large examples of these, and construct maximal partial spreads of $H(3,q^2)$ for a range of sizes.
Graphical Condensation, Overlapping Pfaffians and Superpositions of Matchings
Authors: Fulmek Markus
Published: January 2020

The purpose of this paper is to exhibit clearly how the "graphical condensation" identities of Kuo, Yan, Yeh and Zhang follow from classical Pfaffian identities by the Kasteleyn–Percus method for the enumeration of matchings. Knuth termed the relevant identities "overlapping Pfaffian" identities and the key concept of proof "superpositions of matchings". In our uniform presentation of the material, we also give an apparently unpublished general "overlapping Pfaffian" identity of Krattenthaler.
The Goldman-Rota Identity and the Grassmann Scheme
Authors: Srinivasan Murali K.
Published: January 2020

We inductively construct an explicit (common) orthogonal eigenbasis for the elements of the Bose-Mesner algebra of the Grassmann scheme.The key step is a constructive, linear algebraic interpretation of the Goldman-Rota recurrence for the number of subspaces of a finite vector space. This interpretation shows that the up operator on subspaces has an explicitly given recursive structure. Using the interpretation above we inductively construct an explicit orthogonal symmetric Jordan basis with respect to the up operator and write down the singular values, i.e., the ratio of the lengths of the successive vectors in the Jordan chains. The collection of all vectors in this basis of a fixed rank $m$ forms a (common) orthogonal eigenbasis for the elements of the Bose-Mesner algebra of the Grassmann scheme of $m$-dimensional subspaces. We also pose a bijective proof problem on the spanning trees of the Grassmann graphs.