Planar graphs | Theorems in graph theory

Kuratowski's theorem

In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of (the complete graph on five vertices) or of (a complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph). (Wikipedia).

Kuratowski's theorem
Video thumbnail

The Homework Problem That Started as a Phd Thesis: 14 set theorem

In a handful of introductory topology textbooks, Kuratowski's 14 set theorem is given as an exercise despite it being one of the results proven as a part of his phd thesis in 1922. This homework problem that started out as a phd thesis is not an easy exercise if you don't know how to think

From playlist The New CHALKboard

Video thumbnail

Yoshihiro Ohnita: Minimal Maslov number of R-spaces canonically embedded in Einstein-Kähler C-spaces

An R-space is a compact homogeneous space obtained as an orbit of the isotropy representation of a Riemannian symmetric space. It is known that each R-space has the canonical embedding into a Kähler C-space as a real form which is a compact embedded totally geodesic Lagrangian submanifold.

From playlist Geometry

Video thumbnail

MATH1081 Discrete Maths: Chapter 5 Question 27 a

This problem is about planar graphs. The theorem mentioned is Fáry's Theorem (1948); see http://bit.ly/1gmUrXT . Presented by Thomas Britz of the School of Mathematics and Statistics, Faculty of Science, UNSW.

From playlist MATH1081 Discrete Mathematics

Video thumbnail

Graph Theory: 61. Characterization of Planar Graphs

We have seen in a previous video that K5 and K3,3 are non-planar. In this video we define an elementary subdivision of a graph, as well as a subdivision of a graph. We then discuss the fact that if a graph G contains a subgraph which is a subdivision of a non-planar graph, then G is non-

From playlist Graph Theory part-10

Video thumbnail

Pär Kurlberg: Class number statistics for imaginary quadratic fields Pär Kurlberg

Abstract: The number F(h) of imaginary quadratic fields with class number h is of classical interest: Gauss' class number problem asks for a determination of those fields counted by F(h). The unconditional computation of F(h) for h x is less or equal to y 100 was completed by M. Watkins, a

From playlist Number Theory

Video thumbnail

Introduction to additive combinatorics lecture 1.8 --- Plünnecke's theorem

In this video I present a proof of Plünnecke's theorem due to George Petridis, which also uses some arguments of Imre Ruzsa. Plünnecke's theorem is a very useful tool in additive combinatorics, which implies that if A is a set of integers such that |A+A| is at most C|A|, then for any pair

From playlist Introduction to Additive Combinatorics (Cambridge Part III course)

Video thumbnail

Introduction to additive combinatorics lecture 10.8 --- A weak form of Freiman's theorem

In this short video I explain how the proof of Freiman's theorem for subsets of Z differs from the proof given earlier for subsets of F_p^N. The answer is not very much: the main differences are due to the fact that cyclic groups of prime order do not have lots of subgroups, so one has to

From playlist Introduction to Additive Combinatorics (Cambridge Part III course)

Video thumbnail

A Classification of Planar Graphs - A Proof of Kuratowski's Theorem

A visually explained proof of Kuratowski's theorem, an interesting, important and useful result classifying "planar" graphs. Proof adapted from: http://math.uchicago.edu/~may/REU2017/REUPapers/Xu,Yifan.pdf and: https://www.math.cmu.edu/~mradclif/teaching/228F16/Kuratowski.pdf Also check

From playlist Summer of Math Exposition Youtube Videos

Video thumbnail

Graph Theory: 62. Graph Minors and Wagner's Theorem

In this video, we begin with a visualisation of an edge contraction and discuss the fact that an edge contraction may be thought of as resulting in a multigraph or simple graph, depending on the application. We then state the definition a contraction of edge e in a graph G resulting in a

From playlist Graph Theory part-10

Video thumbnail

Planar Graphs - Numberphile

Featuring Professor Maria Chudnovsky from Princeton University - see part two about her work on Perfect Graphs - https://youtu.be/C4Zr4cOVm9g More links & stuff in full description below ↓↓↓ Correction at 13:58 - remove the word "not". Professor Chudnovsky's webpage: https://web.math.pri

From playlist Women in Mathematics - Numberphile

Video thumbnail

Monotonicity of the Riemann zeta function and related functions - P Zvengrowski [2012]

General Mathematics Seminar of the St. Petersburg Division of Steklov Institute of Mathematics, Russian Academy of Sciences May 17, 2012 14:00, St. Petersburg, POMI, room 311 (27 Fontanka) Monotonicity of the Riemann zeta function and related functions P. Zvengrowski University o

From playlist Number Theory

Video thumbnail

Maxim Kazarian - 1/3 Mathematical Physics of Hurwitz numbers

Hurwitz numbers enumerate ramified coverings of a sphere. Equivalently, they can be expressed in terms of combinatorics of the symmetric group; they enumerate factorizations of permutations as products of transpositions. It turns out that these numbers obey a huge num

From playlist ­­­­Physique mathématique des nombres de Hurwitz pour débutants

Video thumbnail

Rade Zivaljevic (6/27/17) Bedlewo: Topological methods in discrete geometry; new developments

Some new applications of the configurations space/test map scheme can be found in Chapter 21 of the latest (third) edition of the Handbook of Discrete and Computational Geometry [2]. In this lecture we focus on some of the new developments which, due to the limitations of space, may have b

From playlist Applied Topology in Będlewo 2017

Video thumbnail

Rahim Moosa: Around Jouanolou-type theorems

Abstract: In the mid-90’s, generalising a theorem of Jouanolou, Hrushovski proved that if a D-variety over the constant field C has no non-constant D-rational functions to C, then it has only finitely many D-subvarieties of codimension one. This theorem has analogues in other geometric con

From playlist Combinatorics

Video thumbnail

Wojciech Kucharz: Criteria for equivalence between power series and polynomials

Find this video and other talks given by worldwide mathematicians on CIRM's Audiovisual Mathematics Library: http://library.cirm-math.fr. And discover all its functionalities: - Chapter markers and keywords to watch the parts of your choice in the video - Videos enriched with abstracts, b

From playlist Algebraic and Complex Geometry

Video thumbnail

Dimitri Zvonkine - On two ELSV formulas

The ELSV formula (discovered by Ekedahl, Lando, Shapiro and Vainshtein) is an equality between two numbers. The first one is a Hurwitz number that can be defined as the number of factorizations of a given permutation into transpositions. The second is the integral of a characteristic class

From playlist 4th Itzykson Colloquium - Moduli Spaces and Quantum Curves

Video thumbnail

Ulrich Bauer (3/4/22): Gromov hyperbolicity, geodesic defect, and apparent pairs in Rips filtrations

Motivated by computational aspects of persistent homology for Vietoris-Rips filtrations, we generalize a result of Eliyahu Rips on the contractibility of Vietoris-Rips complexes of geodesic spaces for a suitable parameter depending on the hyperbolicity of the space. We consider the notion

From playlist Vietoris-Rips Seminar

Video thumbnail

Maxim Kazarian - 3/3 Mathematical Physics of Hurwitz numbers

Hurwitz numbers enumerate ramified coverings of a sphere. Equivalently, they can be expressed in terms of combinatorics of the symmetric group; they enumerate factorizations of permutations as products of transpositions. It turns out that these numbers obey a huge num

From playlist ­­­­Physique mathématique des nombres de Hurwitz pour débutants

Related pages

Kelmans–Seymour conjecture | Planar graph | Glossary of graph theory | Homeomorphism (graph theory) | Path (graph theory) | Euler characteristic | Wagner's theorem | Graph theory | Graph minor | Complete bipartite graph | Line segment | Branch and cut | Planarity testing | Complete graph | Vertex (graph theory) | Cubic graph | Euclidean plane | Graph isomorphism | Forbidden graph characterization | Utility graph | Fáry's theorem