9:30-10:00		Registration
Morning session
10:00-10:15	Zoltán Szigeti	Introduction
10:15-10: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 parity-related fundamental result concerning minimal T-joins is Seb’s lemma on conservative ±1-weightings. 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 root-edges can be treated with the help of a min-max theorem on covering crossing supermodular bi-set functions by digraphs.
10:45-11:15	Beth Novick	Location Functions on Finite Metric Spaces A median of a sequence π = x1,x2,…,xk of elements of a finite metric space (X,d) is an element x minimizing ∑ i=1kd(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:45-12:15	Michael Tarsi	The hunting of the snark "Snarks" refers to Non-three-edge-colorable cubic graphs (some say, also 4-cyclically 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, NP-Hard 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) Nowhere-Zero-Flows. Apparently, the "Circular-flow number" of a Snark G, Cf(G), provides a reasonable quantitative measure of its Snarkness: For a 3-edge-colorable 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, Circular-Nowhere-Zero-flow related, definitions, parameters, results, open problems and conjectures. Among those, the old (1992) Z6-connectivity Theorem of Jaeger, Linial, Payan and Tarsi, the recent (2013) celebrated Z3-Connectivity 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:15-12:35	Jean Fonlupt	Quelques souvenirs personnels
Buffet
Afternoon session
2:30-3:00	Joseph Cheriyan	Nash-Williams' Orientation Theorem and Extensions One of Nash-Williams' well-known results gives necessary and sufficient conditions for orienting the edges of a graph such that the resulting digraph is k-edge connected. The talk will address conjectures and extensions to vertex-connectivity requirements. The talk is based on joint work with Olivier Durand de Gevigney, Andres Ruiz-Vargas, Zoltan Szigeti, and Chenglong Zhou.
3:00-3: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 four-leaf subtrees, called quartets. There has been a recent interest in so-called '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 non-tree network is a 'level-1 network', that is an undirected graph whose circuits are vertex disjoint. Let X be a set of taxa. A tree or level-1 network N with leaf set X is said to be compatible with a quartet ab|cd, 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 level-1 network exists is NP-complete. 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 level-1 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:30-4: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 L-natural convex and the behavior of iterative auctions can be analized systematically in terms of L-convex function minimization algorithms in discrete convex analysis.
Coffee Break
4:30-5: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:00-5:30	Nicola Apollonio	A characterization of minimally unbalanced diamond-free 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 diamond-free graphs, namely, those diamond-free graphs whose clique-matrix is not balanced but whose proper subgraphs have a balanced clique-matrix. While the recognition problem of balanced matrices is now solved in full generality and the recognition for linear balanced matrices (namely, balanced clique-matrices of diamond-free 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 diamond-free graphs and other known combinatorial objects such as Dyck paths and Dyck words. This is joint work with Anna Galluccio.
5:30-6: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 polynomial-time using only Edmonds' blossom inequalities; it maintains half-integral 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.

Morning session
9:00-9: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 graph-TSP, and the s-t 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:30-10: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) > 2k2 - 1, then G contains a (k + 1)-connected induced subgraph H such that ∂(H) ⊊ V (H) and |∂(H)|≤ 2k2 - 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:00-10: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 non-edge. The weakest conjecture in the subject is the Clique Pair Conjecture: Every non-clique 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 well-known 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:00-11:30	Henning Bruhn	Structural parametrisations for boxicity Birthday presents are often put into 3-dimensional 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 d-dimensional axes-aligned boxes, provided d is large enough. The smallest such d is called the boxicity of the graph. Boxicity is a hard parameter: for non-trivial graph classes determining the boxicity is usually NP-complete. 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 3-dimensional boxes.
11:30-12:00	András Sebő	Overripe Problem Session
Buffet
Afternoon session
2:00-2: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 Erdos-Hajnal conjecture will also be discussed. Joint work with Aurélie Lagoutte and Nicolas Bousquet.
2:30-3: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) G0 = (V,E0), 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∈Ec(uv), given also costs c(uv) ≥ 0 for every pair u,v ∈ V. In the degree-specified 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 G0 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 degree-specified version by a splitting-off theorem. This splitting-off theorem in turn provides the solution for the minimum cost version in the case when c is node-induced, 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 G0 is the empty graph. This includes the Terminal Backup Problem (r ≡ 1) and the Maximum-Weight b-matching 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 so-called 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 edge-disjoint T-paths. I hope our variant of this theorem will be of interest for András Sebő, too, who worked on packing T-paths together with Laci Szegő. This is joint work with Yusuke Kobayashi and Tatsuya Matsuoka.
3:00-3: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 Ph-D has been for my today researches in computational biology, and conversely.
Coffee Break	Birthday Cake
4:00-4:30	Guyslain Naves	A fresh view on Okamura-Seymour's theorem Okamura-Seymour theorem states: given an instance of the edge-disjoint 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 Okamura-Seymour instance of the edge-disjoint paths problem can be solved using two simple operations : splitting-off and unknotting. Then I will make a connection between Okamura-Seymour theorem and isometric embedding of convex surfaces into L_1.
4:30-5:00	Mouna Sadli	On the Node Demand Problem For n > 10 an nth 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 H-admissible 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 H-admissible edge-disjoint 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.