Thursday 24th April
9:3010:00
  Registration 
Morning session
  
10:0010:15
 Zoltán Szigeti  Introduction 
10:1510:45
 András Frank  On parity and submodularity Parity and submodularity are two major aspects of combinatorial optimization. In
this talk, I discuss two unrelated results: an old lemma from parity and a recent
application of submodularity. A parityrelated fundamental result concerning
minimal Tjoins is Seb’s lemma on conservative ±1weightings. Mathematical
Reviews writes about this result as follows.
One of the lasting contributions of this paper may be its identification of a disarmingly simple property of bipartite graphs as a source of the theory.
I recall the birth of Seb’s lemma and briefly overview how I teach it in these
days in a regular course. In the second part, as a recent application of
submodularity, it will be shown that the problem of finding k disjoint spanning
arborescences of a given root with specified number of rootedges can be treated
with the help of a minmax theorem on covering crossing supermodular biset
functions by digraphs.

10:4511:15  Beth Novick  Location Functions on Finite Metric Spaces
A median of a sequence π = x_{1},x_{2},…,x_{k} of elements of a finite metric space (X,d) is an
element x minimizing ∑
_{i=1}^{k}d(x,x_{
i}). The median function M is defined on the set of all
finite sequences on X by M(π) = {x : x is a median of π}. A median graph is a graph for
which every profile of length 3 has a unique median. Median graphs have been well
studied, possess a beautiful structure and arise in many arenas, including ternary
algebra, ordered sets and discrete distributed lattices. Trees and hypercubes are key
examples of median graphs.
Recently Mulder and Novick, 2013, settled a question originally posed in 1994, by
McMorris, Mulder and Roberts, by characterizing the median function on median graphs.
Only three surprisingly simple axioms were used: Anonymity (A), Betweenness (B) and
Consistency (C). Indeed, these three axioms hold for median functions on every metric
space. Natural questions arise:
 Are (A), (B) and (C) independent?
 What is the relationship between this ‘ABC Theorem’ and an earlier less
intuitively appealing characterization, due to McMorris, Mulder and Powers.
 For which metric spaces do (A), (B) and (C) characterize the median
function?
 For a class of graphs, , what functions satisfy (A), (B) and (C) – what other
axioms are needed?
We settle the first two questions and offer preliminary remarks and conjectures for
the latter two.

Coffee Break
  
11:4512:15
 Michael Tarsi  The hunting of the snark
"Snarks" refers to Nonthreeedgecolorable cubic graphs (some say, also 4cyclically edge connected), so named by Martin Gardner on 1976, to emphasize the rarity and evasive nature of these mysterious creatures.
Although indeed rare in some sense (almost all cubic graphs are Hamiltonian), Snarks are not really hard to "hunt", not anymore. Many infinite families of Snarks are now known; thousands individual Snarks were explicitly listed and studied and their number is constantly growing.
For one, being a Snark is, in general, NPHard to detect, which does suggest certain structural richness and elusiveness.
Back on 1998 we (Goddyn, Tarsi and Zhang) introduced the notion of Fractional (a.k.a. Circular) NowhereZeroFlows.
Apparently, the "Circularflow number" of a Snark G, Cf(G), provides a reasonable quantitative measure of its Snarkness:
For a 3edgecolorable cubic graph G, Cf(G)=4, and recently (2011), Lukot'ka and Skoviera constructed an infinite set of
Snarks G with Cf(G)= q, for every rational 4<q≤5.
I will present various old and new, CircularNowhereZeroflow
related, definitions, parameters, results, open problems and conjectures.
Among those, the old (1992) Z6connectivity Theorem of Jaeger, Linial, Payan and Tarsi,
the recent (2013) celebrated Z3Connectivity Theorem of Thomassen and Zhang and a recent conjecture of Linial and Ban.
I will show how these, and similar, results / conjectures integrate into an ongoing quest for the most elusive Snarks,
Snarkier and more Frumious than ever before.

12:1512:35  Jean Fonlupt  Quelques souvenirs personnels 
Buffet

Afternoon session

2:303:00
 Joseph Cheriyan 
NashWilliams' Orientation Theorem and Extensions
One of NashWilliams' wellknown results gives necessary and sufficient conditions for orienting the edges of a graph such that the resulting digraph is kedge connected. The talk will address conjectures and extensions to vertexconnectivity requirements.
The talk is based on joint work with Olivier Durand de Gevigney, Andres RuizVargas, Zoltan Szigeti, and Chenglong Zhou.

3:003:30
 Judith Keijsper 
The 'ring of life'
In phylogenetics, a tree, with leaves labeled by living species, is traditionally used as a model for evolution: 'the tree of life'.
One approach to construct a phylogenetic tree is from information on its fourleaf subtrees, called quartets.
There has been a recent interest in socalled 'phylogenetic networks' to model evolution in the presence of exchanges of genetic material
between coexisting species, or to display conflicts in phylogenetic trees that may correspond to such exchanges.
A simple kind of nontree network is a 'level1 network', that is an undirected graph whose circuits are vertex disjoint.
Let X be a set of taxa. A tree or level1 network N with leaf set X is said to be compatible with a quartet abcd, where a,b,c,d are from X, if N contains two vertex disjoint paths, one from a to b and one from c to d.
Given an arbitrary set of quartets, the decision problem whether a compatible tree, or level1 network exists is NPcomplete.
A set of quartets is called dense if it contains a quartet on every subset of four taxa. It is not difficult to see that a tree can be reconstructed
in polynomial time from a dense set of quartets.
The question was raised if a level1 network can be reconstructed from a dense set of quartets in polynomial time.
The problem at the core of this question is to construct a cyclic ordering of the taxa, so a circuit graph, compatible with a given dense quartet set.
We propose a polynomial time algorithm for this problem by translating quartets to linear equations over GF(2).
Solving the problem thus becomes a matter of Gaussian elimination over GF(2).
Joint work with Rudi Pendavingh.

3:304:00
 Kazuo Murota  Auction Theory and Discrete Convex Analysis
We discuss iterative auctions in the setting where there are multiple differentiated items in multiple units and each bidder has a gross substitutes valuation. We indicate a close connection between iterative auctions and discrete convex analysis. In particular, it is pointed out that the Liapunouv function is an Lnatural convex and the behavior of iterative auctions can be analized systematically
in terms of Lconvex function minimization algorithms in discrete convex analysis.

Coffee Break

4:305:00
 Antoine Deza 
Combinatorial approaches to the colourful simplicial depth
We present recent results and open questions dealing with a generalization of linear programming introduced
by Bárány and Onn in 1997, and the associated generalization of the Carathéodory's Theorem proven by
Bárány in 1982. In particular, we present recent generalizations of the Colourful Carathéodory Theorem due
to Arocha et al. and Holmsen et al. and our strengthening of these. We discuss a combinatorial approach
which led to the recent determination by Sarrabezolles of a tight lower bound for the colourful simplicial depth
in any dimension and generalizing earlier results due to Bárány and Matoušek, and Stephen and Thomas.
Based on joint works with Frédéric Meunier (ENPC Paris) and Pauline Sarrabezolles (ENPC Paris).

5:005:30
 Nicola Apollonio  A characterization of minimally unbalanced diamondfree graphs by forbidden
subgraphs
After having discussed some concrete "covering", "packing", "recognition"
and "search" problems I had to cope with together with András in the
very beginning of my Postdoc in Grenoble, I will present a forbidden subgraphs
characterization of minimally unbalanced diamondfree graphs, namely, those
diamondfree graphs whose cliquematrix is not balanced but whose proper
subgraphs have a balanced cliquematrix. While the recognition problem of
balanced matrices is now solved in full generality and the recognition for
linear balanced matrices (namely, balanced cliquematrices of diamondfree
graphs) was solved in a series of papers by Conforti and Rao more than twenty
years ago, no such a characterization is known not even in proper subclasses.
Surprisingly enough, we find unexpected relationships between minimally
unbalanced diamondfree graphs and other known combinatorial objects such as
Dyck paths and Dyck words.
This is joint work with Anna Galluccio.

5:306:00
 László Végh  The cutting plane method is polynomial for perfect matchings
The cutting plane approach to optimal matchings has been discussed by several authors over the past decades and its convergence has been an open question. We give a cutting plane algorithm that converges in polynomialtime using only Edmonds' blossom inequalities; it maintains halfintegral intermediate LP solutions supported by a disjoint union of odd cycles and edges. Our main insight is a method to retain only a subset of the previously added cutting planes based on their dual values. This allows us to quickly find violated blossom inequalities and argue convergence by tracking the number of odd cycles in the support of intermediate solutions.
This is joint work with Karthekeyan Chandrasekaran and Santosh Vempala.

Friday 25th April
Morning session

9:009:30
 Jens Vygen  Approximation algorithms for the traveling salesman: recent advances and future directions
35 years after Christofides' algorithm, this topic has received again a lot of interest recently.
Since 2010, different approximation algorithms have been proposed for the asymmetric TSP,
the graphTSP, and the st path TSP. However, we still do not know the integrality ratios
and even less the approximability, and we have still not beaten Christofides.
What could be the next steps?

9:3010:00  Nicolas Trotignon  Isolating highly connected induced subgraphs When G is a graph, we denote by δ(G) the minimum degree of G. If H is an
induced subgraph of G, then ∂(H) is the set of vertices of H that have
neighbors outside of H. We prove the following theorem.
Let k be a positive integer, and G be a graph. If δ(G) > 2k^{2}  1, then G
contains a (k + 1)connected induced subgraph H such that ∂(H) ⊊ V (H) and
∂(H)≤ 2k^{2}  1.
This may be seen as a generalization of a classical result of Mader.
We will try to convince the audience that this theorem is meaningful in
structural graph theory. We will discuss several variants, and for each
of them how the bounds can be improved. We will see how to use our
theorem to prove that gluing graphs with bounded chromatic number
along a fixed number of vertices keeps the chromatic number bounded.
This is joint work with Irena Penev and Stéphan Thomassé.

10:0010:30
 Gábor Bacsó  Old and young – perfect graphs and their cliques Though the Perfect Graph Conjecture has become a theorem, many amazing
open problems remained in the area. We discuss only two of them in the talk.
A(n arbitrary) graph is uniquely colourable if there is only one partition of the
vertex set yielding a minimum (proper) vertex colouring. Denoting the maximum
size of a clique in G by ω(G) = ω, a clique pair is a subgraph having ω + 1
vertices and exactly one nonedge. The weakest conjecture in the subject is the
Clique Pair Conjecture: Every nonclique uniquely colourable perfect graph has a
clique pair.
Dropping the condition of perfectness, the statement is not true even for ω(G) = 3.
The other group of problem is more familiar and popular nowadays. The following
concepts are wellknown but we define them here. Let (G) be the hypergraph on V (G),
constructed from the vertex sets, spanning a maximal clique of (an arbitrary) G. The
clique chromatic number χ_{C}(G) is the (traditional) chromatic number of (G).
Anonymous Conjecture: There exists a constant c such that χ_{C}(G) ≤ c for every
perfect graph G.
For general graphs this is false, similarly as above. In the Anonymous Conjecture, even
c = 3 is possible.
I hope I will have enough time to tell also about the clique chromatic number of line
graphs.
You conjecture that we were working together with András on the subjects above? –
This conjecture is true. 
Coffee Break

11:0011:30  Henning Bruhn 
Structural parametrisations for boxicity
Birthday presents are often put into 3dimensional boxes. While higher dimensional boxes seem to be of less use for presents, they may be employed to represent a graph. Indeed, as Roberts observed in 1969, any graph is the intersection graph of ddimensional axesaligned boxes, provided d is large enough. The smallest such d is called the boxicity of the graph.
Boxicity is a hard parameter: for nontrivial graph classes determining the boxicity is usually NPcomplete. In the talk, which is based on joint work with M. Chopin, F. Joos and O. Schaudt, I will discuss the boxicity problem from an FPT point of view. I will also give an application of 3dimensional boxes.

11:3012:00  András Sebő 
Overripe Problem Session 
Buffet

Afternoon session

2:002:30
 Stéphan Thomassé  Separating Cliques from Stable Sets
Extended formulations for the stable set polytope of perfect
graphs would imply in particular that a polynomial number of cuts can always
separate all pairs of (disjoint) cliques and stable sets in perfect graphs.
The nice property could even be true for general graphs, but is still open
even for perfect graphs.
I will show here that the property holds in the class of graphs avoiding an induced
path, and its complement. A link with the ErdosHajnal conjecture will also be
discussed.
Joint work with Aurélie Lagoutte and Nicolas Bousquet.

2:303:00  Attila Bernáth 
The Generalized Terminal Backup Problem
We consider the following network design problem, that we call the Generalized
Terminal Backup Problem. Given a graph (or a hypergraph) G_{0} = (V,E_{0}), a set of
(at least 2) terminals T ⊆ V and a requirement r(t) for every t ∈ T, find a multigraph
G = (V,E) such that λ_{G0+G}(t,T t) ≥ r(t) for any t ∈ T. In the minimum cost version
the objective is to find G minimizing the total cost c(E) = ∑
_{uv∈E}c(uv), given also costs
c(uv) ≥ 0 for every pair u,v ∈ V. In the degreespecified version the question is
to decide whether such a G exists, satisfying that the number of edges is a
prescribed value g(v) at each node v ∈ V . The Terminal Backup Problem is
the special case where G_{0} is the empty graph and r(t) = 1 for every terminal
t ∈ T. We solve the Generalized Terminal Backup Problem in the following two
cases.
In the first case we start with the minimum cost version for c ≡ 1, which helps
solving the degreespecified version by a splittingoff theorem. This splittingoff
theorem in turn provides the solution for the minimum cost version in the case
when c is nodeinduced, that is c(uv) = w(u) + w(v) for some node weights
w : V → ℝ_{+}.
In the second solved case we turn to the general minimum cost version, and we
are able to solve it when G_{0} is the empty graph. This includes the Terminal
Backup Problem (r ≡ 1) and the MaximumWeight bmatching Problem
(T = V ). The solution depends on an interesting new variant of a theorem of
Lovász and Cherkassky, and on the solution of the socalled Simplex Matching
problem.
Our algorithms run in strongly polynomial time for both problems. This research was
initiated by a question from András Frank. He was motivated by the theorem of Lovász
and Cherkassky on edgedisjoint Tpaths. I hope our variant of this theorem will be of
interest for András Sebő, too, who worked on packing Tpaths together with Laci Szegő.
This is joint work with Yusuke Kobayashi and Tatsuya Matsuoka.

3:003:30
 Eric Tannier  The binary matroid of genome arrangements
In this talk genomes are circular orderings of oriented genes, that is, for comparison purposes and evolutionary studies, signed permutations. Following F. Jaeger we explore the properties of the adjacency matroid of the circle graph drawn from a circular signed permutation by joining consecutive numbers with chords. In particular we prove that an inversion on the signed permutation, which is the most common mutation of genome arrangements, induces, under certain conditions, a matroid minor operation. In consequence an evolutionary distance may be computed as the rank of the binary matroid. The purpose of these results is to show to Andras how useful
the study of binary matroids during my PhD has been for my today researches in computational biology, and conversely.

Coffee Break
 Birthday Cake 
4:004:30
 Guyslain Naves  A fresh view on OkamuraSeymour's theorem
OkamuraSeymour theorem states:
given an instance of the edgedisjoint paths problem in a planar graph with
all the terminals on the boundary of the outer face,
this instance has a solution if and only if the cut condition is satisfied.
I will give a proof of this classical theorem, and show that any
OkamuraSeymour instance of the edgedisjoint paths problem can be solved
using two simple operations : splittingoff and unknotting. Then I will
make a connection between OkamuraSeymour theorem and isometric embedding
of convex surfaces into L_1.

4:305:00
 Mouna Sadli  On the Node Demand Problem For n > 10 an n^{th} birthday is definitely a great opportunity to relate old memories.
This talk is an overview of some of these memories about the Node Demand
Problem.
Let G = (V,E) and H = (T,F), where T ⊆ V , be two undirected graphs. The graph G
is called a supply graph, the elements of T are terminals, and the graph H is a demand
graph. A path of G is Hadmissible if it connects two terminals s,t such that st ∈ F.
Given m ∈ ℤ_{+}^{T } The node demand demand problem (G,H,m) is the following question :
Is there a system of Hadmissible edgedisjoint paths of G such that each terminal t is
the end node of precisely m(t) paths ? If the answer is yes, the NDP is said to be feasible.
In this talk we recall some of the NDP feasibility results and discuss some ”nice”
conjectures about the feasibility polytope.

