Posts Tagged ‘colloquium’

KAIST Graph Theory Day 2012

Thursday, November 29th, 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.

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

Saturday, September 29th, 2012

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.

(Colloquium) Satoru Iwata, Submodular Optimization and Approximation Algorithms

Thursday, September 15th, 2011
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.

(Colloquium) Xuding Zhu (朱緒鼎), Circular Colouring of Graphs

Tuesday, March 22nd, 2011
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.

(Colloquium) Shakhar Smorodinsky, Conflict-Free colorings

Wednesday, September 1st, 2010
Conflict-Free colorings
Shakhar Smorodinsky
Department of Mathematics, Ben-Gurion University, Israel
2010/9/16 Thu 4:30PM-5:30PM (Room 1501)

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.