bluuebunny/crossref_metadata_2025_split huggingface dataset:
On Rainbow Hamilton Cycles in Random Hypergraphs
Authors: Dudek Andrzej , English Sean , Frieze Alan 
Published: January 2020

Let $H_{n,p,r}^{(k)}$ denote a randomly colored random hypergraph, constructed on the vertex set $[n]$ by taking each $k$-tuple independently with probability $p$, and then independently coloring it with a random color from the set $[r]$. Let $H$ be a $k$-uniform hypergraph of order $n$. An $\ell$-Hamilton cycle is a spanning subhypergraph $C$ of $H$ with $n/(k-\ell)$ edges and such that for some cyclic ordering of the vertices each edge of $C$ consists of $k$ consecutive vertices and every pair of adjacent edges in $C$ intersects in precisely $\ell$ vertices.In this note we study the existence of rainbow $\ell$-Hamilton cycles (that is every edge receives a different color) in $H_{n,p,r}^{(k)}$. We mainly focus on the most restrictive case when $r = n/(k-\ell)$. In particular, we show that for the so called tight Hamilton cycles ($\ell=k-1$) $p = e^2/n$ is the sharp threshold for the existence of a rainbow tight Hamilton cycle in $H_{n,p,n}^{(k)}$ for each $k\ge 4$.
Antimagic Orientation of Biregular Bipartite Graphs
Authors: Shan Songling , Yu Xiaowei 
Published: January 2020

An antimagic labeling of a directed graph $D$ with $n$ vertices and $m$ arcs is a bijection from the set of arcs of $D$ to the integers $\{1, \cdots, m\}$ such that all $n$ oriented vertex sums are pairwise distinct, where an oriented vertex sum is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. An undirected graph $G$ is said to have an antimagic orientation if $G$ has an orientation which admits an antimagic labeling. Hefetz, Mütze, and Schwartz conjectured that every connected undirected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that every biregular bipartite graph admits an antimagic orientation.
Bipartite Ramsey Numbers for Graphs of Small Bandwidth
Authors: Shen Lili , Lin Qizhong , Liu Qinghai 
Published: January 2020

A graph $H=(W,E_H)$ is said to have bandwidth at most $b$ if there exists a labeling of $W$ as $w_1,w_2,\dots,w_n$ such that $|i-j|\leq b$ for every edge $w_iw_j\in E_H$, and a bipartite balanced $(\beta,\Delta)$-graph $H$ is a bipartite graph with bandwidth at most $\beta |W|$ and maximum degree at most $\Delta$, and furthermore it has a proper 2-coloring $\chi :W\rightarrow[2]$ such that $||\chi^{-1}(1)|-|\chi^{-1}(2)||\leq\beta|\chi^{-1}(2)|$. We prove that for any fixed $0<\gamma<1$ and integer $\Delta\ge1$, there exist a constant $\beta=\beta(\gamma,\Delta)>0$ and a natural number $n_0$ such that for every balanced $(\beta,\Delta)$-graph $H$ on $n\geq n_0$ vertices the bipartite Ramsey number $br(H,H)$ is at most $(1+\gamma)n$. In particular, $br(C_{2n},C_{2n})=(2+o(1))n$.
Homotopy Type of the Neighborhood Complexes of Graphs of Maximal Degree at most $3$ and $4$-Regular Circulant Graphs
Authors: Shukla Samir 
Published: January 2020

To estimate the lower bound for the chromatic number of a graph $G$, Lovász associated a simplicial complex $\mathcal{N}(G)$ called the neighborhood complex and related the topological connectivity of $\mathcal{N}(G)$ to the chromatic number of $G$. More generally he proved that the chromatic number of $G$ is bounded below by the topological connectivity of $\mathcal{N}(G)$ plus $3$. In this article, we consider the graphs of maximal degree at most $3$ and $4$-regular circulant graphs. We show that each connected component of the neighborhood complexes of these graphs is homotopy equivalent either to a point, to a wedge sum of circles, to a wedge sum of $2$-spheres $S^2$, to $S^3$, to a garland of $2$-spheres $S^2$ or to a connected sum of tori.
Counting Compositions over Finite Abelian Groups
Authors: Gao Zhicheng , MacFie Andrew , Wang Qiang 
Published: January 2020

We find the number of compositions over finite abelian groups under two types of restrictions: (i) each part belongs to a given subset and (ii) small runs of consecutive parts must have given properties. Waring's problem over finite fields can be converted to type (i) compositions, whereas Carlitz and "locally Mullen" compositions can be formulated as type (ii) compositions. We use the multisection formula to translate the problem from integers to group elements, the transfer matrix method to do exact counting, and finally the Perron-Frobenius theorem to derive asymptotics. We also exhibit bijections involving certain restricted classes of compositions.
Powerful Sets: a Generalisation of Binary Matroids
Authors: Farr Graham E. , Wang Andrew Y.Z. 
Published: January 2020

A set $S\subseteq\{0,1\}^E$ of binary vectors, with positions indexed by $E$, is said to be a powerful code if, for all $X\subseteq E$, the number of vectors in $S$ that are zero in the positions indexed by $X$ is a power of 2. By treating binary vectors as characteristic vectors of subsets of $E$, we say that a set $S\subseteq2^E$ of subsets of $E$ is a powerful set if the set of characteristic vectors of sets in $S$ is a powerful code. Powerful sets (codes) include cocircuit spaces of binary matroids (equivalently, linear codes over $\mathbb{F}_2$), but much more besides. Our motivation is that, to each powerful set, there is an associated nonnegative-integer-valued rank function (by a construction of Farr), although it does not in general satisfy all the matroid rank axioms.In this paper we investigate the combinatorial properties of powerful sets. We prove fundamental results on special elements (loops, coloops, frames, near-frames, and stars), their associated types of single-element extensions, various ways of combining powerful sets to get new ones, and constructions of nonlinear powerful sets. We show that every powerful set is determined by its clutter of minimal nonzero members. Finally, we show that the number of powerful sets is doubly exponential, and hence that almost all powerful sets are nonlinear.
Algebraically Grid-Like Graphs have Large Tree-Width
Authors: Weißauer Daniel 
Published: January 2020

By the Grid Minor Theorem of Robertson and Seymour, every graph of sufficiently large tree-width contains a large grid as a minor. Tree-width may therefore be regarded as a measure of 'grid-likeness' of a graph.
The grid contains a long cycle on the perimeter, which is the $\mathbb{F}_2$-sum of the rectangles inside. Moreover, the grid distorts the metric of the cycle only by a factor of two. We prove that every graph that resembles the grid in this algebraic sense has large tree-width:
Let $k, p$ be integers, $\gamma$ a real number and $G$ a graph. Suppose that $G$ contains a cycle of length at least $2 \gamma p k$ which is the $\mathbb{F}_2$-sum of cycles of length at most $p$ and whose metric is distorted by a factor of at most $\gamma$. Then $G$ has tree-width at least $k$.
On the Alon-Tarsi Number and Chromatic-Choosability of Cartesian Products of Graphs
Authors: Kaul Hemanshu , Mudrock Jeffrey A. 
Published: January 2020

We study the list chromatic number of Cartesian products of graphs through the Alon-Tarsi number as defined by Jensen and Toft (1995) in their seminal book on graph coloring problems. The Alon-Tarsi number of $G$, $AT(G)$, is the smallest $k$ for which there is an orientation, $D$, of $G$ with max indegree $k\!-\!1$ such that the number of even and odd circulations contained in $D$ are different. It is known that $\chi(G) \leq \chi_\ell(G) \leq \chi_p(G) \leq AT(G)$, where $\chi(G)$ is the chromatic number, $\chi_\ell(G)$ is the list chromatic number, and $\chi_p(G)$ is the paint number of $G$. In this paper we find families of graphs $G$ and $H$ such that $\chi(G \square H) = AT(G \square H)$, reducing this sequence of inequalities to equality.
We show that the Alon-Tarsi number of the Cartesian product of an odd cycle and a path is always equal to 3. This result is then extended to show that if $G$ is an odd cycle or a complete graph and $H$ is a graph on at least two vertices containing the Hamilton path $w_1, w_2, \ldots, w_n$ such that for each $i$, $w_i$ has a most $k$ neighbors among $w_1, w_2, \ldots, w_{i-1}$, then $AT(G \square H) \leq \Delta(G)+k$ where $\Delta(G)$ is the maximum degree of $G$. We discuss other extensions for $G \square H$, where $G$ is such that $V(G)$ can be partitioned into odd cycles and complete graphs, and $H$ is a graph containing a Hamiltonian path. We apply these bounds to get chromatic-choosable Cartesian products, in fact we show that these families of graphs have $\chi(G) = AT(G)$, improving previously known bounds.
Counting Proper Colourings in 4-Regular Graphs via the Potts Model
Authors: Davies Ewan 
Published: January 2020

We give tight upper and lower bounds on the internal energy per particle in the antiferromagnetic $q$-state Potts model on $4$-regular graphs, for $q\ge 5$. This proves the first case of a conjecture of the author, Perkins, Jenssen and Roberts, and implies tight bounds on the antiferromagnetic Potts partition function. The zero-temperature limit gives upper and lower bounds on the number of proper $q$-colourings of $4$-regular graphs, which almost proves the case $d=4$ of a conjecture of Galvin and Tetali. For any $q \ge 5$ we prove that the number of proper $q$-colourings of a $4$-regular graph is maximised by a union of $K_{4,4}$'s.
A Bijection between Necklaces and Multisets with Divisible Subset Sum
Authors: Chan Swee Hong 
Published: January 2020

Consider these two distinct combinatorial objects: (1) the necklaces of length $n$ with at most $q$ colors, and (2) the multisets of integers modulo $n$ with subset sum divisible by $n$ and with the multiplicity of each element being strictly less than $q$. We show that these two objects have the same cardinality if $q$ and $n$ are mutually coprime. Additionally, when $q$ is a prime power, we construct a bijection between these two objects by viewing necklaces as cyclic polynomials over the finite field of size $q$. Specializing to $q=2$ answers a bijective problem posed by Richard Stanley (Enumerative Combinatorics Vol. 1 Chapter 1, Problem 105(b)).
Ramsey Numbers of Ordered Graphs
Authors: Balko Martin , Cibulka Josef , Král Karel , Kynčl Jan 
Published: January 2020

An ordered graph is a pair $\mathcal{G}=(G,\prec)$ where $G$ is a graph and $\prec$ is a total ordering of its vertices.
The ordered Ramsey number $\overline{R}(\mathcal{G})$ is the minimum number $N$ such that every ordered complete graph with $N$ vertices and with edges colored by two colors contains a monochromatic copy of $\mathcal{G}$.
In contrast with the case of unordered graphs, we show that there are arbitrarily large ordered matchings $\mathcal{M}_n$ on $n$ vertices for which $\overline{R}(\mathcal{M}_n)$ is superpolynomial in $n$. This implies that ordered Ramsey numbers of the same graph can grow superpolynomially in the size of the graph in one ordering and remain linear in another ordering.
We also prove that the ordered Ramsey number $\overline{R}(\mathcal{G})$ is polynomial in the number of vertices of $\mathcal{G}$ if the bandwidth of $\mathcal{G}$ is constant or if $\mathcal{G}$ is an ordered graph of constant degeneracy and constant interval chromatic number.
The first result gives a positive answer to a question of Conlon, Fox, Lee, and Sudakov.
For a few special classes of ordered paths, stars or matchings, we give asymptotically tight bounds on their ordered Ramsey numbers. For so-called monotone cycles we compute their ordered Ramsey numbers exactly. This result implies exact formulas for geometric Ramsey numbers of cycles introduced by Károlyi, Pach, Tóth, and Valtr.
Clumsy Packings of Graphs
Authors: Axenovich Maria , Kaufmann Anika , Yuster Raphael 
Published: January 2020

Let $G$ and $H$ be graphs. We say that $P$ is an $H$-packing of $G$ if $P$ is a set of edge-disjoint copies of $H$ in $G$. An $H$-packing $P$ is maximal if there is no other $H$-packing of $G$ that properly contains P. Packings of maximum cardinality have been studied intensively, with several recent breakthrough results. Here, we consider minimum cardinality maximal packings. An $H$-packing $P$ is called clumsy if it is maximal of minimum size. Let $\mathrm{cl}(G,H)$ be the size of a clumsy $H$-packing of $G$. We provide nontrivial bounds for $\mathrm{cl}(G,H)$, and in many cases asymptotically determine $\mathrm{cl}(G,H)$ for some generic classes of graphs G such as $K_n$ (the complete graph), $Q_n$ (the cube graph), as well as square, triangular, and hexagonal grids. We asymptotically determine $\mathrm{cl}(K_n,H)$ for every fixed non-empty graph $H$. In particular, we prove that
$$\mathrm{cl}(K_n, H) = \frac{\binom{n}{2}- \mathrm{ex}(n,H)}{|E(H)|}+o(\mathrm{ex}(n,H)),$$where $ex(n,H)$ is the extremal number of $H$.
A related natural parameter is $\mathrm{cov}(G,H)$, that is the smallest number of copies of $H$ in $G$ (not necessarily edge-disjoint) whose removal from $G$ results in an $H$-free graph. While clearly $\mathrm{cov}(G,H) \leqslant\mathrm{cl}(G,H)$, all of our lower bounds for $\mathrm{cl}(G,H)$ apply to $\mathrm{cov}(G,H)$ as well.
A Note on Counting Flows in Signed Graphs
Authors: DeVos Matt , Rollová Edita , Šámal Robert 
Published: January 2020

Tutte initiated the study of nowhere-zero flows and proved the following fundamental theorem: For every graph $G$ there is a polynomial $f$ so that for every abelian group $\Gamma$ of order $n$, the number of nowhere-zero $\Gamma$-flows in $G$ is $f(n)$. For signed graphs (which have bidirected orientations), the situation is more subtle. For a finite group $\Gamma$, let $\epsilon_2(\Gamma)$ be the largest integer $d$ so that $\Gamma$ has a subgroup isomorphic to $\mathbb{Z}_2^d$. We prove that for every signed graph $G$ and $d \ge 0$ there is a polynomial $f_d$ so that $f_d(n)$ is the number of nowhere-zero $\Gamma$-flows in $G$ for every abelian group $\Gamma$ with $\epsilon_2(\Gamma) = d$ and $|\Gamma| = 2^d n$. Beck and Zaslavsky [JCTB 2006] had previously established the special case of this result when $d=0$ (i.e., when $\Gamma$ has odd order).
On Almost-Equidistant Sets - II
Authors: Polyanskii Alexandr 
Published: January 2020

A set in $\mathbb R^d$ is called almost-equidistant if for any three distinct points in the set, some two are at unit distance apart. First, we give a short proof of the result of Bezdek and Lángi claiming that an almost-equidistant set lying on a $(d-1)$-dimensional sphere of radius $r$, where $r<1/\sqrt{2}$, has at most $2d+2$ points. Second, we prove that an almost-equidistant set $V$ in $\mathbb R^d$ has $O(d)$ points in two cases: if the diameter of $V$ is at most $1$ or if $V$ is a subset of a $d$-dimensional ball of radius at most $1/\sqrt{2}+cd^{-2/3}$, where $c<1/2$. Also, we present a new proof of the result of Kupavskii, Mustafa and Swanepoel that an almost-equidistant set in $\mathbb R^d$ has $O(d^{4/3})$ elements.
On Grounded L-Graphs and their Relatives
Authors: Jelínek Vít , Töpfer Martin 
Published: January 2020

We consider the graph classes Grounded-L and Grounded-{𝖫,⅃} corresponding to graphs that admit an intersection representation by 𝖫-shaped curves (or 𝖫-shaped and ⅃-shaped curves, respectively), where additionally the topmost points of each curve are assumed to belong to a common horizontal line. We prove that Grounded-L graphs admit an equivalent characterisation in terms of vertex ordering with forbidden patterns.
We also compare these classes to related intersection classes, such as the grounded segment graphs, the monotone 𝖫-graphs (a.k.a. max point-tolerance graphs), or the outer-1-string graphs. We give constructions showing that these classes are all distinct and satisfy only trivial or previously known inclusions.
Spectral Lower Bounds for the Orthogonal and Projective Ranks of a Graph
Authors: Wocjan Pawel , Elphick Clive 
Published: January 2020

The orthogonal rank of a graph $G=(V,E)$ is the smallest dimension $\xi$ such that there exist non-zero column vectors $x_v\in\mathbb{C}^\xi$ for $v\in V$ satisfying the orthogonality condition $x_v^\dagger x_w=0$ for all $vw\in E$. We prove that many spectral lower bounds for the chromatic number, $\chi$, are also lower bounds for $\xi$. This result complements a previous result by the authors, in which they showed that spectral lower bounds for $\chi$ are also lower bounds for the quantum chromatic number $\chi_q$. It is known that the quantum chromatic number and the orthogonal rank are incomparable.
We conclude by proving an inertial lower bound for the projective rank $\xi_f$, and conjecture that a stronger inertial lower bound for $\xi$ is also a lower bound for $\xi_f$.
The Smallest Strictly Neumaier Graph and its Generalisations
Authors: Evans Rhys J. , Goryainov Sergey , Panasenko Dmitry 
Published: January 2020

A regular clique in a regular graph is a clique such that every vertex outside of the clique is adjacent to the same positive number of vertices inside the clique. We continue the study of regular cliques in edge-regular graphs initiated by A. Neumaier in the 1980s and attracting current interest. We thus define a Neumaier graph to be an non-complete edge-regular graph containing a regular clique, and a strictly Neumaier graph to be a non-strongly regular Neumaier graph. We first prove some general results on Neumaier graphs and their feasible parameter tuples. We then apply these results to determine the smallest strictly Neumaier graph, which has $16$ vertices. Next we find the parameter tuples for all strictly Neumaier graphs having at most $24$ vertices. Finally, we give two sequences of graphs, each with $i^{th}$ element a strictly Neumaier graph containing a $2^{i}$-regular clique (where $i$ is a positive integer) and having parameters of an affine polar graph as an edge-regular graph. This answers questions recently posed by G. Greaves and J. Koolen.
Non-Monochromatic Triangles in a 2-Edge-Coloured Graph
Authors: DeVos Matt , McDonald Jessica , Montejano Amanda 
Published: January 2020

Let $G = (V,E)$ be a simple graph and let $\{R,B\}$ be a partition of $E$. We prove that whenever $|E| + \mathrm{min}\{ |R|, |B| \} > { |V| \choose 2 }$, there exists a subgraph of $G$ isomorphic to $K_3$ which contains edges from both $R$ and $B$. If instead equality holds, and $G$ has no such subgraph, then we show that $G$ is in one of a few simple classes.
Cutting Resilient Networks – Complete Binary Trees
Authors: Cai Xing Shi , Holmgren Cecilia 
Published: January 2020

In our previous work, we introduced the random $k$-cut number for rooted graphs. In this paper, we show that the distribution of the $k$-cut number in complete binary trees of size n, after rescaling, is asymptotically a periodic function of $\lg n − \lg \lg n$. Thus there are different limit distributions for different subsequences, where these limits are similar to weakly $1$-stable distributions. This generalizes the result for the case $k = 1$, i.e., the traditional cutting model, by Janson (2004).
Collapsibility of Simplicial Complexes of Hypergraphs
Authors: Lew Alan 
Published: January 2020

Let $\mathcal{H}$ be an $r$-uniform hypergraph. We show that the simplicial complex whose simplices are the hypergraphs $\mathcal{F}\subset\mathcal{H}$ with covering number at most $p$ is $\left(\binom{r+p}{r}-1\right)$-collapsible. Similarly, the simplicial complex whose simplices are the pairwise intersecting hypergraphs $\mathcal{F}\subset\mathcal{H}$ is $\frac{1}{2}\binom{2r}{r}$-collapsible.
A Note on the Connectivity of 2-Polymatroid Minors
Authors: Gershkoff Zachary , Oxley James 
Published: January 2020

Brylawski and Seymour independently proved that if $M$ is a connected matroid with a connected minor $N$, and $e \in E(M) - E(N)$, then $M \backslash e$ or $M / e$ is connected having $N$ as a minor. This paper proves an analogous but somewhat weaker result for $2$-polymatroids. Specifically, if $M$ is a connected $2$-polymatroid with a proper connected minor $N$, then there is an element $e$ of $E(M) - E(N)$ such that $M \backslash e$ or $M / e$ is connected having $N$ as a minor. We also consider what can be said about the uniqueness of the way in which the elements of $E(M) - E(N)$ can be removed so that connectedness is always maintained.
Partitioning the Power Set of $[n]$ into $C_k$-free parts
Authors: Blaisdell Eben , Gyárfás András , Krueger Robert A. , Wdowinski Ronen 
Published: January 2020

We show that for $n \geq 3, n\ne 5$, in any partition of $\mathcal{P}(n)$, the set of all subsets of $[n]=\{1,2,\dots,n\}$, into $2^{n-2}-1$ parts, some part must contain a triangle — three different subsets $A,B,C\subseteq [n]$ such that $A\cap B,A\cap C,B\cap C$ have distinct representatives. This is sharp, since by placing two complementary pairs of sets into each partition class, we have a partition into $2^{n-2}$ triangle-free parts. We also address a more general Ramsey-type problem: for a given graph $G$, find (estimate) $f(n,G)$, the smallest number of colors needed for a coloring of $\mathcal{P}(n)$, such that no color class contains a Berge-$G$ subhypergraph. We give an upper bound for $f(n,G)$ for any connected graph $G$ which is asymptotically sharp when $G$ is a cycle, path, or star. Additional bounds are given when $G$ is a $4$-cycle and when $G$ is a claw.
Fractional Factors, Component Factors and Isolated Vertex Conditions in Graphs
Authors: Yu Roger , Kano Mikio , Lu Hongliang 
Published: January 2020

For a graph $G = (V, E)$, a fractional $[a, b]$-factor is a real valued function $h:E(G)\to [0,1]$ that satisfies $a \le ~ \sum_{e\in E_G(v)} h(e) ~ \le b$ for all $ v\in V(G)$, where $a$ and $b$ are real numbers and $E_G(v)$ denotes the set of edges incident with $v$. In this paper, we prove that the condition $\mathit{iso}(G-S) \le (k+\frac{1}{2})|S|$ is equivalent to the existence of fractional $[1,k+ \frac{1}{2}]$-factors, where ${\mathit{iso}}(G-S)$ denotes the number of isolated vertices in $G-S$. Using fractional factors as a tool, we construct component factors under the given isolated conditions. Namely, (i) a graph $G$ has a $\{P_2,C_3,P_5, \mathcal{T}(3)\}$-factor if and only if $\mathit{iso}(G-S) \le \frac{3}{2}|S|$ for all $S\subset V(G)$; (ii) a graph $G$ has a $\{K_{1,1}, K_{1,2}, \ldots,$ $K_{1,k}, \mathcal{T}(2k+1)\}$-factor ($k\ge 2$) if and only if $\mathit{iso}(G-S) \le (k+\frac{1}{2})|S|$ for all $S\subset V(G)$, where $\mathcal{T}(3)$ and $\mathcal{T}(2k+1)$ are two special families of trees.
When is the $q$-Multiplicity of a Weight a Power of $q$?
Authors: Harris Pamela E. , Rahmoeller Margaret , Schneider Lisa , Simpson Anthony 
Published: January 2020

Berenshtein and Zelevinskii provided an exhaustive list of pairs of weights $(\lambda,\mu)$ of simple Lie algebras $\mathfrak{g}$ (up to Dynkin diagram isomorphism) for which the multiplicity of the weight $\mu$ in the representation of $\mathfrak{g}$ with highest weight $\lambda$ is equal to one. Using Kostant's weight multiplicity formula we describe and enumerate the contributing terms to the multiplicity for subsets of these pairs of weights and show that, in these cases, the cardinality of these contributing sets is enumerated by (multiples of) Fibonacci numbers. We conclude by using these results to compute the associated $q$-multiplicity for the pairs of weights considered, and conjecture that in all cases the $q$-multiplicity of such pairs of weights is given by a power of $q$.
A Note on Hedetniemi's Conjecture, Stahl's Conjecture and the Poljak-Rödl Function
Authors: Tardif Claude , Zhu Xuding 
Published: January 2020

We prove that $\min\{\chi(G), \chi(H)\} - \chi(G\times H)$ can be arbitrarily large, and that if Stahl's conjecture on the multichromatic number of Kneser graphs holds, then $\min\{\chi(G), \chi(H)\}/\chi(G\times H) \leq 1/2 + \epsilon$ for large values of $\min\{\chi(G), \chi(H)\}$.