bluuebunny/crossref_metadata_2025 huggingface dataset:
Large Deviations for Permutations Avoiding Monotone Patterns
Authors: Madras Neal , Pehlivan Lerna
Published: January 2020

For a given permutation $\tau$, let $P_N^{\tau}$ be the uniform probability distribution on the set of $N$-element permutations $\sigma$ that avoid the pattern $\tau$. For $\tau=\mu_k:=123\ldots k$, we consider $P_N^{\mu_k}(\sigma_I=J)$ where $I\sim \gamma N$ and $J\sim \delta N$ for $\gamma, \delta \in (0,1)$. If $\gamma+ \delta \neq 1$, then we are in the large deviations regime with the probability decaying exponentially, and we calculate the limiting value of $P_N^{\mu_k}(\sigma_I=J)^{1/N}$. We also observe that for $\tau = \lambda_{k,\ell} := 12\ldots\ell k(k-1)\ldots(\ell+1)$ and $\gamma+\delta<1$, the limit of $P_N^{\tau}(\sigma_I=J)^{1/N}$ is the same  as for $\tau=\mu_k$.
An Improved Bound on (A+A)/(A+A)
Authors: Lund Ben
Published: January 2020

We show that, for a finite set $A$ of real numbers, the size of the set$$\frac{A+A}{A+A} = \left\{ \frac{a+b}{c+d} : a,b,c,d \in A, c+d \neq 0 \right \}$$is bounded from below by$$\left|\frac{A+A}{A+A} \right| \gg \frac{|A|^{2+1/4}}{|A / A|^{1/8} \log |A|}.$$This improves a result of Roche-Newton (2016).
Large Cliques in Sparse Random Intersection Graphs
Authors: Bloznelis Mindaugas , Kurauskas Valentas
Published: January 2020

An intersection graph defines an adjacency relation between subsets $S_1,\dots, S_n$ of a finite set $W=\{w_1,\dots, w_m\}$: the subsets $S_i$ and $S_j$ are adjacent if they intersect. Assuming that the subsets are drawn independently at random according to the probability distribution $\mathbb{P}(S_i=A)=P(|A|){\binom{m}{|A|}}^{-1}$, $A\subseteq W$, where $P$ is a probability on $\{0, 1, \dots, m\}$, we obtain the random intersection graph $G=G(n,m,P)$. We establish  the asymptotic order of the clique number $\omega(G)$ of  a sparse random intersection graph as $n,m\to+\infty$. For $m = \Theta(n)$ we show that the maximum clique is of size $(1-\alpha/2)^{-\alpha/2}n^{1-\alpha/2}(\ln n)^{-\alpha/2}(1+o_P(1))$ in the case where the asymptotic degree distribution of $G$ is a power-law with exponent $\alpha \in (1,2)$. It is of size $\frac {\ln n} {\ln \ln n}(1+o_P(1))$ if the degree distribution has bounded variance, i.e., $\alpha>2$. We construct a simple polynomial-time algorithm which finds a clique of the optimal order $\omega(G) (1-o_P(1))$.
Counting Outerplanar Maps
Authors: Geffner Ivan , Noy Marc
Published: January 2020

A map is outerplanar if all its vertices lie in the outer face. We enumerate various classes of rooted outerplanar maps with respect to the number of edges and vertices. The proofs involve several bijections with lattice paths. As a consequence of our results, we obtain an efficient scheme for encoding simple outerplanar maps.
Graphical Mahonian Statistics on Words
Authors: Grady Amy , Poznanović Svetlana
Published: January 2020

Foata and Zeilberger defined the graphical major index, $\mathrm{maj}_U$, and the graphical inversion index, $\mathrm{inv}_U$, for words over the alphabet $\{1, 2, \dots, n\}$. These statistics are a generalization of the classical permutation statistics $\mathrm{maj}$ and $\mathrm{inv}$ indexed by directed graphs $U$. They showed that $\mathrm{maj}_U$ and $\mathrm{inv}_U$ are equidistributed over all rearrangement classes if and only if $U$ is bipartitional. In this paper we strengthen their result by showing that if $\mathrm{maj}_U$ and $\mathrm{inv}_U$ are equidistributed on a single rearrangement class then $U$ is essentially bipartitional. Moreover, we define a graphical sorting index, $\mathrm{sor}_U$, which generalizes the sorting index of a permutation. We then characterize the graphs $U$ for which $\mathrm{sor}_U$ is equidistributed with $\mathrm{inv}_U$ and $\mathrm{maj}_U$ on a single rearrangement class.
Three Interactions of Holes in Two Dimensional Dimer Systems
Authors: Gilmore Tomack
Published: January 2020

Consider the unit triangular lattice in the plane with origin $O$, drawn so that one of the sets of lattice lines is vertical. Let $l$ and $l'$ denote respectively the vertical and horizontal lines that intersect $O$. Suppose the plane contains a pair of triangular holes of side length two, distributed symmetrically with respect to $l$ and $l'$ and oriented so that both holes point toward the origin. In the following article rhombus tilings of three different regions of the plane are considered, namely: tilings of the entire plane; tilings of the half plane that lies to the left of $l$ (where $l$ is considered a free boundary, so unit rhombi are allowed to protrude halfway across it); and tilings of the half plane that lies just below the fixed boundary $l'$. Asymptotic expressions for the interactions of the triangular holes in these three different regions are obtained thus providing further evidence for Ciucu's ongoing program that seeks to draw parallels between gaps in dimer systems on the hexagonal lattice and certain electrostatic phenomena.
Asymptotic and Exact Results on the Complexity of the Novelli-Pak-Stoyanovskii Algorithm
Authors: Schneider Carsten , Sulzgruber Robin
Published: January 2020

The Novelli-Pak-Stoyanovskii algorithm is a sorting algorithm for Young tableaux of a fixed shape that was originally devised to give a bijective proof of the hook-length formula. We obtain new asymptotic results on the average case and worst case complexity of this algorithm as the underlying shape tends to a fixed limit curve. Furthermore, using the summation package Sigma we prove an exact formula for the average case complexity when the underlying shape consists of only two rows. We thereby answer questions posed by Krattenthaler and Müller.
On the Number of Non-Zero Elements of Joint Degree Vectors
Authors: Czabarka Éva , Rauh Johannes , Sadeghi Kayvan , Short Taylor , Székely László
Published: January 2020

Joint degree vectors give the number of edges between vertices of degree $i$ and degree $j$ for $1\le i\le j\le n-1$ in an $n$-vertex graph. We find lower and upper bounds for the maximum number of nonzero elements in a joint degree vector as a function of $n$. This provides an upper bound on the number of estimable parameters in the exponential random graph model with bidegree-distribution as its sufficient statistics.
A General Method to Determine Limiting Optimal Shapes for Edge-Isoperimetric Inequalities
Authors: Veomett Ellen , Tsukerman Emmanuel
Published: January 2020

For a general family of graphs on $\mathbb{Z}^n$, we translate the edge-isoperimetric problem into a continuous isoperimetric problem in $\mathbb{R}^n$. We then solve the continuous isoperimetric problem using the Brunn-Minkowski inequality and Minkowski's theorem on mixed volumes. This translation allows us to conclude, under a reasonable assumption about the discrete problem, that the shapes of the optimal sets in the discrete problem approach the shape of the optimal set in the continuous problem as the size of the set grows. The solution is the zonotope defined as the Minkowski sum of the edges of the original graph.  We demonstrate the efficacy of this method by revisiting some previously solved classical edge-isoperimetric problems. We then apply our method to some discrete isoperimetric problems which had not previously been solved. The complexity of those solutions suggest that it would be quite difficult to find them using discrete methods only.
A Better Lower Bound on Average Degree of Online $k$-List-Critical Graphs
Authors: Rabern Landon
Published: January 2020

We improve the best known bounds on average degree of online $k$-list-critical graphs for $k \geqslant 6$. Specifically, for $k \geqslant 7$ we show that every non-complete online $k$-list-critical graph has average degree at least $k-1 + \frac{(k-3)^2 (2 k-3)}{k^4-2 k^3-11 k^2+28 k-14}$ and every non-complete online $6$-list-critical graph has average degree at least $5 + \frac{93}{766}$. The same bounds hold for offline $k$-list-critical graphs.
On some Ramsey Numbers for Quadrilaterals
Authors: Dybizbański Janusz , Dzido Tomasz
Published: January 2020

We will prove that $R(C_4, C_4, K_4-e)=16$. This fills one of the gaps in the tables presented in a 1996 paper by Arste et al. Moreover by using computer methods we improve lower and upper bounds for some other multicolor Ramsey numbers involving quadrilateral $C_4$. We consider $3$ and $4$-color numbers, our results improve known bounds.
Majority Colourings of Digraphs
Authors: Kreutzer Stephan , Oum Sang-il , Seymour Paul , Van der Zypen Dominic , Wood David R.
Published: January 2020

We prove that every digraph has a vertex 4-colouring such that for each vertex $v$, at most half the out-neighbours of $v$ receive the same colour as $v$. We then obtain several results related to the conjecture obtained by replacing 4 by 3.
A Note on the Speed of Hereditary Graph Properties
Authors: Lozin Vadim V. , Mayhill Colin , Zamaraev Victor
Published: January 2020

For a graph property $X$, let $X_n$ be the number of graphs with vertex set $\{1,\ldots,n\}$ having property $X$, also known as the speed of $X$. A property $X$ is called factorial if $X$ is hereditary (i.e. closed under taking induced subgraphs) and $n^{c_1n}\le X_n\le n^{c_2n}$ for some positive constants $c_1$ and $c_2$. Hereditary properties with the speed slower than factorial are surprisingly well structured. The situation with factorial properties is more complicated and less explored, although this family includes many properties of theoretical or practical importance, such as planar graphs or graphs of bounded vertex degree. To simplify the study of factorial properties, we propose the following conjecture: the speed of a hereditary property $X$ is factorial if and only if the fastest of the following three properties is factorial: bipartite graphs in $X$, co-bipartite graphs in $X$ and split graphs in $X$. In this note, we verify the conjecture for hereditary properties defined by forbidden induced subgraphs with at most 4 vertices.
On Ryser’s Conjecture for $t$-Intersecting and Degree-Bounded Hypergraphs
Authors: Király Zoltán , Tóthmérész Lilla
Published: January 2020

A famous conjecture (usually called Ryser's conjecture) that appeared in the PhD thesis of his student, J. R. Henderson, states that for an $r$-uniform $r$-partite hypergraph $\mathcal{H}$, the inequality $\tau(\mathcal{H})\le(r-1)\!\cdot\! \nu(\mathcal{H})$ always holds. This conjecture is widely open, except in the case of $r=2$, when it is equivalent to Kőnig's theorem, and in the case of $r=3$, which was proved by Aharoni in 2001.Here we study some special cases of Ryser's conjecture. First of all, the most studied special case is when $\mathcal{H}$ is intersecting. Even for this special case, not too much is known: this conjecture is proved only for $r\le 5$ by Gyárfás and Tuza. For $r>5$ it is also widely open.Generalizing the conjecture for intersecting hypergraphs, we conjecture the following. If an $r$-uniform $r$-partite hypergraph $\mathcal{H}$ is $t$-intersecting (i.e., every two hyperedges meet in at least $t r/4$.Gyárfás showed that Ryser's conjecture for intersecting hypergraphs is equivalent to saying that the vertices of an $r$-edge-colored complete graph can be covered by $r-1$ monochromatic components.Motivated by this formulation, we examine what fraction of the vertices can be covered by $r-1$ monochromatic components of different colors in an $r$-edge-colored complete graph. We prove a sharp bound for this problem.Finally we prove Ryser's conjecture for the very special case when the maximum degree of the hypergraph is two.
The Largest Pure Partial Planes of Order 6 Have Size 25
Authors: Gao Yibo
Published: January 2020

In this paper, we prove that the largest pure partial plane of order 6 has size 25. At the same time, we classify all pure partial planes of order 6 and size 25 up to isomorphism. Our major approach is computer search. The search space is very large so we use combinatorial arguments to rule out some of the cases. For the remaining cases, we subdivide each search by phases and use multiple checks to reduce search space via symmetry.
Nice Restrictions of Reflection Arrangements
Authors: Möller Tilman , Röhrle Gerhard
Published: January 2020

In a recent paper, Hoge and the second author classified all nice and all inductively factored reflection arrangements. In this note we extend this classification by determining all nice and all inductively factored restrictions of reflection arrangements.
On the Minimum Number of Monochromatic Generalized Schur Triples
Authors: Thanatipanonda Thotsaporn , Wong Elaine
Published: January 2020

The solution to the problem of finding the minimum number of monochromatic triples $(x,y,x+ay)$ with $a\geq 2$ being a fixed positive integer over any 2-coloring of $[1,n]$ was conjectured by Butler, Costello, and Graham (2010) and Thanathipanonda (2009). We solve this problem using a method based on Datskovsky's proof (2003) on the minimum number of monochromatic Schur triples $(x,y,x+y)$. We do this by exploiting the combinatorial nature of the original proof and adapting it to the general problem.
Counting Gluings of Octahedra
Authors: Bonzom Valentin , Lionni Luca
Published: January 2020

Three-dimensional colored triangulations are gluings of tetrahedra whose faces carry the colors 0, 1, 2, 3 and in which the attaching maps between tetrahedra are defined using the colors. This framework makes it possible to generalize the notion of two-dimensional $2p$-angulations to three dimensions in a way which is suitable for combinatorics and enumeration. In particular, universality classes of three-dimensional triangulations can be investigated within this framework. Here we study colored triangulations obtained by gluing octahedra. Those which maximize the number of edges at fixed number of octahedra are fully characterized and are shown to have the topology of the 3-sphere. They are further shown to be in bijection with a family of plane trees. The enumeration is performed both directly and using this bijection.
A Recurrence for Bounds on Dominating Sets in $k$-Majority Tournaments
Authors: Fidler Dror
Published: January 2020

A $k$-majority tournament is realized by $2k-1$ linear orders on the set of vertices, where a vertex $u$ dominates $v$ if $u$ precedes $v$ in at least $k$ of the orders. Various properties of such tournaments have been studied, among them the problem of finding the size of a smallest dominating set. It is known that $2$-majority tournaments are dominated by $3$ vertices and that $k$-majority tournaments are dominated by $O(k \log k)$ vertices. However, precise values are not known even for $k=3$. We establish new upper bounds for the size of a smallest dominating set in $k$-majority tournaments that considerably improve upon previous bounds for small $k$. In particular our result shows that $3$-majority tournaments are dominated by at most $12$ vertices.
Strongly Connected Multivariate Digraphs
Authors: Wu Yaokun , Xu Zeying , Zhu Yinfeng
Published: January 2020

Generalizing the idea of viewing a digraph as a model of a linear map, we suggest a multi-variable analogue of a digraph, called a hydra, as  a model of a multi-linear map. Walks in digraphs correspond to usual matrix multiplication while walks in hydras correspond to the tensor multiplication introduced by Robert Grone in 1987.  By viewing matrix multiplication as a special case of this tensor multiplication, many concepts on strongly connected digraphs are generalized to corresponding  ones for hydras, including strongly connectedness, periods and primitiveness, etc. We explore the structure of all possible periods of strongly connected hydras, which turns out to be related to the existence of certain kind of  combinatorial designs. We also provide estimates of largest primitive exponents and largest diameters of relevant hydras. Much  existing research  on tensors are based on some other definitions of multiplications of tensors and so our work here  supplies new perspectives for understanding irreducible and primitive  nonnegative tensors.
Defining the $q$-Analogue of a Matroid
Authors: Jurrius Relinde , Pellikaan Ruud
Published: January 2020

This paper defines the $q$-analogue of a matroid and establishes several properties like duality, restriction and contraction. We discuss possible ways to define a $q$-matroid, and why they are (not) cryptomorphic. Also, we explain the motivation for studying $q$-matroids by showing that a rank metric code gives a $q$-matroid.
The Pentagram Integrals on Inscribed Polygons
Authors: Schwartz Richard Evan , Tabachnikov Serge
Published: January 2020

The pentagram map is a completely integrable system defined on the moduli space of polygons. The integrals for the system are certain weighted homogeneous polynomials, which come in pairs: $E_1,O_2,E_2,O_2,\dots$ In this paper we prove that $E_k=O_k$ for all $k$, when these integrals are restricted to the space of polygons which are inscribed in a conic section. Our proof is essentially a combinatorial analysis of the integrals.
Juxtaposing Catalan Permutation Classes with Monotone Ones
Authors: Brignall Robert , Sliačan Jakub
Published: January 2020

This paper enumerates all juxtaposition classes of the form "$\mathrm{Av}(abc)$ next to $\mathrm{Av}(xy)$", where $abc$ is a permutation of length three and $xy$ is a permutation of length two. We use Dyck paths decorated by sequences of points to represent elements from such a juxtaposition class. Context free grammars are then used to enumerate these decorated Dyck paths.
On a Special Class of Hyper-Permutahedra
Authors: Agnarsson Geir
Published: January 2020

Minkowski sums of simplices in ${\mathbb{R}}^n$ form an interesting class of polytopes that seem to emerge in various situations. In this paper we discuss the Minkowski sum of the  simplices $\Delta_{k-1}$ in ${\mathbb{R}}^n$ where $k$ and $n$ are fixed, their flags and some of their face lattice structure. In particular, we derive a closed formula for their exponential generating flag function. These polytopes are simple, include both the simplex $\Delta_{n-1}$ and the permutahedron $\Pi_{n-1}$, and form a Minkowski basis for more general permutahedra.
On the Multicolor Ramsey Number for 3-Paths of Length Three
Authors: Łuczak Tomasz , Polcyn Joanna
Published: January 2020

We show that if we color the hyperedges of the complete $3$-uniform hypergraph on $2n+\sqrt{18n+1}+2$ vertices with $n$ colors, then one of the color classes contains a loose path of length three.
Group Actions on Partitions
Authors: Kim Byungchan
Published: January 2020

We introduce group actions on the integer partitions and their variances. Using generating functions and Burnside's lemma, we study arithmetic properties of the counting functions arising from group actions. In particular, we find a modulo 4 congruence involving the number of ordinary partitions and the number of partitions into distinct parts.
A Note on Sparse Supersaturation and Extremal Results for Linear Homogeneous Systems
Authors: Spiegel Christoph
Published: January 2020

We study the thresholds for the property of containing a solution to a linear homogeneous system in random sets. We expand a previous sparse Szémeredi-type result of Schacht to the broadest class of matrices possible. We also provide a shorter proof of a sparse Rado result of Friedgut, Rödl, Ruciński and Schacht based on a hypergraph container approach due to Nenadov and Steger. Lastly we further extend these results to include some solutions with repeated entries using a notion of non-trivial solutions due to Rúzsa as well as Rué et al.
Eulerian-Catalan Numbers
Authors: Bidkhori Hoda , Sullivant Seth
Published: January 2020

We show that the Eulerian-Catalan numbers enumerate Dyck permutations. We provide two proofs for this fact, the first using the geometry of alcoved polytopes and the second a direct combinatorial proof via an Eulerian-Catalan analogue of the Chung-Feller theorem.
Signed Cycle Double Covers
Authors: Shi Lingsheng , Zhang Zhang
Published: January 2020

The cycle double cover conjecture states that every bridgeless graph has a collection of cycles which together cover every edge of the graph exactly twice. A signed graph is a graph with each edge assigned by a positive or a negative sign. In this article, we prove a weak version of this conjecture that is the existence of a signed cycle double cover for all bridgeless graphs. We also show the relationships of the signed cycle double cover and other famous conjectures such as the Tutte flow conjectures and the shortest cycle cover conjecture etc.
Paths and Cycles in Random Subgraphs of Graphs with Large Minimum Degree
Authors: Ehard Stefan , Joos Felix
Published: January 2020

For a graph $G$ and $p\in [0,1]$, let $G_p$ arise from $G$ by deleting every edge mutually independently with probability $1-p$. The random graph model $(K_n)_p$ is certainly the most investigated random graph model and also known as the $G(n,p)$-model. We show that several results concerning the length of the longest path/cycle naturally translate to $G_p$ if $G$ is an arbitrary graph of minimum degree at least $n-1$.For a constant $c>0$ and $p=\frac{c}{n}$, we show that asymptotically almost surely the length of the longest path in $G_p$ is at least $(1-(1+\epsilon(c))ce^{-c})n$ for some function $\epsilon(c)\to 0$ as $c\to \infty$, and the length of the longest cycle is a least $(1-O(c^{- \frac{1}{5}}))n$. The first result is asymptotically best-possible. This extends several known results on the length of the longest path/cycle of a random graph in the $G(n,p)$-model to the random graph model $G_p$ where $G$ is a graph of minimum degree at least $n-1$.
Degenerate Turán Problems for Hereditary Properties
Authors: Nikiforov Vladimir , Tait Michael , Timmons Craig
Published: January 2020

Let $H$ be a graph and $t\geqslant s\geqslant 2$ be integers. We prove that if $G$ is an $n$-vertex graph with no copy of $H$ and no induced copy of $K_{s,t}$, then $\lambda(G) = O\left(n^{1-1/s}\right)$ where $\lambda(G)$ is the spectral radius of the adjacency matrix of $G$. Our results are motivated by results of Babai, Guiduli, and Nikiforov bounding the maximum spectral radius of a graph with no copy (not necessarily induced) of $K_{s,t}$.
On the Union Complexity of Families of Axis-Parallel Rectangles with a Low Packing Number
Authors: Keller Chaya , Smorodinsky Shakhar
Published: January 2020

Let $\mathcal{R}$ be a family of $n$ axis-parallel rectangles with packing number $p-1$, meaning that among any $p$ of the rectangles, there are two with a non-empty intersection. We show that the union complexity of $\mathcal{R}$ is at most $O(n+p^2)$, and that the $(k-1)$-level complexity of $\mathcal{R}$ is at most $O(n+k p^2)$. Both upper bounds are tight.
On Super-Strong Wilf Equivalence Classes of Permutations
Authors: Hadjiloucas Demetris , Michos Ioannis , Savvidou Christina
Published: January 2020

Super-strong Wilf equivalence is a type of Wilf equivalence on words that was originally introduced as strong Wilf equivalence by Kitaev et al. [Electron. J. Combin. 16(2)] in $2009$. We provide a necessary and sufficient condition for two permutations in $n$ letters to be super-strongly Wilf equivalent, using distances between letters within a permutation. Furthermore, we give a characterization of such equivalence classes via two-colored binary trees. This allows us to prove, in the case of super-strong Wilf equivalence, the conjecture stated in the same article by Kitaev et al. that the cardinality of each Wilf equivalence class is a power of $2$.
Linear Chord Diagrams with Long Chords
Authors: Sullivan Everett
Published: January 2020

A linear chord diagram of size $n$ is a partition of the set $\{1,2,\dots,2n\}$ into sets of size two, called chords. From a table showing the number of linear chord diagrams of degree $n$ such that every chord has length at least $k$, we observe that if we proceed far enough along the diagonals, they are given by a geometric sequence. We prove that this holds for all diagonals, and identify when the effect starts.
Partitioning Sparse Graphs into an Independent Set and a Forest of Bounded Degree
Authors: Dross François , Montassier Mickael , Pinlou Alexandre
Published: January 2020

An $({\cal I},{\cal F}_d)$-partition of a graph is a partition of the vertices of the graph into two sets $I$ and $F$, such that $I$ is an independent set and $F$ induces a forest of maximum degree at most $d$. We show that for all $M<3$ and $d \ge \frac{2}{3-M} - 2$, if a graph has maximum average degree less than $M$, then it has an $({\cal I},{\cal F}_d)$-partition. Additionally, we prove that for all $\frac{8}{3} \le M < 3$ and $d \ge \frac{1}{3-M}$, if a graph has maximum average degree less than $M$ then it has an $({\cal I},{\cal F}_d)$-partition. It follows that planar graphs with girth at least $7$ (resp. $8$, $10$) admit an $({\cal I},{\cal F}_5)$-partition (resp. $({\cal I},{\cal F}_3)$-partition, $({\cal I},{\cal F}_2)$-partition).
Plurigraph Coloring and Scheduling Problems
Authors: Machacek John
Published: January 2020

We define a new type of vertex coloring which generalizes vertex coloring in graphs, hypergraphs, and simplicial complexes. This coloring also generalizes oriented coloring, acyclic coloring, and star coloring. There is an associated symmetric function in noncommuting variables for which we give a deletion-contraction formula. In the case of graphs this symmetric function in noncommuting variables agrees with the chromatic symmetric function in noncommuting variables of Gebhard and Sagan. Our vertex coloring is a special case of the scheduling problems defined by Breuer and Klivans. We show how the deletion-contraction law can be applied to scheduling problems. Also, we show that the chromatic symmetric function determines the degree sequence of uniform hypertrees, but there exists pairs of 3-uniform hypertrees which are not isomorphic yet have the same chromatic symmetric function.
Posets from Admissible Coxeter Sequences
Authors: Macauley Matthew , Mortveit Henning S.
Published: January 2020

We study the equivalence relation on the set of acyclic orientations of an undirected graph $\Gamma$ generated by source-to-sink conversions. These conversions arise in the contexts of admissible sequences in Coxeter theory, quiver representations, and asynchronous graph dynamical systems. To each equivalence class we associate a poset, characterize combinatorial properties of these posets, and in turn, the admissible sequences. This allows us to construct an explicit bijection from the equivalence classes over $\Gamma$ to those over $\Gamma'$ and $\Gamma"$, the graphs obtained from $\Gamma$ by edge deletion and edge contraction of a fixed cycle-edge, respectively. This bijection yields quick and elegant proofs of two non-trivial results: $(i)$ A complete combinatorial invariant of the equivalence classes, and $(ii)$ a solution to the conjugacy problem of Coxeter elements for simply-laced Coxeter groups. The latter was recently proven by H. Eriksson and K. Eriksson using a much different approach.
Uniform Mixing on Cayley Graphs
Authors: Godsil Chris , Zhan Hanmeng
Published: January 2020

We provide new examples of Cayley graphs on which the quantum walks reach uniform mixing. Our first result is a complete characterization of all $2(d+2)$-regular Cayley graphs over $\mathbb{Z}_3^d$ that admit uniform mixing at time $2\pi/9$. Our second result shows that for every integer $k\ge 3$, we can construct Cayley graphs over $\mathbb{Z}_q^d$ that admit uniform mixing at time $2\pi/q^k$, where $q=3, 4$.We also find the first family of irregular graphs, the Cartesian powers of the star $K_{1,3}$, that admit uniform mixing.
The Gonality Sequence of Complete Graphs
Authors: Cools Filip , Panizzut Marta
Published: January 2020

The gonality sequence $(\gamma_r)_{r\geq1}$ of a finite graph/metric graph/algebraic curve comprises the minimal degrees $\gamma_r$ of linear systems of rank $r$. For the complete graph $K_d$, we show that $\gamma_r =  kd - h$ if $r<g=\frac{(d-1)(d-2)}{2}$, where $k$ and $h$ are the uniquely determined integers such that $r = \frac{k(k+3)}{2} - h$ with $1\leq k\leq d-3$ and $0 \leq h \leq k $. This shows that the graph $K_d$ has the gonality sequence of a smooth plane curve of degree $d$. The same result holds for the corresponding metric graphs.
Quasiregular Matroids
Authors: Kingan S. R.
Published: January 2020

Regular matroids are binary matroids with no minors isomorphic to the Fano matroid $F_7$ or its dual $F_7^*$. Seymour proved that 3-connected regular matroids are either graphs, cographs, or $R_{10}$, or else can be decomposed along a non-minimal exact 3-separation induced by $R_{12}$. Quasiregular matroids are binary matroids with no minor isomorphic to the self-dual binary matroid $E_4$. The class of quasiregular matroids properly contains the class of regular matroids. We prove that 3-connected quasiregular matroids are either graphs, cographs, or deletion-minors of $PG(3,2)$, $R_{17}$ or $M_{12}$ or else can be decomposed along a non-minimal exact 3-separation induced by $R_{12}$, $P_9$, or $P_9^*$.
Cover $k$-Uniform Hypergraphs by Monochromatic Loose Paths
Authors: Lu Changhong , Mao Rui , Wang Bing , Zhang Ping
Published: January 2020

A conjecture of Gyárfás and Sárközy says that in every $2$-coloring of the edges of the complete $k$-uniform hypergraph $\mathcal{K}_n^k$, there are two disjoint monochromatic loose paths of distinct colors such that they cover all but at most $k-2$ vertices. Recently, the authors affirmed the conjecture. In the note we show that for every $2$-coloring of $\mathcal{K}_n^k$, one can find two monochromatic paths of distinct colors to cover all vertices of $\mathcal{K}_n^k$ such that they share at most $k-2$ vertices. Omidi and Shahsiah conjectured that $R(\mathcal{P}_t^k,\mathcal{P}_t^k) =t(k-1)+\lfloor \frac{t+1}{2}\rfloor$ holds for $k\ge 3$ and they affirmed the conjecture for $k=3$ or $k\ge 8$. We show that if the conjecture is true, then $k-2$ is best possible for our result.
Tomaszewski's Problem on Randomly Signed Sums: Breaking the 3/8 Barrier
Authors: Boppana Ravi B. , Holzman Ron
Published: January 2020

Let $v_1$, $v_2$, ..., $v_n$ be real numbers whose squares add up to 1.  Consider the $2^n$ signed sums of the form $S = \sum \pm v_i$.  Holzman and Kleitman (1992) proved that at least 3/8 of these sums satisfy $|S| \le 1$.  This 3/8 bound seems to be the best their method can achieve.  Using a different method, we improve the bound to 13/32, thus breaking the 3/8 barrier.
Tail Positive Words and Generalized Coinvariant Algebras
Authors: Rhoades Brendon , Wilson Andrew Timothy
Published: January 2020

Let $n,k,$ and $r$ be nonnegative integers and let $S_n$ be the symmetric group. We introduce a quotient $R_{n,k,r}$ of the polynomial ring $\mathbb{Q}[x_1, \dots, x_n]$ in $n$ variables which carries the structure of a graded $S_n$-module.  When $r \ge n$ or $k = 0$ the quotient $R_{n,k,r}$ reduces to the classical coinvariant algebra $R_n$ attached to the symmetric group. Just as algebraic properties of $R_n$ are controlled by combinatorial properties of permutations in $S_n$, the algebra of $R_{n,k,r}$ is controlled by the combinatorics of objects called tail positive words. We calculate the standard monomial basis of $R_{n,k,r}$ and its graded $S_n$-isomorphism type. We also view $R_{n,k,r}$ as a module over the 0-Hecke algebra $H_n(0)$, prove that $R_{n,k,r}$ is a projective 0-Hecke module, and calculate its quasisymmetric and nonsymmetric 0-Hecke characteristics. We conjecture a relationship between our quotient $R_{n,k,r}$ and the delta operators of the theory of Macdonald polynomials.
Distinct Triangle Areas in a Planar Point Set over Finite Fields
Authors: Vinh Le Anh
Published: January 2020

Let $\mathcal{P}$ be a set of $n$ points in the finite plane $\mathbb{F}_q^2$ over the finite field $\mathbb{F}_q$ of $q$ elements, where $q$ is an odd prime power. For any $s \in \mathbb{F}_q$, denote by $A (\mathcal{P}; s)$ the number of ordered triangles whose vertices in $\mathcal{P}$ having area $s$. We show that if the cardinality of $\mathcal{P}$ is large enough then $A (\mathcal{P}; s)$ is close to the expected number $|\mathcal{P}|^3/q$.
Piercing Axis-Parallel Boxes
Authors: Chudnovsky Maria , Spirkl Sophie , Zerbib Shira
Published: January 2020

Let $\mathcal{F}$ be a finite family of axis-parallel boxes in $\mathbb{R}^d$ such that $\mathcal{F}$ contains no $k+1$ pairwise disjoint boxes. We prove that if $\mathcal{F}$ contains a subfamily $\mathcal{M}$ of $k$ pairwise disjoint boxes with the property that for every $F\in \mathcal{F}$ and $M\in \mathcal{M}$ with $F \cap M \neq \emptyset$, either $F$ contains a corner of $M$ or $M$ contains $2^{d-1}$ corners of $F$, then $\mathcal{F}$ can be pierced by $O(k)$ points. One consequence of this result is that if $d=2$ and the ratio between any of the side lengths of any box is bounded by a constant, then $\mathcal{F}$ can be pierced by $O(k)$ points. We further show that if for each two intersecting boxes in $\mathcal{F}$ a corner of one is contained in the other, then $\mathcal{F}$ can be pierced by at most $O(k\log\log(k))$ points, and in the special case where $\mathcal{F}$ contains only cubes this bound improves to $O(k)$.
Induced Ramsey-Type Results and Binary Predicates for Point Sets
Authors: Balko Martin , Kynčl Jan , Langerman Stefan , Pilz Alexander
Published: January 2020

Let $k$ and $p$ be positive integers and let $Q$ be a finite point set in general position in the plane. We say that $Q$ is $(k,p)$-Ramsey if there is a finite point set $P$ such that for every $k$-coloring $c$ of $\binom{P}{p}$ there is a subset $Q'$ of $P$ such that $Q'$ and $Q$ have the same order type and $\binom{Q'}{p}$ is monochromatic in $c$. Nešetřil and Valtr proved that for every $k \in \mathbb{N}$, all point sets are $(k,1)$-Ramsey. They also proved that for every $k \ge 2$ and $p \ge 2$, there are point sets that are not $(k,p)$-Ramsey.As our main result, we introduce a new family of $(k,2)$-Ramsey point sets, extending a result of Nešetřil and Valtr. We then use this new result to show that for every $k$ there is a point set $P$ such that no function $\Gamma$ that maps ordered pairs of distinct points from $P$ to a set of size $k$ can satisfy the following "local consistency" property: if $\Gamma$ attains the same values on two ordered triples of points from $P$, then these triples have the same orientation. Intuitively, this implies that there cannot be such a function that is defined locally and determines the orientation of point triples.
Constraining the Clustering Transition for Colorings of Sparse Random Graphs
Authors: Anastos Michael , Frieze Alan , Pegden Wesley
Published: January 2020

Let $\Omega_q$ denote the set of proper $[q]$-colorings of the random graph $G_{n,m}, m=dn/2$ and let $H_q$ be the graph with vertex set $\Omega_q$ and an edge $\{\sigma,\tau\}$ where $\sigma,\tau$ are mappings $[n]\to[q]$ iff $h(\sigma,\tau)=1$. Here $h(\sigma,\tau)$ is the Hamming distance $|\{v\in [n]:\sigma(v)\neq\tau(v)\}|$. We show that w.h.p. $H_q$ contains a single giant component containing almost all colorings in $\Omega_q$ if $d$ is sufficiently large and $q\geq \frac{cd}{\log d}$ for a constant $c>3/2$.
The Structure of Delta-Matroids with Width One Twists
Authors: Chun Carolyn , Hall Rhiannon , Merino Criel , Moffatt Iain , Noble Steven D
Published: January 2020

The width of a delta-matroid is the difference in size between a maximal and minimal feasible set. We give a Rough Structure Theorem for delta-matroids that admit a twist of width one. We apply this theorem to give an excluded minor characterisation of delta-matroids that admit a twist of width at most one.
Hard Squares with Negative Activity on Cylinders with Odd Circumference
Authors: Jonsson Jakob
Published: January 2020

Let $C_{m,n}$ be the graph on the vertex set $\{1, \ldots, m\} \times \{0, \ldots, n-1\}$ in which there is an edge between $(a,b)$ and $(c,d)$ if and only if either $(a,b) = (c,d\pm 1)$ or $(a,b) = (c \pm 1,d)$, where the second index is computed modulo $n$. One may view $C_{m,n}$ as a unit square grid on a cylinder with circumference $n$ units. For odd $n$, we prove that the Euler characteristic of the simplicial complex $\Sigma_{m,n}$ of independent sets in $C_{m,n}$ is either $2$ or $-1$, depending on whether or not $\gcd(m-1,n)$ is divisble by $3$. The proof relies heavily on previous work due to Thapper, who reduced the problem of computing the Euler characteristic of $\Sigma_{m,n}$ to that of analyzing a certain subfamily of sets with attractive properties. The situation for even $n$ remains unclear. In the language of statistical mechanics, the reduced Euler characteristic of $\Sigma_{m,n}$ coincides with minus the partition function of the corresponding hard square model with activity $-1$.
Maximal Planar Subgraphs of Fixed Girth in Random Graphs
Authors: Fernández Manuel , Sieger Nicholas , Tait Michael
Published: January 2020

In 1991, Bollobás and Frieze showed that the threshold for $G_{n,p}$ to contain a spanning maximal planar subgraph is very close to $p = n^{-1/3}$. In this paper, we compute similar threshold ranges for $G_{n,p}$ to contain a maximal bipartite planar subgraph and for $G_{n,p}$ to contain a maximal planar subgraph of fixed girth $g$.
Multicolor Ramsey Numbers and Restricted Turán Numbers for the Loose 3-Uniform Path of Length Three
Authors: Ruciński Andrzej , Jackowska Eliza , Polcyn Joanna
Published: January 2020

Let $P$ denote a 3-uniform hypergraph consisting of 7 vertices $a,b,c,d,e,f,g$ and 3 edges $\{a,b,c\}, \{c,d,e\},$ and $\{e,f,g\}$. It is known that the $r$-colored Ramsey number for $P$ is $R(P;r)=r+6$ for $r=2,3$, and that $R(P;r)\le 3r$ for all $r\ge3$. The latter result follows by a standard application of the Turán number $\mathrm{ex}_3(n;P)$, which was determined to be $\binom{n-1}2$ in our previous work. We have also shown that the full star is the only extremal 3-graph for $P$. In this paper, we perform a subtle analysis of the Turán numbers for $P$ under some additional restrictions. Most importantly, we determine the largest number of edges in an $n$-vertex $P$-free 3-graph which is not a star. These Turán-type results, in turn, allow us to confirm the formula $R(P;r)=r+6$ for $r\in\{4,5,6,7\}$.
Genetic Algorithms Applied to Problems of Forbidden Configurations
Authors: Anstee R. P. , Raggi Miguel
Published: January 2020

A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix $F$, we say a (0,1)-matrix $A$ avoids $F$ (as a configuration) if there is no submatrix of $A$ which is a row and column permutation of $F$. Let $\|{A}\|$ denote the number of columns of $A$. We define $\mathrm{forb}(m,F)=\max\{\|{A}\|\ : A$ is an $m$-rowed simple matrix that avoids $F \}$. Define an extremal matrix as an $m$-rowed simple matrix $A$ with that avoids $F$ and $\|{A}\|=\mathrm{forb}(m,F)$. We describe the use of Local Search Algorithms (in particular a Genetic Algorithm) for finding extremal matrices. We apply this technique to two forbidden configurations in turn, obtaining a guess for the structure of an $m\times\mathrm{forb}(m,F)$ simple matrix avoiding $F$ and then proving the guess is indeed correct. The Genetic Algorithm was also helpful in finding the proof.
A Construction of Cospectral Graphs for the Normalized Laplacian
Authors: Butler Steve , Grout Jason
Published: January 2020

We give a method to construct cospectral graphs for the normalized Laplacian by a local modification in some graphs with special structure. Namely, under some simple assumptions, we can replace a small bipartite graph with a cospectral mate without changing the spectrum of the entire graph. We also consider a related result for swapping out biregular bipartite graphs for the matrix $A+tD$. We produce (exponentially) large families of non-bipartite, non-regular graphs which are mutually cospectral, and also give an example of a graph which is cospectral with its complement but is not self-complementary.
The Complexity of Computing the Cylindrical and the $t$-Circle Crossing Number of a Graph
Authors: Duque Frank , González-Aguilar Hernán , Hernández-Vélez César , Leaños Jesús , Medina Carolina
Published: January 2020

A plane drawing of a graph is cylindrical if there exist two concentric circles that contain all the vertices of the graph, and no edge intersects (other than at its endpoints) any of these circles. The cylindrical crossing number of a graph \(G\) is the minimum number of crossings in a cylindrical drawing of \(G\). In his influential survey on the variants of the definition of the crossing number of a graph, Schaefer lists the complexity of computing the cylindrical crossing number of a graph as an open question. In this paper, we prove that the problem of deciding whether a given graph admits a cylindrical embedding is NP-complete, and as a consequence we show that the \(t\)-cylindrical crossing number problem is also NP-complete. Moreover, we show an analogous result for the natural generalization of the cylindrical crossing number,  namely the \(t\)-crossing number.
A Polynomial Bound on the Mixing Time of a Markov Chain for Sampling Regular Directed Graphs
Authors: Greenhill Catherine
Published: January 2020

The switch chain is a well-known Markov chain for sampling directed graphs with a given degree sequence. While not ergodic in general, we show that it is ergodic for regular degree sequences. We then prove that the switch chain is rapidly mixing for regular directed graphs of degree $d$, where $d$ is any positive integer-valued function of the number of vertices. We bound the mixing time by bounding the eigenvalues of the chain. A new result is presented and applied to bound the smallest (most negative) eigenvalue. This result is a modification of a lemma by Diaconis and Stroock [Annals of Applied Probability 1991], and by using it we avoid working with a lazy chain. A multicommodity flow argument is used to bound the second-largest eigenvalue of the chain. This argument is based on the analysis of a related Markov chain for undirected regular graphs by Cooper, Dyer and Greenhill [Combinatorics, Probability and Computing 2007], but with significant extension required.
Domination and Fractional Domination in Digraphs
Authors: Harutyunyan Ararat , Le Tien-Nam , Newman Alantha , Thomasse Stéphan
Published: January 2020

In this paper, we investigate the relation between the (fractional) domination number of a digraph $G$ and the independence number of its underlying graph, denoted by $\alpha(G)$. More precisely, we prove that every digraph $G$ on $n$ vertices has fractional domination number at most $2\alpha(G)$ and domination number at most $2\alpha(G) \cdot \log{n}$. Both bounds are sharp.
Undesired Parking Spaces and Contractible Pieces of the Noncrossing Partition Link
Authors: Dougherty Michael , McCammond Jon
Published: January 2020

There are two natural simplicial complexes associated to the noncrossing partition lattice: the order complex of the full lattice and the order complex of the lattice with its bounding elements removed. The latter is a complex that we call the noncrossing partition link because it is the link of an edge in the former. The first author and his coauthors conjectured that various collections of simplices of the noncrossing partition link (determined by the undesired parking spaces in the corresponding parking functions) form contractible subcomplexes. In this article we prove their conjecture by combining the fact that the star of a simplex in a flag complex is contractible with the second author's theory of noncrossing hypertrees.
Linear Dependence Between Hereditary Quasirandomness Conditions
Authors: He Xiaoyu
Published: January 2020

Answering a question of Simonovits and Sós, Conlon, Fox, and Sudakov proved that for any nonempty graph $H$, and any $\varepsilon>0$, there exists $\delta>0$ polynomial in $\varepsilon$, such that if $G$ is an $n$-vertex graph with the property that every $U\subseteq V(G)$ contains $p^{e(H)}|U|^{v(H)}\pm\delta n^{v(H)}$ labeled copies of $H$, then $G$ is $(p,\varepsilon)$-quasirandom in the sense that every subset $U\subseteq G$ contains $\frac{1}{2}p|U|^{2}\pm\varepsilon n^{2}$ edges. They conjectured that $\delta$ may be taken to be linear in $\varepsilon$ and proved this in the case that $H$ is a complete graph. We study a labelled version of this quasirandomness property proposed by Reiher and Schacht. Let $H$ be any nonempty graph on $r$ vertices $v_{1},\ldots,v_{r}$, and $\varepsilon>0$. We show that there exists $\delta=\delta(\varepsilon)>0$ linear in $\varepsilon$, such that if $G$ is an $n$-vertex graph with the property that every sequence of $r$ subsets $U_{1},\ldots,U_{r}\subseteq V(G)$, the number of copies of $H$ with each $v_{i}$ in $U_{i}$ is $p^{e(H)}\prod|U_{i}|\pm\delta n^{v(H)}$, then $G$ is $(p,\varepsilon)$-quasirandom.
An Easy Subexponential Bound for Online Chain Partitioning
Authors: Bosek Bartłomiej , Kierstead H. A. , Krawczyk Tomasz , Matecki Grzegorz , Smith Matthew E.
Published: January 2020

Bosek and Krawczyk exhibited an online algorithm for partitioning an online poset of width $w$ into $w^{14\lg w}$ chains. We improve this to $w^{6.5 \lg w + 7}$ with a simpler and shorter proof by combining the work of Bosek & Krawczyk with work of Kierstead & Smith on First-Fit chain partitioning of ladder-free posets. We also provide examples illustrating the limits of our approach.
Chip-Firing on Trees of Loops
Authors: Kailasa Sameer , Kuperberg Vivian , Wawrykow Nicholas
Published: January 2020

Cools, Draisma, Payne, and Robeva proved that generic metric graphs that are "paths of loops" are Brill-Noether general. We show that Brill-Noether generality does not hold for "trees of loops": the only trees of loops that are Brill-Noether general are paths of loops. We study various notions of generality and examine which of these graphs satisfy them.
On the Stability of Independence Polynomials
Authors: Brown Jason I. , Cameron Ben
Published: January 2020

The independence polynomial of a graph is the generating polynomial for the number of independent sets of each size and its roots are called independence roots. We investigate the stability of such polynomials, that is, conditions under which the independence roots lie in the left half-plane. We use results from complex analysis to determine graph operations that result in a stable or nonstable independence polynomial. In particular, we prove that every graph is an induced subgraph of a graph with stable independence polynomial. We also show that the independence polynomials of graphs with independence number at most three are necessarily stable, but for larger independence number, we show that the independence polynomials can have roots arbitrarily far to the right.
Infinite Graphical Frobenius Representations
Authors: Watkins Mark E.
Published: January 2020

A graphical Frobenius representation (GFR) of a Frobenius (permutation) group $G$ is a graph $\Gamma$ whose automorphism group Aut$(\Gamma)$ acts as a Frobenius permutation group on the vertex set of $\Gamma$, that is, Aut$(\Gamma)$ acts vertex-transitively with the property that all nonidentity automorphisms fix either exactly one or zero vertices and there are some of each kind. The set $K$ of all fixed-point-free automorphisms together with the identity is called the kernel of $G$. Whenever $G$ is finite, $K$ is a regular normal subgroup of $G$ (F. G. Frobenius, 1901), in which case $\Gamma$ is a Cayley graph of $K$. The same holds true for all the infinite instances presented here.Infinite, locally finite, vertex-transitive graphs can be classified with respect to (i) the cardinality of their set of ends and (ii) their growth rate. We construct families of infinite GFRs for all possible combinations of these two properties. There exist infinitely many GFRs with polynomial growth of degree $d$ for every positive integer $d$, and there exist infinite families of GFRs of exponential growth, both $1$-ended and infinitely-ended, that underlie infinite chiral planar maps. There also exist GFRs of free products of finitely many finitely generated groups. Graphs of connectivity 1 having a Frobenius automorphism group are characterized.