CS4410 - Topics in Algorithmic Combinatorics and Graph Theory

Meetings  

• Theme 1 : Connectivity - 8 meetings

  • Meeting 01 : Tue, Jan 14, 11:00 am-11:50 am

  Introduction and administrative announcements.

  References
  Exercises
  Reading

  Introduction and administrative announcements.
  

  References:

  None

  • Meeting 02 : Thu, Jan 16, 08:00 am-08:50 am

  Properties of 2-connected graphs. A characterization.

  References	[Diest]
  Exercises
  Reading

  Properties of 2-connected graphs. A characterization.
  

  References:

  [Diest]

  • Meeting 03 : Thu, Jan 16, 10:00 am-10:50 am

  No lecture

  References	[Diest]
  Exercises
  Reading

  No lecture
  

  References:

  [Diest]

  • Meeting 04 : Fri, Jan 17, 05:00 pm-05:50 pm

  Vector spaces a brief intro. Cycle space of a graph.

  References
  Exercises
  Reading

  Vector spaces a brief intro. Cycle space of a graph.
  

  References:

  None

  • Meeting 05 : Tue, Jan 21, 11:00 am-11:50 am

  Cycle space of a graph. A cycle basis from fundamental circuits.

  References
  Exercises
  Reading

  Cycle space of a graph. A cycle basis from fundamental circuits.
  

  References:

  None

  • Meeting 06 : Wed, Jan 22, 10:00 am-10:50 am

  Cycle basis of 3-connected graphs. Menger's theorem.

  References
  Exercises
  Reading

  Cycle basis of 3-connected graphs. Menger's theorem.
  

  References:

  None

  • Meeting 07 : Thu, Jan 23, 08:00 am-08:50 am

  Meger's Theorem.

  References
  Exercises
  Reading

  Meger's Theorem.
  

  References:

  None

  • Meeting 08 : Fri, Jan 24, 05:00 pm-05:50 pm

  Menger's theorem (full details)

  References
  Exercises
  Reading

  Menger's theorem (full details)
  

  References:

  None

• Theme 2 : Substructures - 25 meetings

  • Meeting 09 : Fri, Feb 07, 05:00 pm-05:50 pm

  Turan's theorem (Proof). Extremal problems related to paths and cycles.

  References
  Exercises
  Reading

  Turan's theorem (Proof). Extremal problems related to paths and cycles.
  

  References:

  None

  • Meeting 10 : Tue, Feb 11, 11:00 am-11:50 am

  Szemeredi Regularity Lemma.

  References
  Exercises
  Reading

  Szemeredi Regularity Lemma.
  

  References:

  None

  • Meeting 11 : Wed, Feb 12, 10:00 am-10:50 am

  Applications of SRL - 1

  References
  Exercises
  Reading

  Applications of SRL - 1
  

  References:

  None

  • Meeting 12 : Thu, Feb 13, 08:00 am-08:50 am

  Applications of SRL - 2

  References
  Exercises
  Reading

  Applications of SRL - 2
  

  References:

  None

  • Meeting 13 : Fri, Feb 14, 02:00 pm-02:50 pm

  Applications of SRL - 3

  References
  Exercises
  Reading

  Applications of SRL - 3
  

  References:

  None

  • Meeting 14 : Tue, Feb 18, 11:00 am-11:50 am

  Proof of SRL.

  References
  Exercises
  Reading

  Proof of SRL.
  

  References:

  None

  • Meeting 15 : Wed, Feb 19, 10:00 am-10:50 am

  Introduction to Ramsey Theory

  References
  Exercises
  Reading

  Introduction to Ramsey Theory
  

  References:

  None

  • Meeting 16 : Thu, Feb 20, 08:00 am-08:50 am

  Ramsey type theorems - 1

  References
  Exercises
  Reading

  Ramsey type theorems - 1
  

  References:

  None

  • Meeting 17 : Fri, Feb 21, 02:00 pm-02:50 pm

  Ramsey type theorems - 2

  References
  Exercises
  Reading

  Ramsey type theorems - 2
  

  References:

  None

  • Meeting 18 : Tue, Feb 25, 11:00 am-11:50 am

  Ramsey type theorems - 3

  References
  Exercises
  Reading

  Ramsey type theorems - 3
  

  References:

  None

  • Meeting 19 : Wed, Feb 26, 10:00 am-10:50 am

  Ramsey type theorems - 4

  References
  Exercises
  Reading

  Ramsey type theorems - 4
  

  References:

  None

  • Meeting 20 : Thu, Feb 27, 08:00 am-08:50 am

  Extremal Combinatorics: Sunflower lemma

  References
  Exercises
  Reading

  Extremal Combinatorics: Sunflower lemma
  

  References:

  None

  • Meeting 21 : Fri, Feb 28, 02:00 pm-02:50 pm

  Modifications of sunflowers. Flower lemma by Hastad.

  References
  Exercises
  Reading

  Modifications of sunflowers. Flower lemma by Hastad.
  

  References:

  None

  • Meeting 22 : Tue, Mar 03, 11:00 am-11:50 am

  Application of flower lemma: min terms of a CNF.

  References
  Exercises
  Reading

  Application of flower lemma: min terms of a CNF.
  

  References:

  None

  • Meeting 23 : Wed, Mar 04, 10:00 am-10:50 am

  Erdos Ko Rado Theoream

  References
  Exercises
  Reading

  Erdos Ko Rado Theoream
  

  References:

  None

  • Meeting 24 : Thu, Mar 05, 08:00 am-08:50 am

  No Lecture.

  References
  Exercises
  Reading

  No Lecture.
  

  References:

  None

  • Meeting 25 : Fri, Mar 06, 02:00 pm-02:50 pm

  Mid Sem

  References
  Exercises
  Reading

  Mid Sem
  

  References:

  None

  • Meeting 26 : Tue, Mar 10, 11:00 am-11:50 am

  Introduction to Graph Minor Theory

  References
  Exercises
  Reading

  Introduction to Graph Minor Theory
  

  References:

  None

  • Meeting 27 : Wed, Mar 11, 10:00 am-10:50 am

  Tree decompositions - 3

  References
  Exercises
  Reading

  Tree decompositions - 3
  

  References:

  None

  • Meeting 28 : Thu, Mar 12, 08:00 am-08:50 am

  Tree decompositions - 4

  References
  Exercises
  Reading

  Tree decompositions - 4
  

  References:

  None

  • Meeting 29 : Fri, Mar 13, 02:00 pm-02:50 pm

  Notion of tangles - 1

  References
  Exercises
  Reading

  Notion of tangles - 1
  

  References:

  None

  • Meeting 30 : Tue, Mar 17, 11:00 am-11:50 am

  Notion of tangles - 2

  References
  Exercises
  Reading

  Notion of tangles - 2
  

  References:

  None

  • Meeting 31 : Wed, Mar 18, 10:00 am-10:50 am

  Notion of tangles - 3

  References
  Exercises
  Reading

  Notion of tangles - 3
  

  References:

  None

  • Meeting 32 : Thu, Mar 19, 08:00 am-08:50 am

  Overview of the Graph minor theorem

  References
  Exercises
  Reading

  Overview of the Graph minor theorem
  

  References:

  None

  • Meeting 33 : Fri, Mar 20, 02:00 pm-02:50 pm

  Overview of the Graph minor theorem

  References
  Exercises
  Reading

  Overview of the Graph minor theorem
  

  References:

  None

• Theme 3 : Random Graphs - 19 meetings

  • Meeting 34 : Tue, Mar 24, 11:00 am-11:50 am

  Fundamental models of Random graphs.

  References
  Exercises
  Reading

  Fundamental models of Random graphs.
  

  References:

  None

  • Meeting 35 : Wed, Mar 25, 10:00 am-10:50 am

  Properties of almost all graphs.

  References
  Exercises
  Reading

  Properties of almost all graphs.
  

  References:

  None

  • Meeting 36 : Thu, Mar 26, 08:00 am-08:50 am

  Connectivity.

  References
  Exercises
  Reading

  Connectivity.
  

  References:

  None

  • Meeting 37 : Fri, Mar 27, 02:00 pm-02:50 pm

  Giant components.

  References
  Exercises
  Reading

  Giant components.
  

  References:

  None

  • Meeting 38 : Tue, Mar 31, 11:00 am-11:50 am

  Appearanceof subgraphs - 1

  References
  Exercises
  Reading

  Appearanceof subgraphs - 1
  

  References:

  None

  • Meeting 39 : Wed, Apr 01, 10:00 am-10:50 am

  Appearanceof subgraphs - 1

  References
  Exercises
  Reading

  Appearanceof subgraphs - 1
  

  References:

  None

  • Meeting 40 : Thu, Apr 02, 08:00 am-08:50 am

  Matchings - 1

  References
  Exercises
  Reading

  Matchings - 1
  

  References:

  None

  • Meeting 41 : Fri, Apr 03, 02:00 pm-02:50 pm

  Matchings - 2

  References
  Exercises
  Reading

  Matchings - 2
  

  References:

  None

  • Meeting 42 : Tue, Apr 07, 11:00 am-11:50 am

  Threshold phenomenon - 1

  References
  Exercises
  Reading

  Threshold phenomenon - 1
  

  References:

  None

  • Meeting 43 : Wed, Apr 08, 10:00 am-10:50 am

  Threshold phenomenon - 2

  References
  Exercises
  Reading

  Threshold phenomenon - 2
  

  References:

  None

  • Meeting 44 : Thu, Apr 09, 08:00 am-08:50 am

  Real world models of random networks. Power law graphs

  References
  Exercises
  Reading

  Real world models of random networks. Power law graphs
  

  References:

  None

  • Meeting 45 : Fri, Apr 10, 02:00 pm-02:50 pm

  Preferential attachment model - 1

  References
  Exercises
  Reading

  Preferential attachment model - 1
  

  References:

  None

  • Meeting 46 : Tue, Apr 14, 11:00 am-11:50 am

  Preferential attachment model - 2

  References
  Exercises
  Reading

  Preferential attachment model - 2
  

  References:

  None

  • Meeting 47 : Wed, Apr 15, 10:00 am-10:50 am

  Preferential attachment model - 3

  References
  Exercises
  Reading

  Preferential attachment model - 3
  

  References:

  None

  • Meeting 48 : Thu, Apr 16, 08:00 am-08:50 am

  Applications - 1

  References
  Exercises
  Reading

  Applications - 1
  

  References:

  None

  • Meeting 49 : Fri, Apr 17, 02:00 pm-02:50 pm

  Applications - 2

  References
  Exercises
  Reading

  Applications - 2
  

  References:

  None

  • Meeting 50 : Tue, Apr 21, 11:00 am-11:50 am

  Applications - 3

  References
  Exercises
  Reading

  Applications - 3
  

  References:

  None

  • Meeting 51 : Wed, Apr 22, 10:00 am-10:50 am

  Concluding remarks

  References
  Exercises
  Reading

  Concluding remarks
  

  References:

  None

  • Meeting 52 : Thu, Apr 23, 08:00 am-08:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

• Theme 4 : Planar Graphs - 7 meetings

  • Meeting 53 : Tue, Jan 28, 11:00 am-11:50 am

  Some elementary facts from topology. Plane graphs. Faces. First properties.

  References	[Diestel]
  Exercises
  Reading

  Some elementary facts from topology. Plane graphs. Faces. First properties.
  

  References:

  [Diestel]

  • Meeting 54 : Wed, Jan 29, 10:00 am-10:50 am

  2 connected and 3 connected plane graphs. Maximal plane graphs are triangulated.

  References	[Diestel]
  Exercises
  Reading

  2 connected and 3 connected plane graphs. Maximal plane graphs are triangulated.
  

  References:

  [Diestel]

  • Meeting 55 : Thu, Jan 30, 08:00 am-08:50 am

  Lecture cancelled as the instructor was unwell. To be re-scheduled.

  References
  Exercises
  Reading

  Lecture cancelled as the instructor was unwell. To be re-scheduled.
  

  References:

  None

  • Meeting 56 : Fri, Jan 31, 05:00 pm-05:50 pm

  Euler's formula. Kuratowski's theorem.

  References	For Kuratowski's theorem <a href="http://www.math.cmu.edu/~mradclif/teaching/228F16/Kuratowski.pdf"> See notes by Mary Radicliffe </a>
  Exercises
  Reading

  Euler's formula. Kuratowski's theorem.
  

  References:

  For Kuratowski's theorem See notes by Mary Radicliffe

  • Meeting 57 : Tue, Feb 04, 11:00 am-11:50 am

  Kuratowski's theorem (contd).

  References
  Exercises
  Reading

  Kuratowski's theorem (contd).
  

  References:

  None

  • Meeting 58 : Wed, Feb 05, 10:00 am-10:50 am

  Algebraic characterization of planar graphs. Planar Graphs and embeddings. Unique embeddings for 3-connected graphs.

  References
  Exercises
  Reading

  Algebraic characterization of planar graphs. Planar Graphs and embeddings. Unique embeddings for 3-connected graphs.
  

  References:

  None

  • Meeting 59 : Thu, Feb 06, 08:00 am-08:50 am

  Equivalence of embeddings for 3-connected graphs (Without proof). Introduction to extremal graph theory. Turan's theorem.( statement)

  References
  Exercises
  Reading

  Equivalence of embeddings for 3-connected graphs (Without proof). Introduction to extremal graph theory. Turan's theorem.( statement)
  

  References:

  None