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
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.
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
All lectures will take
place in S6, 2^{nd} floor, KAM, Malostranské nám. 25 unless otherwise indicated.
October |
November | December |
09.10 Thursday | 03.11 Monday | 04.12 Thursday |
12:20 – 14:00 M. DeVos | 14:00 – 15:40 M. Pinsker | 14:00 – 15:40 A. Goodall (VKK I) |
14:30 – 16:00 M. DeVos | ||
06.11 Thursday | 11.12 Thursday | |
10.10 Friday | 12:20 – 14:00 M. Pinsker | 14:00 – 15:40 A. Goodall (VKK I) |
14:00 – 15:40 J. Makowsky | 14:10 – 15:40 M. Pinsker | |
18.12 Thursday | ||
13.10 Monday | 10.11 Monday | NO LECTURE |
14:00 – 15:40 M. DeVos |
14:00 – 15:40 L. Zdeborová | |
16.10 Thursday | 11.11 Tuesday (in S7, 2^{nd} floor) | January |
12:20 – 14:00 J. Makowsky | 14:00 – 15:40 L. Zdeborová | |
14:10 – 15:40 J. Makowsky | 8.1 Thursday | |
13.11 Thursday | 14:00 – 15:40 A. Goodall (VKK I) | |
20.10 Monday | 14:00 – 15:40 J. Nešetřil (VKK I) | |
14:00 – 15:40 G. Kun | ||
20.11 Thursday | ||
23.10 Thursday | 12:20 – 14:00 L. Zdeborová | |
12:20 – 14:00 M. Pinsker | ||
14:00
– 15:30 G. Kun |
27.11 Thursday | |
14:00 – 15:40 A. Goodall (VKK I) | ||
30.10 Thursday | ||
14:00 – 15:40 A. Goodall (VKK I) |
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.
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
Jian Ding, Allan Sly, Nike Sun: Proof of the satisfiability conjecture for large k: arXiV paper