bluuebunny/crossref_metadata_2025 huggingface dataset:
On The Binomial Edge Ideal of a Pair of Graphs
Authors: Saeedi Madani Sara , Kiani Dariush
Published: January 2020

We characterize all pairs of graphs $(G_1,G_2)$, for which the binomial edge ideal $J_{G_1,G_2}$ has linear relations. We show that $J_{G_1,G_2}$ has a linear resolution if and only if $G_1$ and $G_2$ are complete and one of them is just an edge. We also compute some of the graded Betti numbers of the binomial edge ideal of a pair of graphs with respect to some graphical terms. In particular, we show that for every pair of graphs $(G_1,G_2)$ with girth (i.e. the length of a shortest cycle in the graph) greater than 3, $\beta_{i,i+2}(J_{G_1,G_2})=0$, for all $i$. Moreover, we give a lower bound for the Castelnuovo-Mumford regularity of any binomial edge ideal $J_{G_1,G_2}$ and hence the ideal of adjacent $2$-minors of a generic matrix. We also obtain an upper bound for the regularity of $J_{G_1,G_2}$, if $G_1$ is complete and $G_2$ is a closed graph.
Hom Complexes of Set Systems
Authors: Jonsson Jakob
Published: January 2020

A set system is a pair $\mathcal{S} = (V(\mathcal{S}),\Delta(\mathcal{S}))$, where $\Delta(\mathcal{S})$ is a family of subsets of the set $V(\mathcal{S})$. We refer to the members of $\Delta(\mathcal{S})$ as the stable sets of $\mathcal{S}$. A homomorphism between two set systems $\mathcal{S}$ and $\mathcal{T}$ is a map $f : V(\mathcal{S}) \rightarrow V(\mathcal{T})$ such that the preimage under $f$ of every stable set of $\mathcal{T}$ is a stable set of $\mathcal{S}$. Inspired by a recent generalization due to Engström of Lovász's Hom complex construction, the author associates a cell complex $\mathrm{Hom}(\mathcal{S},\mathcal{T})$ to any two finite set systems $\mathcal{S}$ and $\mathcal{T}$. The main goal of the paper is to examine basic topological and homological properties of this cell complex for various pairs of set systems.
Crossings in Grid Drawings
Authors: Dujmović Vida , Morin Pat , Sheffer Adam
Published: January 2020

We prove tight crossing number inequalities for geometric graphs whose vertex sets are taken from a $d$-dimensional grid of volume $N$ and give applications of these inequalities to counting the number of crossing-free geometric graphs that can be drawn on such grids.In particular, we show that any geometric graph with $m\geq 8N$ edges and with vertices on a 3D integer grid of volume $N$, has $\Omega((m^2/N)\log(m/N))$ crossings. In $d$-dimensions, with $d\ge 4$, this bound becomes $\Omega(m^2/N)$. We provide matching upper bounds for all $d$. Finally, for $d\ge 4$ the upper bound implies that the maximum number of crossing-free geometric graphs with vertices on some $d$-dimensional grid of volume $N$ is $N^{\Theta(N)}$. In 3 dimensions it remains open to improve the trivial bounds, namely, the $2^{\Omega(N)}$ lower bound and the $N^{O(N)}$ upper bound.
A Bipartite Graph with Non-Unimodal Independent Set Sequence
Authors: Bhattacharyya Arnab , Kahn Jeff
Published: January 2020

We show that the independent set sequence of a bipartite graph need not be unimodal.
Factorisation of Snarks
Authors: Chladný Miroslav , Škoviera Martin
Published: January 2020

We develop a theory of factorisation of snarks — cubic graphs with edge-chromatic number $4$ — based on the classical concept of the dot product. Our main concern are irreducible snarks, those where the removal of every nontrivial edge-cut yields a $3$-edge-colourable graph. We show that if an irreducible snark can be expressed as a dot product of two smaller snarks, then both of them are irreducible. This result constitutes the first step towards the proof of the following "unique-factorisation" theorem: Every irreducible snark $G$ can be factorised into a collection $\{H_1,\dots,H_n\}$ of cyclically $5$-connected irreducible snarks such that $G$ can be reconstructed from them by iterated dot products. Moreover, such a collection is unique up to isomorphism and ordering of the factors regardless of the way in which the decomposition was performed. The result is best possible in the sense that it fails for snarks that are close to being irreducible but themselves are not irreducible. Besides this theorem, a number of other results are proved. For example, the unique-factorisation theorem is extended to the case of factorisation with respect to a preassigned subgraph $K$ which is required to stay intact during the whole factorisation process. We show that if $K$ has order at least $3$, then the theorem holds, but is false when $K$ has order $2$.
Diagrammatic Description of $c$-Vectors and $d$-Vectors of Cluster Algebras of Finite Type
Authors: Nakanishi Tomoki , Stella Salvatore
Published: January 2020

We provide an explicit Dynkin diagrammatic description of the $c$-vectors and the $d$-vectors (the denominator vectors) of any cluster algebra of finite type with principal coefficients and any initial exchange matrix. We use the surface realization of cluster algebras for types $A_n$ and $D_n$, then we apply the folding method to $D_{n+1}$ and $A_{2n-1}$ to obtain types $B_n$ and $C_n$. Exceptional types are done by direct inspection with the help of a computer algebra software. We also propose a conjecture on the root property of $c$-vectors for a general cluster algebra.
Spectral Characterizations of Dumbbell Graphs
Authors: Wang Jianfeng , Belardo Francesco , Huang Qiongxiang , Marzi Enzo M. Li
Published: January 2020

A dumbbell graph, denoted by $D_{a,b,c}$, is a bicyclic graph consisting of two vertex-disjoint cycles $C_a$, $C_b$ and a path $P_{c+3}$ ($c \geq -1$) joining them having only its end-vertices in common with the two cycles. In this paper, we study the spectral characterization w.r.t. the adjacency spectrum of $D_{a,b,0}$ (without cycles $C_4$) with $\gcd(a,b)\geq 3$, and we complete the research started in [J.F. Wang et al., A note on the spectral characterization of dumbbell graphs, Linear Algebra Appl. 431 (2009) 1707–1714]. In particular we show that $D_{a,b,0}$ with $3 \leq \gcd(a,b) < a$ or $\gcd(a,b)=a$ and $b\neq 3a$ is determined by the spectrum. For $b=3a$, we determine the unique graph cospectral with $D_{a,3a,0}$. Furthermore we give the spectral characterization w.r.t. the signless Laplacian spectrum of all dumbbell graphs.
The Cost of 2-Distinguishing Cartesian Powers
Authors: Boutin Debra
Published: January 2020

A graph $G$ is said to be $2$-distinguishable if there is a labeling of the vertices with two labels so that only the trivial automorphism preserves the label classes.  The minimum size of a label class in any such labeling of $G$ is called the cost of $2$-distinguishing $G$ and is denoted by $\rho(G)$.  The determining number of a graph $G$, denoted $\det(G)$, is the minimum size of a set of vertices whose pointwise stabilizer is trivial.  The main result of this paper is that if $G^k$ is a $2$-distinguishable Cartesian power of a prime, connected graph $G$ on at least three vertices with $\det(G)\leq k$ and $\max\{2, \det(G)\} < \det(G^k)$, then $\rho(G^k) \in \{\det(G^k), \det(G^k)+1\}$.  In particular, for $n\geq 3$, $\rho(K_3^n)\in \{ \left\lceil {\log_3 (2n+1)} \right\rceil$ $+1, \left\lceil {\log_3 (2n+1)} \right\rceil$ $+2\}$.
On Wilf Equivalence for Alternating Permutations
Authors: Yan Sherry H.F.
Published: January 2020

In this paper, we obtain several new classes of Wilf-equivalent patterns for alternating permutations. In particular, we prove that for any nonempty pattern $\tau$, the patterns $12\ldots k\oplus\tau$ and $k\ldots 21\oplus\tau$ are Wilf-equivalent for  alternating permutations, paralleling a result of Backelin, West, and Xin for Wilf equivalence for permutations.
Ascent-Descent Young Diagrams and Pattern Avoidance in Alternating Permutations
Authors: Jagadeesan Ravi
Published: January 2020

We investigate pattern avoidance in alternating permutations and an alternating analogue of Young diagrams. In particular, using an extension of Babson and West's notion of shape-Wilf equivalence described in our recent paper (with N. Gowravaram), we generalize results of Backelin, West, and Xin and Ouchterlony to alternating permutations. Unlike Ouchterlony and Bóna's bijections, our bijections are not the restrictions of Backelin, West, and Xin's bijections to alternating permutations. This paper is the second of a two-paper series presenting the work of Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux (with N. Gowravaram, arXiv:1301.6796v1). The first paper in the series is Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux (with N. Gowravaram, Electronic Journal of Combinatorics 20(4):#P17, 2013).
Sisterhood in the Gale-Shapley Matching Algorithm
Authors: Gonczarowski Yannai A. , Friedgut Ehud
Published: January 2020

Lying in order to manipulate the Gale-Shapley matching algorithm has been studied by Dubins and Freedman (1981) and by Gale and Sotomayor (1985), and was shown to be generally more appealing to the proposed-to side (denoted as the women in Gale and Shapley's seminal paper (1962)) than to the proposing side (denoted as men there). It can also be shown that in the case of lying women, for every woman who is better off due to lying, there exists a man who is worse off.In this paper, we show that an even stronger dichotomy between the goals of the sexes holds, namely, if no woman is worse off then no man is better off, while a form of sisterhood between the lying and the "innocent" women also holds, namely, if none of the former is worse off, then neither is any of the latter. These results are robust: they generalize to the one-to-many variants of the algorithm and do not require the resulting matching to be stable (i.e. they hold even in out-of-equilibria situations). The machinery we develop in our proofs sheds new light on the structure of lying by women in the Gale-Shapley matching algorithm.This paper is based upon an undergraduate thesis (2007) by the first author.
Eigenvalue Pairing in the Response Matrix for a Class of Network Models with Circular Symmetry
Authors: Farber Miriam , Johnson Charles R , Zhen Wei
Published: January 2020

We consider the response matrices in certain weighted networks that display a circular symmetry. It had been observed empirically that these exhibit several paired (multiplicity two) eigenvalues. Here, this pairing is explained analytically for a version of the model more general than the original. The exact number of necessarily paired eigenvalues is given in terms of the structure of the model, and the special structure of the eigenvectors is also described. Examples are provided.
Skew Spectra of Oriented Bipartite Graphs
Authors: Anuradha A. , Balakrishnan R. , Chen Xiaolin , Li Xueliang , Lian Huishu , So Wasin
Published: January 2020

A graph $G$ is said to have a parity-linked orientation $\phi$ if every even cycle $C_{2k}$ in $G^{\phi}$ is evenly (resp. oddly) oriented whenever $k$ is even (resp. odd). In this paper, this concept is used to provide an affirmative answer to the following conjecture of D. Cui and Y. Hou [D. Cui, Y. Hou, On the skew spectra of Cartesian products of graphs, Electronic J. Combin. 20(2):#P19, 2013]: Let $G=G(X,Y)$ be a bipartite graph. Call the $X\rightarrow Y$ orientation of $G,$ the canonical orientation. Let $\phi$ be any orientation of $G$ and let $Sp_S(G^{\phi})$ and $Sp(G)$ denote respectively the skew spectrum of $G^{\phi}$ and the spectrum of $G.$ Then $Sp_S(G^{\phi}) = {\bf{i}} Sp(G)$ if and only if $\phi$ is switching-equivalent to the canonical orientation of $G.$ Using this result, we determine the switch for a special family of oriented hypercubes $Q_d^{\phi},$ $d\geq 1.$ Moreover, we give an orientation of the Cartesian product of a bipartite graph and a graph, and then determine the skew spectrum of the resulting oriented product graph, which generalizes a result of Cui and Hou. Further this can be used to construct new families of oriented graphs with maximum skew energy.
Coupon Collector Problem for Non-Uniform Coupons and Random Quotas
Authors: Shank Nathan B. , Yang Hannah
Published: January 2020

We extend the classical coupon collector problem to find the expected number of selections needed to collect $m_i$ (possible random) copies of coupon $i$, when the distribution of the coupons is not necessarily equally likely.  Upper and lower bounds which provide limiting asymptotics are also obtained for the expected number of selections needed to fulfill a random quota for each coupon.
Capturing the Drunk Robber on a Graph
Authors: Komarov Natasha , Winkler Peter
Published: January 2020

We show that the expected time for a smart "cop"' to catch a drunk "robber" on an $n$-vertex graph is at most $n + {\rm o}(n)$. More precisely, let $G$ be a simple, connected, undirected graph with distinguished points $u$ and $v$ among its $n$ vertices. A cop begins at $u$ and a robber at $v$; they move alternately from vertex to adjacent vertex. The robber moves randomly, according to a simple random walk on $G$; the cop sees all and moves as she wishes, with the object of "capturing" the robber—that is, occupying the same vertex—in least expected time. We show that the cop succeeds in expected time no more than $n {+} {\rm o}(n)$. Since there are graphs in which capture time is at least $n {-} o(n)$, this is roughly best possible. We note also that no function of the diameter can be a bound on capture time.
A Characterization of the Hermitian Variety in Finite 3-Dimensional Projective Spaces
Authors: Napolitano Vito
Published: January 2020

A combinatorial characterization of a non-singular Hermitian variety of the finite 3-dimensional projective space via its intersection numbers with respect to lines and planes is given.

 

A corrigendum was added on March 29, 2019.
Some Extremal Problems for Hereditary Properties of Graphs
Authors: Nikiforov Vladimir
Published: January 2020

Given an infinite hereditary property of graphs $\mathcal{P}$, the principal extremal parameter of $\mathcal{P}$ is the value\[ \pi\left( \mathcal{P}\right) =\lim_{n\rightarrow\infty}\binom{n}{2}^{-1}\max\{e\left( G\right) :\text{ }G\in\mathcal{P}\text{ and }v\left(G\right) =n\}.\]The Erdős-Stone theorem gives $\pi\left( \mathcal{P}\right) $ if $\mathcal{P}$ is monotone, but this result does not apply to hereditary $\mathcal{P}$. Thus, one of the results of this note is to establish $\pi\left( \mathcal{P}\right) $ for any hereditary property $\mathcal{P}.$Similar questions are studied for the parameter $\lambda^{\left( p\right)}\left( G\right)$, defined for every real number $p\geq1$ and every graph $G$ of order $n$ as\[\lambda^{\left( p\right) }\left( G\right) =\max_{\left\vert x_{1}\right\vert^{p}\text{ }+\text{ }\cdots\text{ }+\text{ }\left\vert x_{n}\right\vert ^{p} \text{ }=\text{ }1}2\sum_{\{u,v\}\in E\left( G\right) }x_{u}x_{v}.\]It is shown that the limit\[ \lambda^{\left( p\right) }\left( \mathcal{P}\right) =\lim_{n\rightarrow\infty}n^{2/p-2}\max\{\lambda^{\left( p\right) }\left( G\right) :\text{ }G\in \mathcal{P}\text{ and }v\left( G\right) =n\}\]exists for every hereditary property $\mathcal{P}$.A key result of the note is the equality \[\lambda^{(p)}\left( \mathcal{P}\right) =\pi\left( \mathcal{P}\right) ,\]which holds for all $p>1.$ In particular, edge extremal problems andspectral extremal problems for graphs are asymptotically equivalent.
On Sets with Few Intersection Numbers in Finite Projective and Affine Spaces
Authors: Durante Nicola
Published: January 2020

In this paper we study sets $X$ of points of both affine and projective spaces over the Galois field $\mathop{\rm{GF}}(q)$ such that every line of the geometry that is neither contained in $X$ nor disjoint from $X$ meets the set $X$ in a constant number of points and we determine all such sets. This study has its main motivation in connection with a recent study of neighbour transitive codes in Johnson graphs by Liebler and Praeger [Designs, Codes and Crypt., 2014]. We prove that, up to complements, in $\mathop{\rm{PG}}(n,q)$ such a set $X$ is either a subspace or $n=2,q$ is even and $X$ is a maximal arc of degree $m$. In $\mathop{\rm{AG}}(n,q)$ we show that $X$ is either the union of parallel hyperplanes or a cylinder with base a maximal arc of degree $m$ (or the complement of a maximal arc) or a cylinder with base the projection of a quadric. Finally we show that in the affine case there are examples (different from subspaces or their complements) in $\mathop{\rm{AG}}(n,4)$ and in $\mathop{\rm{AG}}(n,16)$ giving new neighbour transitive codes in Johnson graphs.
The Centers of Gravity of the Associahedron and of the Permutahedron are the Same
Authors: Hohlweg Christophe , Lortie Jonathan , Raymond Annie
Published: January 2020

In this article, we show that Loday's realization of the associahedron has the the same center of gravity as the permutahedron. This proves an observation made by F. Chapoton. We also prove that this result holds for the associahedron and the cyclohedron as realized by the first author and C. Lange.
A Simple Formula for the Series of Constellations and Quasi-Constellations with Boundaries
Authors: Collet Gwendal , Fusy Éric
Published: January 2020

We obtain a very simple formula for the generating function of bipartite (resp. quasi-bipartite) planar maps with boundaries (holes) of prescribed lengths, which generalizes certain expressions obtained by Eynard in a book to appear. The formula is derived from a bijection due to Bouttier, Di Francesco and Guitter combined with a process (reminiscent of a construction of Pitman) of aggregating connected components of a forest into a single tree. The formula naturally extends to $p$-constellations and quasi-$p$-constellations with boundaries (the case $p=2$ corresponding to bipartite maps).
On the Strong Partition Dimension of Graphs
Authors: González Yero Ismael
Published: January 2020

We present a new style of metric generator in graphs. Specifically we introduce a metric generator based on a partition of the vertex set of a graph. The sets of the partition will work as the elements which will uniquely determine the position of each single vertex of the graph. A set $W$ of vertices of a connected graph $G$ strongly resolves two different vertices $x,y\notin W$ if either $d_G(x,W)=d_G(x,y)+d_G(y,W)$ or $d_G(y,W)=d_G(y,x)+d_G(x,W)$, where $d_G(x,W)=\min\left\{d(x,w)\;:\;w\in W\right\}$. An ordered vertex partition $\Pi=\left\{U_1,U_2,...,U_k\right\}$ of a graph $G$ is a strong resolving partition for $G$ if every two different vertices of $G$ belonging to the same set of the partition are strongly resolved by some set of $\Pi$. A strong resolving partition of minimum cardinality is called a strong partition basis and its cardinality the strong partition dimension. In this article we introduce the concepts of strong resolving partition and strong partition dimension and we begin with the study of its mathematical properties.
Modular, $k$-Noncrossing Diagrams
Authors: Reidys Christian M. , Wang Rita R. , Zhao Albus Y. Y.
Published: January 2020

In this paper we compute the generating function of modular, $k$-noncrossing diagrams. A $k$-noncrossing diagram is called modular if it does not contain any isolated arcs and any arc has length at least four. Modular diagrams represent the deformation retracts of RNA tertiary structures and their properties reflect basic features of these bio-molecules. The particular case of modular noncrossing diagrams has been extensively studied. Let ${Q}_k(n)$ denote the number of modular $k$-noncrossing diagrams over $n$ vertices. We derive exact enumeration results as well as the asymptotic formula ${Q}_k(n)\sim c_k n^{-(k-1)^2-{k-1\over2}}\gamma_{k}^{-n}$ for $k=3, \ldots, 9$ and derive a new proof of the formula ${Q}_2(n)\sim 1.4848\, n^{-3/2}\,1.8489^{n}$ (Hofacker et al. 1998).
Convolution Identities for Bernoulli and Genocchi Polynomials
Authors: Agoh Takashi
Published: January 2020

The main purpose of this paper is to derive various Matiyasevich-Miki-Gessel type convolution identities for Bernoulli and Genocchi polynomials and numbers by applying some Euler type identities with two parameters.
Self-Dual Spherical Grids
Authors: Graver Jack E. , Hartung Elizabeth J.
Published: January 2020

Self-dual plane graphs have been studied extensively. C. A. B Smith and W. T. Tutte published A class of self-dual maps in 1950; in 1992, Archdeacon and Richter described a method for constructing all self-dual plane graphs and a second construction was produced by Servatius and Christopher in 1992. Both constructions are inductive.  In this paper, we produce four templates from which all self-dual plane graphs with maximum degree 4 (self-dual spherical grids) can be constructed.  The self-dual spherical grids are further subdivided into 27 basic automorphism classes.  Self-dual spherical grids in the same automorphism class have similar architecture. A smallest example of each class is constructed.
Integral Cayley Graphs over Abelian Groups
Authors: Klotz Walter , Sander Torsten
Published: January 2020

Let $\Gamma$ be a finite, additive group, $S \subseteq \Gamma, 0\notin S, -S=\{-s: s\in S\}=S$. The undirected Cayley graph Cay$(\Gamma,S)$ has vertex set $\Gamma$ and edge set $\{\{a,b\}: a,b\in \Gamma$, $a-b \in S\}$. A graph is called integral, if all of its eigenvalues are integers. For an abelian group $\Gamma$ we show that Cay$(\Gamma,S)$ is integral, if $S$ belongs to the Boolean algebra $B(\Gamma)$ generated by the subgroups of $\Gamma$. The converse is proven for cyclic groups. A finite group $\Gamma$ is called Cayley integral, if every undirected Cayley graph over $\Gamma$ is integral. We determine all abelian Cayley integral groups.
The Ihara Zeta Function of the Infinite Grid
Authors: Clair Bryan
Published: January 2020

The infinite grid is the Cayley graph of $\mathbb{Z} \times \mathbb{Z}$ with the usual generators. In this paper, the Ihara zeta function for the infinite grid is computed using elliptic integrals and theta functions. The zeta function of the grid extends to an analytic, multivalued function which satisfies a functional equation. The set of singularities in its domain is finite.The grid zeta function is the first computed example which is non-elementary, and which takes infinitely many values at each point of its domain. It is also the limiting value of the normalized sequence of Ihara zeta functions for square grid graphs and torus graphs.
Discrete bidding games
Authors: Develin Mike , Payne Sam
Published: January 2020

We study variations on combinatorial games in which, instead of alternating moves, the players bid with discrete bidding chips for the right to determine who moves next. We consider both symmetric and partisan games, and explore differences between discrete bidding games and Richman games, which allow real-valued bidding. Unlike Richman games, discrete bidding game variations of many familiar games, such as chess, Connect Four, and even Tic-Tac-Toe, are suitable for recreational play. We also present an analysis of Tic-Tac-Toe for both discrete and real-valued bidding.
Biclique Covers and Partitions
Authors: Pinto Trevor
Published: January 2020

The biclique cover number (resp. biclique partition number) of a graph $G$, $\mathrm{bc}(G$) (resp. $\mathrm{bp}(G)$), is the least number of bicliques - complete bipartite subgraphs - that are needed to cover (resp. partition) the edges of $G$.The local biclique cover number (resp. local biclique partition number)  of a graph $G$, $\mathrm{lbc}(G$) (resp. $\mathrm{lbp}(G)$), is the least $r$ such that there is a cover (resp. partition) of the edges of $G$ by bicliques with no vertex in more than $r$ of these bicliques.We show that $\mathrm{bp}(G)$ may be bounded in terms of $\mathrm{bc}(G)$, in particular, $\mathrm{bp}(G)\leq \frac{1}{2}(3^\mathrm{bc(G)}-1)$. However, the analogous result does not hold for the local measures. Indeed, in our main result, we show that $\mathrm{lbp}(G)$ can be arbitrarily large, even for graphs with $\mathrm{lbc}(G)=2$. For such graphs, $G$, we try to bound $\mathrm{lbp}(G)$ in terms of additional information about biclique covers of $G$. We both answer and leave open questions related to this.There is a well known link between biclique covers and subcube intersection graphs. We consider the problem of finding the least $r(n)$ for which every graph on $n$ vertices can be represented as a subcube intersection graph in which every subcube has dimension $r$. We reduce this problem to the much studied question of finding the least $d(n)$ such that every graph on $n$ vertices is the intersection graph of subcubes of a $d$-dimensional cube.
Quantized Dual Graded Graphs
Authors: Lam Thomas
Published: January 2020

We study quantized dual graded graphs, which are graphs equipped with linear operators satisfying the relation $DU - qUD = rI$. We construct examples based upon: the Fibonacci differential poset, permutations, standard Young tableau, and plane binary trees.
Hyperoctahedral Eulerian Idempotents, Hodge Decompositions, and Signed Graph Coloring Complexes
Authors: Braun Benjamin , Crown Rundell Sarah
Published: January 2020

Phil Hanlon proved that the coefficients of the chromatic polynomial of a graph $G$ are equal (up to sign) to the dimensions of the summands in a Hodge-type decomposition of the top homology of the coloring complex for $G$.  We prove a type B analogue of this result for chromatic polynomials of signed graphs using hyperoctahedral Eulerian idempotents.
Schur Times Schubert via the Fomin-Kirillov Algebra
Authors: Mészáros Karola , Panova Greta , Postnikov Alexander
Published: January 2020

We study multiplication of any Schubert polynomial $\mathfrak{S}_w$ by a Schur polynomial $s_{\lambda}$ (the Schubert polynomial of a Grassmannian permutation) and the expansion of this product in the ring of Schubert polynomials. We derive explicit nonnegative combinatorial expressions for the expansion coefficients for certain special partitions $\lambda$, including hooks and the $2\times 2$ box. We also prove combinatorially the existence of such nonnegative expansion when the Young diagram of $\lambda$ is a hook plus a box at the $(2,2)$ corner. We achieve this by evaluating Schubert polynomials at the Dunkl elements of the Fomin-Kirillov algebra and proving special cases of the nonnegativity conjecture of Fomin and Kirillov.This approach works in the more general setup of the (small) quantum cohomology ring of the complex flag manifold and the corresponding (3-point) Gromov-Witten invariants. We provide an algebro-combinatorial proof of the nonnegativity of the Gromov-Witten invariants in these cases, and present combinatorial expressions for these coefficients.
Equipopularity Classes of 132-Avoiding Permutations
Authors: Chua Lynn , Sankar Krishanu Roy
Published: January 2020

The popularity of a pattern $p$ in a set of permutations is the sum of the number of copies of $p$ in each permutation of the set. We study pattern popularity in the set of 132-avoiding permutations. Two patterns are equipopular if, for all $n$, they have the same popularity in the set of length-$n$ 132-avoiding permutations. There is a well-known bijection between 132-avoiding permutations and binary plane trees. The spines of a binary plane tree are defined as the connected components when all edges connecting left children to their parents are deleted, and the spine structure is the sorted sequence of lengths of the spines. Rudolph shows that patterns of the same length are equipopular if their associated binary plane trees have the same spine structure. We prove the converse of this result using the method of generating functions, which gives a complete classification of 132-avoiding permutations into equipopularity classes.
On the Betti Numbers of some Classes of Binomial Edge Ideals
Authors: Zafar Sohail , Zahid Zohaib
Published: January 2020

We study the Betti numbers of binomial edge ideal associated to some classes of graphs with large Castelnuovo-Mumford regularity. As an application we give several lower bounds of the Castelnuovo-Mumford regularity of arbitrary graphs depending on induced subgraphs.
The Ladder Crystal
Authors: Berg Chris
Published: January 2020

In this paper I introduce a new description of the crystal $B(\Lambda_0)$ of $\widehat{\mathfrak{sl}}_\ell$. As in the Misra-Miwa model of $B(\Lambda_0)$, the nodes of this crystal are indexed by partitions and the $i$-arrows correspond to adding a box of residue $i$. I then show that the two models are equivalent by interpreting the operation of regularization introduced by James as a crystal isomorphism.
How Many Colors Guarantee a Rainbow Matching?
Authors: Glebov Roman , Sudakov Benny , Szabó Tibor
Published: January 2020

Given a coloring of the edges of a multi-hypergraph, a rainbow $t$-matching is a collection of $t$ disjoint edges, each having a different color. In this note we study the problem of finding a rainbow $t$-matching in an $r$-partite $r$-uniform multi-hypergraph whose edges are colored with $f$ colors such that every color class is a matching of size $t$. This problem was posed by Aharoni and Berger, who asked to determine the minimum number of colors which guarantees a rainbow matching. We improve on the known upper bounds for this problem for all values of the parameters. In particular for every fixed $r$, we give an upper bound which is polynomial in $t$, improving the superexponential estimate of Alon. Our proof also works in the setting not requiring the hypergraph to be $r$-partite.
Colour-blind Can Distinguish Colour Pallets
Authors: Przybyło Jakub
Published: January 2020

Let $c:E\to\{1,\ldots,k\}$ be an edge colouring of a connected graph $G=(V,E)$. Each vertex $v$ is endowed with a naturally defined pallet under $c$, understood as the multiset of colours incident with $v$. If $\delta(G)\geq 2$, we obviously (for $k$ large enough) may colour the edges of $G$ so that adjacent vertices are distinguished by their pallets of colours. Suppose then that our coloured graph is examined by a person who is unable to name colours, but perceives if two object placed next to each other are coloured differently. Can we colour $G$ so that this individual can distinguish colour pallets of adjacent vertices? It is proved that if $\delta(G)$ is large enough, then it is possible using just colours 1, 2 and 3. This result is sharp and improves all earlier ones. It also constitutes a strengthening of a result by Addario-Berry, Aldred, Dalal and Reed (2005).
The Terwilliger Algebra of the Incidence Graphs of Johnson Geometry
Authors: Kong Qian , Lv Benjian , Wang Kaishun
Published: January 2020

In 2007, Levstein and Maldonado  computed the Terwilliger algebra of the Johnson graph $J(n,m)$ when $3m\leq n$. It is well known that the halved graphs of the incidence graph $J(n,m,m+1)$ of Johnson geometry are Johnson graphs. In this paper, we determine the Terwilliger algebra of $J(n,m,m+1)$ when $3m\leq n$, give two bases of this algebra, and calculate its dimension.
The Asymptotic Behavior of the Average $L^p-$Discrepancies and a Randomized Discrepancy
Authors: Steinerberger Stefan
Published: January 2020

This paper gives the limit of the average $L^p-$star and the average $L^p-$extreme discrepancy for $[0,1]^d$ and $0 < p < \infty$. This complements earlier results by Heinrich, Novak, Wasilkowski & Woźnia-kowski, Hinrichs & Novak and Gnewuch and proves that the hitherto best known upper bounds are optimal up to constants.We furthermore introduce a new discrepancy $D_{N}^{\mathbb{P}}$ by taking a probabilistic approach towards the extreme discrepancy $D_{N}$. We show that it can be interpreted as a centralized $L^1-$discrepancy $D_{N}^{(1)}$, provide upper and lower bounds and prove a limit theorem.
Generalized Stirling Numbers and Hyper-Sums of Powers of Binomials Coefficients
Authors: Pita-Ruiz V. Claudio de J.
Published: January 2020

We work with a generalization of Stirling numbers of the second kind related to the boson normal ordering problem (P. Blasiak et al.). We show that these numbers appear as part of the coefficients of expressions in which certain sequences of products of binomials, together with their partial sums, are written as linear combinations of some other binomials. We show that the number arrays formed by these coefficients can be seen as natural generalizations of Pascal and Lucas triangles, since many of the known properties on rows, columns, falling diagonals and rising diagonals in Pascal and Lucas triangles, are also valid (some natural generalizations of them) in the arrays considered in this work. We also show that certain closed formulas for hyper-sums of powers of binomial coefficients appear in a natural way in these arrays.
On Compact Symmetric Regularizations of Graphs
Authors: Vandell R. , Walsh M. , Weakley W. D.
Published: January 2020

Let $G$ be a finite simple graph of order $n$, maximum degree $\Delta$, and minimum degree $\delta$. A compact regularization of $G$ is a $\Delta$-regular graph $H$ of which $G$ is an induced subgraph: $H$ is symmetric if every automorphism of $G$ can be extended to an automorphism of $H$. The index $|H:G|$ of a regularization $H$ of $G$ is the ratio $|V(H)|/|V(G)|$. Let $\mbox{mcr}(G)$ denote the index of a minimum compact regularization of $G$ and let $\mbox{mcsr}(G)$ denote the index of a minimum compact symmetric regularization of $G$.Erdős and Kelly proved that every graph $G$ has a compact regularization and $\mbox{mcr}(G) \leq 2$. Building on a result of König, Chartrand and Lesniak showed that every graph has a compact symmetric regularization and $\mbox{mcsr}(G) \leq 2^{\Delta - \delta}$.  Using a partial Cartesian product construction, we improve this to $\mbox{mcsr}(G) \leq \Delta - \delta + 2$ and give examples to show this bound cannot be reduced below $\Delta - \delta + 1$.
Maximum Induced Forests in Graphs of Bounded Treewidth
Authors: Chappell Glenn G. , Pelsmajer Michael J.
Published: January 2020

Given a nonnegative integer $d$ and a graph $G$, let $f_d(G)$ be the maximum order of an induced forest in $G$ having maximum degree at most $d$. We seek lower bounds for $f_d(G)$ based on the order and treewidth of $G$.We show that, for all $k,d\ge 2$ and $n\ge 1$, if $G$ is a graph with order $n$ and treewidth at most $k$, then $f_d(G)\ge\lceil{(2dn+2)/(kd+d+1)}\rceil$, unless $G\in\{K_{1,1,3},K_{2,3}\}$ and $k=d=2$. We give examples that show that this bound is tight to within $1$.We conjecture a bound for $d=1$: $f_1(G) \ge\lceil{2n/(k+2)}\rceil$, which would also be tight to within $1$, and we prove it for $k\le 3$. For $k\ge 4$ the conjecture remains open, and we prove a weaker bound: $f_1(G)\ge (2n+2)/(2k+3)$. We also examine the cases $d=0$ and $k=0,1$.Lastly, we consider open problems relating to $f_d$ for graphs on a given surface, rather than graphs of bounded treewidth.
Ramsey Precompact Expansions of Homogeneous Directed Graphs
Authors: Jasiński Jakub , Laflamme Claude , Nguyen Van Thé Lionel , Woodrow Robert
Published: January 2020

In 2005, Kechris, Pestov and Todorčević provided a powerful tool to compute an invariant of topological groups known as the universal minimal flow, immediately leading to an explicit representation of this invariant in many concrete cases. More recently, the framework was generalized allowing for further applications, and the purpose of this paper is to apply these new methods in the context of homogeneous directed graphs. In this paper, we show that the age of any homogeneous directed graph allows a Ramsey precompact expansion. Moreover, we verify the relative expansion properties and consequently describe the respective universal minimal flows.
Grid Minors in Damaged Grids
Authors: Eppstein David
Published: January 2020

We prove upper and lower bounds on the size of the largest square grid graph that is a subgraph, minor, or shallow minor of a graph in the form of a larger square grid from which a specified number of vertices have been deleted. Our bounds are tight to within constant factors. We also provide less-tight bounds on analogous problems for higher-dimensional grids.
Cyclic partitions of complete uniform hypergraphs
Authors: Szymański Artur , Wojda A. Paweł
Published: January 2020

By $K^{(k)}_n$ we denote the complete $k$-uniform hypergraph of order $n$, $1\le k \le n-1$, i.e. the hypergraph with the set $V_n=\{ 1,2,...,n\}$ of vertices and the set $V_n \choose k$ of edges. If there exists a permutation $\sigma$ of the set $V_n$ such that $\{ E,\sigma (E),..., \sigma^{q-1}(E) \}$ is a partition of the set $V_n \choose k$ then we call it cyclic $q$-partition of $K^{(k)}_n$ and $\sigma$ is said to be a $(q,k)$-complementing. In the paper, for arbitrary integers $k,q$ and $n$, we give a necessary and sufficient condition for a permutation to be $(q,k)$-complementing permutation of $K^{(k)}_n$. By $\tilde{K}_n$ we denote the hypergraph with the set of vertices $V_n$ and the set of edges $2^{V_n} - \{ \emptyset , V_n \}$. If there is a permutation $\sigma$ of $V_n$ and a set $E \subset 2^{V_n} - \{ \emptyset , V_n \}$ such that $\{ E, \sigma (E),..., \sigma^{p-1}(E) \}$ is a $p$-partition of $ 2^{V_n} - \{ \emptyset , V_n \}$ then we call it a cyclic $p$-partition of $K_n$ and we say that $\sigma$ is $p$-complementing. We prove that $\tilde{K}_n$ has a cyclic $p$-partition if and only if $p$ is prime and $n$ is a power of $p$ (and $n > p$). Moreover, any $p$-complementing permutation is cyclic.
Bijective Proofs of Partition Identities of MacMahon, Andrews, and Subbarao
Authors: Fu Shishuo , Sellers James Allen
Published: January 2020

We revisit a classic partition theorem due to MacMahon that relates partitions with all parts repeated at least once and partitions with parts congruent to $2,3,4,6 \pmod 6$, together with a generalization by Andrews and two others by Subbarao. Then we develop a unified bijective proof for all four theorems involved, and obtain a natural further generalization as a result.
The Distinguishing Index of Infinite Graphs
Authors: Broere Izak , Pilśniak Monika
Published: January 2020

The  distinguishing index $D^\prime(G)$ of a graph $G$ is the least cardinal $d$ such that $G$ has an edge colouring with $d$ colours that is only preserved by the trivial automorphism. This is similar to the notion of the distinguishing number $D(G)$ of a graph $G$, which is defined with respect to vertex colourings.We derive several bounds for infinite graphs, in particular, we prove the general bound $D^\prime(G)\leq\Delta(G)$ for an arbitrary infinite graph. Nonetheless,  the distinguishing index is at most two for many countable graphs, also for the infinite random graph and for uncountable tree-like graphs.We also investigate the concept of the motion of edges and its relationship with the Infinite Motion Lemma.
The Combinatorics of $\mathsf{A_2}$-Webs
Authors: Benkart Georgia , Cho Soojin , Moon Dongho
Published: January 2020

The nonelliptic $\mathsf{A_2}$-webs with $k$ "$+$''s on the top boundary and $3n-2k$ "$-$''s on the bottom boundary combinatorially model the space $\mathsf{Hom}_{\mathfrak{sl}_3}(\mathsf{V}^{\otimes (3n-2k)}, \mathsf{V}^{\otimes k})$ of  $\mathfrak{sl}_3$-module maps on tensor powers of the natural 3-dimensional $\mathfrak{sl}_3$-module $\mathsf{V}$,  and they have connections with the combinatorics ofSpringer varieties. Petersen, Pylyavskyy, and Rhodes showed  that the set of such  $\mathsf{A_2}$-webs and the set of  semistandard tableaux of shape $(3^n)$ and type $\{1^2,\dots,k^2,k+1,\dots, 3n-k\}$ have the same cardinalities. In this work, we use the $\sf{m}$-diagrams introduced by Tymoczko and the Robinson-Schensted correspondence to construct an explicit bijection, different from the one given by Russell, between these two sets.  In establishing our result, we show that the pair of standard  tableaux constructed using the notion of path depth is the same as the pair constructed from applying the Robinson-Schensted correspondence to a $3\,2\,1$-avoiding permutation.  We also obtain a bijection between such pairs of standard tableaux and Westbury's $\mathsf{A_2}$ flow diagrams.
Small Snarks with Large Oddness
Authors: Lukoťka Robert , Máčajová Edita , Mazák Ján , Škoviera Martin
Published: January 2020

We estimate the minimum number of vertices of a cubic graph with given oddness and cyclic connectivity. We prove that a bridgeless cubic graph $G$ with oddness $\omega(G)$ other than the Petersen graph has at least $5.41\, \omega(G)$ vertices, and for each integer $k$ with $2\le k\le 6$ we construct an infinite family of cubic graphs with cyclic connectivity $k$ and small oddness ratio $|V(G)|/\omega(G)$. In particular, for cyclic connectivity $2$, $4$, $5$, and $6$ we improve the upper bounds on the oddness ratio of snarks to $7.5$, $13$, $25$, and $99$ from the known values $9$, $15$, $76$, and $118$, respectively. In addition, we construct a cyclically $4$-connected snark of girth $5$ with oddness $4$ on $44$ vertices, improving the best previous value of $46$. Corrigendum added March 19, 2018.
Automorphism Groups of a Graph and a Vertex-Deleted Subgraph
Authors: Hartke Stephen G. , Kolb Hannah , Nishikawa Jared , Stolee Derrick
Published: January 2020

Understanding the structure of a graph along with the structure of its subgraphs is important for several problems in graph theory. Two examples are the Reconstruction Conjecture and isomorph-free generation. This paper raises the question of which pairs of groups can be represented as the automorphism groups of a graph and a vertex-deleted subgraph. This, and more surprisingly the analogous question for edge-deleted subgraphs, are answered in the most positive sense using concrete constructions.
On Fence Patrolling by Mobile Agents
Authors: Dumitrescu Adrian , Ghosh Anirban , Tóth Csaba D.
Published: January 2020

Suppose that a fence needs to be protected (perpetually) by $k$ mobile agents with maximum speeds $v_1,\ldots,v_k$ so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the idle time, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by Czyzowicz et al. (2011), and discuss several strategies for the cases where the fence is an open and a closed curve, respectively.In particular: (i) we disprove a conjecture by Czyzowicz et al. regarding the optimality of their algorithm ${\mathcal A}_2$ for unidirectional patrolling of a closed fence; (ii) we present a schedule with a lower idle time for patrolling an open fence, improving an earlier result of Kawamura and Kobayashi.
Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique
Authors: Atminas Aistis , Brignall Robert , Korpelainen Nicholas , Lozin Vadim , Vatter Vincent
Published: January 2020

We consider well-quasi-order for classes of permutation graphs which omit both a path and a clique. Our principle result is that the class of permutation graphs omitting $P_5$ and a clique of any size is well-quasi-ordered. This is proved by giving a structural decomposition of the corresponding permutations. We also exhibit three infinite antichains to show that the classes of permutation graphs omitting $\{P_6,K_6\}$, $\{P_7,K_5\}$, and $\{P_8,K_4\}$ are not well-quasi-ordered.
Densities of Minor-Closed Graph Families
Authors: Eppstein David
Published: January 2020

We define the limiting density of a minor-closed family of simple graphs $\mathcal{F}$ to be the smallest number $k$ such that every $n$-vertex graph in $\mathcal{F}$ has at most $kn(1+o(1))$ edges, and we investigate the set of numbers that can be limiting densities. This set of numbers is countable, well-ordered, and closed; its order type is at least $\omega^\omega$. It is the closure of the set of densities of density-minimal graphs, graphs for which no minor has a greater ratio of edges to vertices. By analyzing density-minimal graphs of low densities, we find all limiting densities up to the first two cluster points of the set of limiting densities, $1$ and $3/2$. For multigraphs, the only possible limiting densities are the integers and the superparticular ratios $i/(i+1)$.
A $q$-Queens Problem. I. General Theory
Authors: Chaiken Seth , Hanusa Christopher R. H. , Zaslavsky Thomas
Published: January 2020

By means of the Ehrhart theory of inside-out polytopes we establish a general counting theory for nonattacking placements of chess pieces with unbounded straight-line moves, such as the queen, on a polygonal convex board. The number of ways to place $q$ identical nonattacking pieces on a board of variable size $n$ but fixed shape is (up to a normalization) given by a quasipolynomial function of $n$, of degree $2q$, whose coefficients are polynomials in $q$. The number of combinatorially distinct types of nonattacking configuration is the evaluation of our quasipolynomial at $n=-1$. The quasipolynomial has an exact formula that depends on a matroid of weighted graphs, which is in turn determined by incidence properties of lines in the real affine plane. We study the highest-degree coefficients and also the period of the quasipolynomial, which is needed if the quasipolynomial is to be interpolated from data, and which is bounded by some function, not well understood, of the board and the piece's move directions.
Growth Rates for Subclasses of $\mathrm{Av}(321)$
Authors: Albert M. H. , Atkinson M. D. , Brignall R. , Ruškuc N. , Smith Rebecca , West J.
Published: January 2020

Pattern classes which avoid $321$ and other patterns are shown to have the same growth rates as similar (but strictly larger) classes obtained by adding articulation points to any or all of the other patterns. The method of proof is to show that the elements of the latter classes can be represented as bounded merges of elements of the original class, and that the bounded merge construction does not change growth rates.
The Extendability of Matchings in Strongly Regular Graphs
Authors: Cioabă Sebastian M , Li Weiqiang
Published: January 2020

A graph $G$ of even order $v$ is called $t$-extendable if it contains a perfect matching, $t<v/2$ and any matching of $t$ edges is contained in some perfect matching. The extendability of $G$ is the maximum $t$ such that $G$ is $t$-extendable. In this paper, we study the extendability properties of strongly regular graphs. We improve previous results and classify all strongly regular graphs that are not $3$-extendable. We also show that strongly regular graphs of valency $k\geq 3$ with $\lambda \geq 1$ are $\lfloor k/3\rfloor$-extendable (when $\mu \leq k/2$) and $\lceil \frac{k+1}{4}\rceil$-extendable (when $\mu>k/2$), where $\lambda$ is the number of common neighbors of any two adjacent vertices and $\mu$ is the number of common neighbors of any two non-adjacent vertices. Our results are close to being best possible as there are strongly regular graphs of valency $k$ that are not $\lceil k/2\rceil $-extendable. We show that the extendability of many strongly regular graphs of valency $k$ is at least $\lceil k/2 \rceil -1$ and we conjecture that this is true for all primitive strongly regular graphs. We obtain similar results for strongly regular graphs of odd order.
Locally Restricted Compositions III. Adjacent-Part Periodic Inequalities
Authors: Bender Edward A. , Canfield E. Rodney
Published: January 2020

We study compositions $c_1,\dots,c_k$ of the integer $n$ in which adjacent parts may be constrained to satisfy some periodic inequalities, for example $$ c_{2i}>c_{2i+1} < c_{2i+2} \mbox{(alternating compositions).} $$ The types of inequalities considered are $ < $, $\le$, $>$, $\ge$ and $\ne$. We show how to obtain generating functions from which various pieces of asymptotic information can be computed. There are asymptotically $Ar^{-n}$ compositions of $n$. In a random uniformly selected composition of $n$, the largest part and number of distinct parts are almost surely asymptotic to $\log_{1/r}(n)$. The length of the longest run is almost surely asymptotic to $C\log_{1/r}(n)$ where C is an easily determined rational number. Many other counts are asymptotically normally distributed. We present some numerical results for the various types of alternating compositions.