Open Collections

Page Metadata

Item Metadata

Title	Disjointness Graphs
Creator	Pach, Janos
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2017-05-23T13:30
Description	The {\em disjointness graph} $G=G({\cal S})$ of a set of segments ${\cal S}$ in ${R}^d$, $d\ge 2,$ is a graph whose vertex set is ${\cal S}$ and two vertices are connected by an edge if and only if the corresponding segments are disjoint. We prove that the chromatic number of $G$ is bounded by a function of $\omega(G)$, the clique number of $G$. More precisely, we have $\chi(G)\le(\omega(G))^4+(\omega(G))^3$. It follows, that $\cal S$ has $\Omega(n^{1/5})$ pairwise intersecting or pairwise disjoint elements. Stronger bounds are established for lines in space, instead of segments. We show that computing $\omega(G)$ and $\chi(G)$ for disjointness graphs of lines in space are NP-complete tasks. However, we can design efficient algorithms to compute proper colorings of $G$ in which the number of colors satisfies the above upper bounds. One cannot expect similar results for sets of continuous arcs, instead of segments, even in the plane. We construct families of arcs whose disjointness graphs are triangle-free ($\omega(G)=2$), but whose chromatic numbers are arbitrarily large. Joint work with G\'abor Tardos and G\'eza T\'oth.
Extent	34 minutes
Subject	Mathematics Convex and discrete geometry Geometry Discrete mathematics
Geographic Location	Banff (Alta.)
Type	Moving Image
FileFormat	video/mp4
Language	eng
Notes	Author affiliation: Ecole Polytechnique Federale de Lausanne
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2017-12-03
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0361151
URI	http://hdl.handle.net/2429/63800
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
AggregatedSourceRepository	DSpace

Download

Media

48630-201705231330-Pach_lrv.mp4 [ 130.09MB ]

Metadata

JSON: 48630-1.0361151.json

JSON-LD: 48630-1.0361151-ld.json

RDF/XML (Pretty): 48630-1.0361151-rdf.xml

RDF/JSON: 48630-1.0361151-rdf.json

Turtle: 48630-1.0361151-turtle.txt

N-Triples: 48630-1.0361151-rdf-ntriples.txt

Original Record: 48630-1.0361151-source.json

Citation

48630-1.0361151.ris

Cite

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.

Include Metadata Specify width in pixels (leave blank for auto-width):

                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    

Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:

http://iiif.library.ubc.ca/presentation/dsp.48630.1-0361151/manifest

Comment

Related Items