bluuebunny/crossref_metadata_2025_split huggingface dataset:
Sharp Lower Bounds on the Spectral Radius of Uniform Hypergraphs Concerning Degrees
Authors: Kang Liying , Liu Lele , Shan Erfang 
Published: January 2020

Let $\mathcal{A}(H)$ and $\mathcal{Q}(H)$ be the adjacency tensor and signless Laplacian tensor of an $r$-uniform hypergraph $H$. Denote by $\rho(H)$ and $\rho(\mathcal{Q}(H))$ the spectral radii of $\mathcal{A}(H)$ and $\mathcal{Q}(H)$, respectively. In this paper we present a lower bound on $\rho(H)$ in terms of vertex degrees and we characterize the extremal hypergraphs attaining the bound, which solves a problem posed by Nikiforov [Analytic methods for uniform hypergraphs, Linear Algebra Appl. 457 (2014) 455–535]. Also, we prove a lower bound on $\rho(\mathcal{Q}(H))$ concerning degrees and give a characterization of the extremal hypergraphs attaining the bound.
On Bipartite Cages of Excess 4
Authors: Filipovski Slobodan 
Published: January 2020

The Moore bound $M(k,g)$ is a lower bound on the order of $k$-regular graphs of girth $g$ (denoted $(k,g)$-graphs). The excess $e$ of a $(k,g)$-graph of order $n$ is the difference $ n-M(k,g) $. In this paper we consider the existence of $(k,g)$-bipartite graphs of excess $4$ by studying spectral properties of their adjacency matrices. For a given graph $G$ and for the integers $i$ with $0\leq i\leq diam(G)$, the $i$-distance matrix $A_i$ of $G$ is an $n\times n$ matrix such that the entry in position $(u,v)$ is $1$ if the distance between the vertices $u$ and $v$ is $i$, and zero otherwise. We prove that the $(k,g)$-bipartite graphs of excess $4$ satisfy the equation $kJ=(A+kI)(H_{d-1}(A)+E)$, where $A=A_{1}$ denotes the adjacency matrix of the graph in question, $J$ the $n \times n$ all-ones matrix, $E=A_{d+1}$ the adjacency matrix of a union of vertex-disjoint cycles, and $H_{d-1}(x)$ is the Dickson polynomial of the second kind with parameter $k-1$ and degree $d-1$. We observe that the eigenvalues other than $\pm k$ of these graphs are roots of the polynomials $H_{d-1}(x)+\lambda$, where $\lambda$ is an eigenvalue of $E$. Based on the irreducibility of $H_{d-1}(x)\pm2$, we give necessary conditions for the existence of these graphs. If $E$ is the adjacency matrix of a cycle of order $n$, we call the corresponding graphs graphs with cyclic excess; if $E$ is the adjacency matrix of a disjoint union of two cycles, we call the corresponding graphs graphs with bicyclic excess. In this paper we prove the non-existence of $(k,g)$-graphs with cyclic excess $4$ if $k\geq6$ and $k \equiv1 \!\! \pmod {3}$, $g=8, 12, 16$ or $k \equiv2 \!\! \pmod {3}$, $g=8;$ and the non-existence of $(k,g)$-graphs with bicyclic excess $4$ if $k\geq7$ is an odd number and $g=2d$ such that $d\geq4$ is even.
On $t$-Common List-Colorings
Authors: Choi Hojin , Kwon Young Soo 
Published: January 2020

In this paper, we introduce a new variation of list-colorings. For a graph $G$ and for a given nonnegative integer $t$, a $t$-common list assignment of $G$ is a mapping $L$ which assigns each vertex $v$ a set $L(v)$ of colors such that given set of $t$ colors belong to $L(v)$ for every $v\in V(G)$. The $t$-common list chromatic number of $G$ denoted by $ch_t(G)$ is defined as the minimum positive integer $k$ such that there exists an $L$-coloring of $G$ for every $t$-common list assignment $L$ of $G$, satisfying $|L(v)| \ge k$ for every vertex $v\in V(G)$. We show that for all positive integers $k, \ell$ with $2 \le k \le \ell$ and for any positive integers $i_1 , i_2, \ldots, i_{k-2}$ with $k \le i_{k-2} \le \cdots \le i_1 \le \ell$, there exists a graph $G$ such that $\chi(G)= k$, $ch(G) = \ell$ and $ch_t(G) = i_t$ for every $t=1, \ldots, k-2$. Moreover, we consider the $t$-common list chromatic number of planar graphs. From the four color theorem and the result of Thomassen (1994), for any $t=1$ or $2$, the sharp upper bound of $t$-common list chromatic number of planar graphs is $4$ or $5$. Our first step on $t$-common list chromatic number of planar graphs is to find such a sharp upper bound. By constructing a planar graph $G$ such that $ch_1(G) =5$, we show that the sharp upper bound for $1$-common list chromatic number of planar graphs is $5$. The sharp upper bound of $2$-common list chromatic number of planar graphs is still open. We also suggest several questions related to $t$-common list chromatic number of planar graphs.
Toggling Independent Sets of a Path Graph
Authors: Joseph Michael , Roby Tom 
Published: January 2020

This paper explores the orbit structure and homomesy (constant averages over orbits) properties of certain actions of toggle groups on the collection of independent sets of a path graph. In particular we prove a generalization of a homomesy conjecture of Propp that for the action of a "Coxeter element" of vertex toggles, the difference of indicator functions of symmetrically-located vertices is 0-mesic. Then we use our analysis to show facts about orbit sizes that are easy to conjecture but nontrivial to prove. Besides its intrinsic interest, this particular combinatorial dynamical system is valuable in providing an interesting example of (a) homomesy in a context where large orbit sizes make a cyclic sieving phenomenon unlikely to exist, (b) the use of Coxeter theory to greatly generalize the set of actions for which results hold, and (c) the usefulness of Striker's notion of generalized toggle groups.
Bispindles in Strongly Connected Digraphs with Large Chromatic Number
Authors: Cohen Nathann , Havet Frédéric , Lochet William , Lopes Raul 
Published: January 2020

A $(k_1+k_2)$-bispindle is the union of $k_1$ $(x,y)$-dipaths and $k_2$ $(y,x)$-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every $(1,1)$- bispindle $B$, there exists an integer $k$ such that every strongly connected digraph with chromatic number greater than $k$ contains a subdivision of $B$. We investigate generalizations of this result by first showing constructions of strongly connected digraphs with large chromatic number without any $(3,0)$-bispindle or $(2,2)$-bispindle. We then consider $(2,1)$-bispindles. Let $B(k_1,k_2;k_3)$ denote the $(2,1)$-bispindle formed by three internally disjoint dipaths between two vertices $x,y$, two $(x,y)$-dipaths, one of length $k_1$ and the other of length $k_2$, and one $(y,x)$-dipath of length $k_3$. We conjecture that for any positive integers $k_1, k_2,k_3$, there is an integer $g(k_1,k_2,k_3)$ such that every strongly connected digraph with chromatic number greater than $g(k_1,k_2,k_3)$ contains a subdivision of $B(k_1,k_2;k_3)$. As evidence, we prove this conjecture for $k_2=1$ (and $k_1, k_3$ arbitrary).
Majority Choosability of Digraphs
Authors: Anholcer Marcin , Bosek Bartłomiej , Grytczuk Jarosław 
Published: January 2020

A majority coloring of a digraph is a coloring of its vertices such that for each vertex $v$, at most half of the out-neighbors of $v$ have the same color as $v$. A digraph $D$ is majority $k$-choosable if for any assignment of lists of colors of size $k$ to the vertices there is a majority coloring of $D$ from these lists. We prove that every digraph is majority $4$-choosable. This gives a positive answer to a question posed recently by Kreutzer, Oum, Seymour, van der Zypen, and Wood (2017). We obtain this result as a consequence of a more general theorem, in which majority condition is profitably extended. For instance, the theorem implies also that every digraph has a coloring from arbitrary lists of size three, in which at most $2/3$ of the out-neighbors of any vertex share its color. This solves another problem posed by the same authors, and supports an intriguing conjecture stating that every digraph is majority $3$-colorable.
Fair Representation in the Intersection of Two Matroids
Authors: Aharoni Ron , Berger Eli , Kotlar Dani , Ziv Ran 
Published: January 2020

Mysteriously, hypergraphs that are the intersection of two matroids behave in some respects almost as well as one matroid. In the present paper we study one such phenomenon - the surprising ability of the intersection of two matroids to fairly represent the parts of a given partition of the ground set. For a simplicial complex $\mathcal{C}$ denote by $\beta(\mathcal{C})$ the minimal number of edges from $\mathcal{C}$ needed to cover the ground set. If $\mathcal{C}$ is a matroid then for every partition $A_1, \ldots, A_m$ of the ground set there exists a set $S \in \mathcal{C}$ meeting each $A_i$ in at least $\lfloor \frac{|A_i|}{\beta(\mathcal{C})}\rfloor$ elements. We conjecture that a slightly weaker result is true for the intersection of two matroids: if $\mathcal{D}=\mathcal{P}\cap \mathcal{Q}$, where $\mathcal{P},\mathcal{Q}$ are matroids on the same ground set $V$ and $\beta(\mathcal{P}), \beta(\mathcal{Q}) \le k$, then for every partition $A_1, \ldots, A_m$ of the ground set there exists a set $S \in \mathcal{D}$ meeting each $A_i$ in at least $\frac{1}{k}|A_i|-1$ elements. We prove that if $m=2$ (meaning that the partition is into two sets) there is a set belonging to $\mathcal{D}$ meeting each $A_i$ in at least $(\frac{1}{k}-\frac{1}{|V|})|A_i|-1$ elements.
Expanders with Superquadratic Growth
Authors: Balog Antal , Roche-Newton Oliver , Zhelezov Dmitry 
Published: January 2020

We prove several expanders with exponent strictly greater than $2$. For any finite set $A \subset \mathbb R$, we prove the following six-variable expander results:$|(A-A)(A-A)(A-A)| \gg \frac{|A|^{2+\frac{1}{8}}}{\log^{\frac{17}{16}}|A|},$$\left|\frac{A+A}{A+A}+\frac{A}{A}\right| \gg \frac{|A|^{2+\frac{2}{17}}}{\log^{\frac{16}{17}}|A|},$ $\left|\frac{AA+AA}{A+A}\right| \gg \frac{|A|^{2+\frac{1}{8}}}{\log |A|},$ $\left|\frac{AA+A}{AA+A}\right| \gg \frac{|A|^{2+\frac{1}{8}}}{\log |A|}.$
Burling Graphs, Chromatic Number, and Orthogonal Tree-Decompositions
Authors: Felsner Stefan , Joret Gwenaël , Micek Piotr , Trotter William T. , Wiechert Veit 
Published: January 2020

A classic result of Asplund and Grünbaum states that intersection graphs of axis-aligned rectangles in the plane are $\chi$-bounded. This theorem can be equivalently stated in terms of path-decompositions as follows: There exists a function $f:\mathbb{N}\to\mathbb{N}$ such that every graph that has two path-decompositions such that each bag of the first decomposition intersects each bag of the second in at most $k$ vertices has chromatic number at most $f(k)$. Recently, Dujmović, Joret, Morin, Norin, and Wood asked whether this remains true more generally for two tree-decompositions. In this note we provide a negative answer: There are graphs with arbitrarily large chromatic number for which one can find two tree-decompositions such that each bag of the first decomposition intersects each bag of the second in at most two vertices. Furthermore, this remains true even if one of the two decompositions is restricted to be a path-decomposition. This is shown using a construction of triangle-free graphs with unbounded chromatic number due to Burling, which we believe should be more widely known.
Orbits of Antichains in Certain Root Posets
Authors: Dong Chao-Ping , Wang Suijie 
Published: January 2020

Building everything from scratch, we give another proof of Propp and Roby's theorem saying that the average antichain size in any reverse operator orbit of the poset $[m]\times [n]$ is $\frac{mn}{m+n}$. It is conceivable that our method should work for other situations. As a demonstration, we show that the average size of antichains in any reverse operator orbit of $[m]\times K_{n-1}$ equals $\frac{2mn}{m+2n-1}$. Here $K_{n-1}$ is the minuscule poset $[n-1]\oplus ([1] \sqcup [1]) \oplus [n-1]$. Note that $[m]\times [n]$ and $[m]\times K_{n-1}$ can be interpreted as sub-families of certain root posets. We guess these root posets should provide a unified setting to exhibit the homomesy phenomenon defined by Propp and Roby.
A Combinatorial Proof of a Formula of Biane and Chapuy
Authors: Chewi Sinho , Anantharam Venkat 
Published: January 2020

Let $G$ be a simple strongly connected weighted directed graph. Let $\mathcal{G}$ denote the spanning tree graph of $G$. That is, the vertices of $\mathcal{G}$ consist of the directed rooted spanning trees on $G$, and the edges of $\mathcal{G}$ consist of pairs of trees $(t_i, t_j)$ such that $t_j$ can be obtained from $t_i$ by adding the edge from the root of $t_i$ to the root of $t_j$ and deleting the outgoing edge from $t_j$. A formula for the ratio of the sum of the weights of the directed rooted spanning trees on $\mathcal{G}$ to the sum of the weights of the directed rooted spanning trees on $G$ was recently given by Biane and Chapuy. Our main contribution is an alternative proof of this formula, which is both simple and combinatorial.
Defective 3-Paintability of Planar Graphs
Authors: Gutowski Grzegorz , Han Ming , Krawczyk Tomasz , Zhu Xuding 
Published: January 2020

A $d$-defective $k$-painting game on a graph $G$ is played by two players: Lister and Painter. Initially, each vertex is uncolored and has $k$ tokens. In each round, Lister marks a chosen set $M$ of uncolored vertices and removes one token from each marked vertex. In response, Painter colors vertices in a subset $X$ of $M$ which induce a subgraph $G[X]$ of maximum degree at most $d$. Lister wins the game if at the end of some round there is an uncolored vertex that has no more tokens left. Otherwise, all vertices eventually get colored and Painter wins the game. We say that $G$ is $d$-defective $k$-paintable if Painter has a winning strategy in this game. In this paper we show that every planar graph is 3-defective 3-paintable and give a construction of a planar graph that is not 2-defective 3-paintable.
On Vertex-Disjoint Paths in Regular Graphs
Authors: Han Jie 
Published: January 2020

Let $c\in (0, 1]$ be a real number and let $n$ be a sufficiently large integer. We prove that every $n$-vertex $c n$-regular graph $G$ contains a collection of $\lfloor 1/c \rfloor$ paths whose union covers all but at most $o(n)$ vertices of $G$. The constant $\lfloor 1/c \rfloor$ is best possible when $1/c\notin \mathbb{N}$ and off by $1$ otherwise. Moreover, if in addition $G$ is bipartite, then the number of paths can be reduced to $\lfloor 1/(2c) \rfloor$, which is best possible.
Symmetric Chain Decompositions of Products of Posets with Long Chains
Authors: David Stefan , Spink Hunter , Tiba Marius 
Published: January 2020

We ask if there exists a symmetric chain decomposition of the cuboid $Q_k \times n$ such that no chain is taut, i.e. no chain has a subchain of the form $(a_1,\ldots, a_k,0)\prec \cdots\prec (a_1,\ldots,a_k,n-1)$. In this paper, we show this is true precisely when $k \ge 5$ and $n\ge 3$. This question arises naturally when considering products of symmetric chain decompositions which induce orthogonal chain decompositions — the existence of the decompositions provided in this paper unexpectedly resolves the most difficult case of previous work by the second author on almost orthogonal symmetric chain decompositions (2017), making progress on a conjecture of Shearer and Kleitman (1979). In general, we show that for a finite graded poset $P$, there exists a canonical bijection between symmetric chain decompositions of $P \times m$ and $P \times n$ for $m, n\ge rk(P) + 1$, that preserves the existence of taut chains. If $P$ has a unique maximal and minimal element, then we also produce a canonical $(rk(P) +1)$ to $1$ surjection from symmetric chain decompositions of $P \times (rk(P) + 1)$ to symmetric chain decompositions of $P \times rk(P)$ which sends decompositions with taut chains to decompositions with taut chains.
The Extremal Function and Colin de Verdière Graph Parameter
Authors: McCarty Rose 
Published: January 2020

The Colin de Verdière parameter $\mu(G)$ is a minor-monotone graph parameter with connections to differential geometry. We study the conjecture that for every integer $t$, if $G$ is a graph with at least $t$ vertices and $\mu(G) \leq t$, then $|E(G)| \leq t|V(G)|-\binom{t+1}{2}$. We observe a relation to the graph complement conjecture for the Colin de Verdière parameter and prove the conjectured edge upper bound for graphs $G$ such that either $\mu(G) \leq 7$, or $\mu(G) \geq |V(G)|-6$, or the complement of $G$ is chordal, or $G$ is chordal.
Generalized Non-Crossing Partitions and Buildings
Authors: Heller Julia , Schwer Petra 
Published: January 2020

For any finite Coxeter group $W$ of rank $n$ we show that the order complex of the lattice of non-crossing partitions $\mathrm{NC}(W)$ embeds as a chamber subcomplex into a spherical building of type $A_{n-1}$. We use this to give a new proof of the fact that the non-crossing partition lattice in type $A_n$ is supersolvable for all $n$. Moreover, we show that in case $B_n$, this is only the case if $n<4$. We also obtain a lower bound on the radius of the Hurwitz graph $H(W)$ in all types and re-prove that in type $A_n$ the radius is $\binom{n}{2}$. A Corrigendum for this paper was added on May 17, 2018.
Pentagon Contact Representations
Authors: Felsner Stefan , Schrezenmaier Hendrik , Steiner Raphael 
Published: January 2020

Representations of planar triangulations as contact graphs of a set of internally disjoint homothetic triangles or of a set of internally disjoint homothetic squares have received quite some attention in recent years. In this paper we investigate representations of planar triangulations as contact graphs of a set of internally disjoint homothetic pentagons. Surprisingly such a representation exists for every triangulation whose outer face is a $5$-gon. We relate these representations to five color forests. These combinatorial structures resemble Schnyder woods and transversal structures, respectively. In particular there is a bijection to certain $\alpha$-orientations and consequently a lattice structure on the set of five color forests of a given graph. This lattice structure plays a role in an algorithm that is supposed to compute a contact representation with pentagons for a given graph. Based on a five color forest the algorithm builds a system of linear equations and solves it, if the solution is non-negative, it encodes distances between corners of a pentagon representation. In this case the representation is constructed and the algorithm terminates. Otherwise negative variables guide a change of the five color forest and the procedure is restarted with the new five color forest. Similar algorithms have been proposed for contact representations with homothetic triangles and with squares.
Baxter Posets
Authors: Meehan Emily 
Published: January 2020

We define a family of combinatorial objects, which we call Baxter posets. We prove that Baxter posets are counted by the Baxter numbers by showing that they are the adjacency posets of diagonal rectangulations. Given a diagonal rectangulation, we describe the cover relations in the associated Baxter poset. Given a Baxter poset, we describe a method for obtaining the associated Baxter permutation and the associated twisted Baxter permutation.
Vizing's 2-Factor Conjecture Involving Toughness and Maximum Degree Conditions
Authors: Kanno Jinko , Shan Songling 
Published: January 2020

Let $G$ be a simple graph, and let $\Delta(G)$ and $\chi'(G)$ denote the maximum degree and chromatic index of $G$, respectively. Vizing proved that $\chi'(G)=\Delta(G)$ or $\chi'(G)=\Delta(G)+1$. We say $G$ is $\Delta$-critical if $\chi'(G)=\Delta(G)+1$ and $\chi'(H)<\chi'(G)$ for every proper subgraph $H$ of $G$. In 1968, Vizing conjectured that if $G$ is a $\Delta$-critical graph, then $G$ has a 2-factor. Let $G$ be an $n$-vertex $\Delta$-critical graph. It was proved that if $\Delta(G)\ge n/2$, then $G$ has a 2-factor; and that if $\Delta(G)\ge 2n/3+13$, then $G$ has a hamiltonian cycle, and thus a 2-factor. It is well known that every 2-tough graph with at least three vertices has a 2-factor. We investigate the existence of a 2-factor in a $\Delta$-critical graph under "moderate" given toughness and maximum degree conditions. In particular, we show that if $G$ is an $n$-vertex $\Delta$-critical graph with toughness at least 3/2 and with maximum degree at least $n/3$, then $G$ has a 2-factor. We also construct a family of graphs that have order $n$, maximum degree $n-1$, toughness at least $3/2$, but have no 2-factor. This implies that the $\Delta$-criticality in the result is needed. In addition, we develop new techniques in proving the existence of 2-factors in graphs.
On Bergeron's Positivity Problem for $q$-Binomial Coefficients
Authors: Zanello Fabrizio 
Published: January 2020

F. Bergeron recently asked the intriguing question whether $\binom{b+c}{b}_q -\binom{a+d}{d}_q$ has nonnegative coefficients as a polynomial in $q$, whenever $a,b,c,d$ are positive integers, $a$ is the smallest, and $ad=bc$. We conjecture that, in fact, this polynomial is also always unimodal, and combinatorially show our conjecture for $a\le 3$ and any $b,c\ge 4$. The main ingredient will be a novel (and rather technical) application of Zeilberger's KOH theorem.
Likelihood Orders for the $p$-Cycle Walks on the Symmetric Group
Authors: Bernstein Megan 
Published: January 2020

Consider for a random walk on a group, the order from most to least likely element of the walk at each step, called the likelihood order. Up to periodicity issues, this order stabilizes after a sufficient number of steps. Here discrete Fourier analysis and the representations of the symmetric group, particularly formulas for the characters, are used to find the order after sufficient time for the random walks on the symmetric group generated by $p$-cycles for any $p$ fixed, $n$ sufficiently large. For the transposition walk, generated by all the $2$-cycles, at various levels of laziness, it is shown that order $n^2$ steps suffice for the order to stabilize. Likelihood orders can aid in finding the total variation or separation distance mixing times.
Uniquely $K_r^{(k)}$-Saturated Hypergraphs
Authors: Gyárfás András , Hartke Stephen G. , Viss Charles 
Published: January 2020

In this paper we generalize the concept of uniquely $K_r$-saturated graphs to hypergraphs. Let $K_r^{(k)}$ denote the complete $k$-uniform hypergraph on $r$ vertices. For integers $k,r,n$ such that $2\leqslant k <r<n$, a $k$-uniform hypergraph $H$ with $n$ vertices is uniquely $K_r^{(k)}$-saturated if $H$ does not contain $K_r^{(k)}$ but adding to $H$ any $k$-set that is not a hyperedge of $H$ results in exactly one copy of $K_r^{(k)}$. Among uniquely $K_r^{(k)}$-saturated hypergraphs, the interesting ones are the primitive ones that do not have a dominating vertex—a vertex belonging to all possible ${n-1\choose k-1}$ edges. Translating the concept to the complements of these hypergraphs, we obtain a natural restriction of $\tau$-critical hypergraphs: a hypergraph $H$ is uniquely $\tau$-critical if for every edge $e$, $\tau(H-e)=\tau(H)-1$ and $H-e$ has a unique transversal of size $\tau(H)-1$.We have two constructions for primitive uniquely $K_r^{(k)}$-saturated hypergraphs. One shows that for $k$ and $r$ where $4\leqslant k<r\leqslant 2k-3$, there exists such a hypergraph for every $n>r$. This is in contrast to the case $k=2$ and $r=3$ where only the Moore graphs of diameter two have this property. Our other construction keeps $n-r$ fixed; in this case we show that for any fixed $k\ge 2$ there can only be finitely many examples. We give a range for $n$ where these hypergraphs exist. For $n-r=1$ the range is completely determined: $k+1\leqslant n \leqslant {(k+2)^2\over 4}$. For larger values of $n-r$ the upper end of our range reaches approximately half of its upper bound. The lower end depends on the chromatic number of certain Johnson graphs.
A Limit Theorem for the Six-length of Random Functional Graphs with a Fixed Degree Sequence
Authors: Leckey Kevin , Wormald Nick 
Published: January 2020

We obtain results on the limiting distribution of the six-length of a random functional graph, also called a functional digraph or random mapping, with given in-degree sequence. The six-length of a vertex $v\in V$ is defined from the associated mapping, $f:V\to V$, to be the maximum $i\in V$ such that the elements $v, f(v), \ldots, f^{i-1}(v)$ are all distinct. This has relevance to the study of algorithms for integer factorisation.