Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userS-hypersimplices, pulling triangulations, and monotone paths
92
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
An $S$-hypersimplex for $S subseteq {0,1, dots,d}$ is the convex hull of all $0/1$-vectors of length $d$ with coordinate sum in $S$. These polytopes generalize the classical hypersimplices as well as cubes, crosspolytopes, and halfcubes. In this paper we study faces and dissections of $S$-hypersimplices. Moreover, we show that monotone path polytopes of $S$-hypersimplices yield all types of multipermutahedra. In analogy to cubes, we also show that the number of simplices in a pulling triangulation of a halfcube is independent of the pulling order.
rate research
Read More
An edge-ordered graph is a graph with a total ordering of its edges. A path $P=v_1v_2ldots v_k$ in an edge-ordered graph is called increasing if $(v_iv_{i+1}) > (v_{i+1}v_{i+2})$ for all $i = 1,ldots,k-2$; it is called decreasing if $(v_iv_{i+1}) < (v_{i+1}v_{i+2})$ for all $i = 1,ldots,k-2$. We say that $P$ is monotone if it is increasing or decreasing. A rooted tree $T$ in an edge-ordered graph is called monotone if either every path from the root of to a leaf is increasing or every path from the root to a leaf is decreasing. Let $G$ be a graph. In a straight-line drawing $D$ of $G$, its vertices are drawn as different points in the plane and its edges are straight line segments. Let $overline{alpha}(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing path of length $overline{alpha}(G)$. Let $overline{tau}(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing complete binary tree of size $overline{tau}(G)$. In this paper we show that $overline alpha(K_n) = Omega(loglog n)$, $overline alpha(K_n) = O(log n)$, $overline tau(K_n) = Omega(loglog log n)$ and $overline tau(K_n) = O(sqrt{n log n})$.
An ordered hypergraph is a hypergraph $H$ with a specified linear ordering of the vertices, and the appearance of an ordered hypergraph $G$ in $H$ must respect the specified order on $V(G)$. In on-line Ramsey theory, Builder iteratively presents edges that Painter must immediately color. The $t$-color on-line size Ramsey number $tilde R_t (G)$ of an ordered hypergraph $G$ is the minimum number of edges Builder needs to play (on a large ordered set of vertices) to force Painter using $t$ colors to produce a monochromatic copy of $G$. The monotone tight path $P_r^{(k)}$ is the ordered hypergraph with $r$ vertices whose edges are all sets of $k$ consecutive vertices. We obtain good bounds on $tilde R_t (P_r^{(k)})$. Letting $m=r-k+1$ (the number of edges in $P_r^{(k)}$), we prove $m^{t-1}/(3sqrt t)letilde R_t (P_r^{(2)})le tm^{t+1}$. For general $k$, a trivial upper bound is ${R choose k}$, where $R$ is the least number of vertices in a $k$-uniform (ordered) hypergraph whose $t$-colorings all contain $P_r^{(k)}$ (and is a tower of height $k-2$). We prove $R/(klg R)letilde R_t(P_r^{(k)})le R(lg R)^{2+epsilon}$, where $epsilon$ is any positive constant and $t(m-1)$ is sufficiently large. Our upper bounds improve prior results when $t$ grows faster than $m/log m$. We also generalize our results to $ell$-loose monotone paths, where each successive edge begins $ell$ vertices after the previous edge.
We consider the problem of finding an inductive construction, based on vertex splitting, of triangulated spheres with a fixed number of additional edges (braces). We show that for any positive integer $b$ there is such an inductive construction of triangulations with $b$ braces, having finitely many base graphs. In particular we establish a bound for the maximum size of a base graph with $b$ braces that is linear in $b$. In the case that $b=1$ or $2$ we determine the list of base graphs explicitly. Using these results we show that doubly braced triangulations are (generically) minimally rigid in two distinct geometric contexts arising from a hypercylinder in $mathbb{R}^4$ and a class of mixed norms on $mathbb{R}^3$.
A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is $x$- and $y$-monotone. Angle-monotone graphs are $sqrt 2$-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone---specifically, we prove that the half-$theta_6$-graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex $s$ to any vertex $t$ whose length is within $1 + sqrt 2$ times the Euclidean distance from $s$ to $t$. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.
Let $ G $ be a connected graph. If $bar{sigma}(v)$ denotes the arithmetic mean of the distances from $v$ to all other vertices of $G$, then the proximity, $pi(G)$, of $G$ is defined as the smallest value of $bar{sigma}(v)$ over all vertices $v$ of $G$. We give upper bounds for the proximity of simple triangulations and quadrangulations of given order and connectivity. We also construct simple triangulations and quadrangulations of given order and connectivity that match the upper bounds asymptotically and are likely optimal.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
