Posts Tagged ‘DanielKral’

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.

Daniel Král’, Total fractional colorings of graphs with large girth

Tuesday, January 12th, 2010
Total fractional colorings of graphs with large girth
Daniel Král’
ITI, Charles University, Prague, Czech Republic
2010/1/26 Tue, 4PM-5PM

A total coloring is a combination of a vertex coloring and an edge coloring of a graph: every vertex and every edge is assigned a color and any two adjacent/incident objects must receive distinct colors. One of the main open problems in the area of graph colorings is the Total Coloring Conjecture of Behzad and Vizing from the 1960’s asserting that every graph has a total coloring with at most D+2 colors where D is its maximum degree.

Fractional colorings are linear relaxation of ordinary colorings. In the setting of fractional total colorings, the Total Coloring Conjecture was proven by Kilakos and Reed. In the talk, we will present a proof of the following recent conjecture of Reed:

For every real ε>0 and integer D, there exists g such that every graph with maximum degree D and girth at least g has total fractional chromatic number at most D+1+ε.

For D=3 and D=4,6,8,10,…, we prove the conjecture in a stronger
form: there exists g such that every graph with maximum degree D and girth at least g has total fractional chromatic number equal to D+1.

Joint work with Tomás Kaiser, František Kardoš, Andrew King and Jean-Sébastien Sereni.

Daniel Král’, Algebraic versions of Removal Lemma

Monday, January 11th, 2010
Algebraic versions of Removal Lemma
Daniel Král’
ITI, Charles University, Prague, Czech Republic
2010/1/19 Tue, 4PM-5PM

We study algebraic analogues of the graph Removal Lemma. Vaguely speaking, the graph Removal Lemma says that if a given graph does not contain too many subgraphs of a given kind, then all the subgraphs of this kind can be destroyed by removing few edges. In 2005, Green conjectured the following analogue of it for systems of equations over integers:

For every k x m integral matrix A with rank k and every ε>0, there exists δ>0 such that the following holds for every N and every subset S of {1,…N}: if the number of solutions of A x = 0 with x ∈ Sm is at most δ N^{m-k}, then it is possible to destroy all solutions x ∈ Sm of A x = 0 by removing at most ε N elements from the set S.

We prove this conjecture by establishing its variant for not necessarily homogenous systems of equations over finite fields. The core of our proof is a reduction of the statement to the colored version of hypergraph Removal Lemma for (k+1)-uniform hypergraphs. Independently of us, Shapira obtained the same result using a reduction to the colored version of hypergraph Removal Lemma for O(m2)-uniform hypergraphs. The talk will be self-contained and no previous knowledge of the area related to the graph Removal Lemma will be assumed.

Joint work with Oriol Serra and Lluis Vena.