Ramsey-type theorems for lines in 3-space
We prove geometric Ramsey-type statements on collections of lines in 3-space. These statements give guarantees on the size of a clique or an independent set in (hyper)graphs induced by incidence relations between lines, points, and reguli in 3-space. Among other things, we prove that: (1) The inters...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2016-09-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/1367/pdf |
| _version_ | 1797270049230159872 |
|---|---|
| author | Jean Cardinal Michael S. Payne Noam Solomon |
| author_facet | Jean Cardinal Michael S. Payne Noam Solomon |
| author_sort | Jean Cardinal |
| collection | DOAJ |
| description | We prove geometric Ramsey-type statements on collections of lines in 3-space.
These statements give guarantees on the size of a clique or an independent set
in (hyper)graphs induced by incidence relations between lines, points, and
reguli in 3-space. Among other things, we prove that: (1) The intersection
graph of n lines in R^3 has a clique or independent set of size Omega(n^{1/3}).
(2) Every set of n lines in R^3 has a subset of n^{1/2} lines that are all
stabbed by one line, or a subset of Omega((n/log n)^{1/5}) such that no
6-subset is stabbed by one line. (3) Every set of n lines in general position
in R^3 has a subset of Omega(n^{2/3}) lines that all lie on a regulus, or a
subset of Omega(n^{1/3}) lines such that no 4-subset is contained in a regulus.
The proofs of these statements all follow from geometric incidence bounds --
such as the Guth-Katz bound on point-line incidences in R^3 -- combined with
Tur\'an-type results on independent sets in sparse graphs and hypergraphs.
Although similar Ramsey-type statements can be proved using existing generic
algebraic frameworks, the lower bounds we get are much larger than what can be
obtained with these methods. The proofs directly yield polynomial-time
algorithms for finding subsets of the claimed size. |
| first_indexed | 2024-04-25T01:58:05Z |
| format | Article |
| id | doaj.art-06ddf17ee058423e83302191f5525988 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:05Z |
| publishDate | 2016-09-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-06ddf17ee058423e83302191f55259882024-03-07T15:31:26ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502016-09-01Vol. 18 no. 3Combinatorics10.46298/dmtcs.13671367Ramsey-type theorems for lines in 3-spaceJean CardinalMichael S. PayneNoam SolomonWe prove geometric Ramsey-type statements on collections of lines in 3-space. These statements give guarantees on the size of a clique or an independent set in (hyper)graphs induced by incidence relations between lines, points, and reguli in 3-space. Among other things, we prove that: (1) The intersection graph of n lines in R^3 has a clique or independent set of size Omega(n^{1/3}). (2) Every set of n lines in R^3 has a subset of n^{1/2} lines that are all stabbed by one line, or a subset of Omega((n/log n)^{1/5}) such that no 6-subset is stabbed by one line. (3) Every set of n lines in general position in R^3 has a subset of Omega(n^{2/3}) lines that all lie on a regulus, or a subset of Omega(n^{1/3}) lines such that no 4-subset is contained in a regulus. The proofs of these statements all follow from geometric incidence bounds -- such as the Guth-Katz bound on point-line incidences in R^3 -- combined with Tur\'an-type results on independent sets in sparse graphs and hypergraphs. Although similar Ramsey-type statements can be proved using existing generic algebraic frameworks, the lower bounds we get are much larger than what can be obtained with these methods. The proofs directly yield polynomial-time algorithms for finding subsets of the claimed size.https://dmtcs.episciences.org/1367/pdfmathematics - combinatoricscomputer science - computational geometry05d10, 52c35 |
| spellingShingle | Jean Cardinal Michael S. Payne Noam Solomon Ramsey-type theorems for lines in 3-space Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics computer science - computational geometry 05d10, 52c35 |
| title | Ramsey-type theorems for lines in 3-space |
| title_full | Ramsey-type theorems for lines in 3-space |
| title_fullStr | Ramsey-type theorems for lines in 3-space |
| title_full_unstemmed | Ramsey-type theorems for lines in 3-space |
| title_short | Ramsey-type theorems for lines in 3-space |
| title_sort | ramsey type theorems for lines in 3 space |
| topic | mathematics - combinatorics computer science - computational geometry 05d10, 52c35 |
| url | https://dmtcs.episciences.org/1367/pdf |
| work_keys_str_mv | AT jeancardinal ramseytypetheoremsforlinesin3space AT michaelspayne ramseytypetheoremsforlinesin3space AT noamsolomon ramseytypetheoremsforlinesin3space |