Axiomatic Number Theory and Godel's Theorems
Beyond planarity of graphs
Eyal Ackerman
University of Haifa and Oranim College
Drawing graphs in the plane
Consider drawings of graphs in the plane s.t.
No loops or parallel edges
Vertices
distinct points
Edges
Jordan arcs (no self-intersection)
Two edges intersect finitely many times
Intersection = crossing / common vertex
No three edges cross at a point
T
o
p
o
l
o
g
i
c
a
l
g
r
a
p
h
s
Two edges intersect at most once
S
i
m
p
l
e
t
o
p
o
l
o
g
i
c
a
l
g
r
a
p
h
s
Straight-line edges
G
e
o
m
e
t
r
i
c
g
r
a
p
h
s
The Crossing Lemma
The Crossing Lemma
Applications
Applications: Albertson Conjecture
Applications: Albertson Conjecture
The local (pair) crossing number
A Hanani-Tutte-type problem
Lower bounds
Virtually crossing edges
p
a
r
a
l
l
e
l
/
a
v
o
i
d
i
n
g
e
d
g
e
s
v
i
r
t
u
a
l
l
y
c
r
o
s
s
i
n
g
e
d
g
e
s
Virtually crossing edges
p
a
r
a
l
l
e
l
/
a
v
o
i
d
i
n
g
e
d
g
e
s
v
i
r
t
u
a
l
l
y
c
r
o
s
s
i
n
g
e
d
g
e
s
Virtually crossing edges (2)
Fan-planar graphs
* that’s actually part of the definition of fan-planar graphs there and elsewhere
Fan-planar graphs (2)
Yet another not-far-from-planar graph
Thank you
Georg Cantor, Bertrand Russell, and Kurt Gödel made significant contributions to the development of axiomatic theories in mathematics, specifically in number theory and set theory. Gödel's Incompleteness Theorems revolutionized the understanding of formal systems and paved the way for deeper investigations into the nature of mathematical truth and provability. This presentation delves into the foundations of axiomatic theories, the historical context, and the key ideas behind Gödel's groundbreaking results. It explores the concepts of axioms, rules of inference, and Gödel numbering, shedding light on the intricate relationship between mathematical logic and theoretical foundations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Beyond planarity of graphs Eyal Ackerman University of Haifa and Oranim College
Drawing graphs in the plane Consider drawings of graphs in the plane s.t. No loops or parallel edges Vertices distinct points Edges Jordan arcs (no self-intersection) Two edges intersect finitely many times Intersection = crossing / common vertex No three edges cross at a point Topological graphs Two edges intersect at most once Simple topological graphs Straight-line edges Geometric graphs
?-planar graphs A topological graph is ?-plane if every edge is crossed at most ? times. A graph is ?-planar if it can be drawn as a ?-plane topological graph. ??? = max size of a ?-planar graph ?0? = 3? 6 ?1? = 4? 8, ?2? = 5? 10 [Pach and T th 97] ?3? = 5.5? ? 1 [Pach et al. 06] ?4? = 6? ?(1) [A. 14] Problem: determine ?5? . ??? = ( ??) by the Crossing Lemma
The Crossing Lemma Crossing Lemma: For every graph ? with ? vertices and ? 4? edges cr(?) ? ?3/?2. [Ajtai, Chv tal, Newborn, Szemer di 82; Leighton 83] cr(?) = crossing number = minimum number of crossings in a drawing of ?.
The Crossing Lemma Crossing Lemma: For every graph ? with ? vertices and ? 4? edges cr(?) ? ?3/?2. [Ajtai, Chv tal, Newborn, Szemer di 82; Leighton 83] Tight apart from ?. 100, later 1 1 Originally 64 1 33.75 1 31.1 [Pach & T th 97]: Using new bounds on ??? for small ? [Pach et al. 06]: [A. 14]: 1 29 0.0345 Problem [T th, Eml kt bla 2011]: improve the bounds on ?. ? 0.09 [Pach & T th 97]
Applications Improving the crossing lemma yields immediate improvements in all of its applications. For example: ??? 3.81 ??, for ? 2 Previous best constant factor was 3.95 The number of incidences between ? lines and ? points in the plane is at most 2.44?2/3?2/3+ ? + ?. Previous best constant factor was 2.5 Should be greater than 0.63
Applications: Albertson Conjecture Albertson Conj.: if ? ? = ? then cr ? cr(??). It suffices to verify for ?-critical graphs ? 4 trivial ? = 5 Four Color Theorem: Suppose there is a planar graph ? with ? ? = 5. However, by AC cr ? cr ?5 = 1 > cr(?) = 0. If ? ? = 5 then ? cannot be planar, cr ? 1 = cr ?5.
Applications: Albertson Conjecture Albertson Conj.: if ? ? = ? then cr ? cr(??). It suffices to verify for ?-critical graphs ? 4 trivial ? = 5 Four Color Theorem ? = 6 [Oporowskia & Zhao 09] ? 12 [Albertson, Cranston & Fox 10] ? 16 [Bar t & T th 10] ? 18 [A. 14] following [Bar t & T th 10]. AC holds for ?-vertex ?-critical graphs if ? ? + 4 or ? 3.03? [A. 14, Bar t & T th 10].
The local (pair) crossing number lcr(?) = min ? s.t. ? is ?-planar lpcr(?) = min ? s.t. ? is can be drawn such that every edge crosses at most ? other edges (possibly more than once). Clearly, lpcr ? lcr(?). ? s.t. lpcr ? < lcr(?): lpcr ? = 4, lcr ? = 5 lcr ? < 2lpcr(?)[Schaefer & tefankovi 2004] If lpcr ? 2 then lpcr ? = lcr ? [A. & Schaefer 14]. Problem: Does lpcr ? = 3 imply lcr ? = 3 ? If true, then lpcr ? 3 implies |?(?)| 5.5? ?(1). Can only show that lpcr ? 3 implies |?(?)| 6? ?(1).
A Hanani-Tutte-type problem Hanani-Tutte Thm: if ? can be drawn such that every edge crosses no other edge an odd number of times, then ? is planar. Problem: Is it true that if ? can be drawn such that every edge crosses at most one other edge an odd number of times, then ? is 1-planar? Can we show that ? is ?-planar for some ??
Decomposing ?-planar graphs Every ?-plane graph can be decomposed into ? + 1 plane graphs: Remove a maximal plane subgraph Yields (? 1)-plane graph Recall: max size of a ?-plane graph ? 1 4? 8 2 5? 10 3 5.5? ?(1) 4 6? ?(1) 1-plane graph = plane + forest [A. 14] Problem: 2-plane graph = plane + 2 forest ? What about ?-plane graphs for ? > 2?
?-quasi-planar graphs A topological graph is ?-quasi-plane if it has no ? pairwise crossing edges. E.g.,2-quasi-plane = plane graph and 3-quasi-plane means no A graph is ?-quasi-planar if it can be drawn as a ?-quasi- plane topological graph. Conj.: For any ? 2 every ?-quasi-planar graph has at most ??? edges.
?-quasi-planar graphs (2) Conj.: For any ? 2 every ?-quasi-planar graph has at most ??? edges. Trivial for ? = 2 For ? = 3: [Agarwal et al. 97]: true for simple topological graphs [Pach et al. 03]: true for the general case [A. & Tardos 07]: simpler proofs with better constants Max size of a simple 3-quasi-planar graph is 6.5? ?(1) Max size of a 3-quasi-planar graph is between 7? ? 1 and 8? ? 1 For ? = 4 the conjecture holds [A. 09]. For ? > 4 the conjecture is open.
?-quasi-planar graphs (3) Conj.: For any ? 2 every ?-quasi-planar graph has at most ??? edges. For ? > 4 the conjecture is open. Best upper bounds on the size of ?-quasi-planar graphs: ??(?log?) for simple graphs [Suk & Walczack 13] ? (log?)?(log ?)[Fox & Pach 12] Problem: improve these bounds.
Decomposing ?-quasi-plane graphs Problem: what is the minimum number = (?,?) s.t. any ?-vertex ?-quasi-plane graph can be decomposed into plane graphs? If ? is ?-quasi-plane then |?(?)| 3? (?,?) ?,3 = (loglog?) [Palwik et al. 14] ?,? = (log?)?(log ?)[Fox & Pach, 12] ?,? = ??(log?) for ?-monotone graphs [Suk, 14]
Lower bounds Problem: find non-trivial lower bounds on the maximum size of a ?-quasi-planar graph. 3?(? 1) ?(?) by overlaying ? 1 edge-disjoint triangulations The thickness of K?is ?/6 + ?(1) Most planar subgraphs have 3? ?(1) edges Any planar graph can be embedded into any set of points according to any bijection [Pach & Wenger 01] 3?(? 1) ?(?2) for geometric graphs: ? (? 1) ? 1
Virtually crossing edges Consider two (independent) edges in a geometric graph: parallel / avoiding edges virtually crossing edges Conj.: For any ? 2 every geometric graph with no ? pairwise virtually crossing edges has at most ??? edges. [Valtr 98]: For any ? 2 every geometric graph with no ? pairwise parallel edges has at most ??? edges.
Virtually crossing edges Consider two (independent) edges in a geometric graph: parallel / avoiding edges virtually crossing edges Conj.: For any ? 2 every geometric graph with no ? pairwise virtually crossing edges has at most ??? edges. For ? 4 holds by ?-quasi-planarity Problem: provide different proofs (and better bounds) For ? = 2 the maximum size is 2? 3 Not so easy if ? is not in general position [A., Nitzan, Pinchasi 14]
Virtually crossing edges (2) Showing that a complete geometric graph has ?/2 pairwise virtually crossing edges is easy: whereas, showing that a complete geometric graph has (?) pairwise crossing edges is an open problem. Best bound is only ? [Aronov et al. 94]
Fan-planar graphs A (simple) topological graph is fan-planar if for every three edges ?1, ?2,?3if ?2and ?3cross ?1then they share a vertex. Easy: if ? is fan-planar then |?(?)| = ?(?) Conj.: if ? is fan-planar then ? ? Tight if true Holds if ?2and ?3must share a vertex on the same side of ??[Kaufmann & Ueckerdt]*: 5? 10 * that s actually part of the definition of fan-planar graphs there and elsewhere
Fan-planar graphs (2) Can we rule out triangle crossing? Note that ??has no further crossings If yes, then all edges crossing ??share the same vertex.
Yet another not-far-from-planar graph Maximal fan- and 1-plane graphs satisfy: for every two crossing edges there is a crossing-free edge that connects endpoints of these edges. Problem: what is the maximum size of a topological graph satisfying the above? 9-quasi-planar, hence at most ?(log?)? Should be ? ? . At least 6? ?(1)
