The 3-symmetric Pseudolinear Crossing Number of
We show that the 3-symmetric rectilinear and the 3-symmetric pseudolinear crossing numbers of are equal. Specifically, we prove that .
Source author record
Jesús Leaños
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
5works
3topics
4close collaborators
Published work
5 publications
preprint2012arXiv
The Erdős-Sós Conjecture for Geometric Graphs
Let f(n,k) be the minimum number of edges that must be removed from some complete geometric graph G on n points, so that there exists a tree on k vertices that is no longer a planar subgraph of G. In this paper we show that (1/2)k−1n2−2n≤f(n,k)≤2k−2n(n−2). For the case when k=n, we show that 2≤f(n,n)≤3. For the case when k=n and G is a geometric graph on a set of points in convex position, we show that at least three edges must be removed.
Open access
preprint2011arXiv
Minor crossing number is additive over arbitrary cuts
We prove that if G is a graph with an minimal edge cut F of size three and G1, G2 are the two (augmented) components of G−F, then the crossing number of G is equal to the sum of crossing numbers of G1 and G2. Combining with known results, this implies that crossing number is additive over edge-cuts of size d for d∈{0,1,2,3}, whereas there are counterexamples for every d≥4. The techniques generalize to show that minor crossing number is additive over edge cuts of arbitrary size, as well as to provide bounds for crossing number additivity in arbitrary surfaces. We point out several applications to exact crossing number computation and crossing critical graphs, as well as provide a very general lower bound for the minor crossing number of the Cartesian product of an arbitrary graph with a tree.
Open access
preprint2011arXiv
On (≤k)-edges, crossings, and halving lines of geometric drawings of Kn
Let P be a set of points in general position in the plane. Join all pairs of points in P with straight line segments. The number of segment-crossings in such a drawing, denoted by $\crg(P)$, is the \emph{rectilinear crossing number} of P. A \emph{halving line} of P is a line passing though two points of P that divides the rest of the points of P in (almost) half. The number of halving lines of P is denoted by h(P). Similarly, a k\emph{-edge}, 0≤k≤n/2−1, is a line passing through two points of P and leaving exactly k points of P on one side. The number of (≤k)-edges of P is denoted by E≤k(P). Let $\rcr(n)$, h(n), and E≤k(n) denote the minimum of $\crg(P)$, the maximum of h(P), and the minimum of E≤k(P), respectively, over all sets P of n points in general position in the plane. We show that the previously best known lower bound on E≤k(n) is tight for k<⌈(4n−2)/9⌉ and improve it for all k≥⌈(4n−2)/9⌉. This in turn improves the lower bound on $\rcr(n)$ from 0.37968(4n)+Θ(n3) to {277/729}\binom{n}{4}+Θ(n^{3})\geq 0.37997\binom{n}{4}+Θ(n^{3}).Wealsogivetheexactvaluesof\rcr(n)andh(n) foralln\leq27.Exactvalueswereknownonlyforn\leq18andoddn\leq21forthecrossingnumber,andforn\leq14andoddn\leq21$ for halving lines.
Open access
preprint2011arXiv
On the number of mth roots of permutations
Let m be a fixed positive integer. It is well-known that a permutation σ may have one, many, or no mth roots. In this note we provide an explicit expression and a generating function for the number of mth roots of σ. Let p_m(n) be the probability that a random n-permutation has an mth root. We also include a proof that p_m(jq)=p_m(jq+1)=... =p_m(jq+(q-1)) where j=0,1,... and m is a power of prime q.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.