BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Jesús García

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

ResearcherUnclaimed source record
math.CO

Catalog footprint

Research overview

2works
1topics
3close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

2 publications

preprint2008arXiv

New results on lower bounds for the number of (at most k)-facets

In this paper we present three different results dealing with the number of (≤k)(\leq k)-facets of a set of points: 1. We give structural properties of sets in the plane that achieve the optimal lower bound 3(k+22)3\binom{k+2}{2} of (≤k)(\leq k)-edges for a fixed 0≤k≤⌊n/3⌋−10\leq k\leq \lfloor n/3 \rfloor -1; 2. We give a simple construction showing that the lower bound 3(k+22)+3(k−⌊n3⌋+22)3\binom{k+2}{2}+3\binom{k-\lfloor \frac{n}{3} \rfloor+2}{2} for the number of (≤k)(\leq k)-edges of a planar point set appeared in [Aichholzer et al. New lower bounds for the number of (≤k\leq k)-edges and the rectilinear crossing number of KnK_n. {\em Disc. Comput. Geom.} 38:1 (2007), 1--14] is optimal in the range ⌊n/3⌋≤k≤⌊5n/12⌋−1\lfloor n/3 \rfloor \leq k \leq \lfloor 5n/12 \rfloor -1; 3. We show that for k<⌊n/(d+1)⌋k < \lfloor n/(d+1) \rfloor the number of (≤k)(\leq k)-facets of a set of nn points in general position in Rd\mathbb{R}^d is at least (d+1)(k+dd)(d+1)\binom{k+d}{d}, and that this bound is tight in the given range of kk.

Open access
preprint2006arXiv

New lower bounds for the number of (≤k)(\leq k)-edges and the rectilinear crossing number of KnK_n

We provide a new lower bound on the number of (≤k)(\leq k)-edges of a set of nn points in the plane in general position. We show that for 0≤k≤⌊n−22⌋0 \leq k \leq\lfloor\frac{n-2}{2}\rfloor the number of (≤k)(\leq k)-edges is at least Ek(S)≥3(k+22)+∑j=⌊n3⌋k(3j−n+3), E_k(S) \geq 3\binom{k+2}{2} + \sum_{j=\lfloor\frac{n}{3}\rfloor}^k (3j-n+3), which, for k≥⌊n3⌋k\geq \lfloor\tfrac{n}{3}\rfloor, improves the previous best lower bound in [J. Balogh, G. Salazar, Improved bounds for the number of (≤k\leq k)-sets, convex quadrilaterals, and the rectilinear crossing number of KnK_n]. As a main consequence, we obtain a new lower bound on the rectilinear crossing number of the complete graph or, in other words, on the minimum number of convex quadrilaterals determined by nn points in the plane in general position. We show that the crossing number is at least (41/108+ε)(n4)+O(n3)≥0.379631(n4)+O(n3), \Bigl({41/108}+ε\Bigr) \binom{n}{4} + O(n^3) \geq 0.379631 \binom{n}{4} + O(n^3), which improves the previous bound of 0.37533(n4)+O(n3)0.37533 \binom{n}{4} + O(n^3) in [J. Balogh, G. Salazar, Improved bounds for the number of (≤k\leq k)-sets, convex quadrilaterals, and the rectilinear crossing number of KnK_n] and approaches the best known upper bound 0.38058(n4)0.38058\binom{n}{4} in [O. Aichholzer, H. Krasser, Abstract order type extension and new results on the rectilinear crossing number].

Open access

Research graph

See the researcher in context

Open full explorer

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.