Show simple item record

dc.contributor.author
Goaoc, Xavier
dc.contributor.author
Hubard, Alfredo
dc.contributor.author
de Joannis de Verclos, Rémi
dc.contributor.author
Sereni, Jean-Sébastien
dc.contributor.author
Volec, Jan
dc.contributor.editor
Arge, Lars
dc.contributor.editor
Pach, János
dc.date.accessioned
2019-07-18T07:40:18Z
dc.date.available
2017-06-11T22:02:38Z
dc.date.available
2019-07-18T07:40:18Z
dc.date.issued
2015
dc.identifier.isbn
978-3-939897-83-5
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.SOCG.2015.300
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/108611
dc.identifier.doi
10.3929/ethz-b-000108611
dc.description.abstract
The notion of limits of dense graphs was invented, among other reasons, to attack problems in extremal graph theory. It is straightforward to define limits of order types in analogy with limits of graphs, and this paper examines how to adapt to this setting two approaches developed to study limits of dense graphs. We first consider flag algebras, which were used to open various questions on graphs to mechanical solving via semidefinite programming. We define flag algebras of order types, and use them to obtain, via the semidefinite method, new lower bounds on the density of 5- or 6-tuples in convex position in arbitrary point sets, as well as some inequalities expressing the difficulty of sampling order types uniformly. We next consider graphons, a representation of limits of dense graphs that enable their study by continuous probabilistic or analytic methods. We investigate how planar measures fare as a candidate analogue of graphons for limits of order types. We show that the map sending a measure to its associated limit is continuous and, if restricted to uniform measures on compact convex sets, a homeomorphism. We prove, however, that this map is not surjective. Finally, we examine a limit of order types similar to classical constructions in combinatorial geometry (Erdos-Szekeres, Horton...) and show that it cannot be represented by any somewhere regular measure; we analyze this example via an analogue of Sylvester's problem on the probability that k random points are in convex position.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Order types
en_US
dc.subject
Limits of discrete structures
en_US
dc.subject
Flag algebras
en_US
dc.subject
Erdos-Szekeres
en_US
dc.subject
Sylvester’s problem
en_US
dc.title
Limits of order types
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
31st International Symposium on Computational Geometry (SoCG 2015)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
34
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
300
en_US
ethz.pages.end
314
en_US
ethz.size
15 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
31st International Symposium on Computational Geometry (SoCG 2015)
en_US
ethz.event.location
Eindhoven, Netherlands
ethz.event.date
June 22-25, 2015
en_US
ethz.grant
Problems in Extremal Combinatorics
en_US
ethz.identifier.scopus
ethz.identifier.nebis
010527402
ethz.publication.place
Dagstuhl
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03993 - Sudakov, Benjamin / Sudakov, Benjamin
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03993 - Sudakov, Benjamin / Sudakov, Benjamin
ethz.grant.agreementno
149111
ethz.grant.fundername
SNF
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.program
Projektförderung in Mathematik, Natur- und Ingenieurwissenschaften (Abteilung II)
ethz.date.deposited
2017-06-11T22:02:43Z
ethz.source
ECIT
ethz.identifier.importid
imp593653d22f51393547
ethz.ecitpid
pub:169602
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-12T14:37:02Z
ethz.rosetta.lastUpdated
2024-02-02T08:31:55Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Limits%20of%20order%20types&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2015&rft.volume=34&rft.spage=300&rft.epage=314&rft.issn=1868-8969&rft.au=Goaoc,%20Xavier&Hubard,%20Alfredo&de%20Joannis%20de%20Verclos,%20R%C3%A9mi&Sereni,%20Jean-S%C3%A9bastien&Volec,%20Jan&rft.isbn=978-3-939897-83-5&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.SOCG.2015.300&rft.btitle=31st%20International%20Symposium%20on%20Computational%20Geometry%20(SoCG%202015)
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record