# Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

Belépés
címtáras azonosítással

vissza a tantárgylistához   nyomtatható verzió

Graph Theory

A tantárgy neve magyarul / Name of the subject in Hungarian: Gráfelmélet

Last updated: 2010. november 11.

 Budapest University of Technology and Economics Faculty of Electrical Engineering and Informatics Mérnök informatikus szakBSc képzés
 Course ID Semester Assessment Credit Tantárgyfélév VISZA086 3/1/0/v 4
3. Course coordinator and department Dr. Fleiner Tamás,
Web page of the course www.cs.bme.hu/....
4. Instructors
 Name Position Department Gábor SIMONYI Professor Department of Computer Science and Information Theory Tamás FLEINER Assoc. professor Department of Computer Science and Information Theory Dávid SZESZLÉR Assoc. professor Department of Computer Science and Information Theory Gábor WIENER Assoc. professor Department of Computer Science and Information Theory Ildikó SCHLOTTER Assistant lecturer Department of Computer Science and Information Theory
7. Objectives, learning outcomes and obtained knowledge

The objective of the first part of this course is to introduce the students with some of the most important notions of graph theory and develop their skill to solve basic exercises. It is also an objective of the course that on the way they become able to identify graph theory problems in a natural way even if those appear in a different setting.

The objective of the second part is to deepen the students' knowledge of graph theory by showing interrelations of some of the seemingly loosely related concepts and further develop their problem solving skills. Although there is no formal prerequisite for this course, some basic mathematical maturity is expected.

8. Synopsis
1. Introduction

Basic notions of graphs

Why are they interesting and what are we interested in about them

Trees and their main properties

Coding and counting trees on n labelled vertices

2. The Königsberg bridges problem and Euler tours

Euler tours in directed graphs

The existence of deBruijn sequences

Hamiltonian cycles

The different nature of Hamiltonian cycles and Euler tours

Necessary conditions for Hamiltonicity

Sufficient conditions for Hamiltonicity due to Dirac, Pósa, Ore, and Chvátal

1. Matchings and their relevance

Necessary and sufficient conditions for the existence of a perfect matching in   bipartite graphs

Kőnig's min-max theorem

Perfect matchings in general graphs, Tutte's criterion

Stable matchings and their use

The existence of stable matchings in bipartite graphs

1. Network flows

The augmenting paths algorithm

The Ford-Fulkerson min-max result and its relation to Kőnig's one

Menger's min-max results

The relevance of min-max formulae in general

1. Planarity,

Euler's formula and Kuratowski's criterion

Minors and Wagner's criterion

The equivalence of forbidding the Kuratowski graphs as minors and as topological

subgraphs

1. Coloring graphs as a model for scheduling

Bounding the chromatic number from above, greedy algorithm

Bounding the chromatic number from below, Mycielski's construction

Coloring edges

Line graphs and the analogs of the previous bounds

Improving the greedy algorithm, Vizing's upper bound

1. Coloring planar graphs, 4-color theorem and 5-color theorem,

Tait's result on the the relation of edge-coloring cubic planar graphs and the 4-color

theorem

Perfect graphs, perfectness of bipartite graphs, their line graphs and the complements

of these

Odd holes, odd antiholes and their relevance

Relation of complementation and perfectness in general

8. List coloring

Relation of the list coloring number to the chromatic number, list coloring conjecture

Galvin's theorem and its relation to stable matchings

List coloring planar graphs

Thomassen's inductive argument

Voigt's construction for the sharpness of Thomassen's result

1. Extremal graph theory

Turán's sharp upper bound on the number of edges if the clique number is bounded

The Erdős-Stone theorem and the Erdős-Simonovits limit result

The Kővari-T.Sós-Turán upper bound for the analogous bipartite problem

1. Ramsey theory

Basic Ramsey-type results in graph theory

Examples of Ramsey-type results outside graph theory

Ramsey numbers, upper and lower bounds

1. Hypergraphs as generalizations of graphs and as set systems

Ramsey's result in the hypergraph setting

Sperner systems and their maximum possible size

LYM inequality

1. Kneser's conjecture as a problem on hypergraphs

Kneser graphs and their chromatic number, the Lovász-Kneser theorem

Kneser graphs and fractional colorings

9. Method of instruction Lectures and recitations

10. Assessment The grade given will be based on four homework assignments consisting of five problems each, and on the final exam. The solutions should be handed in by the due date that will be on the 4th, 6th, 9th and 11th weeks, respectively. The assignments will be handed out at least a week before the due date. (Please note that no late homework will be accepted.) The assignments weigh 15% each while the final exam weighs 40% in calculating the final score.

12. Consultations You can reach the instructor at the following e-mail address for consultation:

Gábor SIMONYI: simonyi@renyi.hu

13. References, textbooks and resources

Reinhard Diestel: Graph Theory, 3rd Edition, Springer-Verlag, Heidelberg, 2005;  or

Béla Bollobás: Modern Graph Theory, Springer-Verlag, Heidelberg, Corr. 2nd printing 2002.

Additional useful reading: Martin Aigner, Günter Ziegler:Proofs from the Book, Springer-Verlag, Heidelberg, 1998.

14. Required learning hours and assignment
 Number of contact hours 56 Preparation to the classes 14 Preparation to the tests Homework 30 Assigned reading Preparation to the exam 20 Total 120
15. Syllabus prepared by
 Name Position Department Gábor SIMONYI Professor Department of Computer Science and Information Theory