Structural Graph Theory 

Doc-Course, October - December 2014

Computer Science Inst. (IÚUK)  & Dept. Applied Mathematics (KAM), Faculty of Mathematics and Physics (MFF), Charles University (UK)
Malostranské nám. 25, Prague 1, Czech Republic

Vybrané Kapitoly z Kombinatoriky I/ Selected Chapters in Combinatorics NDMI055. Guarantor: J. Nešetřil,  A. Goodall       Assistant:   L. Vena Cros

About               Lecturers          Schedule          Titles & Abstracts         Further reading

About the course

Five distinguished visiting speakers will each give a short series of lectures. The intended audience includes graduate students and postdocs in Mathematics or Computer Science, with an interest in graph theory, Ramsey theory, the interaction of combinatorics with logic and mathematical physics, and related fields. Students at other universities (domestic and abroad) are welcome. Financial assistance for students who need to travel to attend the lectures is possible: please write to andrew@iuuk.mff.cuni.cz

Students taking the KAM/ IÚUK course NDMI055 Vybrané Kapitoly z Kombinatoriky I (Selected Chapters in Combinatorics) may as an alternative to end-of-semester exams select at least two of the special lectures and write an exam in the form of a project based on material from some of these lectures. For this course, complementary lectures will be given by Prof. Nešetřil and Dr Goodall, details of which will become available at the beginning of the Doc-Course and posted on this web page.
This page will also provide links to lecture slides or notes, if available, as well as links to resources of relevance to the lectures.

For further information about attending the course please write to andrew@iuuk.mff.cuni.cz

Poster and information leaflet.

«

Lecturers

Prof. M. DeVos, Simon Fraser University, Vancouver

Prof. J. Makowsky, Technion - Israel Institute of Technology, Haifa

Dr G. Kun, ELTE, Budapest

Prof. M. Pinsker, Technische Universität Wien/ Université Diderot - Paris 7

Dr L. Zdeborová, CEA & CNRS, Saclay

«

Schedule

All lectures will take place in S6, 2^nd floor, KAM, Malostranské nám. 25 unless otherwise indicated.

«

Titles & Abstracts

Prof. Matt DeVos

Immersion for 2-regular digraphs

In this talk we will focus on the world of 2-regular digraphs, i.e. digraphs for which every vertex has indegree and outdegree equal to 2.  Surprisingly, this family of digraphs behaves under the operation of immersion in a manner very similar to the way in which standard graphs behave under minors.  This deep truth is best evidenced by the work of Thor Johnson, who developed an analogue of the Robertson-Seymour Graph Minor Theory for 2-regular digraphs under immersion.  We will discuss some recent work together with Archdeacon, Hannie, and Mohar in this vein.  Namely, we establish the excluded immersions for certain surface embeddings of 2-regular digraphs in the projective plane.

Flows in bidirected graphs

Tutte showed that for planar dual graphs G and G*, a k-coloring of G is equivalent to the existence of a nowhere-zero k-flow in G*.  This led him to his famous conjecture that every bridgeless graph has a nowhere-zero 5-flow.  Although this conjecture remains open, Seymour has proved that every such graph has a nowhere-zero 6-flow.  Bouchet studied this flow-coloring duality on more general surfaces, and this prompted him to introduce the notion of nowhere-zero flows in bidirected graphs.  He conjectured that every bidirected graph without a certain obvious obstruction has a nowhere-zero 6-flow.  Improving on a sequence of earlier theorems, we show that every such graph has a nowhere-zero 12-flow.

Average degree in graph powers

For a graph G and a positive integer k, we let G^k denote the graph with vertex set V(G) and two vertices adjacent in G^k if they have distance at most k in the original graph G.  Motivated by some problems in additive number theory (which we will

explain), we turn our attention to determining lower bounds on the average degree of the graph G^k when the original graph G is d-regular.  We will describe fairly complete answers to this question when k < 6 and in general when k is congruent to 2 (mod 3).  This talk represents joint work with McDonald, Scheide, and Thomassé.

Prof. Johann Makowsky

Classical graph properties and graph parameters and their definability in SOL

Intriguing graph polynomials. Why is the chromatic polynomial a polynomial? Comparing graph polynomials. Connection matrices and their use in showing non-definability.

Dr Gábor Kun

Expanders everywhere

I will give the most important equivalent definitions of expanders. I plan to highlight many different applications from group theory to graph theory, computer science and number theory. I would like to mention some basic ideas of the proof of the Banach-Ruziewicz problem, the Jerrum-Sinclair algorithm and, if time allows, the Bourgain-Gamburd-Sarnak sieve.

Prof. Michael Pinsker

Algebraic and model-theoretic methods in constraint satisfaction

The Constraint Satisfaction Problem (CSP) of a finite or countable first-order structure S in a finite relational language is the problem of deciding whether a given conjunction of atomic formulas in that language is satisfiable in S. Many classical computational problems can be modelled this way. The study of the complexity of CSPs involves an interesting combination of techniques from universal algebra, Ramsey theory, and model theory. This tutorial will present an overview over these techniques as well as some wild conjectures.

Dr Lenka Zdeborová

Coloring random and planted graphs: Thresholds, structure of solutions, algorithmic hardness

Random graph coloring is a key problem for understanding average algorithmic complexity. Planted random graph coloring is a typical example of an inference problem where the planted configuration corresponds to an unknown signal and the graph edges to observations about the signal. Remarkably, over the recent decade or two tremendous progress has been made on the problem using (principled, but mostly non-rigorous) methods of statistical physics. We will describe the methods - message passing algorithms and the cavity method. We will discuss their results - structure of the space of solutions, associated algorithmic implications, and corresponding phase transitions. We will conclude by summarizing recent mathematical progress in making these results rigorous and discuss interesting open problems.

«

Further reading

Prof. Matt DeVos

Lecture notes: Immersion for 2-regular digraphs, Flows in bidirected graphs, Average degree in graph powers

Flows on bidirected graphs: arXiV paper
Edge growth in graph cubes (with Stéphan Thomassé): arXiV paper

Prof. Johann Makowsky

Lecture notes/slides including an overview with further links to relevant papers.

Graph polynomials project in Haifa: homepage

Vienna 2014 lecture course on graph polynomials: slides

Dr Gábor Kun

Expanders have a spanning Lipschitz subgraph with large girth: arXiV paper

Prof. Michael Pinsker

Slides: Part I, Part II, Part III,  Part IV

Schaefer's theorem for graphs (with Manuel Bodirsky): arXiV paper
Topological Birkhoff (with Manuel Bodirsky): arXiV paper

Dr Lenka Zdeborová

Hiding quiet solutions in random constraint satisfaction problems (with Florent Krzakala): arXiV paper

«

Counting flows on graphs: finite Abelian group and integer flows

Bill Jackson: Nowhere-zero flows in graphs (slides)

Matthias Beck, Sinai Robins: Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra. Non-printable pdf. See also links on Matthias Beck's homepage.

Martin Kochol: Polynomials associated with nowhere-zero flows

Matthias Beck, Thomas Zaslavsky: The number of nowhere-zero flows on graphs and signed graphs

Felix Breuer, Raman Sanyal: Ehrhart theory, modular flow reciprocity, and the Tutte polynomial

Beifang Chen, Arthur L.B. Yang: A note on flow polynomials of graphs  

Beifang Chen, Richard Stanley: Orientations, lattice polytopes, and group arrangements II:  Modular and integral flow polynomials of graphs

«