colloquium

Archive of posts with tag 'colloquium'

  • (Colloquium) András Sebő, Classical tools and recent advances in combinatorial optimization

    FYI: Colloquium of Dept. of Mathematical Sciences.

    Classical tools and recent advances in combinatorial optimization
    András Sebő
    CNRS, Laboratoire G-SCOP, Université Grenoble-Alpes, France
    2016/04/28 Thu 4:15PM-5:15PM (Room 1501, Bldg. E6-1)
    Combinatorial optimization has recently discovered new usages of probability theory, information theory, algebra, semidefinit programming, etc. This allows addressing the problems arising in new application areas such as the management of very large networks, which require new tools. A new layer of results make use of several classical methods at the same time, in new ways, combined with newly developed arguments.
    After a brief panorama of this evolution, I would like to show the new place of the best-known, classical combinatorial optimization tools in this jungle: matroids, matchings, elementary probabilities, polyhedra, linear programming.
    More concretely, I try to demonstrate on the example of the Travelling Salesman Problem, how strong meta-methods may predict possibilities, and then be replaced by better suited elementary methods. The pillars of combinatorial optimization such as matroid intersection, matchings, T-joins, graph connectivity, used in parallel with elements of freshmen’s probabilities, and linear programming, appropriately merged with newly developed ideas tailored for the problems, may not only replace difficult generic methods, but essentially improve the results. I would like to show how this has happened with various versions of the TSP problem in the past years (see results of Gharan, Saberi, Singh, Mömke and Svensson, and several recent results of Anke van Zuylen, Jens Vygen and the speaker), essentially improving the approximation ratios of algorithms.
    Tags:

  • [Colloquium] Jinwoo Shin (신진우), Belief Propagation for Combinatorial Optimization
    (FYI: Colloquium)
    Belief Propagation for Combinatorial Optimization
    Jinwoo Shin (신진우)
    Department of Electrical Engineering, KAIST
    2015/11/19 4:15PM-5:15PM (Room 1501, Bldg. E6)
    Belief propagation (BP) is a popular message-passing algorithm for computing a maximum-a-posteriori assignment in a graphical model. It has been shown that BP can solve a few classes of Linear Programming (LP) formulations to combinatorial optimization problems including maximum weight matching and shortest path. However, it has been not clear what extent these results can be generalized to. In this talk, I first present a generic criteria that BP converges to the optimal solution of given LP, and show that it is satisfied in LP formulations associated to many classical combinatorial optimization problems including maximum weight perfect matching, shortest path, network flow, traveling salesman, cycle packing and vertex cover. Using the criteria, we also construct the exact distributed algorithm, called Blossom-BP, solving the maximum weight matching problem over arbitrary graphs. In essence, Blossom-BP offers a distributed version of the celebrated Blossom algorithm (Edmonds 1965) jumping at once over many sub-steps of the Blossom-V (most recent implementation of the Blossom algorithm due to Kolmogorov, 2011). Finally, I report the empirical performance of BP for solving large-scale combinatorial optimization problems. This talk is based on a series of joint works with Sungsoo Ahn (KAIST), Michael Chertkov (LANL), Inho Cho (KAIST), Dongsu Han (KAIST) and Sejun Park (KAIST).
    Tags:

  • [Colloquium] Choongbum Lee (이중범), Ramsey numbers of graphs
    Ramsey numbers of graphs
    Choongbum Lee
    Department of Mathematics, UCSD, San Diego, CA, USA
    2015/09/10 Thu 4:15PM-5:15PM
    The Ramsey number of a graph G is the minimum integer n for which every edge coloring of the complete graph on n vertices with two colors admits a monochromatic copy of G. It was first introduced in 1930 by Ramsey, who proved that the Ramsey number of complete graphs are finite, and applied it to a problem of formal logic. This fundamental result gave birth to the subfield of Combinatorics referred to as Ramsey theory which informally can be described as the study of problems that can be grouped under the common theme that “Every large system contains a large well-organized subsystem.”
    In this talk, I will review the history of Ramsey numbers of graphs and discuss recent developments.
    Tags:

  • [Colloquium] Jang Soo Kim, Combinatorics of orthogonal polynomials
    Combinatorics of orthogonal polynomials
    Jang Soo Kim (김장수)
    Department of Mathematics, Sungkyunkwan University, Suwon
    2015/4/9 Thu 4:30PM-5:30PM (E6, Room 1501)
    Orthogonal polynomials are a family of polynomials which are orthogonal with respect to certain inner product. The n-th moment of orthogonal polynomials is an important quantity, which is given as an integral. In 1983 Viennot found a combinatorial expression for moments using lattice paths. In this talk we will compute the moments of several important orthogonal polynomials using Viennot’s theory. We will also see their connections with continued fractions, matchings, set partitions, and permutations.
    Tags:

  • (Colloquium) Matt DeVos, On the structure of very small product sets

    FYI (Colloquium)

    On the structure of very small product sets
    Matt DeVos
    Simon Fraser University, Canada
    2014/09/25 Thursday 4:30PM – 5:30PM
    Room 1501

    (SLIDE)

    Let A and B be finite nonempty subsets of a multiplicative group G, and consider the product set AB = { ab | a in A and b in B }. When |G| is prime, a famous theorem of Cauchy and Davenport asserts that |AB| is at least the minimum of {|G|, |A| + |B| – 1}. This lower bound was refined by Vosper, who characterized all pairs (A,B) in such a group for which |AB| < |A| + |B|. Kneser generalized the Cauchy-Davenport theorem by providing a natural lower bound on |AB| which holds in every abelian group. Shortly afterward, Kemperman determined the structure of those pairs (A,B) with |AB| < |A| + |B| in abelian groups. Here we present a further generalization of these results to arbitrary groups. Namely we generalize Kneser’s Theorem, and we determine the structure of those pairs with |AB| < |A| + |B| in arbitrary groups.
    Tags:

  • KAIST Graph Theory Day 2012
    KAIST Graph Theory Day 2012
    2012/12/13 Thursday (Room: 3433, Building E6-1)

    List of speakers

    • 11AM-12PM Tomáš Kaiser (University of West Bohemia, Czech Republic) : Applications of the matroid-complex intersection theorem
    • 1:30PM-2:30PM Paul Seymour (Princeton University, USA) : Graphs, Tournaments, Colouring and Containment
    • 2:45PM-3:45PM  Maria Chudnovsky (Columbia University, USA) : Excluding paths and antipaths
    • 4:30PM-5:30PM Daniel Kráľ (University of Warwick, UK) : Quasirandomness and property testing of permutations (Colloquium)
    Applications of the matroid-complex intersection theorems
    Tomáš Kaiser
    The Matroid intersection theorem of Edmonds gives a formula for the maximum size of a common independent set in two matroids on the same ground set. Aharoni and Berger generalized this theorem to the `topological’ setting where one of the matroids is replaced by an arbitrary simplicial complex. I will present two applications of this result to graph-theoretical problems. The first application is related to the existence of spanning 2-walks in tough graphs, the other one is more recent and gives a bound on the fractional arboricity of a graph G ensuring that G can be covered by k forests and a matching. In both cases, slightly better results can be obtained by other methods, but there seems to be room for improvement on the topological side as well.
    Graphs, tournaments, colouring and containment
    Paul Seymour
    Some tournaments H are heroes; they have the property that all tournaments not containing H as a subtournament have bounded chromatic number (colouring a tournament means partitioning its vertex-set into transitive subsets). In joint work with eight authors, we found all heroes explicitly. That was great fun, and it would be nice to find an analogue for graphs instead of tournaments.
    The problem is too trivial for graphs, if we only exclude one graph H; but it becomes fun again if we exclude a finite set of graphs. The Gyarfas-Sumner conjecture says that if we exclude a forest and a clique then chromatic number is bounded. So what other combinations of excluded subgraphs will give bounded chromatic (or cochromatic) number? It turns out (assuming the Gyarfas-Sumner conjecture) that for any finite set S of graphs, the graphs not containing any member of S all have bounded cochromatic number if and only if S contains a complete multipartite graph, the complement of a complete multipartite graph, a forest, and the complement of a forest.
    Proving this led us to the following: for every complete multipartite graph H, and every disjoint union of cliques J, there is a number n with the following property. For every graph G, if G contains neither of H,J as an induced subgraph, then V(G) can be partitioned into two sets such that the first contains no n-vertex clique and the second no n-vertex stable set.
    In turn, this led us (with Alex Scott) to the following stronger result. Let H be the disjoint union of H_1,H_2, and let J be obtained from the disjoint union of J_1,J_2 by making every vertex of J_1 adjacent to every vertex of J_2. Then there is a number n such that for every graph G containing neither of H,J as an induced subgraph, V(G) can be partitioned into n sets such that for each of them, say X, one of H_1,H_2,J_1,J_2 is not contained in G|X.
    How about a tournament analogue of this? It exists, and the same (short) proof works; and this leads to a short proof of the most difficult result of the heroes paper that we started with.
    There are a number of other related results and open questions. Joint work with Maria Chudnovsky.
    Excluding paths and antipaths
    Maria Chudnovsky
    The Erdos-Hajnal conjecture states that for every graph H, there exists a constant delta(H)>0, such that every n-vertex graph with no induced subgraph isomorphic to H contains a clique or a stable set of size at least n^delta(H). This conjecture is still open. We consider a variant of the conjecture, where instead of excluding a single graph H as an induced subgraph, a family of graphs is excluded. We prove this modified conjecture for the case when the five-edge path and its complement are excluded. Our second result is an asymmetric version of this: we prove that for every graph G such that G contains no induced six-edge path, and the complement of G contains no induced four-edge path, G contains a polynomial-size clique or stable set. This is joint work with Paul Seymour.
    Quasirandomness and property testing of permutations
    Daniel Kráľ
    A systematic study of large combinatorial objects has recently led to discovering many connections between discrete mathematics and analysis. In this talk, we explore the analytic view of large permutations. We associate every sequence of permutations with a measure on a unit square and show the following: if the density of every 4-element subpermutations in a permutation p is 1/4!+o(1), then the density of every k-element subpermutation is 1/k!+o(1). This solves a question of Graham whether quasirandomness of a permutation is captured by densities of its 4-element subpermutations. At the end of the talk, we present a result related to an area of computer science called property testing. A property tester is an algorithm which determines (with a small error probability) properties of a large input object based on a small sample of it. Specifically, we prove a conjecture of Hoppen, Kohayakawa, Moreira and Sampaio asserting that hereditary properties of permutations are testatble with respect to the so-called Kendal’s tau distance.
    The results in this talk were obtained jointly with Tereza Klimosova or Oleg Pikhurko.
    Tags:

  • (Colloquium) Jaroslav Nešetřil, Limits of Structures and Sparse-Dense Dichotomy

    FYI (Department Colloquium)

    Limits of Structures and Sparse-Dense Dichotomy
    Jaroslav Nešetřil
    Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague
    2012/11/1 Thu 4:30PM-5:30PM (Room 1501, Bldg. E6)
    Based on the newly understood dichotomy of sparse and dense structures, we provide the general framework for study of structural (mostly graph) limits. Our approach uses both model theoretic and analytic tools and uses structural theory of bounded expansion classes.
    Tags:

  • (Colloquium) Satoru Iwata, Submodular Optimization and Approximation Algorithms
    Submodular Optimization and Approximation Algorithms
    Satoru Iwata
    RIMS, Kyoto University, Kyoto, Japan
    2011/11/10 Thu 4PM-5PM
    Submodular functions are discrete analogues of convex functions. Examples include cut capacity functions, matroid rank functions, and entropy functions. Submodular functions can be minimized in polynomial time, which provides a fairly general framework of efficiently solvable combinatorial optimization problems. In contrast, the maximization problems are NP-hard and several approximation algorithms have been developed so far.
    In this talk, I will review the above results in submodular optimization and present recent approximation algorithms for combinatorial optimization problems described in terms of submodular functions.
    Tags:

  • (Colloquium) Xuding Zhu (朱緒鼎), Circular Colouring of Graphs
    FYI (Department Colloquium)
    Circular Colouring of Graphs
    Xuding Zhu (朱緒鼎)
    Institute of Mathematics, Zhejiang Normal University, Jinhua, China
    2011/4/21 Thu 4:30PM-5:30PM (Room 1501)

    Vertex colouring of graphs is an active research area in graph theory. It has wide applications to practical problems and also has many theoretically deep results and challenging problems. Circular colouring of graphs is a refinement of the conventional vertex colouring of graphs. It has atttract a lot of attention in the past twenty years, and becomes an important branch of chromatic graph theory, with many exciting results and new techniques. This talk gives a survey on research in this area.

    Tags:

  • (Colloquium) Shakhar Smorodinsky, Conflict-Free colorings
    Conflict-Free colorings
    Shakhar Smorodinsky
    Department of Mathematics, Ben-Gurion University, Israel
    2010/9/16 Thu 4:30PM-5:30PM (Room 1501)</em>

    Given a hypergraph H = (V,E), a coloring of its vertices is said to be conflict-free if for every hyperedge S ∈ E there is at least one vertex whose color is distinct from the colors of all other vertices in S. When all hyperedges in H have cardinality two (i.e., when H is a simple graph), this coloring coincides with the classical graph coloring. The study of this coloring is motivated by frequency assignment problems in wireless networks and several other applications. We will survey this notion and introduce some fascinating open problems.

    Tags:

  • (Colloquium) Carsten Thomassen, Rendezvous numbers and von Neumann’s min-max theorem
    FYI (Department Colloquium)
    Rendezvous numbers and von Neumann’s min-max theorem
    Carsten Thomassen
    Department of Mathematics, Technical University of Denmark, Lyngby, Denmark
    2010/04/01 Thursday 4:30PM-5:30PM (Room 1501)

    A rendezvous number for a metric space M is a number a such that, for every finite subset Q of M, there is an element p in M, such that the average distance from p to the elements in Q is a.

    O. Gross showed in 1964 that every compact connected metric space has precisely one rendezvous number. This result is a consequence of von Neumann’s min-max theorem in game theory.

    In an article in the American Math. Monthly 93(1986) 260-275, J. Cleary and A. A. Morris asked if a (more) elementary proof of Gross’ result exists.

    In this talk I shall formulate a min-max result for real matrices which immediately implies these results of Gross and von Neumann.

    The proof is easy and involves only mathematical induction.

    Tags:

  • (Colloquium) Ken-ichi Kawarabayashi, The disjoint paths problem: Algorithm and Structure
    FYI (Department Colloquium)
    The disjoint paths problem: Algorithm and Structure
    Ken-ichi Kawarabayashi (河原林 健一)
    National Institute of Informatics, Tokyo, Japan.
    2009/11/26 Thursday 4:30PM-5:30PM (Room 1501)

    In this talk, we shall discuss the following well-known problem, which
    is called the disjoint paths problem.

    Given a graph G with n vertices and m edges, k pairs of vertices (s1,t1),(s2,t2),…,(sk,tk) in G (which are sometimes called terminals). Are there disjoint paths P1,…,Pk in G such that Pi joins si and ti for i=1,2,…,k?

    We discuss recent progress on this topic, including algorithmic aspect of the disjoint paths problem.

    We also discuss some structure theorems without the k disjoint paths. Topics include the uniquely linkage problem and the connectivity function that guarantees the existence of the k disjoint paths.

    Tags:

  • (Colloquium) Paul Seymour, Well-quasi-ordering tournaments and Rao’s degree-sequence conjecture
    FYI (Department Colloquium)
    Well-quasi-ordering tournaments and Rao’s degree-sequence conjecture
    Paul Seymour
    Department of Mathematics, Princeton University, Princeton, New Jersey, USA.
    2009/5/21 Thursday 4:30PM-5:30PM (Room 1501)

    Rao conjectured about 1980 that in every infinite set of degree sequences (of graphs), there are two degree sequences with graphs one of which is an induced subgraph of the other. We recently found a proof, and we sketch the main ideas.

    The problem turns out to be related to ordering digraphs by immersion (vertices are mapped to vertices, and edges to edge-disjoint directed paths). Immersion is not a well-quasi-order for the set of all digraphs, but for certain restricted sets (for instance, the set of tournaments) we prove it is a well-quasi-order.

    The connection between Rao’s conjecture and digraph immersion is as follows. One key lemma reduces Rao’s conjecture to proving the same assertion for degree sequences of split graphs (a split graph is a graph whose vertex set is the union of a clique and a stable set); and to handle split graphs it helps to encode the split graph as a directed complete bipartite graph, and to replace Rao’s containment relation with immersion.

    (Joint with Maria Chudnovsky, Columbia)

    Tags:

Monthly Archives