Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBalanced subdivisions and flips on surfaces
132
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we show that two balanced triangulations of a closed surface are not necessary connected by a sequence of balanced stellar subdivisions and welds. This answers a question posed by Izmestiev, Klee and Novik. We also show that two balanced triangulations of a closed surface are connected by a sequence of three local operations, which we call the pentagon contraction, the balanced edge subdivision and the balanced edge weld. In addition, we prove that two balanced triangulations of the 2-sphere are connected by a sequence of pentagon contractions and their inverses if none of them are octahedral spheres.
rate research
Read More
We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions of bounded-degree bipartite graphs with a mild separability condition. As corollaries, we answer several questions of Reed and Wood on embedding sparse minors. Among others, $bullet$ $(1+o(1))t^2$ average degree is sufficient to force the $ttimes t$ grid as a topological minor; $bullet$ $(3/2+o(1))t$ average degree forces every $t$-vertex planar graph as a minor, and the constant $3/2$ is optimal, furthermore, surprisingly, the value is the same for $t$-vertex graphs embeddable on any fixed surface; $bullet$ a universal bound of $(2+o(1))t$ on average degree forcing every $t$-vertex graph in any nontrivial minor-closed family as a minor, and the constant 2 is best possible by considering graphs with given treewidth.
Athanasiadis conjectured that, for every positive integer $r$, the local $h$-polynomial of the $r$th edgewise subdivision of any simplex has only real zeros. In this paper, based on the theory of interlacing polynomials, we prove that a family of polynomials related to the desired local $h$-polynomial is interlacing and hence confirm Athanasiadis conjecture.
Given a flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on a region of the plane) with a mountain-valley (MV) assignment $mu:Eto{-1,1}$ indicating which creases in $E$ bend convexly (mountain) or concavely (valley), we may emph{flip} a face $F$ of $G$ to create a new MV assignment $mu_F$ which equals $mu$ except for all creases $e$ bordering $F$, where we have $mu_F(e)=-mu(e)$. In this paper we explore the configuration space of face flips for a variety of crease patterns $G$ that are tilings of the plane, proving examples where $mu_F$ results in a MV assignment that is either never, sometimes, or always flat-foldable for various choices of $F$. We also consider the problem of finding, given two foldable MV assignments $mu_1$ and $mu_2$ of a given crease pattern $G$, a minimal sequence of face flips to turn $mu_1$ into $mu_2$. We find polynomial-time algorithms for this in the cases where $G$ is either a square grid or the Miura-ori, and show that this problem is NP-hard in the case where $G$ is the triangle lattice.
Let $ngeq 6,kgeq 0$ be two integers. Let $H$ be a graph of order $n$ with $k$ components, each of which is an even cycle of length at least $6$ and $G$ be a bipartite graph with bipartition $(X,Y)$ such that $|X|=|Y|geq n/2$. In this paper, we show that if the minimum degree of $G$ is at least $n/2-k+1$, then $G$ contains a subdivision of $H$. This generalized an older result of Wang.
Bimonotone subdivisions in two dimensions are subdivisions all of whose sides are either vertical or have nonnegative slope. They correspond to statistical estimates of probability distributions of strongly positively dependent random variables. The number of bimonotone subdivisions compared to the total number of subdivisions of a point configuration provides insight into how often the random variables are positively dependent. We give recursions as well as formulas for the numbers of bimonotone and total subdivisions of $2times n$ grid configurations in the plane. Furthermore, we connect the former to the large Schroder numbers. We also show that the numbers of bimonotone and total subdivisions of a $2times n$ grid are asymptotically equal. We then provide algorithms for counting bimonotone subdivisions for any $m times n$ grid. Finally, we prove that all bimonotone triangulations of an $m times n$ grid are connected by flips. This gives rise to an algorithm for counting the number of bimonotone (and total) triangulations of an $mtimes n$ grid.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
