Search

The spread of a graph $G$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $G$. In this paper, we consider the family of graphs which contain no $K_{s,t}$-minor. We show that for any $t\geq s \geq 2$, there is an integer $\xi_{t}$ such that the extremal $n$-vertex $K_{s,t}$-minor-free graph attaining the maximum spread is the graph obtained by joining a graph $L$ on $(s-1)$ vertices to the disjoint union of $\lfloor \frac{2n+\xi_{t}}{3t}\rfloor$ copies of $K_t$ and $n-s+1 - t\lfloor \frac{2n+\xi_t}{3t}\rfloor$ isolated vertices. Furthermore, we give an explicit formula for $\xi_{t}$ and an explicit description for the graph $L$ for $t \geq \frac32(s-3) +\frac{4}{s-1}$., Comment: 21 pages. arXiv admin note: text overlap with arXiv:2212.05540

For integers $k>\ell\ge0$, a graph $G$ is $(k,\ell)$-stable if $\alpha(G-S)\geq \alpha(G)-\ell$ for every $S\subseteq V(G)$ with $|S|=k$. A recent result of Dong and Wu [SIAM J. Discrete Math., 36 (2022) 229--240] shows that every $(k,\ell)$-stable graph $G$ satisfies $\alpha(G) \le \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$. A $(k,\ell)$-stable graph $G$ is tight if $\alpha(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$; and $q$-tight for some integer $q\ge0$ if $\alpha(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell-q$. In this paper, we first prove that for all $k\geq 24$, the only tight $(k, 0)$-stable graphs are $K_{k+1}$ and $K_{k+2}$, answering a question of Dong and Luo [arXiv: 2401.16639]. We then prove that for all nonnegative integers $k, \ell, q$ with $k\geq 3\ell+3$, every $q$-tight $(k,\ell)$-stable graph has at most $k-3\ell-3+2^{3(\ell+2q+4)^2}$ vertices, answering a question of Dong and Luo in the negative., Comment: 11 pages

In this paper, we show that all simple outerplanar graphs $G$ with minimum degree at least $2$ and positive Lin-Lu-Yau Ricci curvature on every edge have maximum degree at most $9$. Furthermore, if $G$ is maximally outerplanar, then $G$ has at most $10$ vertices. Both upper bounds are sharp., Comment: 10 pages

In this paper, we show that the oriented diameter of any $n$-vertex $2$-connected near triangulation is at most $\lceil{\frac{n}{2}}\rceil$ (except for seven small exceptions), and the upper bound is tight. This extends a result of Wang et.al. on the oriented diameter of maximal outerplanar graphs, and improves an upper bound of $n/2+O(\sqrt{n})$ on the oriented diameter of planar triangulations by Mondal, Parthiban and Rajasingh.

The spread of a graph $G$ is the difference between the largest and smallest eigenvalues of the adjacency matrix of $G$. In this paper, we consider the family of graphs which contain no $K_{2,t}$-minor. We show that for any $t\geq 2$, there is an integer $\xi_t$ such that the maximum spread of an $n$-vertex $K_{2,t}$-minor-free graph is achieved by the graph obtained by joining a vertex to the disjoint union of $\lfloor \frac{2n+\xi_t}{3t}\rfloor$ copies of $K_t$ and $n-1 - t\lfloor \frac{2n+\xi_t}{3t}\rfloor$ isolated vertices. The extremal graph is unique, except when $t\equiv 4 \mod 12$ and $\frac{2n+ \xi_t} {3t}$ is an integer, in which case the other extremal graph is the graph obtained by joining a vertex to the disjoint union of $\lfloor \frac{2n+\xi_t}{3t}\rfloor-1$ copies of $K_t$ and $n-1-t(\lfloor \frac{2n+\xi_t}{3t}\rfloor-1)$ isolated vertices. Furthermore, we give an explicit formula for $\xi_t$., Comment: Minor revisions. arXiv admin note: text overlap with arXiv:2209.13776

The spread of a graph $G$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $G$. Gotshall, O'Brien and Tait conjectured that for sufficiently large $n$, the $n$-vertex outerplanar graph with maximum spread is the graph obtained by joining a vertex to a path on $n-1$ vertices. In this paper, we disprove this conjecture by showing that the extremal graph is the graph obtained by joining a vertex to a path on $\lceil (2n-1)/3\rceil$ vertices and $\lfloor(n-2)/3\rfloor$ isolated vertices. For planar graphs, we show that the extremal $n$-vertex planar graph attaining the maximum spread is the graph obtained by joining two nonadjacent vertices to a path on $\lceil(2n-2)/3\rceil$ vertices and $\lfloor(n-4)/3\rfloor$ isolated vertices.

A graph $G$ is said to satisfy the Vizing bound if $\chi(G)\leq \omega(G)+1$, where $\chi(G)$ and $\omega(G)$ denote the chromatic number and clique number of $G$, respectively. It was conjectured by Randerath in 1998 that if $G$ is a triangle-free and fork-free graph, where the fork (also known as trident) is obtained from $K_{1,4}$ by subdividing two edges, then $G$ satisfies the Vizing bound. In this paper, we confirm this conjecture., Comment: 24 pages, 1 figure

For any positive integer $t$, a \emph{$t$-broom} is a graph obtained from $K_{1,t+1}$ by subdividing an edge once. In this paper, we show that, for graphs $G$ without induced $t$-brooms, we have $\chi(G) = o(\omega(G)^{t+1})$, where $\chi(G)$ and $\omega(G)$ are the chromatic number and clique number of $G$, respectively. When $t=2$, this answers a question of Schiermeyer and Randerath. Moreover, for $t=2$, we strengthen the bound on $\chi(G)$ to $7\omega(G)^2$, confirming a conjecture of Sivaraman. For $t\geq 3$ and \{$t$-broom, $K_{t,t}$\}-free graphs, we improve the bound to $o(\omega^{t})$., Comment: 14 pages, 1 figure

Hakimi, Schmeichel, and Thomassen in 1979 conjectured that every $4$-connected planar triangulation $G$ on $n$ vertices has at least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a double wheel. In this paper, we show that every $4$-connected planar triangulation on $n$ vertices has $\Omega(n^2)$ Hamiltonian cycles. Moreover, we show that if $G$ is a $4$-connected planar triangulation on $n$ vertices and the distance between any two vertices of degree $4$ in $G$ is at least $3$, then $G$ has $2^{\Omega(n^{1/4})}$ Hamiltonian cycles., Comment: arXiv admin note: text overlap with arXiv:2104.04898

An edge-colored graph $G$ is called \textit{rainbow} if every edge of $G$ receives a different color. Given any host graph $G$, the \textit{anti-Ramsey} number of $t$ edge-disjoint rainbow spanning trees in $G$, denoted by $r(G,t)$, is defined as the maximum number of colors in an edge-coloring of $G$ containing no $t$ edge-disjoint rainbow spanning trees. For any vertex partition $P$, let $E(P,G)$ be the set of non-crossing edges in $G$ with respect to $P$. In this paper, we determine $r(G,t)$ for all host graphs $G$: $r(G,t)=|E(G)|$ if there exists a partition $P_0$ with $|E(G)|-|E(P_0,G)|

In this paper, we study the maximum spectral radius of outerplanar $3$-uniform hypergraphs. Given a hypergraph $\mathcal{H}$, the shadow of $\mathcal{H}$ is a graph $G$ with $V(G)= V(\mathcal{H})$ and $E(G) = \{uv: uv \in h \textrm{ for some } h\in E(\mathcal{H})\}$. A graph is \textit{outerplanar} if it can be embedded in the plane such that all its vertices lie on the outer face. A $3$-uniform hypergraph $\mathcal{H}$ is called \textit{outerplanar} if its shadow has an outerplanar embedding such that every hyperedge of $\mathcal{H}$ is the vertex set of an interior triangular face of the shadow. Cvetkovi\'c and Rowlinson conjectured in 1990 that among all outerplanar graphs on $n$ vertices, the graph $K_1+ P_{n-1}$ attains the maximum spectral radius. We show a hypergraph analogue of the Cvetkovi\'c-Rowlinson conjecture. In particular, we show that for sufficiently large $n$, the $n$-vertex outerplanar $3$-uniform hypergraph of maximum spectral radius is the unique $3$-uniform hypergraph whose shadow is $K_1 + P_{n-1}$., Comment: 13 pages, 3 figures

We show that if a planar graph $G$ with minimum degree at least $3$ has positive Lin-Lu-Yau Ricci curvature on every edge, then $\Delta(G)\leq 17$, which then implies that $G$ is finite. This is an analogue of a result of DeVos and Mohar [{\em Trans. Amer. Math. Soc., 2007}] on the size of planar graphs with positive combinatorial curvature., Comment: 10 pages, 2 figures

In 1964, Erd\H{o}s, Hajnal and Moon introduced a saturation version of Tur\'an's classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a $K_r$-free, $n$-vertex graph with the property that the addition of any further edge yields a copy of $K_r$. We consider analogues of this problem in other settings. We prove a saturation version of the Erd\H{o}s-Szekeres theorem about monotone subsequences and saturation versions of some Ramsey-type theorems on graphs and Dilworth-type theorems on posets. We also consider semisaturation problems, wherein we allow the family to have the forbidden configuration, but insist that any addition to the family yields a new copy of the forbidden configuration. In this setting, we prove a semisaturation version of the Erd\H{o}s-Szekeres theorem on convex $k$-gons, as well as multiple semisaturation theorems for sequences and posets.

We verify an upper bound of Pach and T\'oth [Combinatorica 17(1997), 427-439, Discrete and Computational Geometry 36(2006), 527-552] on the midrange crossing constant. Details of their $\frac{8}{9\pi^2}$ upper bound have not been available. Our verification is different from their method and hinges on a result of Moon [J. Soc. Indust. Appl. Math. 13(1965), 506-510]. As Moon's result is optimal, we raise the question whether the midrange crossing constant is $\frac{8}{9\pi^2}$.

In this paper, we prove an Azuma-Hoeffding-type inequality in several classical models of random configurations, including the Erd\H{o}s-R\'enyi random graph models $G(n,p)$ and $G(n,M)$, the random $d$-out(in)-regular directed graphs, and the space of random permutations. The main idea is using Ollivier's work on the Ricci curvature of Markov chairs on metric spaces. Here we give a cleaner form of such concentration inequality in graphs. Namely, we show that for any Lipschitz function $f$ on any graph (equipped with an ergodic random walk and thus an invariant distribution $\nu$) with Ricci curvature at least $\kappa>0$, we have \[\nu \left( |f-E_{\nu}f| \geq t \right) \leq 2\exp\left( -\frac{t^2\kappa}{7} \right).\], Comment: 22 pages

For a fixed set of positive integers $R$, we say $\mathcal{H}$ is an $R$-uniform hypergraph, or $R$-graph, if the cardinality of each edge belongs to $R$. For a graph $G=(V,E)$, a hypergraph $\mathcal{H}$ is called a Berge-$G$, denoted by $BG$, if there exists a bijection $f: E(G) \to E(\mathcal{H})$ such that for every $e \in E(G)$, $e \subseteq f(e)$. In this paper, we define a variant of Tur\'an number in hypergraphs, namely the cover Tur\'an number, denoted as $\hat{ex}_R(n, G)$, as the maximum number of edges in the shadow graph of a Berge-$G$ free $R$-graph on $n$ vertices. We show a general upper bound on the cover Tur\'an number of graphs and determine the cover Tur\'an density of all graphs when the uniformity of the host hypergraph equals to $3$., Comment: 14 pages

For a fixed set of positive integers $R$, we say $\mathcal{H}$ is an $R$-uniform hypergraph, or $R$-graph, if the cardinality of each edge belongs to $R$. An $R$-graph $\mathcal{H}$ is \emph{covering} if every vertex pair of $\mathcal{H}$ is contained in some hyperedge. For a graph $G=(V,E)$, a hypergraph $\mathcal{H}$ is called a \textit{Berge}-$G$, denoted by $BG$, if there exists an injection $f: E(G) \to E(\mathcal{H})$ such that for every $e \in E(G)$, $e \subseteq f(e)$. In this note, we define a new type of Ramsey number, namely the \emph{cover Ramsey number}, denoted as $\hat{R}^R(BG_1, BG_2)$, as the smallest integer $n_0$ such that for every covering $R$-uniform hypergraph $\mathcal{H}$ on $n \geq n_0$ vertices and every $2$-edge-coloring (blue and red) of $\mathcal{H}$ , there is either a blue Berge-$G_1$ or a red Berge-$G_2$ subhypergraph. We show that for every $k\geq 2$, there exists some $c_k$ such that for any finite graphs $G_1$ and $G_2$, $R(G_1, G_2) \leq \hat{R}^{[k]}(BG_1, BG_2) \leq c_k \cdot R(G_1, G_2)^3$. Moreover, we show that for each positive integer $d$ and $k$, there exists a constant $c = c(d,k)$ such that if $G$ is a graph on $n$ vertices with maximum degree at most $d$, then $\hat{R}^{[k]}(BG,BG) \leq cn$., Comment: 9 pages

Given a set $R$, a hypergraph is $R$-uniform if the size of every hyperedge belongs to $R$. A hypergraph $\mathcal{H}$ is called \textit{covering} if every vertex pair is contained in some hyperedge in $\mathcal{H}$. In this note, we show that every covering $[3]$-uniform hypergraph on $n\geq 6$ vertices contains a Berge cycle $C_s$ for any $3\leq s\leq n$. As an application, we determine the maximum Lagrangian of $k$-uniform Berge-$C_{t}$-free hypergraphs and Berge-$P_{t}$-free hypergraphs., Comment: Title changed to "On Hamiltonian Berge cycles in $3$-uniform hypergraphs"

Let $G$ be a graph. We say that a hypergraph $H$ is a Berge-$G$ if there is a bijection $\phi: E(G)\to E(H)$ such that $e\subseteq \phi(e)$ for all $e\in E(G)$. For any $r$-uniform hypergraph $H$ and a real number $p\geq 1$, the $p$-spectral radius $\lambda^{(p)}(H)$ of $H$ is defined as \[ \lambda^{(p)}(H):=\max_{{\bf x}\in\mathbb{R}^n,\,\|{\bf x}\|_p=1} r\sum_{\{i_1,i_2,\ldots,i_r\}\in E(H)} x_{i_1}x_{i_2}\cdots x_{i_r}. \] In this paper, we study the $p$-spectral radius of Berge-$G$ hypergraphs. We determine the $3$-uniform hypergraphs with maximum $p$-spectral radius for $p\geq 1$ among Berge-$G$ hypergraphs when $G$ is a path, a cycle or a star., Comment: 15 pages

We propose a directed acyclic hypergraph framework for a probabilistic graphical model that we call Bayesian hypergraphs. The space of directed acyclic hypergraphs is much larger than the space of chain graphs. Hence Bayesian hypergraphs can model much finer factorizations than Bayesian networks or LWF chain graphs and provide simpler and more computationally efficient procedures for factorizations and interventions. Bayesian hypergraphs also allow a modeler to represent causal patterns of interaction such as Noisy-OR graphically (without additional annotations). We introduce global, local and pairwise Markov properties of Bayesian hypergraphs and prove under which conditions they are equivalent. We define a projection operator, called shadow, that maps Bayesian hypergraphs to chain graphs, and show that the Markov properties of a Bayesian hypergraph are equivalent to those of its corresponding chain graph. We extend the causal interpretation of LWF chain graphs to Bayesian hypergraphs and provide corresponding formulas and a graphical criterion for intervention.

For positive integers $n$ and $e$, let $\kappa(n,e)$ be the minimum crossing number (the standard planar crossing number) taken over all graphs with $n$ vertices and at least $e$ edges. Pach, Spencer and T\'oth [Discrete and Computational Geometry 24 623--644, (2000)] showed that $\kappa(n,e) n^2/e^3$ tends to a positive constant (called midrange crossing constant) as $n\to \infty$ and $n \ll e \ll n^2$, proving a conjecture of Erd\H{o}s and Guy. In this note, we extend their proof to show that the midrange crossing constant exists for graph classes that satisfy a certain set of graph properties. As a corollary, we show that the the midrange crossing constant exists for the family of bipartite graphs. All these results have their analogues for rectilinear crossing numbers.

For a graph $G=(V,E)$, a hypergraph $\mathcal{H}$ is called a Berge-$G$, denoted by $BG$, if there exists a bijection $f: E(G) \to E(\mathcal{H})$ such that for every $e \in E(G)$, $e \subseteq f(e)$. Let the Ramsey number $R^r(BG,BG)$ be the smallest integer $n$ such that for any $2$-edge-coloring of a complete $r$-uniform hypergraph on $n$ vertices, there is a monochromatic Berge-$G$ subhypergraph. In this paper, we show that the 2-color Ramsey number of Berge cliques is linear. In particular, we show that $R^3(BK_s, BK_t) = s+t-3$ for $s,t \geq 4$ and $\max(s,t) \geq 5$ where $BK_n$ is a Berge-$K_n$ hypergraph. For higher uniformity, we show that $R^4(BK_t, BK_t) = t+1$ for $t\geq 6$ and $R^k(BK_t, BK_t)=t$ for $k \geq 5$ and $t$ sufficiently large. We also investigate the Ramsey number of trace hypergraphs, suspension hypergraphs and expansion hypergraphs., Comment: Updated to include suggestions of the referee

The crossing number ${\mbox {cr}}(G)$ of a graph $G=(V,E)$ is the smallest number of edge crossings over all drawings of $G$ in the plane. For any $k\ge 1$, the $k$-planar crossing number of $G$, ${\mbox {cr}}_k(G)$, is defined as the minimum of ${\mbox {cr}}(G_1)+{\mbox {cr}}(G_2)+\ldots+{\mbox {cr}}(G_{k})$ over all graphs $G_1, G_2,\ldots, G_{k}$ with $\cup_{i=1}^{k}G_i=G$. Pach et al. [\emph{Computational Geometry: Theory and Applications} {\bf 68} 2--6, (2018)] showed that for every $k\ge 1$, we have ${\mbox {cr}}_k(G)\le \left(\frac{2}{k^2}-\frac1{k^3}\right){\mbox {cr}}(G)$ and that this bound does not remain true if we replace the constant $\frac{2}{k^2}-\frac1{k^3}$ by any number smaller than $\frac1{k^2}$. We improve the upper bound to $\frac{1}{k^2}(1+o(1))$ as $k\rightarrow \infty$. For the class of bipartite graphs, we show that the best constant is exactly $\frac{1}{k^2}$ for every $k$. The results extend to the rectilinear variant of the $k$-planar crossing number., Comment: 13 pages, 1 figure, 1 table

In the cops and robber games played on a simple graph $G$, Aigner and Fromme's lemma states that one cop can guard a shortest path in the sense that the robber cannot enter this path without getting caught after finitely many steps. In this paper, we extend Aigner and Fromme's lemma to cover a larger family of graphs and give metric characterizations of these graphs. In particular, we show that a generalization of block graphs, namely vertebrate graphs, are 1-guardable. We use this result to give the cop number of some special class of multi-layer generalized Peterson graphs., Comment: fixing typos

We provide a cyclic permutation analogue of the Erd\H os-Szekeres theorem. In particular, we show that every cyclic permutation of length $(k-1)(\ell-1)+2$ has either an increasing cyclic sub-permutation of length $k+1$ or a decreasing cyclic sub-permutation of length $\ell+1$, and show that the result is tight. We also characterize all maximum-length cyclic permutations that do not have an increasing cyclic sub-permutation of length $k+1$ or a decreasing cyclic sub-permutation of length $\ell+1$., Comment: 8 pages, 2 figures

The dimension of a partially-ordered set (poset), introduced by Dushnik and Miller (1941), has been studied extensively in the literature. Recently, Ueckerdt (2016) proposed a variation called local dimension which makes use of partial linear extensions. While local dimension is bounded above by dimension, they can be arbitrarily far apart as the dimension of the standard example is $n$ while its local dimension is only $3$. Hiraguchi (1955) proved that the maximum dimension of a poset of order $n$ is $n/2$. However, we find a very different result for local dimension, proving a bound of $\Theta(n/\log n)$. This follows from connections with covering graphs using difference graphs which are bipartite graphs whose vertices in a single class have nested neighborhoods. We also prove that the local dimension of the $n$-dimensional Boolean lattice is $\Omega(n/\log n)$ and make progress toward resolving a version of the removable pair conjecture for local dimension., Comment: 13 pages, 1 figure

An edge-colored graph $G$ is called rainbow if every edge of $G$ receives a different color. The anti-Ramsey number of $t$ edge-disjoint rainbow spanning trees, denoted by $r(n,t)$, is defined as the maximum number of colors in an edge-coloring of $K_n$ containing no $t$ edge-disjoint rainbow spanning trees. Jahanbekam and West [J. Graph Theory, 2014] conjectured that for any fixed $t$, $r(n,t)=\binom{n-2}{2}+t$ whenever $n\geq 2t+2 \geq 6$. In this paper, we prove this conjecture. We also determine $r(n,t)$ when $n = 2t+1$. Together with previous results, this gives the anti-Ramsey number of $t$ edge-disjoint rainbow spanning trees for all values of $n$ and $t$., Comment: 17 pages, fixed an error in the proof of Theorem 3 using Matroid methods

For any $r\geq 2$ and $k\geq 3$, the $r$-color size-Ramsey number $\hat R(\mathcal{G},r)$ of a $k$-uniform hypergraph $\mathcal{G}$ is the smallest integer $m$ such that there exists a $k$-uniform hypergraph $\mathcal{H}$ on $m$ edges such that any coloring of the edges of $\mathcal{H}$ with $r$ colors yields a monochromatic copy of $\mathcal{G}$. Let $\mathcal{P}_{n,k-1}^{(k)}$ denote the $k$-uniform tight path on $n$ vertices. Dudek, Fleur, Mubayi and R\H{o}dl showed that the size-Ramsey number of tight paths $\hat R(\mathcal{P}_{n,k-1}^{(k)}, 2) = O(n^{k-1-\alpha} (\log n)^{1+\alpha})$ where $\alpha = \frac{k-2}{\binom{k-1}{2}+1}$. In this paper, we improve their bound by showing that $\hat R(\mathcal{P}_{n,k-1}^{(k)}, r) = O(r^k (n\log n)^{k/2})$ for all $k\geq 3$ and $r\geq 2$., Comment: 9 pages

We give an explicit extension of Spencer's result on the biplanar crossing number of the Erdos-Renyi random graph $G(n,p)$. In particular, we show that the k-planar crossing number of $G(n,p)$ is almost surely $\Omega((n^2p)^2)$. Along the same lines, we prove that for any fixed $k$, the $k$-planar crossing number of various models of random $d$-regular graphs is $\Omega ((dn)^2)$ for $d > c_0$ for some constant $c_0=c_0(k)$.