Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBounds on Gromov Hyperbolicity Constant
163
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
If $X$ is a geodesic metric space and $x_{1},x_{2},x_{3} in X$, a geodesic triangle $T={x_{1},x_{2},x_{3}}$ is the union of the three geodesics $[x_{1}x_{2}]$, $[x_{2}x_{3}]$ and $[x_{3}x_{1}]$ in $X$. The space $X$ is $delta$-hyperbolic in the Gromov sense if any side of $T$ is contained in a $delta$-neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$. If $X$ is hyperbolic, we denote by $delta(X)$ the sharp hyperbolicity constant of $X$, i.e. $delta(X) =inf { deltageq 0:{0.3cm}$ X ${0.2cm}$ $text{is} {0.2cm} delta text{-hyperbolic} }.$ To compute the hyperbolicity constant is a very hard problem. Then it is natural to try to bound the hyperbolycity constant in terms of some parameters of the graph. Denote by $mathcal{G}(n,m)$ the set of graphs $G$ with $n$ vertices and $m$ edges, and such that every edge has length $1$. In this work we estimate $A(n,m):=min{delta(G)mid G in mathcal{G}(n,m) }$ and $B(n,m):=max{delta(G)mid G in mathcal{G}(n,m) }$. In particular, we obtain good bounds for $B(n,m)$, and we compute the precise value of $A(n,m)$ for all values of $n$ and $m$. Besides, we apply these results to random graphs.
rate research
Read More
We obtain explicit and simple conditions which in many cases allow one decide, whether or not a Denjoy domain endowed with the Poincare or quasihyperbolic metric is Gromov hyperbolic. The criteria are based on the Euclidean size of the complement. As a corollary, the main theorem allows to deduce the non-hyperbolicity of any periodic Denjoy domain.
Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs, which is an important class of geometric intersection graphs. In this paper we give sharp bounds for the hyperbolicity constant of (finite and infinite) circular-arc graphs. Moreover, we obtain bounds for the hyperbolicity constant of the complement and line of any circular-arc graph. In order to do that, we obtain new results about regular, chordal and line graphs which are interesting by themselves.
If $X$ is a geodesic metric space and $x_1,x_2,x_3in X$, a geodesic triangle $T={x_1,x_2,x_3}$ is the union of the three geodesics $[x_1x_2]$, $[x_2x_3]$ and $[x_3x_1]$ in $X$. The space $X$ is $delta$-hyperbolic (in the Gromov sense) if any side of $T$ is contained in a $delta$-neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$. The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. In the context of graphs, to remove and to contract an edge of a graph are natural transformations. The main aim in this work is to obtain quantitative information about the distortion of the hyperbolicity constant of the graph $G setminus e$ (respectively, $,G/e,$) obtained from the graph $G$ by deleting (respectively, contracting) an arbitrary edge $e$ from it. This work provides information about the hyperbolicity constant of minor graphs.
We study a family of variants of ErdH os unit distance problem, concerning distances and dot products between pairs of points chosen from a large finite point set. Specifically, given a large finite set of $n$ points $E$, we look for bounds on how many subsets of $k$ points satisfy a set of relationships between point pairs based on distances or dot products. We survey some of the recent work in the area and present several new, more general families of bounds.
To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let $mathcal{G}(g,c,n)$ be the set of graphs $G$ with girth $g(G)=g$, circumference $c(G)=c$, and $n$ vertices; and let $mathcal{H}(g,c,m)$ be the set of graphs with girth $g$, circumference $c$, and $m$ edges. In this work, we study the four following extremal problems on graphs: $A(g,c,n)=min{delta(G),|; G in mathcal{G}(g,c,n) }$, $B(g,c,n)=max{delta(G),|; G in mathcal{G}(g,c,n) }$, $alpha(g,c,m)=min{delta(G),|; in mathcal{H}(g,c,m) }$ and $beta(g,c,m)=max{delta(G),|; G in mathcal{H}(g,c,m) }$. In particular, we obtain bounds for $A(g,c,n)$ and $alpha(g,c,m)$, and we compute the precise value of $B(g,c,n)$ and $beta(g,c,m)$ for all values of $g$, $c$, $n$ and $m$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
