Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimum number of partial triangulations
73
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that the number of partial triangulations of a set of $n$ points on the plane is at least the $(n-2)$-nd Catalan number. This is tight for convex $n$-gons. We also describe all the equality cases.
rate research
Read More
Whitney proved in 1931 that 4-connected planar triangulations are Hamiltonian. Hakimi, Schmeichel, and Thomassen conjectured in 1979 that if $G$ is a 4-connected planar triangulation with $n$ vertices then $G$ contains at least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a double wheel. On the other hand, a recent result of Alahmadi, Aldred, and Thomassen states that there are exponentially many Hamiltonian cycles in 5-connected planar triangulations. In this paper, we consider 4-connected planar $n$-vertex triangulations $G$ that do not have too many separating 4-cycles or have minimum degree 5. We show that if $G$ has $O(n/{log}_2 n)$ separating 4-cycles then $G$ has $Omega(n^2)$ Hamiltonian cycles, and if $delta(G)ge 5$ then $G$ has $2^{Omega(n^{1/4})}$ Hamiltonian cycles. Both results improve previous work. Moreover, the proofs involve a double wheel structure, providing further evidence to the above conjecture.
Let $T$ be a rooted tree, and $V(T)$ its set of vertices. A subset $X$ of $V(T)$ is called an infima closed set of $T$ if for any two vertices $u,vin X$, the first common ancestor of $u$ and $v$ is also in $X$. This paper determines the trees with minimum number of infima closed sets among all rooted trees of given order, thereby answering a question of Klazar. It is shown that these trees are essentially complete binary trees, with the exception of vertices at the last levels. Moreover, an asymptotic estimate for the minimum number of infima closed sets in a tree with $n$ vertices is also provided.
For a prime number $p$ and a sequence of integers $a_0,dots,a_kin {0,1,dots,p}$, let $s(a_0,dots,a_k)$ be the minimum number of $(k+1)$-tuples $(x_0,dots,x_k)in A_0timesdotstimes A_k$ with $x_0=x_1+dots + x_k$, over subsets $A_0,dots,A_ksubseteqmathbb{Z}_p$ of sizes $a_0,dots,a_k$ respectively. An elegant argument of Lev (independently rediscovered by Samotij and Sudakov) shows that there exists an extremal configuration with all sets $A_i$ being intervals of appropriate length, and that the same conclusion also holds for the related problem, reposed by Bajnok, when $a_0=dots=a_k=:a$ and $A_0=dots=A_k$, provided $k$ is not equal 1 modulo $p$. By applying basic Fourier analysis, we show for Bajnoks problem that if $pge 13$ and $ain{3,dots,p-3}$ are fixed while $kequiv 1pmod p$ tends to infinity, then the extremal configuration alternates between at least two affine non-equivalent sets.
Hakimi and Schmeichel determined a sharp lower bound for the number of cycles of length 4 in a maximal planar graph with $n$ vertices, $ngeq 5$. It has been shown that the bound is sharp for $n = 5,12$ and $ngeq 14$ vertices. However, it was only conjectured by the authors about the minimum number of cycles of length 4 for maximal planar graphs with the remaining small vertex numbers. In this note we confirm their conjecture.
Colored triangulations offer a generalization of combinatorial maps to higher dimensions. Just like maps are gluings of polygons, colored triangulations are built as gluings of special, higher-dimensional building blocks, such as octahedra, which we call colored building blocks and known in the dual as bubbles. A colored building block is determined by its boundary triangulation, which in the case of polygons is simply characterized by its length. In three dimensions, colored building blocks are labeled by some 2D triangulations and those homeomorphic to the 3-ball are labeled by the subset of planar ones. Similarly to Eulers formula in 2D which provides an upper bound to the number of vertices at fixed number of polygons with given lengths, we look in three dimensions for an upper bound on the number of edges at fixed number of given colored building blocks. In this article we solve this problem when all colored building blocks, except possibly one, are homeomorphic to the 3-ball. To do this, we find a characterization of the way a colored building block homeomorphic to the ball has to be glued to other blocks of arbitrary topology in a colored triangulation which maximizes the number of edges. This local characterization can be extended to the whole triangulation as long as there is at most one colored building block which is not a 3-ball. The triangulations obtained this way are in bijection with trees. The number of edges is given as an independent sum over the building blocks of such a triangulation. In the case of all colored building blocks being homeomorphic to the 3-ball, we show that these triangulations are homeomorphic to the 3-sphere. Those results were only known for the octahedron and for melonic building blocks before. This article is self-contained and can be used as an introduction to colored triangulations and their bubbles from a purely combinatorial point of view.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
