Fox, Jacob and Pach, János and Suk, Andrew (2018) Ramsey-Turan numbers for semi-algebraic graphs. ELECTRONIC JOURNAL OF COMBINATORICS, 25 (4). ISSN 1097-1440
|
Text
document.pdf Download (241kB) | Preview |
Abstract
A semi-algebraic graph G = (V, E) is a graph where the vertices are points in R-d, and the edge set E is defined by a semi-algebraic relation of constant complexity on V. In this note, we establish the following Ramsey-Turan theorem: for every integer p >= 3, every K-p-free semi-algebraic graph on n vertices with independence number o(n) has at most 1/2(1 - 1/inverted right perpendicularp/2inverted left perpendicular - 1 + o(1)) n(2) edges. Here, the dependence on 1-1 the complexity of the semi-algebraic relation is hidden in the o(1) term. Moreover, we show that this bound is tight.
| Item Type: | Article |
|---|---|
| Additional Information: | Funding Agency and Grant Number: Packard Fellowship; NSF CAREER award [DMS 1352121]; Swiss National Science Foundation [200020-162884, 200021-175977]; Alfred Sloan Fellowship Funding text: Supported by a Packard Fellowship and by NSF CAREER award DMS 1352121.; Supported by Swiss National Science Foundation Grants 200020-162884 and 200021-175977.; Supported an NSF CAREER award and an Alfred Sloan Fellowship. Funding Agency and Grant Number: Packard FellowshipThe David & Lucile Packard Foundation; NSF CAREER awardNational Science Foundation (NSF)NSF - Office of the Director (OD) [DMS 1352121]; Swiss National Science FoundationSwiss National Science Foundation (SNSF) [200020-162884, 200021-175977]; Alfred Sloan Fellowship Funding text: Supported by a Packard Fellowship and by NSF CAREER award DMS 1352121.; Supported by Swiss National Science Foundation Grants 200020-162884 and 200021-175977.; Supported an NSF CAREER award and an Alfred Sloan Fellowship. |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 19 Oct 2019 04:42 |
| Last Modified: | 30 Sep 2021 02:09 |
| URI: | http://real.mtak.hu/id/eprint/102420 |
Actions (login required)
 |
Edit Item |
