BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Jesús Leaños appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We show that the 3-symmetric rectilinear and the 3-symmetric pseudolinear crossing numbers of $K_{33}$ are equal. Specifically, we prove that $\operatorname{sym}-\overline{\operatorname{cr}}_3(K_{33}) = 14 634 = \operatorname{sym}-\widetilde{\operatorname{cr}}_3(K_{33})$.
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)\frac{n^2}{k-1}-\frac{n}{2}\le f(n,k) \le 2 \frac{n(n-2)}{k-2}$. For the case when $k=n$, we show that $2 \le f(n,n) \le 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.
We prove that if $G$ is a graph with an minimal edge cut $F$ of size three and $G_1$, $G_2$ are the two (augmented) components of $G-F$, then the crossing number of $G$ is equal to the sum of crossing numbers of $G_1$ and $G_2$. Combining with known results, this implies that crossing number is additive over edge-cuts of size $d$ for $d\in\{0, 1, 2, 3\}$, whereas there are counterexamples for every $d\ge 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.
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\leq k\leq 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 $(\le k)$-edges of $P$ is denoted by $E_{\leq k}(P) $. Let $\rcr(n)$, $h(n)$, and $E_{\leq k}(n) $ denote the minimum of $\crg(P)$, the maximum of $h(P)$, and the minimum of $E_{\leq 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_{\leq k}(n)$ is tight for $k<\lceil (4n-2) /9\rceil $ and improve it for all $k\geq \lceil (4n-2) /9 \rceil $. This in turn improves the lower bound on $\rcr(n)$ from $0.37968\binom{n} {4}+Θ(n^{3})$ to {277/729}\binom{n}{4}+Θ(n^{3})\geq 0.37997\binom{n}{4}+Θ(n^{3})$. We also give the exact values of $\rcr(n)$ and $h(n) $ for all $n\leq27$. Exact values were known only for $n\leq18$ and odd $n\leq21$ for the crossing number, and for $n\leq14$ and odd $n\leq21$ for halving lines.
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.