Meeting in honor of András Sebő

April 24-25, 2014, Grenoble, France

Schedule

Thursday 24th April

 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 SpacesA 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

Friday 25th April