BME VIK - Gráfelmélet

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 szak

BSc 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

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

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

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

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

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

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

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

Ramsey theory

Basic Ramsey-type results in graph theory

Examples of Ramsey-type results outside graph theory

Ramsey numbers, upper and lower bounds

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

Intersecting set systems, Erdős-Ko-Rado theorem

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 4^th, 6^th, 9^th and 11^th 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, 3^rd Edition, Springer-Verlag, Heidelberg, 2005; or

Béla Bollobás: Modern Graph Theory, Springer-Verlag, Heidelberg, Corr. 2^nd 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

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

Gráfelmélet