Source author record

Bernardo M. Ábrego

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Geometry Discrete Mathematics

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Shellable drawings and the cylindrical crossing number of $K_n$

The Harary-Hill Conjecture States that the number of crossings in any drawing of the complete graph $K_n$ in the plane is at least $Z(n):=\frac{1}{4}\left\lfloor \frac{n}{2}\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor \frac{n-2}{2}\right\rfloor\left\lfloor \frac{n-3}{2}\right\rfloor$ . In this paper, we settle the Harary-Hill conjecture for {\em shellable drawings}. We say that a drawing $D$ of $K_n$ is {\em $s$ -shellable} if there exist a subset $S = \{v_1,v_2,\ldots,v_ s\}$ of the vertices and a region $R$ of $D$ with the following property: For all $1 \leq i < j \leq s$ , if $D_{ij}$ is the drawing obtained from $D$ by removing $v_1,v_2,\ldots v_{i-1},v_{j+1},\ldots,v_{s}$ , then $v_i$ and $v_j$ are on the boundary of the region of $D_{ij}$ that contains $R$ . For $s\geq n/2$ , we prove that the number of crossings of any $s$ -shellable drawing of $K_n$ is at least the long-conjectured value Z(n). Furthermore, we prove that all cylindrical, $x$ -bounded, monotone, and 2-page drawings of $K_n$ are $s$ -shellable for some $s\geq n/2$ and thus they all have at least $Z(n)$ crossings. The techniques developed provide a unified proof of the Harary-Hill conjecture for these classes of drawings.

preprint2011arXiv

On $(\le k)$ -edges, crossings, and halving lines of geometric drawings of $K_n$

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.

preprint2011arXiv

On the maximum number of isosceles right triangles in a finite point set

Let $Q$ be a finite set of points in the plane. For any set $P$ of points in the plane, $S_{Q}(P)$ denotes the number of similar copies of $Q$ contained in $P$ . For a fixed $n$ , Erdős and Purdy asked to determine the maximum possible value of $S_{Q}(P)$ , denoted by $S_{Q}(n)$ , over all sets $P$ of $n$ points in the plane. We consider this problem when $Q=\triangle$ is the set of vertices of an isosceles right triangle. We give exact solutions when $n\leq9$ , and provide new upper and lower bounds for $S_{\triangle}(n)$ .

preprint2009arXiv

Point-sets in general position with many similar copies of a pattern

For every pattern $P$ , consisting of a finite set of points in the plane, $S_{P}(n,m)$ is defined as the largest number of similar copies of $P$ among sets of $n$ points in the plane without $m$ points on a line. A general construction, based on iterated Minkovski sums, is used to obtain new lower bounds for $S_{P}(n,m)$ when $P$ is an arbitrary pattern. Improved bounds are obtained when $P$ is a triangle or a regular polygon with few sides. It is also shown that $S_{P}(n,m)\geq n^{2-ε}$ whenever $m(n)\to \infty$ as $n \to\infty$ . Finite sets with no collinear triples and not containing the 4 vertices of any parallelogram are called \emph{parallelogram-free}. The more restricted function $S_{P} ^{\nparallel}(n)$ , defined as the maximum number of similar copies of $P$ among parallelogram-free sets of $n$ points, is also studied. It is proved that $Ω(n\log n)\leq S_{P}^{\nparallel}(n)\leq O(n^{3/2})$ .

preprint2009arXiv

Sum of squares of degrees in a graph

Let $\G(v,e)$ be the set of all simple graphs with $v$ vertices and $e$ edges and let $P_2(G)=\sum d_i^2$ denote the sum of the squares of the degrees, $d_1, >..., d_v$ , of the vertices of $G$ . It is known that the maximum value of $P_2(G)$ for $G \in \G(v,e)$ occurs at one or both of two special graphs in $\G(v,e)$--the \qs graph or the \qc graph. For each pair $(v,e)$ , we determine which of these two graphs has the larger value of $P_2(G)$ . We also determine all pairs $(v,e)$ for which the values of $P_2(G)$ are the same for the \qs and the \qc graph. In addition to the \qs and \qc graphs, we find all other graphs in $\G(v,e)$ for which the maximum value of $P_2(G)$ is attained. Density questions posed by previous authors are examined.

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.

Bernardo M. Ábrego

Research overview

Is this your work?

5 publications

Shellable drawings and the cylindrical crossing number of $K_n$

On $(\le k)$ -edges, crossings, and halving lines of geometric drawings of $K_n$

On the maximum number of isosceles right triangles in a finite point set

Point-sets in general position with many similar copies of a pattern

Sum of squares of degrees in a graph

See the researcher in context

Building this map preview

Bernardo M. Ábrego

Research overview

Is this your work?

5 publications

Shellable drawings and the cylindrical crossing number of KnK_nKn​

On (≤k)(\le k)(≤k)-edges, crossings, and halving lines of geometric drawings of KnK_nKn​

On the maximum number of isosceles right triangles in a finite point set

Point-sets in general position with many similar copies of a pattern

Sum of squares of degrees in a graph

See the researcher in context

Building this map preview

Shellable drawings and the cylindrical crossing number of $K_n$

On $(\le k)$ -edges, crossings, and halving lines of geometric drawings of $K_n$