 |
 |
| Tuesday 2 | ||
|---|---|---|
| 9h | Jim LAWRENCE (George Mason University, USA) | |
| Radon Catalogs, the Odd-Even Invariant, and Valuations | ||
| Many numerical invariants of oriented matroids correspond to valuations on the lattice of closed subcomplexes of the associated cell complex. The odd-even invariant and the entries of the Radon catalog are such invariants. We will study this connection by, among other things, describing bases for the space of valuations, whose elements are derived from the Radon catalog or from the odd-even invariants. | ||
| 9h45 | Hans-Jürgen BANDELT (Fachbereich Mathematik, Universität Hamburg) | |
| Geometry of lopsided sets | ||
| Lopsided sets were introduced by Jim Lawrence in 1983 to encompass the intersection patterns of convex sets with the hyperorthants in Euclidean n-space. Lopsided sets were then characterized as the subsets of the discrete n-cube (of ±1-sequences of length n) for which the intersections with the n-cube faces are either the entire faces or empty or non-symmetric (i.e., not closed under the antipodal maps of the respective faces). In the eighties and nineties, lopsided sets were rediscovered in various disguises and alternatively named “simple”, “ample”, “extremal for (reverse) Sauer” or “shattering-extremal”. Altogether we found more than two dozen equivalent descriptions of lopsidedness (Eur. J. Combin. 27, 2006, pp. 669–689); so, there would still be ample opportunity for future rediscoveries. The geometric realization of lopsided sets as cubihedra endowed with the intrinsic l1 metric yields the appropriate “orthoconvex” subsets of the n-space from which the lopsided sets are exactly retrieved as the sign vectors codifying the intersection patterns with the hyperorthants. Moreover, the ±1,0-valued barycenter maps of the maximal hypercube constituents of lopsided sets determine the geometric features of the associated cubihedra and can be characterized in terms of axioms which largely overlap the standard axiom set for covectors (faces) of oriented matroids. This naturally leads to a common generalization of lopsided sets and oriented matroids as “conditional oriented matroids” which can be regarded as certain complexes of oriented matroids. | ||
| (For the most part, joint work with Victor Chepoi, Andreas Dress, and Jack Koolen) | ||
| 11h | Kolja KNAUER (Technische Universität Berlin, Germany) | |
| Between partial cubes and oriented matroids | ||
| A graph is called a partial cube if it is an isometric subgraph of some hypercube. Many nice graphs are partial cubes, e.g., tope graphs of oriented matroids, graphs of lopsided sets, linear extension graphs of posets, diagrams of distributive lattices. Nevertheless the class of partial cubes seems to be too large to capture important features of these graphs. We introduce 'conditional oriented matroids', which may be regarded as complexes of oriented matroids. Tope graphs of conditional oriented matroids form a tighter generalization of the above examples. We present several properties and discuss nice open problems. | ||
| (Joint work with H.-J. Bandelt, V. Chepoi, M. Kovse, supported by ANR TEOMATRO) | ||
| 11h45 | Matjaz KOVSE (University of Leipzig, Germany) | |
| Tutte polynomials and topological representations of partial cubes | ||
| Partial cubes (isometric subgraphs of hypercubes) form a well studied class of graphs with nice metric properties.They appear in diverse areas, like: computer science, mathematical chemistry, mathematical biology, social sciences, psychology. In mathematics they appear, besides in graph theory and coùbinatorics, also in topology, algebra and computational geometry. Tope graphs of oriented matroids are examples of partial cubes. One of the fundamental results about oriented matroids is the topological representation theorem. Topological representation theorem for partial cubes will be discussed and topological representation theorem for planar partial cubes will be presented. Example of a partial cube which is not representable with pseudospheres will be also presented. Tutte polynomials of partial cubes, which generalize Tutte polynomials of hyperplane arrangements, as introduced by Ardila, will be also discussed. | ||
| (Joint work with Kolja Knauer, Martin Milanic, Ferdinando Cicalese. This work was supported in part by the Deutsche Forschungsgemeinschaft within the EUROCORES Programme EUROGIGA (project GReGAS) of the European Science Foundation.) | ||
| 14h30 | András RECSKI (Budapest University of Technology and Economics, Hungary) | |
| Tree decomposition, tree orientation and rigid frameworks | ||
| One can check in polynomial time if a graph with n vertices and 2n-2 edges can be decomposed into two trees. Similarly, one can check whether a sequence of n non-negative integers adding up to n-1 can be realized as the outdegree-sequence of a properly oriented tree of a given graph with n vertices. Both solutions require the 2-matroid-intersection algorithm. Motivated by a problem in the rigidity of bar-and-joint frameworks we formulate a kind of common generalization of these problems and conjecture that it is still polynomial time solvable. | ||
| (This work has been supported by the Hungarian Agency for National Development through the research grant TAMOP (contract no. 4.2.2.B-10/1(2010-0009)) | ||
| 15h15 | Antoine DEZA (McMaster University, Canada) | |
| A combinatorial approach to colourful simplicial depth | ||
| The colourful simplicial depth conjecture states that any point in the convex hull of each of $d+1$ sets, or colours, of $d+1$ points in general position in $R^d$ is contained in at least $d^2+1$ simplices with one vertex from each set. We verify the conjecture in dimension 4 and strengthen the known lower bounds in higher dimensions. These results are obtained using a combinatorial generalization of colourful point configurations called octahedral systems. We present properties of octahedral systems generalizing earlier results on colourful point configurations and exhibit an octahedral system which can not arise from a colourful point configuration. The number of octahedral systems is also given. | ||
| (Joint work with Frédéric Meunier and Pauline Sarrabezolles) | ||
| 16h30 | Federico ARDILA (San Francisco State University, USA) | |
| Matroids in tropical geometry | ||
| Each matroid has a polyhedral complex associated to it, called its Bergman complex. These objects play a prominent role in tropical geometry, since they are the tropical analog of linear spaces. I will describe this correspondence and discuss some recent results. The talk will not assume previous knowledge of tropical geometry. | ||
| 17h15 | Felipe RINCON (University of Warwick, U.K.) | |
| Tropical linear spaces and valuated matroids | ||
| Tropical geometry studies an algebraic variety by `tropicalizing' it into a combinatorially defined polyhedral complex. Much of the information about the original variety can be recovered from its tropicalization. In this talk I will show how tropicalized linear spaces are intimately related to valuated matroids and matroid polytopes, and I will explain some of the very nice combinatorics they satisfy. I will also present a similar picture for a more general class of matroids called Coxeter matroids. | ||
| Wednesday 3 | ||
| 8h45 | Komei FUKUDA (ETH Zurich, Switzerland) | |
| My personal memories of Michel and his work | ||
| 9h | Richard POLLACK (New York University, USA) | |
| Double Permutation Sequences and Arrangements of Planar Families of Convex Sets with Applications | ||
| We recall Permutation Sequences and Allowable Permutation Sequences and the Theorem that every Allowable permutation Sequence can be realized by an arrangement of pseudolines We (re)introduce Double Permutation Sequences, which provide a combinatorial encoding of arrangements of convex sets in the plane. We also recall the notion of a Topological Affine Plane and several (some new) of its properties. In particular the conjecture of Goodman-Pollack and proved by Habert-Pocchiola, that for every Allowable Double Permutation Sequence there is a universal Topological Affine Plane P (i.e. any finite arrangement of pseudolines is isomorphic to some arrangement of finitely many lines of P), and that every Allowable Double Permutation Sequence can be realized by an arrangement of simply connected sets and pseudoline double tangents to every pair of these sets. The following applications are then presented: 1 A new proof of the Edelsbrunner-Sharir Theorem: $n$ convex sets in the plane can admit at most $2n - 2$ geometric permutations and we proved the same via Double Permutation Sequences. 2 The Tverberg $(1, k)-$separation problem: In 1979 Tverberg asked, what is the smallest number $f_k$ such that for any family of $f_k$ mutually disjoint plane convex sets, one set can be separated from $k-$others and proved that $f_k$ is finite, 2a In 1980 Hope and Katchalski showed that $f_k < 12(k - 1)$. 2b In 2010 Mordechai Novick, using double permutation sequences, improved the "Katchalski-Hope" bound to $f_k <(7.2)(k - 1)$. | ||
| (Joint work with Raghavan Dhandipani, Jacob E. Goodman, Andreas Holmsen, Shakhar Smorodinsky, Rephael Wenger and Tudor Zamfirescu, supported in part by several NSF grants ) | ||
| 9h45 | Ricardo STRAUSZ (UNAM, Mexico) | |
| Applying the probabilistic method to Separoids theory | ||
| We will review a couple of applications of the probabilistic method to abstract convexity via the notion of separoids; one related to Tverberg's theorem, and the other to Erd\H os-Szekeres ``happy end'' theorem. | ||
| 11h | Csongor CSEHI (Budapest University of Technology and Economics, Hungary) | |
| The graphicity of the sum of graphic matroids | ||
| There is a conjecture that if the sum of graphic matroids is not graphic then it is nonbinary. Some special cases have been proved only, for example if several copies of the same graphic matroid are given. If there are two matroids and the first one can be drawn as a graph with two points, then I formulate an equivalent property for the other matroid for ensuring the graphicity of the sum. Hence the conjecture holds for this special case. | ||
| (This work has been supported by the Hungarian Agency for National Development through the research grant TAMOP (contract no. 4.2.2.B-10/1(2010-0009)) | ||
| 11h45 | Viet Hang NGUYEN (G-SCOP, Grenoble UJF, France) | |
| Inductive construction and decomposition of graded sparse graphs | ||
| Sparse graphs are extensively studied for their role in combinatorial rigidity theory. In this work, we consider graded sparse graphs--a generalization of sparse graphs where different types of edges satisfy different sparsity conditions. We provide an inductive construction and a decomposition into pseudoforests of these graphs. These results generalize the work of Fekete and Szeg\H{o} on the inductive construction of sparse graphs as well as the work of Streinu and Theran on the decomposition of sparse graphs, thus generalize the original work of Nash-Williams on the decomposition of graphs into forests. | ||
| (Joint work with Bill Jackson, Queen Mary University, London. Partially supported by the TEOMATRO grant ANR-10-BLAN 0207) | ||
| Thursday 4 | ||
| 9h | Louis BILLERA (Cornell University, USA) | |
| Unbalanced collections, weak maps and a problem in quantum physics | ||
| We describe the use of a theorem of Dean Lucas on weak maps to give bounds on the number of regions of a hyperplane arrangement arising in thermal field theory and in the theory of threshold functions. While these bounds are not new, the approach seems to be. The real question is whether the number of regions can be computed exactly. | ||
| 9h45 | Michel POCCHIOLA (Institut de Mathématiques de Jussieu, UPMC, Paris) | |
| Arrangements of double pseudolines living in non orientable surfaces | ||
| We show that an arrangement of double pseudolines lives in a sphere with one crosscap if and only if its subarrangements of size 2, 3 and 4 live in spheres with one crosscap. | ||
| 11h | Andreas HOLMSEN (KAIST, Republic of Korea) | |
| Realization spaces and Erd\H{o}s-Szekeres theorems for convex sets | ||
| We consider wiring diagrams where each pair of wires cross at most $m$ times. It turns out that these objects naturally encode what we call the combinatorial-type of an arrangement of compact convex sets in the plane. We will discuss this notion of combinatorial-type and show that it has many nice properties and applications: - It naturally extends the notion of the order-type of a point configuration in the plane and, more generally, acyclic oriented matroids. In particular every acyclic oriented matroid of rank 3 has a realization by convex sets. - It unifies various generalizations and conjectures of the classical Erd\"{o}s-Szekeres theorem. In particular the Erd\"{o}s-Szekeres constant for families of non-crossing convex sets and for acyclic oriented matroids are the same (which relates a conjecture of Goodman and Pollack to a conjecture of Bisztriczky and Fejes-Toth). Moreover we prove a conjecture of Pach and T'{o}th extending the previous results to more general arrangements of bodies. - The realization space of a given order-type is a contractible set, while restricting to configurations of convex k-gons we obtain a generalization of Mn\"{e}v's universality theorem. | ||
| (Joint work with Michael Dobbins and Alfredo Hubard) | ||
| 11h45 | Arnau PADROL (Universitat Politècnica de Catalunya) | |
| From Ehrhart theory to the discrepancy of oriented matroids | ||
| The degree of a point configuration is defined as the maximal codimension of its interior faces. This concept is motivated from a corresponding Ehrhart-theoretic notion for lattice polytopes. I will present some recent developements concerning point configurations whose degree is small with respect to the dimension of its affine span. These results have several interpretations in areas such as neighborly polytopes or Tverberg theory. | ||
| (Joint work with Benjamin Nill) | ||
| 14h30 | Jürgen BOKOWSKI (Technische Universität Darmstadt, Germany) | |
| Oriented Matroids and Configurations of Points and Lines | ||
| The theory of oriented matroids can help finding results in the theory of CONFIGURATIONS OF POINTS AND LINES, although in Grünbaum´s research monograph from 2009 with this title, he does not stress this aspect very much. The talk reports about applications of oriented matroid techniques that have solved open problems of the theory of configurations of points and lines. | ||
| (Joint work with Vincent Pilaud) | ||
| 15h15 | Hiroyuki MIYATA (Tohoku University, Japan) | |
| Complete Enumeration of Small Realizable Oriented Matroids | ||
| Enumeration of combinatorial types of point configurations and polytopes is a fundamental problem in combinatorial geometry. Although many studies have been done, most of them are for 2-dimensional and non-degenerate cases. Finschi and Fukuda (2002) published the first database of oriented matroids including degenerate (i.e., non-uniform) ones and of higher ranks. After that, large amount of work has been done in order to decide realizability of them. In this talk, we explain our recent work on algorithmic ways to classify oriented matroids in terms of realizability, which successfully complete the realizability classification of rank 4 oriented matroids with 8 elements, rank 3 oriented matroids with 9 elements and rank 6 oriented matroids with 9 elements. As an application, we determine all possible combinatorial types (including degenerate ones) of 3-dimensional configurations of 8 points, 2-dimensional configurations of 9 points, and 5-dimensional configurations of 9 points. We also determine all possible combinatorial types of 5-polytopes with 9 vertices. In addition, our method is successfully applied to many other problems such as enumeration of PLCP-orientations of the 4-cube (joint work with Komei Fukuda and Lorenz Klaus) recently. | ||
| (Joint work with Komei Fukuda and Sonoko Moriyama) | ||
| 16h30 | Hidefumi HIRAISHI (Graduate school of Information and Technology, University of Tokyo, Japan ) | |
| Minimal non-orientable matroids of rank $3$ | ||
| We report on our work on minimal non-orientable matroids of rank $3$. There are some well-known minimal non-orientable matroids of rank $3$. Among them, the Fano matroid and the MacLane matroid are unique minimal non-orientable matroids of rank $3$ with $7$ and $8$ elements,respectively. Ziegler showed in 1991 that there exists an infinite family of minimal non-orientable matroids of rank $3$ with $3n+2$ elements. We construct two new infinite families of minimal non-orientable matroids of rank $3$ with $3n$ and $3n+1$ elements. Our first infinite family with $3n$ elements starts from one of the two previously known minimal non-orientable matroids of rank $3$ with $9$ elements, which was discovered in 2012 by Y. Matsumoto et al. Our second infinite family with $3n+1$ elements starts from the Fano matroid. Hence together with Ziegler's infinite family, we now know that there exist minimal non-orientable matroids of rank $3$ for every number of elements. Additionally we examine representability of the two new infinite families, and show in particular that our first infinite family is not representable over any field of characteristic two. | ||
| (Joint work with Sonoko Moriyama.) | ||
| 17h15 | Carsten LANGE (Freie Universität Berlin, Germany) | |
| Counting invariants for realizations of associahedra | ||
| An n-dimensional associahedron is a simple convex polytope with vertex-edge graph isomorphic to the flip graph of triangulations of a planar convex (n+2)-gon. Generalizing a realization studied by J.-L. Loday, S. Shnider, J. Stasheff and S. Sternberg, a large family of realizations can be easily obtained by choosing a point in the complement of the braid arrangement and a Coxeter element of the corresponding symmetric group. This construction guarantees that the resulting normal fans are coarsenings of the brais arrangement and it can be shown that most of them are linearly non-isomorphic. Hence, the normal cone for each vertex of the associahedron is obtained by merging certain maximal cones of the braid arrangement. For a given Coxeter element, we will discuss the number of vertices of the associahedron where the normal cone consists of exactly k maximal cones of the braid arrangement. | ||
| 20h45 | Emeric GIOAN (CNRS, LIRMM, Université Montpellier 2, France) | |
| Michel's slides | ||
| 21h | Jorge RAMIREZ ALFONSIN (Université Montpellier 2, France) | |
| Michel's conjectures | ||
| Friday 5 | ||
| 9h | Joseph KUNG (University of North Texas, USA) | |
| The Tutte polynomial as a resultant force | ||
| Let $G$ be a matrix over a finite field $\mathbb{K}$ with column set $E.$ A flow $G$ is a row vector in the row space of $G,$ considered as a function on $E.$ A parcel is a subset of the set $\mathcal{F},$ defined by $\mathcal{F} = \{ (f,g): f,g:E \to \mathbb{K}, f - g \,\,\text{is a flow}\}.$ Parcels may be defined by a congruence condition -- an equation saying that an algebraical or combinatorial function equals a number modulo a fixed integer $n.$ In this case, $n$ parcels are defined, they partition $\mathcal{F},$ and the sum of their sizes, weighted by an appropriate root of unity, is an evaluation of a simple multiple of the Tutte polynomial at a point on a complex hyperbola. | ||
| 9h45 | Caroline KLIVANS (Brown University, USA) | |
| Cellular matroids | ||
| 11h | Luca MOCI (Institut de Mathématiques de Jussieu, Paris 7) | |
| Matroids over a ring | ||
| We introduce the notion of a matroid M over a commutative ring R, assigning to every subset of the ground set an R-module according to some axioms. When R is a field, we recover matroids. When R=Z (integers), and when R is a DVR, we get (structures which contain all the data of) quasi-arithmetic matroids, and valuated matroids, respectively. More generally, whenever R is a Dedekind domain, we extend all the usual properties and operations holding for matroids (e.g., duality), and we explicitly describe the structure of the matroids over R. Furthermore, we compute the Tutte-Grothendieck group of matroids over R. By specializing the class of a matroid over Z in the Tutte-Grothendieck group, we obtain the Tutte quasi-polynomial and the arithmetic Tutte polynomial, which have applications to toric arrangements, zonotopes, and graphs. | ||
| (Joint work with Alex Fink) | ||
| 11h45 | Nikolai MNEV (Steklov Mathematical Institute RAS, Russia) | |
| Local combinatorial formula for the Chern class of combinatorial $S^1$ bundles | ||
| We can identify triangulated oriented $S^1$-bundle on a simplicial complex with a decoration of the complex by necklaces. In terms of such decorations there is a canonical local combinatorial formula for Chern-Euler class and its powers, expressed as a kind of "expectation of parity" of the necklace. The formula can be conceptually attributed to Gelfand - Mac Pherson, M. Kontsevich, M. Kazarjan, A. Gaifullin and others, but it was never published in this simple form. We apply the theory to produce a toy - a triangulated oriented $S^1$-bundle canonically associated to a triangulation of oriented surface. The bundle has Chern-Euler number equal to the half of the number of triangles. The triangulated bundles has a property of minimality - they has minimal number of simplexes in the class of all triangulated $S^1$ - bundles with given Chern number on the oriented surface. | ||
| 14h30 | Emanuele DELUCCHI (University of Bremen, Germany) | |
| Foundations for a theory of phased matroids | ||
| We introduce "Phased matroids" as a combinatorial abstraction of linear dependency over the complex numbers that parallels the existing theories for general and real linear dependency (given by matroid and oriented matroid theory). Our theory shares much of the structural richness of oriented matroid theory, yet does not refrain from the occasional "twists and turns" - thereby shedding some new light on known aspects of matroid theory. We have a satisfactory duality theory and several cryptomorphic axiomatizations, including ``phirotopes'' as introduced by Below, Krummeck and Richter-Gebert. | ||
| (Joint with Laura Anderson) | ||
| 15h15 | Thomas ZASLAVSKY (Binghamton University (SUNY), USA) | |
| Phased Matroids from Gain Graphs | ||
| Phased matroids are a complex analog of oriented matroid. Gain graphs are graphs whose edges are invertibly labelled from a group. Gain graphs whose group is that of complex units naturally generate phased matroids which are analogous to graphic matroids. I will report on some aspects of this development. | ||
| (Joint work with Laura Anderson.) | ||
| 16h30 | Laura ANDERSON (Binghamton University, SUNY, USA) | |
| Realization spaces of phased matroids and the phased matroid Grassmannian | ||
| Phased matroids are matroids with extra structure. They model vector arrangements over $\mathbb C$ in the same way that oriented matroids model vector arrangements over $\mathbb R$, and many of the topological questions that arise with oriented matroids are at least as intriguing in the context of phased matroids. I'll discuss some recent unexpected results of my student Amanda Ruiz on realization spaces of phased matroids and some light these results shed on the relationship between complex Grassmannians and the corresponding "phased matroid Grassmannians". | ||
| 17h15 | Hiroshi HIRAI (University of Tokyo) | |
| Discrete Convexity and Polynomial Solvability in Minimum 0-extension Problems | ||
| The minimum 0-extension problem 0-Ext[G] on a graph G is: given a set V including the vertex set V(G) of G and a nonnegative cost function c defined on the set of all pairs of V, find a 0-extension d of G with <c, d> minimum, where a 0-extension is a metric d on V such that the restriction of d to V(G) coincides with the path metric of G and for all x in V there exists a vertex s in G with d(x,s) = 0. 0-Ext[G] includes a number of basic combinatorial optimization problems, such as minimum (s,t)-cut problem and multiway cut problem. Karzanov proved the polynomial solvability for a certain large class of modular graphs, and raised the question: What are the graphs G for which 0-Ext[G] can be solved in polynomial time? He also proved that 0-Ext[G] is NP-hard if G is not modular or not orientable (in a certain sense). In this paper, we prove the converse: if G is orientable and modular, then 0-Ext[G] can be solved in polynomial time. This completes the classification of the tractable graphs for the 0-extension problem. To prove our main result, we develop a theory of discrete convex functions on orientable modular graphs, analogous to discrete convex analysis by Murota, and utilize a recent result of Thapper and Zivny on Valued-CSP. | ||
| Saturday 6 | ||
| 9h | Zoltán SZIGETI (Ensimag, INP, Grenoble, France) | |
| Packing of arborescences with matroid constraints | ||
| We provide the directed counterpart of a slight extension of Katoh and Tanigawa's result on rooted-tree decompositions with matroid constraints. Our result characterizes digraphs having a packing of arborescences with matroid constraints. It is a proper extension of Edmonds' result on packing of spanning arborescences and implies -- using a general orientation result of Frank -- the above result of Katoh and Tanigawa. | ||
| (Joint work with Olivier Durand de Gevigney and Viet Hang Nguyen) | ||
| 9h45 | Jérémie CHALOPIN (LIF, Université Aix-Marseille, CNRS, France) | |
| A topological characterization of basis graphs of matroids | ||
| The basis graph of a matroid ${\mathcal M}$ is the graph whose vertices are the bases of ${\mathcal M}$ andedges are the pairs $A,B$ of bases such that $|A\Delta B| = 2$. Basis graphs of matroids have been characterized by Maurer (Matroid basis graphs I, JCTB 14, 1973, 216--240) as graphs satisfying some local conditions and a global metric condition. In his paper, Maurer conjectured that one can replace his global metric condition by the topological condition of simply connectedness of the triangle-square complex of the graph G (the triangle-square complex of $G$ is a 2-dimensional complex in which the $2$-cells are the triangles and the squares of $G$). We show that the conjecture is true if we strengthen the local conditions. | ||
| (Joint work with Victor Chepoi (LIF, Aix-Marseille Université) and Damian Osajda (Universtät Wien and Universytet Wroc{\l}awski)) | ||
| 11h | Kenjiro TAKAZAWA (RIMS, Kyoto Univ., Japan, and INP, Grenoble, France) | |
| Shortest Bibranchings and Valuated Matroid Intersection | ||
| For a digraph $D=(V,A)$ and a partition $\{S,T\}$ of $V$, an arc set $B \subseteq A$ is called an $S$-$T$ bibranching if each vertex in $T$ is reachable from $S$ and each vertex in $S$ reaches $T$ in the subgraph~$(V,B)$. Bibranchings commonly generalize bipartite edge covers and arborescences. A totally dual integral linear system determining the $S$-$T$ bibranching polytope is provided by Schrijver, and the shortest $S$-$T$ bibranching problem can be solved in polynomial time by the ellipsoid method or a faster combinatorial algorithm due to Keijsper and Pendavingh. The valuated matroid intersection problem, introduced by Murota, is a weighted generalization of the independent matching problem. By extending classical combinatorial algorithms for the weighted matroid intersection problem, the valuated matroid intersection problem can be solved with polynomially many value oracles In this talk, we show that the shortest $S$-$T$ bibranching problem is polynomially reducible to the valuated matroid intersection problem. This reduction suggests one answer to why the shortest $S$-$T$ bibranching problem is tractable, and implies new combinatorial algorithms. | ||
| 11h45 | Olivier DURAND DE GEVIGNEY (INP, Grenoble, France) | |
| Packing of Count Matroids Basis | ||
| We give a new proof to show that, in a graph, high connectivity is a sufficient condition for the existence of edge-disjoint basis of some count matroids. This approach implies two generalizations of the classical result of Lovász and Yemini stating that 6-vertex-connected graphs are rigid. Our result also has an application in graph orientation. | ||
| (Joint work with Joseph Cheriyan and Zoltán Szigeti, supported by ANR TEOMATRO ) | ||
|
|