- Видео 57
- Просмотров 66 736
Luke Postle
Добавлен 19 мар 2010
Probabilistic Methods 13-1: Large Independent Sets in Triangle Free Graphs
In the only video of Week 13 (to make up for the half week of Week 9), we state and prove the Caro-Wei Theorem on independence number. We then state and prove the theorem of Ajtai, Komlos and Szemeredi on the independence number of triangle-free graphs. Finally, we use this to prove an upper bound on the Ramsey number R(3,k).
Просмотров: 714
Видео
Probabilistic Methods 12-2: Dependent Random Choice
Просмотров 3553 года назад
In the second video of Week 12, we state and prove the Dependent Random Choice Lemma. We then apply it to upper bound the Turan number of bipartite graphs. For a proof of Turan's Theorem, see my other video: ruclips.net/video/_YPwH3c7OOE/видео.html For a proof of the Erdos-Stone Theorem, see my other video: ruclips.net/video/SM5zBFVs_Kw/видео.html Typo: the Theorem of Turan should have .5 n^2 i...
Probabilistic Methods 12-1: Crossing Lemma
Просмотров 3763 года назад
In the first video of Week 12, we state and prove the Crossing Lemma. We then derive the Szemeredi-Trotter theorem from it as well as a few applications in additive number theory.
Probabilistic Methods 11-2: Brun's Sieve and the Poisson Paradigm
Просмотров 6403 года назад
In the second video of Week 11, we state and the Poisson paradigm and Brun's sieve. We prove the latter and apply it and Janson's to study first the probability G(n,p) is triangle-free near its threshold and then the threshold that every vertex is in a triangle.
Probabilistic Methods 11-1: Janson's Inequality
Просмотров 5373 года назад
In the first video of Week 11, we state and prove Janson's inequality which ensures that the probability none of a set of events occurs is close to what it would be if the events were independent (under some assumptions).
Probabilistic Methods 10-2: Applying Concentration Inequalities, Part 2
Просмотров 3263 года назад
In the second video of Week 10, we apply Chernoff/McDiarmid/Talagrand's inequalities to give a different proof of the key iterative lemma from Pippenger-Spencer.
Probabilistic Methods 10-1: Applying Concentration Inequalities, Part 1
Просмотров 5243 года назад
In the first video of Week 10, we apply Azuma's inequality to concentrate the chromatic number of the random graph G(n,p); in particular to just 4 values if p is large enough.
Probabilistic Methods 9-1: Talagrand's Inequality
Просмотров 2 тыс.3 года назад
In our only video of Week 9, we state and prove Talagrand's Inequality. We then derive a combinatorial version of it - a very useful concentration inequality!
Probabilistic Methods 8-2: Concentration Inequalities
Просмотров 2 тыс.3 года назад
In the second video of Week 8, we begin our discussion of Concentration Inequalities. In particular, we cover: Chernoff Bounds, Hoeffding's inequality, Azuma's inequality, and McDiarmid's inequality. Note there are typos in the general Azuma's inequality and McDiarmid's inequality: namely the sqrt factors in the LHS should be omitted.
Probabilistic Methods 8-1: FKG Inequality
Просмотров 5493 года назад
In the first video of Week 8, we state and prove the FKG inequality (via the Four Functions Theorem) and then derive Kleitman's Lemma.
Probabilistic Methods 7-2: Four Functions Theorem
Просмотров 4213 года назад
Second video of Week 7. We state and prove the Four Functions Theorem on Correlation Inequalities.
Probabilistic Methods 7-1: Moser-Tardos Algorithm
Просмотров 5983 года назад
In the first video of Week 7, we state and prove the running time of the Moser-Tardos Algorithm for the Local Lemma.
Probabilistic Methods 6-2: Applying the Local Lemma
Просмотров 7533 года назад
In this 2nd video of Week 6, we go through a number of applications of the Local Lemma: to hypergraph coloring, multicolored sets of real numbers, Ramsey lower bounds and k-fold coverings.
Probabilistic Methods 6-1: Local Lemma
Просмотров 1,7 тыс.3 года назад
In the first video of Week 6, we state and prove the Lovasz local lemma.
Probabilistic Methods 5-2: Proving Pippenger-Spencer
Просмотров 4303 года назад
2nd video of Week 5. We go through a proof of the Pippenger-Spencer covering theorem using Rodl's nibble and the second moment method.
Probabilistic Methods: 5-1 Rodl's Nibble
Просмотров 7333 года назад
Probabilistic Methods: 5-1 Rodl's Nibble
Graph Theory 1-2: Writing Guidelines
Просмотров 4 тыс.3 года назад
Graph Theory 1-2: Writing Guidelines
Graph Theory 1-3: A Writing Example
Просмотров 1,1 тыс.3 года назад
Graph Theory 1-3: A Writing Example
Graph Theory 1-4: Coloring and Brooks' Theorem.
Просмотров 2 тыс.3 года назад
Graph Theory 1-4: Coloring and Brooks' Theorem.
Graph Theory 2-1: An Informal Proof of Brooks Theorem
Просмотров 3,1 тыс.3 года назад
Graph Theory 2-1: An Informal Proof of Brooks Theorem
Graph Theory 2-2: Towards a Formal Proof of Brooks' Theorem
Просмотров 1,2 тыс.3 года назад
Graph Theory 2-2: Towards a Formal Proof of Brooks' Theorem
Graph Theory 2-3: Beyond Brooks' Theorem
Просмотров 4933 года назад
Graph Theory 2-3: Beyond Brooks' Theorem
Graph Theory 3-2: Proof of Vizing's Theorem
Просмотров 1,9 тыс.3 года назад
Graph Theory 3-2: Proof of Vizing's Theorem
Graph Theory 3-4: Edge Coloring Multigraphs
Просмотров 3653 года назад
Graph Theory 3-4: Edge Coloring Multigraphs
Graph Theory 4-1: Thomassen's Theorem
Просмотров 6653 года назад
Graph Theory 4-1: Thomassen's Theorem
Graph Theory 4-2: Coloring and List Coloring Planar Graphs
Просмотров 9073 года назад
Graph Theory 4-2: Coloring and List Coloring Planar Graphs
Awesome!!
Thank you for this informative discussion.
Thank you for explaining this so clearly and enthusiastically 😊
I appreciate the fact that you take time to discuss the tangible applications of coloring beyond cartography.
You are fantastic!
This most certainly helped, thank you.
Thank you!
Hi Luke! From which university are you?
I'm so thankful for uploding this video.I want to be your student in graph theory dear professor
Grate,👌
thanks
Is there some lectures or slides available?
Dunno about that, but he seems to follow Diestel's book quite closely.
@@computo2000 Thank you!
At 3:40 i think the probability space should be random 2 coloring of vertices ( not the edges)
Yes, you are right indeed 👍
Hi, thanks for sharing your knowledge in the videos. I just want to know whether there is video 1-3?
at 24:24, why would the setting of Xi can deduce to the claim? sholdn't the claim also be in the initial condition of Xi?
The idea is that, given the premise here, we argue that any random permutation has a certain property X_i with a non-zero probability. Later, we accumulate these probabilities over all X_i to get the desired bound.
Thanks, Luke, great content! Is it possible to let me access the slides?
How does R lies in that strip? Can you please explain?
In the proposition about Var[X] at 6:00, I guess the sum over Var[X_i] should go from 1 to n, rather than m (there's an index mismatch).
I'm from a different UNI, but this really helped - thank you!
Question: does the last part imply that the k-coloring problem has FPT algorithm of running time O(k^tw)?
Thank you for this clear presentation. I am just having some trouble understanding the notion of r-verifiability. Can you recommend a resource which explains it in more detail by any chance ?
Namely I don't understand how the set I and the random variable X are related in the definition you give.
Very nice
I think the notation A_r should be A_R from 4:49
Correct
(I'm not sure but) I think you need to check for G_i being odd cycle in Claim 1, because while we agreed that for source G: Delta(G) >= 3, we don't know that for G_i. And since we later say that for G_i by induction there is a Delta(G_i)-colouring, I think we should've separately checked for the odd cycle.
In the case where the max degree of G_i decreases, there exists the desired coloring trivially by greedy and so we are not using induction there (and hence do not need to consider the odd cycle case).
While the first proof is definitely messed up, it's quite sad that formal proofs should have lots of notations, because it makes them several times longer and several times harder to digest for me as a reader (while the first 'proof' is quite intuitive and it's easy to correct the mistakes in your head once you get the right idea).
Correct proofs need to be correct and they also need to be checkable for correctness. Usually that involves notation and some length. Indeed, that is the main the point of the video. Writing ambiguous or incorrect statements does not constitute a proof.
@@LJPostle17 I think it should be possible to add additional signposting (explanatory text saying what's about to happen), reorder things a bit, and use less notation, so as to make the intuition behind a proof more evident to an uninitiated reader early on. In this case it might start something like the following (which could no doubt be improved upon). After the first paragraph, the reader would probably understand how the proof works and would know what to expect in the detailed argument to follow. (In the proof as presented in the video, this isn't really possible until the punchline.) Suppose not. That is, there exist two paths P1 and P2 of G that have no vertex in common. Since G is connected, there exists a shortest path P from V(P1) to V(P2). We claim that a new path that is longer than P1 and P2 can be constructed by concatenating P to suitable subpaths of P1 and P2. Specifically, for each i in {1,2}, let ... P.S. Thanks for a bunch of very helpful videos (including this one).
Hi, thanks for sharing your knowledge in the videos. I want to focus on a question of reducing permutations according to Paul Erdős. It was difficult for me to follow only formulas and I need a live example The example has the following combination: How do I perform a reduction according to the formulas Thanks in advance 3 12 17 18 19 35 3 8 12 13 14 35 3 12 13 14 17 35 3 8 17 18 19 35 3 12 13 14 31 35 3 12 13 14 19 35 3 17 18 19 31 35 3 13 17 18 19 35 3 12 13 14 18 35 3 14 17 18 19 35
Thanks!
Thanks.
great examples. thank you!
Great course. Thank you very much Professor!!!!! How can i access the homework and exam of this course?
I'm so thankful for uploading these lectures. Could you send me your presentation please?
Nice explanation
Greetings from Czech Republic. I am preparing for "Graph Theory and Complexity" exam and find your videos very helpful :)
Glad you like them!
@@LJPostle17 Greetings from Paris too, I am preparing a course on Graph Minor theory and also find your videos very helpful :)