Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
String graphs have the Erdos-Hajnal property
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.ORCID iD: 0000-0001-8344-3592
2024 (English)In: Journal of the European Mathematical Society (Print), ISSN 1435-9855, E-ISSN 1435-9863, Vol. 26, no 1, p. 275-287Article in journal (Refereed) Published
Abstract [en]

The following Ramsey-type question is one of the central problems in combinatorial geometry. Given a collection of certain geometric objects in the plane (e.g. segments, rectangles, convex sets, arcwise connected sets) of size n, what is the size of the largest subcollection in which either any two elements have a nonempty intersection, or any two elements are disjoint? We prove that there exists an absolute constant c > 0 such that if C is a collection of n curves in the plane, then C contains at least nc elements that are pairwise intersecting, or nc elements that are pairwise disjoint. This resolves a problem raised by Alon, Pach, Pinchasi, Radoicic and Sharir, and Fox and Pach. Furthermore, as any geometric object can be arbitrarily closely approximated by a curve, this shows that the answer to the aforementioned question is at least nc for any collection of n geometric objects.

Place, publisher, year, edition, pages
European Mathematical Society Publishing House, 2024. Vol. 26, no 1, p. 275-287
Keywords [en]
Ramsey theory, String graphs
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-222292DOI: 10.4171/JEMS/1362ISI: 001168575300009Scopus ID: 2-s2.0-85186383313OAI: oai:DiVA.org:umu-222292DiVA, id: diva2:1846656
Available from: 2024-03-25 Created: 2024-03-25 Last updated: 2024-03-25Bibliographically approved

Open Access in DiVA

fulltext(257 kB)488 downloads
File information
File name FULLTEXT01.pdfFile size 257 kBChecksum SHA-512
e45bac2edaddc8567129e7e8956444b9687c0095e507233890335bfe712691ac4b8254b775189db0874b1a4a23566371e821cd60576afa3dc3d88346578e35d6
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Tomon, István

Search in DiVA

By author/editor
Tomon, István
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of the European Mathematical Society (Print)
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 488 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 1044 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf