bluuebunny/crossref_metadata_2025 huggingface dataset:
Generating Functions of Bipartite Maps on Orientable Surfaces
Authors: Chapuy Guillaume , Fang Wenjie
Published: January 2020

We compute, for each genus $g\geq 0$, the generating function $L_g\equiv L_g(t;p_1,p_2,\dots)$ of (labelled) bipartite maps on the orientable surface of genus $g$, with control on all face degrees. We exhibit an explicit change of variables such that for each $g$, $L_g$ is a rational function in the new variables, computable by an explicit recursion on the genus. The same holds for the generating function $F_g$ of rooted bipartite maps. The form of the result is strikingly similar to the Goulden/Jackson/Vakil and Goulden/Guay-Paquet /Novak formulas for the generating functions of classical and monotone Hurwitz numbers respectively, which suggests stronger links between these models. Our result  complements recent results of Kazarian and Zograf, who studied the case where the number of faces is bounded, in the equivalent formalism of dessins d'enfants. Our proofs borrow some ideas from Eynard's "topological recursion" that he applied in particular to even-faced maps (unconventionally called "bipartite maps" in his work). However, the present paper requires no previous knowledge of this topic and comes with elementary (complex-analysis-free) proofs written in the perspective of formal power series.
A Note on Chromatic Number and Induced Odd Cycles
Authors: Xu Baogang , Yu Gexin , Zha Xiaoya
Published: January 2020

An odd hole is an induced odd cycle of length at least 5. Scott and Seymour confirmed a conjecture of Gyárfás and proved that if a graph $G$ has no odd holes then $\chi(G)\le 2^{2^{\omega(G)+2}}$. Chudnovsky, Robertson, Seymour and Thomas showed that if $G$ has neither $K_4$ nor odd holes then $\chi(G)\le 4$. In this note, we show that if a graph $G$ has neither triangles nor quadrilaterals, and has no odd holes of length at least 7, then $\chi(G)\le 4$ and $\chi(G)\le 3$ if $G$ has radius at most $3$, and for each vertex $u$ of $G$, the set of vertices of the same distance to $u$ induces a bipartite subgraph. This answers some questions in Plummer and Zha (2014).
Bi-Cohen-Macaulay graphs
Authors: Herzog Jürgen , Rahimi Ahad
Published: January 2020

In this paper we consider bi-Cohen-Macaulay graphs, and give a complete classification of such graphs in the case they are bipartite or chordal. General bi-Cohen-Macaulay graphs are classified up to separation. The inseparable bi-Cohen-Macaulay graphs are determined. We establish a bijection between the set of all trees and the set of inseparable bi-Cohen-Macaulay graphs.
On Universal Hypergraphs
Authors: Hetterich Samuel , Parczyk Olaf , Person Yury
Published: January 2020

A hypergraph $H$ is called universal for a family $\mathcal{F}$ of hypergraphs, if it contains every hypergraph $F \in \mathcal{F}$ as a copy. For the family of $r$-uniform hypergraphs with maximum vertex degree bounded by $\Delta$ and at most $n$ vertices any universal hypergraph has to contain $\Omega(n^{r-r/\Delta})$ many edges. We exploit constructions of Alon and Capalbo to obtain universal $r$-uniform hypergraphs with the optimal number of edges $O(n^{r-r/\Delta})$ when $r$ is even, $r \mid \Delta$ or $\Delta=2$. Further we generalize the result of Alon and Asodi about optimal universal graphs for the family of graphs with at most $m$ edges and no isolated vertices to hypergraphs.
On the Chvátal-Erdős Triangle Game
Authors: Balogh József , Samotij Wojciech
Published: January 2020

Given a graph $G$ and positive integers $n$ and $q$, let ${\bf G}(G;n,q)$ be the game played on the edges of the complete graph $K_n$ in which the two players, Maker and Breaker, alternately claim $1$ and $q$ edges, respectively. Maker's goal is to occupy all edges in some copy of $G$; Breaker tries to prevent it. In their seminal paper on positional games, Chvátal and Erdős proved that in the game ${\bf G}(K_3;n,q)$, Maker has a winning strategy if $q < \sqrt{2n+2}-5/2$, and if $q \geq 2\sqrt{n}$, then Breaker has a winning strategy. In this note, we improve the latter of these bounds by describing a randomized strategy that allows Breaker to win the game ${\bf G}(K_3;n,q)$ whenever $q \geq (2-1/24)\sqrt{n}$. Moreover, we provide additional evidence supporting the belief that this bound can be further improved to $(\sqrt{2}+o(1))\sqrt{n}$.
Enumeration of Parallelograms in Permutation Matrices for Improved Bounds on the Density of Costas Arrays
Authors: Swanson Christopher N. , Correll, Jr. Bill , Ho Randy W.
Published: January 2020

A Costas array of order $n$ is an $n\times n$ permutation matrix such that all vectors between pairs of ones are distinct. Thus, a permutation matrix fails to be a Costas array if and only if it contains ones that form a (possibly degenerate) parallelogram. In this paper, we enumerate parallelograms in an $n\times n$ permutation matrix. We use our new formulas to improve Davies's $O(n^{-1})$ result for the density of Costas arrays.
A General Theory of Wilf-Equivalence for Catalan Structures
Authors: Albert Michael , Bouvel Mathilde
Published: January 2020

The existence of apparently coincidental equalities (also called Wilf-equivalences) between the enumeration sequences or generating functions of various hereditary classes of combinatorial structures has attracted significant interest. We investigate such coincidences among non-crossing matchings and a variety of other Catalan structures including Dyck paths, 231-avoiding permutations and plane forests. In particular we consider principal subclasses defined by not containing an occurrence of a single given structure. An easily computed equivalence relation among structures is described such that if two structures are equivalent then the associated principal subclasses have the same enumeration sequence. We give an asymptotic estimate of the number of equivalence classes of this relation among structures of size $n$ and show that it is exponentially smaller than the $n^{th}$ Catalan number. In other words these "coincidental" equalities are in fact very common among principal subclasses. Our results also allow us to prove in a unified and bijective manner several known Wilf-equivalences from the literature.
Chung-Feller Property of Schröder Objects
Authors: Park Youngja , Kim Sangwook
Published: January 2020

Large Schröder paths, sparse noncrossing partitions, partial horizontal strips, and $132$-avoiding alternating sign matrices are objects enumerated by Schröder numbers. In this paper we give formula for the number of Schröder objects with given type and number of connected components. The proofs are bijective using Chung-Feller style. A bijective proof for the number of Schröder objects with given type is provided. We also give a combinatorial interpretation for the number of small Schröder paths.
Even Cycles and Even 2-Factors in the Line Graph of a Simple Graph
Authors: Bonisoli Arrigo , Bonvicini Simona
Published: January 2020

Let $G$ be a connected graph with an even number of edges. We show that if the subgraph of $G$ induced by the vertices of odd degree has a perfect matching, then the line graph of $G$ has a $2$-factor whose connected components are cycles of even length (an even $2$-factor). For a cubic graph $G$, we also give a necessary and sufficient condition so that the corresponding line graph $L(G)$ has an even cycle decomposition of index $3$, i.e., the edge-set of $L(G)$ can be partitioned into three $2$-regular subgraphs whose connected components are cycles of even length. The more general problem of the existence of even cycle decompositions of index $m$ in $2d$-regular graphs is also addressed.
Inclusion Matrices and the MDS Conjecture
Authors: Chowdhury Ameera
Published: January 2020

Let $\mathbb{F}_{q}$ be a finite field of order $q$ with characteristic $p$. An arc is an ordered family of at least $k$ vectors in $\mathbb{F}_{q}^{k}$ in which every subfamily of size $k$ is a basis of $\mathbb{F}_{q}^{k}$. The MDS conjecture, which was posed by Segre in 1955, states that if $k \leq q$, then an arc in $\mathbb{F}_{q}^{k}$ has size at most $q+1$, unless $q$ is even and $k=3$ or $k=q-1$, in which case it has size at most $q+2$. We propose a conjecture which would imply that the MDS conjecture is true for almost all values of $k$ when $q$ is odd. We prove our conjecture in two cases and thus give simpler proofs of the MDS conjecture when $k \leq p$, and if $q$ is not prime, for $k \leq 2p-2$. To accomplish this, given an arc $G \subset \mathbb{F}_{q}^{k}$ and a nonnegative integer $n$, we construct a matrix $M_{G}^{\uparrow n}$, which is related to an inclusion matrix, a well-studied object in combinatorics. Our main results relate algebraic properties of the matrix $M_{G}^{\uparrow n}$ to properties of the arc $G$ and may provide new tools in the computational classification of large arcs.
Blocking and Double Blocking Sets in Finite Planes
Authors: De Beule Jan , Héger Tamás , Szőnyi Tamás , Van de Voorde Geertrui
Published: January 2020

In this paper, by using properties of Baer subplanes, we describe the construction of a minimal blocking set in the Hall plane of order $q^2$ of size $q^2+2q+2$ admitting $1-$, $2-$, $3-$, $4-$, $(q+1)-$ and $(q+2)-$secants. As a corollary, we obtain the existence of a minimal blocking set of a non-Desarguesian affine plane of order $q^2$ of size at most $4q^2/3+5q/3$, which is considerably smaller than $2q^2-1$, the Jamison bound for the size of a minimal blocking set in an affine Desarguesian plane of order $q^2$.We also consider particular André planes of order $q$, where $q$ is a power of the prime $p$, and give a construction of a small minimal blocking set which admits a secant line not meeting the blocking set in $1$ mod $p$ points. Furthermore, we elaborate on the connection of this problem with the study of value sets of certain polynomials and with the construction of small double blocking sets in Desarguesian projective planes; in both topics we provide some new results.
Generalizations of the Strong Arnold Property and the Minimum Number of Distinct Eigenvalues of a Graph
Authors: Barrett Wayne , Fallat Shaun , Hall H. Tracy , Hogben Leslie , Lin Jephian C.-H. , Shader Bryan L.
Published: January 2020

For a given graph $G$ and an associated class of real symmetric matrices whose diagonal entries are governed by the adjacencies in $G$, the collection of all possible spectra for such matrices is considered. Building on the pioneering work of Colin de Verdière in connection with the Strong Arnold Property, two extensions are devised that target a better understanding of all possible spectra and their associated multiplicities. These new properties are referred to as the Strong Spectral Property and the Strong Multiplicity Property. Finally, these ideas are applied to the minimum number of distinct eigenvalues associated with $G$, denoted by $q(G)$. The graphs for which $q(G)$ is at least the number of vertices of $G$ less one are characterized.
Refined Dual Stable Grothendieck Polynomials and Generalized Bender-Knuth Involutions
Authors: Galashin Pavel , Grinberg Darij , Liu Gaku
Published: January 2020

The dual stable Grothendieck polynomials are a deformation of the Schur functions, originating in the study of the $K$-theory of the Grassmannian. We generalize these polynomials by introducing a countable family of additional parameters, and we prove that this generalization still defines symmetric functions. For this fact, we give two self-contained proofs, one of which constructs a family of involutions on the set of reverse plane partitions generalizing the Bender-Knuth involutions on semistandard tableaux, whereas the other classifies the structure of reverse plane partitions with entries $1$ and $2$.
Internally Perfect Matroids
Authors: Dall Aaron
Published: January 2020

In 1977 Stanley proved that the $h$-vector of a matroid is an $\mathcal{O}$-sequence and conjectured that it is a pure $\mathcal{O}$-sequence. In the subsequent years the validity of this conjecture has been shown for a variety of classes of matroids, though the general case is still open. In this paper we use Las Vergnas' internal order to introduce a new class of matroids which we call internally perfect. We prove that these matroids satisfy Stanley's Conjecture and compare them to other classes of matroids for which the conjecture is known to hold. We also prove that, up to a certain restriction on deletions, every minor of an internally perfect ordered matroid is internally perfect.
On the Maximum Running Time in Graph Bootstrap Percolation
Authors: Bollobás Béla , Przykucki Michał , Riordan Oliver , Sahasrabudhe Julian
Published: January 2020

Graph bootstrap percolation is a simple cellular automaton introduced by Bollobás in 1968. Given a graph $H$ and a set $G \subseteq E(K_n)$ we initially `infect' all edges in $G$ and then, in consecutive steps, we infect every $e \in K_n$ that completes a new infected copy of $H$ in $K_n$. We say that $G$ percolates if eventually every edge in $K_n$ is infected. The extremal question about the size of the smallest percolating sets when $H = K_r$ was answered independently by Alon, Kalai and Frankl. Here we consider a different question raised more recently by Bollobás: what is the maximum time the process can run before it stabilizes? It is an easy observation that for $r=3$ this maximum is $\lceil \log_2 (n-1) \rceil $. However, a new phenomenon occurs for $r=4$ when, as we show, the maximum time of the process is $n-3$. For $r \geq 5$ the behaviour of the dynamics is even more complex, which we demonstrate by showing that the $K_r$-bootstrap process can run for at least $n^{2-\varepsilon_r}$ time steps for some $\varepsilon_r$ that tends to $0$ as $r \to \infty$.
On the Cohen-Macaulay Property for Quadratic Tangent Cones
Authors: Stamate Dumitru I.
Published: January 2020

Let $H$ be an $n$-generated numerical semigroup such that its tangent cone $\operatorname{gr}_\mathfrak{m} K[H]$ is defined by quadratic relations. We show that if $n<5$ then $\operatorname{gr}_\mathfrak{m} K[H]$ is Cohen-Macaulay, and for $n=5$ we explicitly describe the semigroups $H$ such that $\operatorname{gr}_\mathfrak{m} K[H]$ is not Cohen-Macaulay. As an application we show that if the field $K$ is algebraically closed and of characteristic different from two, and $n\leq 5$ then $\operatorname{gr}_\mathfrak{m} K[H]$ is Koszul if and only if (possibly after a change of coordinates) its defining ideal has a quadratic Gröbner basis.
The Existence of a Path-Factor without Small Odd Paths
Authors: Egawa Yoshimi , Furuya Michitaka
Published: January 2020

A $\{P_{2},P_{5}\}$-factor of a graph is a spanning subgraph of the graph each of whose components is isomorphic to either $P_{2}$ or $P_{5}$, where $P_{n}$ denote the path of order $n$. In this paper, we show that if a graph $G$ satisfies $c_{1}(G-X)+\frac{2}{3}c_{3}(G-X)\leq \frac{4}{3}|X|+\frac{1}{3}$ for all $X\subseteq V(G)$, then $G$ has a $\{P_{2},P_{5}\}$-factor, where $c_{i}(G-X)$ is the number of components $C$ of $G-X$ with $|V(C)|=i$. Moreover, it is shown that above condition is sharp.
On Well-Covered, Vertex Decomposable and Cohen-Macaulay Graphs
Authors: Castrillón Iván D. , Cruz Roberto , Reyes Enrique
Published: January 2020

Let $G=(V,E)$ be a graph. If $G$ is a König graph or if $G$ is a graph without 3-cycles and 5-cycles, we prove that the following conditions are equivalent: $\Delta_{G}$ is pure shellable, $R/I_{\Delta}$ is Cohen-Macaulay, $G$ is unmixed vertex decomposable graph and $G$ is well-covered with a perfect matching of König type $e_{1},\dots,e_{g}$ without 4-cycles with two $e_i$'s. Furthermore, we study vertex decomposable and shellable (non-pure) properties in graphs without 3-cycles and 5-cycles. Finally, we give some properties and relations between critical, extendable and shedding vertices.
Face-Degree Bounds for Planar Critical Graphs
Authors: Jin Ligang , Kang Yingli , Steffen Eckhard
Published: January 2020

The only remaining case of a well known conjecture of Vizing states that there is no planar graph with maximum degree 6 and edge chromatic number 7. We introduce parameters for planar graphs,  based on the degrees of the faces, and study the question whether there are upper bounds for these parameters for planar edge-chromatic critical graphs. Our results provide upper bounds on these parameters for smallest counterexamples to Vizing's conjecture, thus providing a partial characterization of such graphs, if they exist.For $k \leq 5$ the results give insights into the structure of planar edge-chromatic critical graphs.
Edge Reconstruction of the Ihara Zeta Function
Authors: Cornelissen Gunther , Kool Janne
Published: January 2020

We show that if a graph $G$ has average degree $\overline d \geq 4$, then the Ihara zeta function of $G$ is edge-reconstructible. We prove some general spectral properties of the edge adjacency operator $T$: it is symmetric for an indefinite form and has a "large" semi-simple part (but it can fail to be semi-simple in general).  We prove that this implies that if $\overline d>4$, one can reconstruct the number of non-backtracking (closed or not) walks through a given edge, the Perron-Frobenius eigenvector of $T$ (modulo a natural symmetry), as well as the closed walks that pass through a given edge in both directions at least once.
Paths vs. Stars in the Local Profile of Trees
Authors: Czabarka Éva , Székely László , Wagner Stephan
Published: January 2020

The aim of this paper is to provide an affirmative answer to a recent question by Bubeck and Linial on the local profile of trees. For a tree $T$, let $p^{(k)}_1(T)$ be the proportion of paths among all $k$-vertex subtrees (induced connected subgraphs) of $T$, and let $p^{(k)}_2(T)$ be the proportion of stars. Our main theorem states: if $p^{(k)}_1(T_n) \to 0$ for a sequence of trees $T_1,T_2,\ldots$ whose size tends to infinity, then $p^{(k)}_2(T_n) \to 1$. Both are also shown to be equivalent to the statement that the number of $k$-vertex subtrees grows superlinearly and the statement that the $(k-1)$th degree moment grows superlinearly.
On the Potts Antiferromagnet on Random Graphs
Authors: Coja-Oghlan Amin , Jaafari Nor
Published: January 2020

Extending a prior result of Contucci et al. [Comm. Math. Phys. 2013], we determine the free energy of the Potts antiferromagnet on the Erdős–Rényi random graph at all temperatures for average degrees $d\le (2k-1)\ln k - 2 - k^{-1/2}$. In particular, we show that for this regime of $d$ there does not occur a phase transition.
A New Construction of Non-Extendable Intersecting Families of Sets
Authors: Majumder Kaushik
Published: January 2020

In 1975, Lovász conjectured that any maximal intersecting family of $k$-sets has at most $\lfloor(e-1)k!\rfloor$ blocks, where $e$ is the base of the natural logarithm. This conjecture was disproved in 1996 by Frankl and his co-authors. In this short note, we reprove the result of Frankl et al. using a vastly simplified construction of maximal intersecting families with many blocks. This construction yields a maximal intersecting family $\mathbb{G}_{k}$ of $k-$sets whose number of blocks is asymptotic to $e^{2}(\frac{k}{2})^{k-1}$ as $k\rightarrow\infty$.
Quantum Walks on Generalized Quadrangles
Authors: Godsil Chris , Guo Krystal , Myklebust Tor G. J.
Published: January 2020

We study the transition matrix of a quantum walk on strongly regular graphs. It is proposed by Emms, Hancock, Severini and Wilson in 2006, that the spectrum of $S^+(U^3)$, a matrix based on the amplitudes of walks in the quantum walk, distinguishes strongly regular graphs. We probabilistically compute the spectrum of the line intersection graphs of two non-isomorphic generalized quadrangles of order $(5^2,5)$ under this matrix and thus provide strongly regular counter-examples to the conjecture.
A Note on Non-$\mathbb{R}$-Cospectral Graphs
Authors: Liu Fenjin , Wang Wei
Published: January 2020

Two graphs $G$ and $H$ are called $\mathbb{R}$-cospectral if $A(G)+yJ$ and $A(H)+yJ$ (where $A(G)$, $A(H)$ are the adjacency matrices of $G$ and $H$, respectively, $J$ is the all-one matrix) have the same spectrum for all $y\in\mathbb{R}$. In this note, we give a necessary condition for having $\mathbb{R}$-cospectral graphs. Further, we provide a sufficient condition ensuring only irrational orthogonal similarity between certain cospectral graphs. Some concrete examples are also supplied to exemplify the main results.
Partitioning Random Graphs into Monochromatic Components
Authors: Bal Deepak , DeBiasio Louis
Published: January 2020

Erdős, Gyárfás, and Pyber (1991) conjectured that every $r$-colored complete graph can be partitioned into at most $r-1$ monochromatic components; this is a strengthening of a conjecture of Lovász (1975) and Ryser (1970) in which the components are only required to form a cover. An important partial result of Haxell and Kohayakawa (1995) shows that a partition into $r$ monochromatic components is possible for sufficiently large $r$-colored complete graphs.We start by extending Haxell and Kohayakawa's result to graphs with large minimum degree, then we provide some partial analogs of their result for random graphs. In particular, we show that if $p\ge \left(\frac{27\log n}{n}\right)^{1/3}$, then a.a.s. in every $2$-coloring of $G(n,p)$ there exists a partition into two monochromatic components, and for $r\geq 2$ if $p\ll \left(\frac{r\log n}{n}\right)^{1/r}$, then a.a.s. there exists an $r$-coloring of $G(n,p)$ such that there does not exist a cover with a bounded number of components. Finally, we consider a random graph version of a classic result of Gyárfás (1977) about large monochromatic components in $r$-colored complete graphs. We show that if $p=\frac{\omega(1)}{n}$, then a.a.s. in every $r$-coloring of $G(n,p)$ there exists a monochromatic component of order at least $(1-o(1))\frac{n}{r-1}$.
Non-Linear Maximum Rank Distance Codes in the Cyclic Model for the Field Reduction of Finite Geometries
Authors: Durante Nicola , Siciliano Alessandro
Published: January 2020

In this paper we construct infinite families of non-linear maximum rank distance codes by using the setting of bilinear forms of a finite vector space. We also give a geometric description of such codes by using the cyclic model for the field reduction of finite geometries and we show that these families contain the non-linear maximum rank distance codes recently provided by Cossidente, Marino and Pavese.
Elliptic Rook and File Numbers
Authors: Schlosser Michael J. , Yoo Meesue
Published: January 2020

Utilizing elliptic weights, we construct an elliptic analogue of rook numbers for Ferrers boards. Our elliptic rook numbers generalize Garsia and Remmel's $q$-rook numbers by two additional independent parameters $a$ and $b$, and a nome $p$. The elliptic rook numbers are shown to satisfy an elliptic extension of a  factorization theorem which in the classical case was established by Goldman, Joichi and White and extended to the $q$-case by Garsia and Remmel. We obtain similar results for elliptic analogues of Garsia and Remmel's $q$-file numbers for skyline boards. We also provide an elliptic extension of the $j$-attacking model introduced by Remmel and Wachs. Various applications of our results include elliptic analogues of (generalized) Stirling numbers of the first and second kind, Lah numbers, Abel numbers, and $r$-restricted versions thereof.
Top Degree Part in $b$-Conjecture for Unicellular Bipartite Maps
Authors: Dołęga Maciej
Published: January 2020

Goulden and Jackson (1996) introduced, using Jack symmetric functions, some multivariate generating series $\psi(\boldsymbol{x}, \boldsymbol{y},\boldsymbol{z}; 1, 1+\beta)$ with an additional parameter $\beta$ that might be interpreted as a continuous deformation of the rooted bipartite maps generating series. Indeed, it has a property that for $\beta \in \{0,1\}$, it specializes to the rooted, orientable (general, i.e. orientable or not, respectively) bipartite maps generating series. They made the following conjecture: coefficients of $\psi$ are polynomials in $\beta$ with positive integer coefficients that can be written as a multivariate generating series of rooted, general bipartite maps, where the exponent of $\beta$ is an integer-valued statistics that in some sense "measures the non-orientability" of the corresponding bipartite map.We show that except two special values of $\beta = 0,1$ for which the combinatorial interpretation of the coefficients of $\psi$ is known, there exists a third special value $\beta = -1$ for which the coefficients of $\psi$ indexed by two partitions $\mu,\nu$, and one partition with only one part are given by rooted, orientable bipartite maps with arbitrary face degrees and black/white vertex degrees given by $\mu$/$\nu$, respectively. We show that this evaluation corresponds, up to a sign, to a top-degree part of the coefficients of $\psi$. As a consequence, we introduce a collection of integer-valued statistics of maps $(\eta)$ such that the top-degree of the multivariate generating series of rooted, bipartite maps with only one face (called unicellular) with respect to $\eta$ gives the top degree of the appropriate coefficients of $\psi$. Finally, we show that $b$ conjecture holds true for all rooted, unicellular bipartite maps of genus at most $2$.
Subgraph Densities in Signed Graphons and the Local Simonovits–Sidorenko Conjecture
Authors: Lovász László
Published: January 2020

We prove inequalities between the densities of various bipartite subgraphs in signed graphs. One of the main inequalities is that the density of any bipartite graph with girth $2r$ cannot exceed the density of the $2r$-cycle. This study is motivated by the Simonovits–Sidorenko conjecture, which states that the density of a bipartite graph $F$ with $m$ edges in any graph $G$ is at least the $m$-th power of the edge density of $G$. Another way of stating this is that the graph $G$ with given edge density minimizing the number of copies of $F$ is, asymptotically, a random graph. We prove that this is true locally, i.e., for graphs $G$ that are "close" to a random graph. Both kinds of results are treated in the framework of graphons (2-variable functions serving as limit objects for graph sequences), which in this context was already used by Sidorenko.
$(s,t)$-Cores: a Weighted Version of Armstrong’s Conjecture
Authors: Fayers Matthew
Published: January 2020

The study of core partitions has been very active in recent years, with the study of $(s,t)$-cores — partitions which are both $s$- and $t$-cores %mdash; playing a prominent role. A conjecture of Armstrong, proved recently by Johnson, says that the average size of an $(s,t)$-core, when $s$ and $t$ are coprime positive integers, is $\frac1{24}(s-1)(t-1)(s+t-1)$. Armstrong also conjectured that the same formula gives the average size of a self-conjugate $(s,t)$-core; this was proved by Chen, Huang and Wang.In the present paper, we develop the ideas from the author's paper [J. Combin. Theory Ser. A 118 (2011) 1525—1539], studying actions of affine symmetric groups on the set of $s$-cores in order to give variants of Armstrong's conjectures in which each $(s,t)$-core is weighted by the reciprocal of the order of its stabiliser under a certain group action. Informally, this weighted average gives the expected size of the $t$-core of a random $s$-core.
Induced Colorful Trees and Paths in Large Chromatic Graphs
Authors: Gyarfas Andras , Sarkozy Gabor
Published: January 2020

In a proper vertex coloring of a graph a subgraph is colorful if its vertices are colored with different colors. It is well-known (see for example in Gyárfás (1980)) that in every proper coloring of a $k$-chromatic graph there is a colorful path $P_k$ on $k$ vertices. The first author proved in 1987 that $k$-chromatic and triangle-free graphs have a path $P_k$ which is an induced subgraph. N.R. Aravind conjectured that these results can be put together: in every proper coloring of a $k$-chromatic triangle-free graph, there is an induced colorful $P_k$. Here we prove the following weaker result providing some evidence towards this conjecture: For a suitable function $f(k)$, in any proper coloring of an $f(k)$-chromatic graph of girth at least five, there is an induced colorful path on $k$ vertices.
Small Feedback Vertex Sets in Planar Digraphs
Authors: Esperet Louis , Lemoine Laetitia , Maffray Frédéric
Published: January 2020

Let $G$ be a directed planar graph on $n$ vertices, with no directed cycle of length less than $g\ge 4$. We prove that $G$ contains a set $X$ of vertices such that $G-X$ has no directed cycle, and $|X|\le \tfrac{5n-5}9$ if $g=4$, $|X|\le \tfrac{2n-5}4$ if $g=5$, and $|X|\le \tfrac{2n-6}{g}$ if $g\ge 6$. This improves recent results of Golowich and Rolnick.
On the Additive Bases Problem in Finite Fields
Authors: De Quehen Victoria , Hatami Hamed
Published: January 2020

We prove that if $G$ is an Abelian group and $A_1,\ldots,A_k \subseteq G$ satisfy $m A_i=G$ (the $m$-fold sumset), then $A_1+\cdots+A_k=G$ provided that $k \ge c_m \log \log |G|$. This generalizes a result of Alon, Linial, and Meshulam [Additive bases of vector spaces over prime fields. J. Combin. Theory Ser. A, 57(2):203—210, 1991] regarding so-called additive bases.
Modification of Griffiths' Result for Even Integers
Authors: Mazumdar Eshita , Sinha Sneh Bala
Published: January 2020

For a finite abelian group $G$ with $\exp(G)=n$, the arithmetical invariant $\mathsf s_A(G)$ is defined to be the least integer $k$ such that any sequence $S$ with length $k$ of elements in $G$ has a $A$ weighted zero-sum subsequence of length $n$. When $A=\{1\}$, it is the Erdős-Ginzburg-Ziv constant and is denoted by $\mathsf s (G)$. For certain class of sets $A$, we already have some general bounds for these weighted constants corresponding to the cyclic group $\mathbb{Z}_n$, which was given by Griffiths. For odd integer $n$, Adhikari and Mazumdar generalized the above mentioned results in the sense that they hold for more sets $A$. In the present paper we modify Griffiths' method for even $n$ and obtain general bound for the weighted constants for certain class of weighted sets which include sets that were not covered by Griffiths for $n\equiv 0 \pmod{4}$.
(Total) Domination in Prisms
Authors: Azarija Jernej , Henning Michael , Klavžar Sandi
Published: January 2020

Using hypergraph transversals it is proved that $\gamma_t(Q_{n+1}) = 2\gamma(Q_n)$, where $\gamma_t(G)$ and $\gamma(G)$ denote the total domination number and the domination number of $G$, respectively, and $Q_n$ is the $n$-dimensional hypercube. More generally, it is shown that if $G$ is a bipartite graph, then $\gamma_t(G \square K_2) = 2\gamma(G)$. Further, we show that the bipartiteness condition is essential by constructing, for any $k \ge 1$, a (non-bipartite) graph $G$ such that $\gamma_t(G\square K_2) = 2\gamma(G) - k$. Along the way several domination-type identities for hypercubes are also obtained.
Transitive Avoidance Games
Authors: Johnson J. Robert , Leader Imre , Walters Mark
Published: January 2020

Positional games are a well-studied class of combinatorial games. In their usual form, two players take turns to play moves in a set ('the board'), and certain subsets are designated as 'winning': the first person to occupy such a set wins the game. For these games, it is well known that (with correct play) the game cannot be a second-player win.In the avoidance (or misère) form, the first person to occupy such a set loses the game. Here it would be natural to expect that the game cannot be a first-player win, at least if the game is transitive, meaning that all points of the board look the same. Our main result is that, contrary to this expectation, there are transitive games that are first-player wins, for all board sizes which are not prime or a power of 2.Further, we show that such games can have additional properties such as stronger transitivity conditions, fast winning times, and 'small' winning sets.
Extension from Precoloured Sets of Edges
Authors: Edwards Katherine , Girão António , Van den Heuvel Jan , Kang Ross J. , Puleo Gregory J. , Sereni Jean-Sébastien
Published: January 2020

We consider precolouring extension problems for proper edge-colourings of graphs and multigraphs, in an attempt to prove stronger versions of Vizing's and Shannon's bounds on the chromatic index of (multi)graphs in terms of their maximum degree $\Delta$. We are especially interested in the following question: when is it possible to extend a precoloured matching to a colouring of all edges of a (multi)graph? This question turns out to be related to the notorious List Colouring Conjecture and other classic notions of choosability.
King-Serf Duo by Monochromatic Paths in $k$-Edge-Coloured Tournaments
Authors: Bérczi Kristóf , Joó Attila
Published: January 2020

An open conjecture of Erdős states that for every positive integer $k$ there is a (least) positive integer $f(k)$ so that whenever a tournament has its edges colored with $k$ colors, there exists a set $S$ of at most $f(k)$ vertices so that every vertex has a monochromatic path to some point in $S$. We consider a related question and show that for every (finite or infinite) cardinal $\kappa>0$ there is a cardinal $ \lambda_\kappa $ such that in every $\kappa$-edge-coloured tournament there exist disjoint vertex sets $K,S$ with total size at most $ \lambda_\kappa$ so that every vertex $ v $ has a monochromatic path of length at most two from $K$ to $v$ or from $v$ to $S$.
Bounds for Distinguishing Invariants of Infinite Graphs
Authors: Imrich Wilfried , Kalinowski Rafał , Pilśniak Monika , Shekarriz Mohammad Hadi
Published: January 2020

We consider infinite graphs. The distinguishing number $D(G)$ of a graph $G$ is the minimum number of colours in a vertex colouring of $G$ that is preserved only by the trivial automorphism. An analogous invariant for edge colourings is called the distinguishing index, denoted by $D'(G)$. We prove that $D'(G)\leq D(G)+1$. For proper colourings, we study relevant invariants called the distinguishing chromatic number $\chi_D(G)$, and the distinguishing chromatic index $\chi'_D(G)$, for vertex and edge colourings, respectively. We show that $\chi_D(G)\leq 2\Delta(G)-1$ for graphs with a finite maximum degree $\Delta(G)$, and we obtain substantially lower bounds for some classes of graphs with infinite motion. We also show that $\chi'_D(G)\leq \chi'(G)+1$, where $\chi'(G)$ is the chromatic index of $G$, and we prove a similar result $\chi''_D(G)\leq \chi''(G)+1$ for proper total colourings. A number of conjectures are formulated.
Note on a Ramsey Theorem for Posets with Linear Extensions
Authors: Arman Andrii , Rödl Vojtěch
Published: January 2020

In this note we consider a Ramsey-type result for partially ordered sets. In particular, we give an alternative short proof of a theorem for a posets with multiple linear extensions recently obtained by Solecki and Zhao (2017).
Flow Polynomials as Feynman Amplitudes and their $\alpha$-Representation
Authors: Kuptsov Andrey , Lerner Eduard , Mukhamedjanova Sofya
Published: January 2020

Let $G$ be a connected graph; denote by $\tau(G)$ the set of its spanning  trees. Let $\mathbb F_q$ be a finite field, $s(\alpha,G)=\sum_{T\in\tau(G)}  \prod_{e \in E(T)} \alpha_e$, where $\alpha_e\in \mathbb F_q$. Kontsevich  conjectured in 1997 that the number of nonzero values of $s(\alpha, G)$ is a polynomial in $q$ for all graphs. This conjecture was disproved by  Brosnan and Belkale. In this paper, using the standard technique of the Fourier transformation of Feynman amplitudes, we express the flow polynomial $F_G(q)$ in terms of the "correct" Kontsevich formula. Our formula represents $F_G(q)$ as a linear combination of Legendre symbols of $s(\alpha, H)$ with coefficients $\pm 1/q^{(|V(H)|-1)/2}$, where $H$  is a contracted graph of $G$ depending on $\alpha\in \left(\mathbb F^*_q \right)^{E(G)}$, and $|V(H)|$ is odd.
Pattern Avoidance and Young Tableaux
Authors: Mei Zhousheng , Wang Suijie
Published: January 2020

This paper extends Lewis's bijection (J. Combin. Theorey Ser. A 118, 2011) to a bijection between a more general class $\mathcal{L}(n,k,I)$ of permutations and the set of standard Young tableaux of shape $\langle (k+1)^n\rangle$, so the cardinality\[|\mathcal{L}(n,k,I)|=f^{\langle (k+1)^n\rangle},\]is independent of the choice of $I\subseteq [n]$. As a consequence, we obtain some new combinatorial realizations and identities on Catalan numbers. In the end, we raise a problem on finding a bijection between $\mathcal{L}(n,k,I)$ and $\mathcal{L}(n,k,I')$ for distinct $I$ and $I'$.
An Application of Hoffman Graphs for Spectral Characterizations of Graphs
Authors: Yang Qianqian , Abiad Aida , Koolen Jack H.
Published: January 2020

In this paper, we present the first application of Hoffman graphs for spectral characterizations of graphs. In particular, we show that the 2-clique extension of the $(t+1)\times (t+1)$-grid is determined by its spectrum when $t$ is large enough. This result will help to show that the Grassmann graph $J_2(2D,D)$ is determined by its intersection numbers as a distance regular graph, if $D$ is large enough.
Rainbow Turán Problems for Paths and Forests of Stars
Authors: Johnston Daniel , Palmer Cory , Sarkar Amites
Published: January 2020

For a fixed graph $F$, we would like to determine the maximum number of edges in a properly edge-colored graph on $n$ vertices which does not contain a rainbow copy of $F$, that is, a copy of $F$ all of whose edges receive a different color. This maximum, denoted by $ex^*(n,F)$, is the rainbow Turán number of $F$, and its systematic study was initiated by Keevash, Mubayi, Sudakov and Verstraëte [Combinatorics, Probability and Computing 16 (2007)]. We determine $ex^*(n,F)$ exactly when $F$ is a forest of stars, and give bounds on $ex^*(n,F)$ when $F$ is a path with $l$ edges, disproving a conjecture in the aforementioned paper for $l=4$.
Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition
Authors: Bahrani Maryam , Lumbroso Jérémie
Published: January 2020

Forbidden characterizations may sometimes be the most natural way to describe families of graphs, and yet these characterizations are usually very hard to exploit for enumerative purposes.By building on the work of Gioan and Paul (2012) and Chauve et al.(2014), we show a methodology by which we constrain a split-decomposition tree to avoid certain patterns, thereby avoiding the corresponding induced subgraphs in the original graph.We thus provide the grammars and full enumeration for a wide set of graph classes: ptolemaic, block, and variants of cactus graphs (2,3-cacti, 3-cacti and 4-cacti). In certain cases, no enumeration was known (ptolemaic, 4-cacti); in other cases, although the enumerations were known, an abundant potential is unlocked by the grammars we provide (in terms of asymptotic analysis, random generation, and parameter analyses, etc.).We believe this methodology here shows its potential; the natural next step to develop its reach would be to study split-decomposition trees which contain certain prime nodes. This will be the object of future work.
Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups?
Authors: Bulatov Andrei A. , Karpova Olga , Shur Arseny M. , Startsev Konstantin
Published: January 2020

The words separation problem, originally formulated by Goralcik and Koubek (1986), is stated as follows. Let $Sep(n)$ be the minimum number such that for any two words of length $\le n$ there is a deterministic finite automaton with $Sep(n)$ states, accepting exactly one of them. The problem is to find the asymptotics of the function $Sep$. This problem is inverse to finding the asymptotics of the length of the shortest identity in full transformation semigroups $T_k$. The known lower bound on $Sep$ stems from the unary identity in $T_k$. We find the first series of identities in $T_k$ which are shorter than the corresponding unary identity for infinitely many values of $k$, and thus slightly improve the lower bound on $Sep(n)$. Then we present some short positive identities in symmetric groups, improving the lower bound on separating words by permutational automata by a multiplicative constant. Finally, we present the results of computer search for short identities for small $k$.
On the Smallest Non-Trivial Tight Sets in Hermitian Polar Spaces
Authors: De Beule Jan , Metsch Klaus
Published: January 2020

We show that an $x$-tight set of the Hermitian polar spaces $\mathrm{H}(4,q^2)$ and $\mathrm{H}(6,q^2)$ respectively, is the union of $x$ disjoint generators of the polar space provided that $x$ is small compared to $q$. For $\mathrm{H}(4,q^2)$ we need the bound $x<q+1$ and we can show that this bound is sharp.
On $r$-Uniform Linear Hypergraphs with no Berge-$K_{2,t}$
Authors: Timmons Craig
Published: January 2020

Let $\mathcal{F}$ be an $r$-uniform hypergraph and $G$ be a multigraph. The hypergraph $\mathcal{F}$ is a Berge-$G$ if there is a bijection $f: E(G) \rightarrow E( \mathcal{F} )$ such that $e \subseteq f(e)$ for each $e \in E(G)$.  Given a family of multigraphs $\mathcal{G}$, a hypergraph $\mathcal{H}$ is said to be $\mathcal{G}$-free if for each $G \in \mathcal{G}$, $\mathcal{H}$ does not contain a subhypergraph that is isomorphic to a Berge-$G$. We prove bounds on the maximum number of edges in an $r$-uniform linear hypergraph that is $K_{2,t}$-free. We also determine an asymptotic formula for the maximum number of edges in a linear 3-uniform 3-partite hypergraph that is $\{C_3 , K_{2,3} \}$-free.
Abaci Structures of $(s, ms\pm1)$-Core Partitions
Authors: Nath Rishi , Sellers James A.
Published: January 2020

We develop a geometric approach to the study of $(s,ms-1)$-core and $(s,ms+1)$-core partitions through the associated $ms$-abaci. This perspective yields new proofs for results of H. Xiong and A. Straub on the enumeration of $(s, s+1)$ and $(s,ms-1)$-core partitions with distinct parts. It also enumerates $(s, ms+1)$-cores with distinct parts. Furthermore, we calculate the weight of the $(s, ms-1,ms+1)$-core partition with the largest number of parts. Finally we use 2-core partitions to enumerate self-conjugate core partitions with distinct parts. The central idea is that the $ms$-abaci of maximal $(s,ms\pm1)$-cores can be built up from $s$-abaci of $(s,s\pm 1)$-cores in an elegant way.
On the Structure of the Power Graph and the Enhanced Power Graph of a Group
Authors: Aalipour Ghodratollah , Akbari Saieed , Cameron Peter J. , Nikandish Reza , Shaveisi Farzad
Published: January 2020

Let $G$ be a group‎. ‎The power graph of $G$ is a graph with the vertex‎ ‎set $G$‎, ‎having an edge between two elements whenever one is a power of the other‎. ‎We characterize nilpotent groups whose power graphs have finite independence number‎. ‎For a bounded exponent group‎, ‎we prove its power graph is a perfect graph and we determine‎ ‎its clique/chromatic number‎. ‎Furthermore‎, ‎it is proved that for every group $G$‎, ‎the clique number of the power graph of $G$ is at most countably infinite‎. ‎We also measure how close the power graph is to the commuting graph by introducing a new graph which lies in between‎. ‎We call this new graph as the enhanced power graph‎. ‎For an arbitrary pair of these three graphs we characterize finite groups for which this pair of graphs are equal‎.
Operads of Finite Posets
Authors: Fauvet Frédéric , Foissy Loïc , Manchon Dominique
Published: January 2020

We describe four natural operad structures on the linear species of finite posets. The three last ones are set-theoretical and can be seen as a simplified version of the first, the same way the NAP operad behaves with respect to the pre-Lie operad. Moreover the two first ones are isomorphic.
Subdivisions in Digraphs of Large Out-Degree or Large Dichromatic Number
Authors: Aboulker Pierre , Cohen Nathann , Havet Frédéric , Lochet William , Moura Phablo F. S. , Thomassé Stéphan
Published: January 2020

In 1985, Mader conjectured the existence of a function $f$ such that every digraph with minimum out-degree at least $f(k)$ contains a subdivision of the transitive tournament of order $k$. This conjecture is still completely open, as the existence of $f(5)$ remains unknown. In this paper, we show that if $D$ is an oriented path, or an in-arborescence (i.e., a tree with all edges oriented towards the root) or the union of two directed paths from $x$ to $y$ and a directed path from $y$ to $x$, then every digraph with minimum out-degree large enough contains a subdivision of $D$. Additionally, we study Mader's conjecture considering another graph parameter. The dichromatic number of a digraph $D$ is the smallest integer $k$ such that $D$ can be partitioned into $k$ acyclic subdigraphs. We show that any digraph with dichromatic number greater than $4^m (n-1)$ contains every digraph with $n$ vertices and $m$ arcs as a subdivision. We show that any digraph with dichromatic number greater than $4^m (n-1)$ contains every digraph with $n$ vertices and $m$ arcs as a subdivision.
Subgraphs with Large Minimum $\ell$-Degree in Hypergraphs where Almost All $\ell$-Degrees are Large
Authors: Falgas-Ravry Victor , Lo Allan
Published: January 2020

Let $G$ be an $r$-uniform hypergraph on $n$ vertices such that all but at most $\varepsilon \binom{n}{\ell}$ $\ell$-subsets of vertices have degree at least $p \binom{n-\ell}{r-\ell}$. We show that $G$ contains a large subgraph with high minimum $\ell$-degree.
On the Maximum Density of Fixed Strongly Connected Subtournaments
Authors: Coregliano Leonardo N. , Parente Roberto F. , Sato Cristiane M.
Published: January 2020

We study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5.
Behavior of Digital Sequences Through Exotic Numeration Systems
Authors: Leroy Julien , Rigo Michel , Stipulanti Manon
Published: January 2020

Many digital functions studied in the literature, e.g., the summatory function of the base-$k$ sum-of-digits function, have a behavior showing some periodic fluctuation. Such functions are usually studied using techniques from analytic number theory or linear algebra. In this paper we develop a method based on exotic numeration systems and we apply it on two examples motivated by the study of generalized Pascal triangles and binomial coefficients of words.
Obstructions to Combinatorial Formulas for Plethysm
Authors: Kahle Thomas , Michałek Mateusz
Published: January 2020

Motivated by questions of Mulmuley and Stanley we investigate quasi-polynomials arising in formulas for plethysm. We demonstrate, on the examples of $S^3(S^k)$ and $S^k(S^3)$, that these need not be counting functions of inhomogeneous polytopes of dimension equal to the degree of the quasi-polynomial. It follows that these functions are not, in general, counting functions of lattice points in any scaled convex bodies, even when restricted to single rays. Our results also apply to special rectangular Kronecker coefficients.
On Ehrhart Polynomials of Lattice Triangles
Authors: Hofscheier Johannes , Nill Benjamin , Öberg Dennis
Published: January 2020

The Ehrhart polynomial of a lattice polygon $P$ is completely determined by the pair $(b(P),i(P))$ where $b(P)$ equals the number of lattice points on the boundary and $i(P)$ equals the number of interior lattice points. All possible pairs $(b(P),i(P))$ are completely described by a theorem due to Scott. In this note, we describe the shape of the set of pairs $(b(T),i(T))$ for lattice triangles $T$ by finding infinitely many new Scott-type inequalities.