Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Paths and stability number in digraphs. | Paths and stability number in digraphs Jacob Fox Benny Sudakov Submitted May 15 2009 Accepted Jul 3 2009 Published Jul 24 2009 Mathematics Subject Classification 05C20 05C38 05C55 Abstract The Gallai-Milgram theorem says that the vertex set of any digraph with stability number k can be partitioned into k directed paths. In 1990 Hahn and Jackson conjectured that this theorem is best possible in the following strong sense. For each positive integer k there is a digraph D with stability number k such that deleting the vertices of any k 1 directed paths in D leaves a digraph with stability number k. In this note we prove this conjecture. 1 Introduction The Gallai-Milgram theorem 7 states that the vertex set of any digraph with stability number k can be partitioned into k directed paths. It generalizes Dilworth s theorem 4 that the size of a maximum antichain in a partially ordered set is equal to the minimum number of chains needed to cover it. In 1990 Hahn and Jackson 8 conjectured that this theorem is best possible in the following strong sense. For each positive integer k there is a digraph D with stability number k such that deleting the vertices of any k 1 directed paths in D leaves a digraph with stability number k. Hahn and Jackson used known bounds on Ramsey numbers to verify their conjecture for k 3. Recently Bondy Buchwalder and Mercier 3 used lexicographic products of graphs to show that the conjecture holds if k 2a3b with a and b nonnegative integers. In this short note we prove the conjecture of Hahn and Jackson for all k. Theorem 1 For each positive integer k there is a digraph D with stability number k such that deleting the vertices of any k 1 directed paths leaves a digraph with stability number k. To prove this theorem we will need some properties of random graphs. As usual the random graph G n p is a graph on n labeled vertices in which each pair of vertices forms an edge randomly and independently with probability p p n . Department of Mathematics .
