Please someone give me the clear idea about dilworth theorem for graph or DAG. I read about it in multiple places but more I am reading getting more confusing. So please someone help me to understand it properly.

Thanks in advance.

Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Before contest

Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)

23:10:10

Register now »

Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)

23:10:10

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3797 |

2 | Benq | 3618 |

3 | Radewoosh | 3525 |

4 | Miracle03 | 3460 |

5 | ecnerwala | 3419 |

6 | Petr | 3408 |

7 | peehs_moorhsum | 3384 |

8 | ksun48 | 3377 |

9 | ko_osaga | 3352 |

10 | maroonrk | 3344 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 205 |

3 | Um_nik | 196 |

4 | Errichto | 182 |

5 | awoo | 179 |

6 | sus | 177 |

7 | tourist | 176 |

8 | antontrygubO_o | 173 |

9 | -is-this-fft- | 170 |

10 | SecondThread | 167 |

Please someone give me the clear idea about dilworth theorem for graph or DAG. I read about it in multiple places but more I am reading getting more confusing. So please someone help me to understand it properly.

Thanks in advance.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/27/2021 18:24:50 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Applicated to a DAG, it says that we can find divide the set of vertices into subsets

V_{1}, ...,V_{k}, so that any two vertices in any subset are reachable one from another (in one direction, of course), and then choose , so that none ofv_{i}are reachable from any other.