bluuebunny/crossref_metadata_2025 huggingface dataset:
Identifying Codes in Vertex-Transitive Graphs and Strongly Regular Graphs
Authors: Gravier Sylvain , Parreau Aline , Rottey Sara , Storme Leo , Vandomme Élise
Published: January 2020

We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the size of optimal integer and fractional solutions is between 1 and $2\ln(|V|)+1$ where $V$ is the set of vertices of the graph. We focus on vertex-transitive graphs for which we can compute the exact fractional solution. There are known examples of vertex-transitive graphs that reach both bounds. We exhibit infinite families of vertex-transitive graphs with integer and fractional identifying codes of order $|V|^{\alpha}$ with $\alpha \in \{\frac{1}{4},\frac{1}{3},\frac{2}{5}\}$. These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs.
A Combinatorial Approach to the $q,t$-Symmetry Relation in Macdonald Polynomials
Authors: Gillespie Maria Monks
Published: January 2020

Using the combinatorial formula for the transformed Macdonald polynomials of Haglund, Haiman, and Loehr, we investigate the combinatorics of the symmetry relation $\widetilde{H}_\mu(\mathbf{x};q,t)=\widetilde{H}_{\mu^\ast}(\mathbf{x};t,q)$. We provide a purely combinatorial proof of the relation in the case of Hall-Littlewood polynomials ($q=0$) when $\mu$ is a partition with at most three rows, and for the coefficients of the square-free monomials in $\mathbf{x}$ for all shapes $\mu$. We also provide a proof for the full relation in the case when $\mu$ is a hook shape, and for all shapes at the specialization $t=1$. Our work in the Hall-Littlewood case reveals a new recursive structure for the cocharge statistic on words.
On the Strong Chromatic Index of Sparse Graphs
Authors: DeOrsey Philip , Ferrara Michael , Graber Nathan , Hartke Stephen G. , Nelsen Luke L. , Sullivan Eric , Jahanbekam Sogol , Lidický Bernard , Stolee Derrick , White Jennifer
Published: January 2020

The strong chromatic index of a graph $G$, denoted $\chi'_s(G)$, is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted $\chi'_{s,\ell}(G)$, is the least integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors.We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with ${\rm girth}(G) \geq 41$ then $\chi'_{s,\ell}(G) \leq 5$, answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and ${\rm girth}(G) \geq 30$, then $\chi_s'(G) \leq 5$, improving a bound from the same paper.Finally, if $G$ is a planar graph with maximum degree at most four and ${\rm girth}(G) \geq 28$, then $\chi'_s(G)N \leq 7$, improving a more general bound of Wang and Zhao from [Odd graphs and its applications to the strong edge coloring, Applied Mathematics and Computation, 325 (2018), 246-251] in this case.
Growth Rates of Groups associated with Face 2-Coloured Triangulations and Directed Eulerian Digraphs on the Sphere
Authors: McCourt Thomas A.
Published: January 2020

Let $\mathcal{G}$ be a properly face $2$-coloured (say black and white) piecewise-linear triangulation of the sphere with vertex set $V$. Consider the abelian group $\mathcal{A}_W$ generated by the set $V$, with relations $r+c+s=0$ for all white triangles with vertices $r$, $c$ and $s$. The group $\mathcal{A}_B$ can be defined similarly, using black triangles. These groups are related in the following manner $\mathcal{A}_W\cong\mathcal{A}_B\cong\mathbb{Z}\oplus\mathbb{Z}\oplus\mathcal{C}$ where $\mathcal{C}$ is a finite abelian group.The finite torsion subgroup $\mathcal{C}$ is referred to as the canonical group of the triangulation. Let $m_t$ be the maximal order of $\mathcal{C}$ over all properly face 2-coloured spherical triangulations with $t$ triangles of each colour. By relating such a triangulation to certain directed Eulerian spherical embeddings of digraphs whose abelian sand-pile groups are isomorphic to the triangulation's canonical group we provide improved upper and lower bounds for $\lim \sup_{t\rightarrow\infty}(m_t)^{1/t}$.
Weakly Distance-Regular Digraphs of Valency Three, I
Authors: Yang Yuefeng , Lv Benjian , Wang Kaishun
Published: January 2020

Suzuki (2004)  classified thin weakly distance-regular digraphs and proposed the project to classify weakly distance-regular digraphs of valency 3. The case of girth 2 was classified by the third author (2004) under the assumption of the commutativity. In this paper, we continue this project and classify these digraphs with girth more than 2 and two types of arcs.
Another Proof of the Harer-Zagier Formula
Authors: Pittel Boris
Published: January 2020

For a regular $2n$-gon there are $(2n-1)!!$ ways to match and glue the $2n$ sides. The Harer-Zagier bivariate generating function enumerates the gluings by $n$ and the genus $g$ of the attendant surface and leads to a recurrence equation for the counts of gluings with parameters $n$ and $g$. This formula was originally obtained using multidimensional Gaussian integrals. Soon after, Jackson and later Zagier found alternative proofs using symmetric group characters. In this note we give a different, characters-based, proof. Its core is computing and marginally inverting the Fourier transform of the underlying probability measure on $S_{2n}$. A key ingredient is the Murnaghan-Nakayama rule for the characters associated with one-hook Young diagrams.
Extremal Permutations in Routing Cycles
Authors: He Jinhua , Valentin Louis A. , Yin Xiaoyan , Yu Gexin
Published: January 2020

Let $G$ be a graph whose vertices are labeled $1,\ldots,n$, and $\pi$ be a permutation on $[n]:=\{1,2,\ldots, n\}$. A pebble $p_i$ that is initially placed at the vertex $i$ has destination $\pi(i)$ for each $i\in [n]$. At each step, we choose a matching and swap the two pebbles on each of the edges. Let $rt(G, \pi)$, the routing number for $\pi$, be the minimum number of steps necessary for the pebbles to reach their destinations.Li, Lu and Yang proved that $rt(C_n, \pi)\le n-1$ for every permutation $\pi$ on the $n$-cycle $C_n$ and conjectured that for $n\geq 5$, if $rt(C_n, \pi) = n-1$, then $\pi = 23\cdots n1$ or its inverse. By a computer search, they showed that the conjecture holds for $n<8$. We prove in this paper that the conjecture holds for all even $n\ge 6$.
Avoiding Letter Patterns in Ternary Square-Free Words
Authors: Petrova Elena A.
Published: January 2020

We consider special patterns of lengths 5 and 6 in a ternary alphabet. We show that some of them are unavoidable in square-free words and prove avoidability of the other ones. Proving the main results, we use  Fibonacci words as codes of ternary words in some natural coding system and show that they can be decoded to square-free words avoiding the required patterns. Furthermore, we estimate the minimal local (critical) exponents of square-free words with such avoidance properties.
A Curved Brunn Minkowski Inequality for the Symmetric Group
Authors: Neeranartvong Weerachai , Novak Jonathan , Sothanaphan Nat
Published: January 2020

In this paper, we construct an injection $A \times B \rightarrow M \times M$ from the product of any two nonempty subsets of the symmetric group into the square of their midpoint set, where the metric is that corresponding to the conjugacy class of transpositions. If $A$ and $B$ are disjoint, our construction allows to inject two copies of $A \times B$ into $M \times M$. These injections imply a positively curved Brunn-Minkowski inequality for the symmetric group analogous to that obtained by Ollivier and Villani for the hypercube. However, while Ollivier and Villani's inequality is optimal, we believe that the curvature term in our inequality can be improved. We identify a hypothetical concentration inequality in the symmetric group and prove that it yields an optimally curved Brunn-Minkowski inequality.
The Smith and Critical Groups of the Square Rook's Graph and its Complement
Authors: Ducey Joshua E. , Gerhard Jonathan , Watson Noah
Published: January 2020

Let $R_{n}$ denote the graph with vertex set consisting of the squares of an $n \times n$ grid, with two squares of the grid adjacent when they lie in the same row or column.  This is the square rook's graph, and can also be thought of as the Cartesian product of two complete graphs of order $n$, or the line graph of the complete bipartite graph $K_{n,n}$.  In this paper we compute the Smith group and critical group of the graph $R_{n}$ and its complement.  This is equivalent to determining the Smith normal form of both the adjacency and Laplacian matrix of each of these graphs.  In doing so we verify a 1986 conjecture of Rushanan.
Disproof of a Conjecture of Neumann-Lara
Authors: Llano Bernardo , Olsen Mika
Published: January 2020

We disprove the following conjecture due to Víctor Neumann-Lara: for every pair $(r,s)$ of integers such that $r\geq s\geq 2$, there is an infinite set of circulant tournaments $T$ such that the dichromatic number and the cyclic triangle free disconnection of $T$ are equal to $r$ and $s$, respectively. Let $\mathcal{F}_{r,s}$ denote the set of circulant tournaments $T$ with $dc(T)=r$ and $\overrightarrow{\omega }_{3}\left( T\right) =s$. We show that for every integer $s\geq 4$ there exists a lower bound $b(s)$ for the dichromatic number $r$ such that $\mathcal{F}_{r,s}=\emptyset $ for every $r<b(s)$. We construct an infinite set of circulant tournaments $T$ such that $dc(T)=b(s)$ and $\overrightarrow{\omega }_{3}(T)=s$ and give an upper bound $B(s)$ for the dichromatic number $r$ such that for every $r\geq B(s)$ there exists an infinite set $\mathcal{F}_{r,s}$ of circulant tournaments. Some infinite sets $\mathcal{F}_{r,s}$ of circulant tournaments are given for $b(s)<r<B(s)$.
Regular Graphs are Antimagic
Authors: Bérczi Kristóf , Bernáth Attila , Vizer Máté
Published: January 2020

An undirected simple graph $G=(V,E)$ is called antimagic if there exists an injective function $f:E\rightarrow\{1,\dots,|E|\}$ such that $\sum_{e\in E(u)} f(e)\neq\sum_{e\in E(v)} f(e)$ for any pair of different nodes $u,v\in V$. In this note we prove — with a slight modification of an argument of Cranston et al. — that $k$-regular graphs are antimagic for $k\ge 2$.

 

A corrigendum was added to this paper on May 2, 2019.
Connected Even Factors in the Square of Essentially 2-Edge-connected Graph
Authors: Ekstein Jan , Wu Baoyindureng , Xiong Liming
Published: January 2020

An essentially $k$-edge connected graph $G$ is a connected graph such that deleting less than $k$ edges from $G$ cannot result in two nontrivial components. In this paper we prove that if an essentially 2-edge-connected graph $G$ satisfies that for any pair of leaves at distance 4 in $G$ there exists another leaf of $G$ that has distance 2 to one of them, then the square $G^2$ has a connected even factor with maximum degree at most 4. Moreover we show that, in general, the square of essentially 2-edge-connected graph does not contain a connected even factor with bounded maximum degree.
Inversions of Semistandard Young Tableaux
Authors: Drube Paul
Published: January 2020

A tableau inversion is a pair of entries from the same column of a row-standard tableau that lack the relative ordering necessary to make the tableau column-standard. An $i$-inverted Young tableau is a row-standard tableau with precisely $i$ inversion pairs, and may be interpreted as a generalization of (column-standard) Young tableaux. Inverted Young tableaux that lack repeated entries were introduced by Fresse to calculate the Betti numbers of Springer fibers in Type A, and were later developed as combinatorial objects in their own right by Beagley and Drube. This paper generalizes earlier notions of tableau inversions to row-standard tableaux with repeated entries, yielding an interesting new generalization of semistandard (as opposed to merely standard) Young tableaux. We develop a closed formula for the maximum numbers of inversion pairs for a row-standard tableau with a specific shape and content, and show that the number of $i$-inverted tableaux of a given shape is invariant under permutation of content. We then enumerate $i$-inverted Young tableaux for a variety of shapes and contents, and generalize an earlier result that places $1$-inverted Young tableaux of a general shape in bijection with $0$-inverted Young tableaux of a variety of related shapes.
Self-dual Planar Hypergraphs and Exact Bond Percolation Thresholds
Authors: Wierman John C. , Ziff Robert M.
Published: January 2020

A generalized star-triangle transformation and a concept of triangle-duality have been introduced recently in the physics literature to predict exact percolation threshold values of several lattices. Conditions for the solution of bond percolation models are investigated, and an infinite class of lattice graphs for which exact bond percolation thresholds may be rigorously determined as the solution of a polynomial equation are identified. This class is naturally described in terms of hypergraphs, leading to definitions of planar hypergraphs and self-dual planar hypergraphs. There exist infinitely many self-dual planar 3-uniform hypergraphs, and, as a consequence, there exist infinitely many real numbers $a \in [0,1]$ for which there are infinitely many lattices that have bond percolation threshold equal to $a$.
An Extension of MacMahon's Equidistribution Theorem to Ordered Multiset Partitions
Authors: Wilson Andrew Timothy
Published: January 2020

A classical result of MacMahon states that inversion number and major index have the same distribution over permutations of a given multiset. In this work, we prove a strengthening of MacMahon's theorem originally conjectured by Haglund. Our result can be seen as an equidistribution theorem over the ordered partitions of a multiset into sets, which we call ordered multiset partitions. Our proof is bijective and involves a new generalization of Carlitz's insertion method. This generalization leads to a new extension of Macdonald polynomials for hook shapes. We use our main theorem to show that these polynomials are symmetric and we give their Schur expansion.

 

A corrigendum was added 17 September 2019.
A Lower Bound on the Diameter of the Flip Graph
Authors: Frati Fabrizio
Published: January 2020

The flip graph is the graph whose vertices correspond to non-isomorphic combinatorial triangulations and whose edges connect pairs of triangulations that can be obtained from one another by flipping a single edge. In this note we show that the diameter of the flip graph is at least $\frac{7n}{3} + \Theta(1)$, improving upon the previous $2n + \Theta(1)$ lower bound.
Sets with Few Differences in Abelian Groups
Authors: Lee Mitchell
Published: January 2020

Let $(G, +)$ be an abelian group. In 2004, Eliahou and Kervaire found an explicit formula for the smallest possible cardinality of the sumset $A+A$, where $A \subseteq G$ has fixed cardinality $r$. We consider instead the smallest possible cardinality of the difference set $A-A$, which is always greater than or equal to the smallest possible cardinality of $A+A$ and can be strictly greater. We conjecture a formula for this quantity and prove the conjecture in the case that $G$ is an elementary abelian $p$-group. This resolves a conjecture of Bajnok and Matzke on signed sumsets.
On Ultralimits of Sparse Graph Classes
Authors: Pilipczuk Michał , Toruńczyk Szymon
Published: January 2020

The notion of nowhere denseness is one of the central concepts of the recently developed theory of sparse graphs. We study the properties of nowhere dense graph classes by investigating appropriate limit objects defined using the ultraproduct construction. It appears that different equivalent definitions of nowhere denseness, for example via quasi-wideness or the splitter game, correspond to natural notions for the limit objects that are conceptually simpler and allow for less technically involved reasonings.
Red-Blue Clique Partitions and (1-1)-Transversals
Authors: Gyárfás Alfréd , Lehel Jeno
Published: January 2020

Motivated by the problem of Gallai on (1-1)-transversals of $2$-intervals, it was proved by the authors in 1969 that if the edges of a complete graph $K$ are colored with red and blue (both colors can appear on an edge) so that there is no monochromatic induced $C_4$ and $C_5$ then the vertices of $K$ can be partitioned into a red and a blue clique. Aharoni, Berger, Chudnovsky and Ziani recently strengthened this by showing that it is enough to assume that there is no induced monochromatic $C_4$ and there is no induced $C_5$ in one of the colors. Here this is strengthened further, it is enough to assume that there is no monochromatic induced $C_4$ and there is no $K_5$ on which both color classes induce a $C_5$.We also answer a question of Kaiser and Rabinovich, giving an example of six $2$-convex sets in the plane such that any three intersect but there is no (1-1)-transversal for them.
Triangular Fully Packed Loop Configurations of Excess 2
Authors: Beil Sabine
Published: January 2020

Triangular fully packed loop configurations (TFPLs) came up in the study of fully packed loop configurations on a square (FPLs) corresponding to link patterns with a large number of nested arches. To a TFPL is assigned a triple $(u,v;w)$ of $01$-words encoding its boundary conditions which must necessarily satisfy that $d(u)+d(v)\leq d(w)$, where $d(u)$ denotes the number of inversions in $u$. Wieland gyration, on the other hand, was invented to show the rotational invariance of the numbers of FPLs having given link patterns. Later, Wieland drift — a map on TFPLs that is based on Wieland gyration — was defined. The main contribution of this article will be a linear expression for the number of TFPLs with boundary $(u,v;w)$ where $d(w)-d(u)-d(v)=2$ in terms of numbers of stable TFPLs, that is, TFPLs invariant under Wieland drift. This linear expression generalises already existing enumeration results for TFPLs with boundary $(u,v;w)$ where $d(w)-d(u)-d(v)=0,1$.
The Rectangle Covering Number of Random Boolean Matrices
Authors: Pourmoradnasseri Mozhgan , Theis Dirk Oliver
Published: January 2020

The rectangle covering number of an $n$-by-$n$ Boolean matrix $M$ is the smallest number of 1-rectangles which are needed to cover all the 1-entries of $M$. Its binary logarithm is the Nondeterministic Communication Complexity, and it equals the chromatic number of a graph $G(M)$ obtained from $M$ by a construction of Lovasz and Saks.We determine the rectangle covering number and related parameters (clique size, independence ratio, fractional chromatic number of $G(M)$) of random Boolean matrices, where each entry is 1 with probability $p = p(n)$, and the entries are independent.
On Some Conjectures Concerning Critical Independent Sets of a Graph
Authors: Short Taylor
Published: January 2020

Let $G$ be a simple graph with vertex set $V(G)$. A set $S\subseteq V(G)$ is independent if no two vertices from $S$ are adjacent. For $X\subseteq V(G)$, the difference of $X$ is $d(X) = |X|-|N(X)|$ and an independent set $A$ is critical if $d(A) = \max \{d(X): X\subseteq V(G) \text{ is an independent set}\}$ (possibly $A=\emptyset$). Let $\text{nucleus}(G)$ and $\text{diadem}(G)$ be the intersection and union, respectively, of all maximum size critical independent sets in $G$. In this paper, we will give two new characterizations of Konig-Egervary graphs involving $\text{nucleus}(G)$ and $\text{diadem}(G)$. We also prove a related lower bound for the independence number of a graph. This work answers several conjectures posed by Jarden, Levit, and Mandrescu.
Multi-Eulerian Tours of Directed Graphs
Authors: Farrell Matthew , Levine Lionel
Published: January 2020

Not every graph has an Eulerian tour. But every finite, strongly connected graph has a multi-Eulerian tour, which we define as a closed path that uses each directed edge at least once, and uses edges e and f the same number of times whenever tail(e)=tail(f). This definition leads to a simple generalization of the BEST Theorem. We then show that the minimal length of a multi-Eulerian tour is bounded in terms of the Pham index, a measure of 'Eulerianness'.
Strong Emergence of Wave Patterns on Kadanoff Sandpiles
Authors: Perrot Kévin , Rémila Eric
Published: January 2020

Emergence is easy to exhibit, but very hard to formally explain. This paper deals with square sand grains moving around on nicely stacked columns in one dimension (the physical sandpile is two dimensional, but the support of sand columns is one dimensional). The Kadanoff sandpile model is a discrete dynamical system describing the evolution of finitely many sand grains falling from an hourglass (or equivalently from a finite stack of sand grains) to a stable configuration. The repeated application of a simple local rule let grains move until reaching a fixed point. The difficulty of understanding its behavior, despite the simplicity of its rule, is the main interest of the model. In this paper we prove the emergence of exact wave patterns periodically repeated on fixed points. Remarkably, those regular patterns do not cover the entire fixed point, but eventually emerge from a seemingly disordered segment: grains are added on the left, triggering avalanches that become regular as they fall down the sandpile. The proof technique we set up associated arguments of linear algebra and combinatorics, which interestingly allow to formally demonstrate the emergence of regular patterns without requiring a precise understanding of the non-regular initial segment's dynamic.
Modeling Limits in Hereditary Classes: Reduction and Application to Trees
Authors: Nešetřil Jaroslav , Ossona de Mendez Patrice
Published: January 2020

The study of limits of graphs led to elegant limit structures for sparse and dense graphs. This has been unified and generalized by the authors in a more general setting combining analytic tools and model theory to ${\rm FO}$-limits (and $X$-limits) and to the notion of modeling. The existence of modeling limits was established for sequences in a bounded degree class and, in addition, to the case of classes of trees with bounded height and of graphs with bounded tree depth. The natural obstacle for the existence of modeling limit for a monotone class of graphs is the nowhere dense property and it has been conjectured that this is a sufficient condition. Extending earlier results here we derive several general results which present a realistic approach to this conjecture. As an example we then prove that the class of all finite trees admits modeling limits.
Symmetric Graphs with Respect to Graph Entropy
Authors: Changiz Rezaei Seyed Saeed , Chiniforooshan Ehsan
Published: January 2020

Let $F_G(P)$ be a functional defined on the set of all the probability distributions on the vertex set of a graph $G$. We say that $G$ is symmetric with respect to $F_G(P)$ if the uniform distribution on $V(G)$ maximizes $F_G(P)$. Using the combinatorial definition of the entropy of a graph in terms of its vertex packing polytope and the relationship between the graph entropy and fractional chromatic number, we characterize all graphs which are symmetric with respect to graph entropy. We show that a graph is symmetric with respect to graph entropy if and only if its vertex set can be uniformly covered by its maximum size independent sets. This is also equivalent to saying that the fractional chromatic number of $G$, $\chi_f(G)$, is equal to $\frac{n}{\alpha(G)}$, where $n = |V(G)|$ and $\alpha(G)$ is the independence number of $G$. Furthermore, given any strictly positive probability distribution $P$ on the vertex set of a graph $G$, we show that $P$ is a maximizer of the entropy of graph $G$ if and only if its vertex set can be uniformly covered by its maximum weighted independent sets. We also show that the problem of deciding if a graph is symmetric with respect to graph entropy, where the weight of the vertices is given by probability distribution $P$, is co-NP-hard.
Weak and Strong Versions of the 1-2-3 Conjecture for Uniform Hypergraphs
Authors: Bennett Patrick , Dudek Andrzej , Frieze Alan , Helenius Laars
Published: January 2020

Given an $r$-uniform hypergraph $H=(V,E)$ and a weight function $\omega:E\to\{1,\dots,w\}$, a coloring of vertices of~$H$, induced by~$\omega$, is defined by $c(v) = \sum_{e\ni v} w(e)$ for all $v\in V$. If there exists such a coloring that is strong (that means in each edge no color appears more than once), then we say that $H$ is strongly $w$-weighted. Similarly, if the coloring is weak (that means there is no monochromatic edge), then we say that $H$ is weakly $w$-weighted. In this paper, we show that almost all 3 or 4-uniform hypergraphs are strongly 2-weighted (but not 1-weighted) and almost all $5$-uniform hypergraphs are either 1 or 2 strongly weighted (with a nontrivial distribution). Furthermore, for $r\ge 6$ we show that almost all $r$-uniform hypergraphs are strongly 1-weighted. We complement these results by showing that almost all 3-uniform hypergraphs are weakly 2-weighted but not 1-weighted and for $r\ge 4$ almost all $r$-uniform hypergraphs are weakly 1-weighted. These results extend a previous work of Addario-Berry, Dalal and Reed for graphs. We also prove general lower bounds and show that there are $r$-uniform hypergraphs which are not strongly $(r^2-r)$-weighted and not weakly 2-weighted. Finally, we show that determining whether a particular uniform hypergraph is strongly 2-weighted is NP-complete.
Coloring Non-Crossing Strings
Authors: Esperet Louis , Gonçalves Daniel , Labourel Arnaud
Published: January 2020

For a family of geometric objects in the plane $\mathcal{F}=\{S_1,\ldots,S_n\}$, define $\chi(\mathcal{F})$ as the least integer $\ell$ such that the elements of $\mathcal{F}$ can be colored with $\ell$ colors, in such a way that any two intersecting objects have distinct colors. When $\mathcal{F}$ is a set of pseudo-disks that may only intersect on their boundaries, and such that any point of the plane is contained in at most $k$ pseudo-disks, it can be proven that $\chi(\mathcal{F})\le 3k/2 + o(k)$ since the problem is equivalent to cyclic coloring of plane graphs. In this paper, we study the same problem when pseudo-disks are replaced by a family $\mathcal{F}$ of pseudo-segments (a.k.a. strings) that do not cross. In other words, any two strings of $\mathcal{F}$ are only allowed to "touch" each other. Such a family is said to be $k$-touching if no point of the plane is contained in more than $k$ elements of $\mathcal{F}$. We give bounds on $\chi(\mathcal{F})$ as a function of $k$, and in particular we show that $k$-touching segments can be colored with $k+5$ colors. This partially answers a question of Hliněný (1998) on the chromatic number of contact systems of strings.
A Hopf Algebraic Approach to Schur Function Identities
Authors: Yeats Karen
Published: January 2020

Using cocommutativity of the Hopf algebra of symmetric functions, certain skew Schur functions are proved to be equal. Some of these skew Schur function identities are new.
A Generalization of Sperner's Theorem on Compressed Ideals
Authors: Mu Lili , Wang Yi
Published: January 2020

Let $[n]=\{1,2,\ldots,n\}$ and $\mathscr{B}_n=\{A: A\subseteq [n]\}$. A family $\mathscr{A}\subseteq \mathscr{B}_n$ is a Sperner family if $A\nsubseteq B$ and $B\nsubseteq A$ for distinct $A,B\in\mathscr{A}$. Sperner's theorem states that the density of the largest Sperner family in $\mathscr{B}_n$ is $\binom{n}{\left\lceil{n/2}\right\rceil}/2^n$. The objective of this note is to show that the same holds if $\mathscr{B}_n$ is replaced by compressed ideals over $[n]$.
Integral Quartic Cayley Graphs on Abelian Groups
Authors: Abdollahi A. , Vatandoost E.
Published: January 2020

A graph is called integral, if its adjacency eigenvalues are integers. In this paper we determine integral quartic Cayley graphs on finite abelian groups. As a side result we show that there are exactly $27$ connected integral Cayley graphs up to $11$ vertices.
The Ramsey Number $r(K_5-P_3,K_5)$
Authors: Boza Luis
Published: January 2020

For two given graphs $G_1$ and $G_2$, the Ramsey number $r(G_1,G_2)$ is the smallest integer $n$ such that for any graph $G$ of order $n$, either $G$ contains $G_1$ or the complement of $G$ contains $G_2$. Let $K_m$ denote a complete graph of order $m$ and $K_n-P_3$ a complete graph of order $n$ without two incident edges. In this paper, we prove that $r(K_5-P_3,K_5)=25$ without help of computer algorithms.
A Sharp Bound for the Product of Weights of Cross-Intersecting Families
Authors: Borg Peter
Published: January 2020

Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be cross-intersecting if each set in $\mathcal{A}$ intersects each set in $\mathcal{B}$. For any two integers $n$ and $k$ with $1 \leq k \leq n$, let ${[n] \choose \leq k}$ denote the family of subsets of $\{1, \dots, n\}$ of size at most $k$, and let $\mathcal{S}_{n,k}$ denote the family of sets in ${[n] \choose \leq k}$ that contain $1$. The author recently showed that if $\mathcal{A} \subseteq {[m] \choose \leq r}$, $\mathcal{B} \subseteq {[n] \choose \leq s}$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then $|\mathcal{A}||\mathcal{B}| \leq \mathcal{S}_{m,r}||\mathcal{S}_{n,s}|$. We prove a version of this result for the more general setting of \emph{weighted} sets. We show that if $g : {[m] \choose \leq r} \rightarrow \mathbb{R}^+$ and $h : {[n] \choose \leq s} \rightarrow \mathbb{R}^+$ are functions that obey certain conditions, $\mathcal{A} \subseteq {[m] \choose \leq r}$, $\mathcal{B} \subseteq {[n] \choose \leq s}$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then $$\sum_{A \in \mathcal{A}} g(A) \sum_{B \in \mathcal{B}} h(B) \leq \sum_{C \in \mathcal{S}_{m,r}} g(C) \sum_{D \in \mathcal{S}_{n,s}} h(D).$$The bound is attained by taking $\mathcal{A} = \mathcal{S}_{m,r}$ and $\mathcal{B} = \mathcal{S}_{n,s}$. We also show that this result yields new sharp bounds for the product of sizes of cross-intersecting families of integer sequences and of cross-intersecting families of multisets.
Increasing the Minimum Distance of Codes by Twisting
Authors: Akbari Marzieh , Gillespie Neil I. , Praeger Cheryl E.
Published: January 2020

Twisted permutation codes, introduced recently by the second and third authors, belong to the family of frequency permutation arrays. Like some other codes in this family, such as the repetition permutation codes, they are obtained by a repetition construction applied to a smaller code (but with a "twist" allowed). The minimum distance of a twisted permutation code is known to be at least the minimum distance of a corresponding repetition permutation code, but in some instances can be larger. We construct two new infinite families of twisted permutation codes with minimum distances strictly greater than those for the corresponding repetition permutation codes. These constructions are based on two infinite families of finite groups and their representations. The first is a family of $p$-groups, for an odd prime $p$, while the second family consists of the $4$-dimensional symplectic groups over a finite field of even order. In the latter construction, properties of the graph automorphism of these symplectic groups play an important role.
On a Permutation Problem for Finite Abelian Groups
Authors: Ge Fan , Sun Zhi-Wei
Published: January 2020

Let $G$ be a finite additive abelian group with exponent $n>1$, and let $a_1,\ldots,a_{n-1}$ be elements of $G$. We show that there is a permutation $\sigma\in S_{n-1}$ such that all the elements $sa_{\sigma(s)}\ (s=1,\ldots,n-1)$ are nonzero if and only if$$\left|\left\{1\leqslant s<n:\ \frac{n}da_s\not=0\right\}\right|\geqslant d-1\ \ \mbox{for any positive divisor}\ d\ \mbox{of}\ n.$$When $G$ is the cyclic group $\mathbb Z/n\mathbb Z$, this confirms a conjecture of Z.-W. Sun.
A Decomposition of Parking Functions by Undesired Spaces
Authors: Bruce Melody , Dougherty Michael , Hlavacek Max , Kudo Ryo , Nicolas Ian
Published: January 2020

There is a well-known bijection between parking functions of a fixed length and maximal chains of the noncrossing partition lattice which we can use to associate to each set of parking functions a poset whose Hasse diagram is the union of the corresponding maximal chains. We introduce a decomposition of parking functions based on the largest number omitted and prove several theorems about the corresponding posets. In particular, they share properties with the noncrossing partition lattice such as local self-duality, a nice characterization of intervals, a readily computable Möbius function, and a symmetric chain decomposition. We also explore connections with order complexes, labeled Dyck paths, and rooted forests.
Antipode Formulas for some Combinatorial Hopf Algebras
Authors: Patrias Rebecca
Published: January 2020

Motivated by work of Buch on set-valued tableaux in relation to the K-theory of the Grassmannian, Lam and Pylyavskyy studied six combinatorial Hopf algebras that can be thought of as K-theoretic analogues of the Hopf algebras of symmetric functions, quasisymmetric functions, noncommutative symmetric functions, and of the Malvenuto-Reutenauer Hopf algebra of permutations. They described the bialgebra structure in all cases that were not yet known but left open the question of finding explicit formulas for the antipode maps. We give combinatorial formulas for the antipode map for the K-theoretic analogues of the symmetric functions, quasisymmetric functions, and noncommutative symmetric functions.
On Vertex, Edge, and Vertex-Edge Random Graphs
Authors: Beer Elizabeth , Fill James Allen , Janson Svante , Scheinerman Edward R.
Published: January 2020

We consider three classes of random graphs: edge random graphs, vertex random graphs, and vertex-edge random graphs. Edge random graphs are Erdős-Rényi random graphs, vertex random graphs are generalizations of geometric random graphs, and vertex-edge random graphs generalize both. The names of these three types of random graphs describe where the randomness in the models lies: in the edges, in the vertices, or in both. We show that vertex-edge random graphs, ostensibly the most general of the three models, can be approximated arbitrarily closely by vertex random graphs, but that the two categories are distinct.
Cubic Graphs and Related Triangulations on Orientable Surfaces
Authors: Fang Wenjie , Kang Mihyun , Moßhammer Michael , Sprüssel Philipp
Published: January 2020

Let $\mathbb{S}_g$ be the orientable surface of genus $g$ for a fixed non-negative integer $g$. We show that the number of vertex-labelled cubic multigraphs embeddable on $\mathbb{S}_g$ with $2n$ vertices is asymptotically $c_g n^{5/2(g-1)-1}\gamma^{2n}(2n)!$, where $\gamma$ is an algebraic constant and $c_g$ is a constant depending only on the genus $g$. We also derive an analogous result for simple cubic graphs and weighted cubic multigraphs. Additionally, for $g\ge1$, we prove that a typical cubic multigraph embeddable on $\mathbb{S}_g$ has exactly one non-planar component.
Fast Möbius Inversion in Semimodular Lattices and ER-labelable Posets
Authors: Kaski Petteri , Kohonen Jukka , Westerbäck Thomas
Published: January 2020

We consider the problem of fast zeta and Möbius transforms in finite posets, particularly in lattices. It has previously been shown that for a certain family of lattices, zeta and Möbius transforms can be computed in $O(e)$ elementary arithmetic operations, where $e$ denotes the size of the covering relation. We show that this family is exactly that of geometric lattices. We also extend the algorithms so that they work in $e$ operations for all semimodular lattices, including chains and divisor lattices. Finally, for both transforms, we provide a more general algorithm that works in $e$ operations for all ER-labelable posets.
An Extension of Matroid Rank Submodularity and the $Z$-Rayleigh Property
Authors: Mani Arun P.
Published: January 2020

We define an extension of matroid rank submodularity called $R$-submodularity, and introduce a minor-closed class of matroids called extended submodular matroids that are well-behaved with respect to $R$-submodularity. We apply $R$-submodularity to study a class of matroids with negatively correlated multivariate Tutte polynomials called the $Z$-Rayleigh matroids. First, we show that the class of extended submodular matroids are $Z$-Rayleigh. Second, we characterize a minor-minimal non-$Z$-Rayleigh matroid using its $R$-submodular properties. Lastly, we use $R$-submodularity to show that the Fano and non-Fano matroids (neither of which is extended submodular) are $Z$-Rayleigh, thus giving the first known examples of $Z$-Rayleigh matroids without the half-plane property.
Disjoint Difference Families from Galois Rings
Authors: Momihara Koji
Published: January 2020

In this paper, we give new constructions of disjoint difference families from Galois rings. The constructions are based on choosing cosets of the unit group of a subring in the Galois ring $\mathrm{GR}(p^2,p^{2s})$. Two infinite families of disjoint difference families are obtained from the Galois rings $\mathrm{GR}(p^{2},p^{4n})$ and $\mathrm{GR}(2^2,2^{2s})$.
Sidorenko's Conjecture, Colorings and Independent Sets
Authors: Csikvári Péter , Lin Zhicong
Published: January 2020

Let $\hom(H,G)$ denote the number of homomorphisms from a graph $H$ to a graph $G$. Sidorenko's conjecture asserts that for any bipartite graph $H$, and a graph $G$ we have$$\hom(H,G)\geq v(G)^{v(H)}\left(\frac{\hom(K_2,G)}{v(G)^2}\right)^{e(H)},$$where $v(H),v(G)$ and $e(H),e(G)$ denote the number of vertices and edges of the graph $H$ and $G$, respectively. In this paper we prove Sidorenko's conjecture for certain special graphs $G$: for the complete graph $K_q$ on $q$ vertices, for a $K_2$ with a loop added at one of the end vertices, and for a path on $3$ vertices with a loop added at each vertex. These cases correspond to counting colorings, independent sets and Widom-Rowlinson colorings of a graph $H$. For instance, for a bipartite graph $H$ the number of $q$-colorings $\mathrm{ch}(H,q)$ satisfies$$\mathrm{ch}(H,q)\geq q^{v(H)}\left(\frac{q-1}{q}\right)^{e(H)}.$$In fact, we will prove that in the last two cases (independent sets and Widom-Rowlinson colorings) the graph $H$ does not need to be bipartite. In all cases, we first prove a certain correlation inequality which implies Sidorenko's conjecture in a stronger form.
On the Number of Solutions in Random Hypergraph 2-Colouring
Authors: Rassmann Felicia
Published: January 2020

We determine the limiting distribution of the logarithm of the number of satisfying assignments in the random $k$-uniform hypergraph 2-colouring problem in a certain density regime for all $k\ge 3$. As a direct consequence we obtain that in this regime the random colouring model is contiguous wrt. the planted model, a result that helps simplifying the transfer of statements between these two models.
Client-Waiter Games on Complete and Random Graphs
Authors: Dean Oren , Krivelevich Michael
Published: January 2020

For a graph $ G $, a monotone increasing graph property $ \mathcal{P} $ and positive integer $ q $, we define the Client-Waiter game to be a two-player game which runs as follows. In each turn Waiter is offering Client a subset of at least one and at most $ q+1 $ unclaimed edges of $ G $ from which Client claims one, and the rest are claimed by Waiter. The game ends when all the edges have been claimed. If Client's graph has property $ \mathcal{P} $ by the end of the game, then he wins the game, otherwise Waiter is the winner. In this paper we study several Client-Waiter games on the edge set of the complete graph, and the $ H $-game on the edge set of the random graph. For the complete graph we consider games where Client tries to build a large star, a long path and a large connected component. We obtain lower and upper bounds on the critical bias for these games and compare them with the corresponding Waiter-Client games and with the probabilistic intuition. For the $ H $-game on the random graph we show that the known results for the corresponding Maker-Breaker game are essentially the same for the Client-Waiter game, and we extend those results for the biased games and for trees.
Equitable Hypergraph Orientations
Authors: Caro Yair , West Douglas , Yuster Raphael
Published: January 2020

A classical result in graph theory asserts that every graph can be oriented so that the indegree and outdegree of each vertex differ by at most $1$. We study the extent to which the result generalizes to uniform hypergraphs.
On the Nonexistence of $k$-Reptile Simplices in $\mathbb R^3$ and $\mathbb R^4$
Authors: Kynčl Jan , Patáková Zuzana
Published: January 2020

A $d$-dimensional simplex $S$ is called a $k$-reptile (or a $k$-reptile simplex) if it can be tiled by $k$ simplices with disjoint interiors that are all mutually congruent and similar to $S$. For $d=2$, triangular $k$-reptiles exist for all $k$ of the form $a^2, 3a^2$ or $a^2 + b^2$ and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, the only $k$-reptile simplices that are known for $d \ge 3$, have $k = m^d$, where $m$ is a positive integer. We substantially simplify the proof by Matoušek and the second author that for $d=3$, $k$-reptile tetrahedra can exist only for $k=m^3$. We then prove a weaker analogue of this result for $d=4$ by showing that four-dimensional $k$-reptile simplices can exist only for $k=m^2$.
Equitable Orientations of Sparse Uniform Hypergraphs
Authors: Cohen Nathann , Lochet William
Published: January 2020

Caro, West, and Yuster (2011) studied how $r$-uniform hypergraphs can be oriented in such a way that (generalizations of) indegree and outdegree are as close to each other as can be hoped. They conjectured an existence result of such orientations for sparse hypergraphs, of which we present a proof.
Transversals and Independence in Linear Hypergraphs with Maximum Degree Two
Authors: Henning Michael A. , Yeo Anders
Published: January 2020

For $k \ge 2$, let $H$ be a $k$-uniform hypergraph on $n$ vertices and $m$ edges. Let $S$ be a set of vertices in a hypergraph $H$. The set $S$ is a transversal if $S$ intersects every edge of $H$, while the set $S$ is strongly independent if no two vertices in $S$ belong to a common edge. The transversal number, $\tau(H)$, of $H$ is the minimum cardinality of a transversal in $H$, and the strong independence number of $H$, $\alpha(H)$, is the maximum cardinality of a strongly independent set in $H$. The hypergraph $H$ is linear if every two distinct edges of $H$ intersect in at most one vertex. Let $\mathcal{H}_k$ be the class of all connected, linear, $k$-uniform hypergraphs with maximum degree $2$. It is known [European J. Combin. 36 (2014), 231–236] that if $H \in \mathcal{H}_k$, then $(k+1)\tau(H) \le n+m$, and there are only two hypergraphs that achieve equality in the bound. In this paper, we prove a much more powerful result, and establish tight upper bounds on $\tau(H)$ and tight lower bounds on $\alpha(H)$ that are achieved for  infinite families of hypergraphs. More precisely, if $k \ge 3$ is odd and $H \in \mathcal{H}_k$ has $n$ vertices and $m$ edges, then we prove that $k(k^2 - 3)\tau(H) \le (k-2)(k+1)n + (k - 1)^2m + k-1$ and $k(k^2 - 3)\alpha(H) \ge  (k^2 + k - 4)n  - (k-1)^2 m - (k-1)$. Similar bounds are proven in the case when $k \ge 2$ is even.
Beyond Degree Choosability
Authors: Cranston Daniel W. , Rabern Landon
Published: January 2020

Let $G$ be a connected graph with maximum degree $\Delta$. Brooks' theorem states that $G$ has a $\Delta$-coloring unless $G$ is a complete graph or an odd cycle. A graph $G$ is degree-choosable if $G$ can be properly colored from its lists whenever each vertex $v$ gets a list of $d(v)$ colors. In the context of list coloring, Brooks' theorem can be strengthened to the following. Every connected graph $G$ is degree-choosable unless each block of $G$ is a complete graph or an odd cycle; such a graph $G$ is a Gallai tree. This degree-choosability result was further strengthened to Alon—Tarsi orientations; these are orientations of $G$ in which the number of spanning Eulerian subgraphs with an even number of edges differs from the number with an odd number of edges. A graph $G$ is degree-AT if $G$ has an Alon—Tarsi orientation in which each vertex has indegree at least 1. Alon and Tarsi showed that if $G$ is degree-AT, then $G$ is also degree-choosable. Hladký, Král', and Schauz showed that a connected graph is degree-AT if and only if it is not a Gallai tree. In this paper, we consider pairs $(G,x)$ where $G$ is a connected graph and $x$ is some specified vertex in $V(G)$. We characterize pairs such that $G$ has no Alon—Tarsi orientation in which each vertex has indegree at least 1 and $x$ has indegree at least 2. When $G$ is 2-connected, the characterization is simple to state.
Reflexive Graphs with Near Unanimity but no Semilattice Polymorphisms
Authors: Siggers Mark
Published: January 2020

We show that every generator, in a certain set of generators for the variety of reflexive near unanimity graphs, admits a semilattice polymorphism. We then find a retract of a product of such graphs (paths, in fact) that has no semilattice polymorphism. This verifies for reflexive graphs that the variety of graphs with semilattice polymorpisms does not contain the variety of graphs with near-unanimity, or even $3$-ary near-unanimity polymorphisms.
Grasshopper Avoidance of Patterns
Authors: Dębski Michał , Pastwa Urszula , Węsek Krzysztof
Published: January 2020

Motivated by a geometrical Thue-type problem, we introduce a new variant of the classical pattern avoidance in words, where jumping over a letter in the pattern occurrence is allowed. We say that pattern $p\in E^+$ occurs with jumps in a word $w=a_1a_2\ldots a_k \in A^+$, if there exist a non-erasing morphism $f$ from $E^*$ to $A^*$ and a sequence $(i_1, i_2, \ldots , i_l)$ satisfying $i_{j+1}\in\{ i_j+1, i_j+2 \}$ for $j=1, 2, \ldots, l-1$, such that $f(p) = a_{i_1}a_{i_2}\ldots a_{i_l}.$ For example, a pattern $xx$ occurs with jumps in a word $abdcadbc$ (for $x \mapsto abc$). A pattern $p$ is grasshopper $k$-avoidable if there exists an alphabet $A$ of $k$ elements, such that there exist arbitrarily long words over $A$ in which $p$ does not occur with jumps. The minimal such $k$ is the grasshopper avoidability index of $p$. It appears that this notion is related to two other problems: pattern avoidance on graphs and pattern-free colorings of the Euclidean plane. In particular, we show that a sequence avoiding a pattern $p$ with jumps can be a tool to construct a line $p$-free coloring of $\mathbb{R}^2$.    In our work, we determine the grasshopper avoidability index of patterns $\alpha^n$ for all $n$ except $n=5$. We also show that every doubled pattern is grasshopper $(2^7+1)$-avoidable, every pattern on $k$ variables of length at least $2^k$ is grasshopper $37$-avoidable, and there exists a constant $c$ such that every pattern of length at least $c$ on $2$ variables is grasshopper $3$-avoidable (those results are proved using the entropy compression method).
Multidimensional Lower Density Versions of Plünnecke’s Inequality
Authors: Bulinski Kamil
Published: January 2020

We investigate the lower asymptotic density of sumsets in $\mathbb{N}^2$ by proving certain Plünnecke type inequalities for various notions of lower density in $\mathbb{N}^2$. More specifically, we introduce a notion of lower tableaux density in $\mathbb{N}^2$ which involves averaging over convex tableaux-shaped regions in $\mathbb{N}^2$ which contain the origin. This generalizes the well known Plünnecke type inequality for the lower asymptotic density of sumsets in $\mathbb{N}$. We also provide a conjectural Plünnecke inequality for the more basic notion of lower rectangular asymtpotic density in $\mathbb{N}^2$ and prove certain partial results.