Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBimonotone Subdivisions of Point Configurations in the Plane
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
The convex grabbing game is a game where two players, Alice and Bob, alternate taking extremal points from the convex hull of a point set on the plane. Rational weights are given to the points. The goal of each player is to maximize the total weight over all points that they obtain. We restrict the setting to the case of binary weights. We show a construction of an arbitrarily large odd-sized point set that allows Bob to obtain almost 3/4 of the total weight. This construction answers a question asked by Matsumoto, Nakamigawa, and Sakuma in [Graphs and Combinatorics, 36/1 (2020)]. We also present an arbitrarily large even-sized point set where Bob can obtain the entirety of the total weight. Finally, we discuss conjectures about optimum moves in the convex grabbing game for both players in general.
Let $X$ be a set and ${mathcal H}$ a collection of functions from $X$ to ${0,1}$. We say that ${mathcal H}$ shatters a finite set $C subset X$ if the restriction of ${mathcal H}$ yields every possible function from $C$ to ${0,1}$. The VC-dimension of ${mathcal H}$ is the largest number $d$ such that there exists a set of size $d$ shattered by ${mathcal H}$, and no set of size $d+1$ is shattered by ${mathcal H}$. Vapnik and Chervonenkis introduced this idea in the early 70s in the context of learning theory, and this idea has also had a significant impact on other areas of mathematics. In this paper we study the VC-dimension of a class of functions ${mathcal H}$ defined on ${Bbb F}_q^d$, the $d$-dimensional vector space over the finite field with $q$ elements. Define $$ {mathcal H}^d_t={h_y(x): y in {Bbb F}_q^d },$$ where for $x in {Bbb F}_q^d$, $h_y(x)=1$ if $||x-y||=t$, and $0$ otherwise, where here, and throughout, $||x||=x_1^2+x_2^2+dots+x_d^2$. Here $t in {Bbb F}_q$, $t ot=0$. Define ${mathcal H}_t^d(E)$ the same way with respect to $E subset {Bbb F}_q^d$. The learning task here is to find a sphere of radius $t$ centered at some point $y in E$ unknown to the learner. The learning process consists of taking random samples of elements of $E$ of sufficiently large size. We are going to prove that when $d=2$, and $|E| ge Cq^{frac{15}{8}}$, the VC-dimension of ${mathcal H}^2_t(E)$ is equal to $3$. This leads to an intricate configuration problem which is interesting in its own right and requires a new approach.
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.
Determining and analyzing the spectra of graphs is an important and exciting research topic in theoretical computer science. The eigenvalues of the normalized Laplacian of a graph provide information on its structural properties and also on some relevant dynamical aspects, in particular those related to random walks. In this paper, we give the spectra of the normalized Laplacian of iterated subdivisions of simple connected graphs. As an example of application of these results we find the exact values of their multiplicative degree-Kirchhoff index, Kemenys constant and number of spanning trees.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
