0 like 0 dislike
0 like 0 dislike
John Urschel | Tackling Graph Theory | The Cartesian Cafe with Timothy Nguyen

8 Answers

0 like 0 dislike
0 like 0 dislike
Timestamps:

00:00:00 : Introduction

00:04:30 : Being a professional mathematician and academia vs industry

00:09:41 : John's taste in mathematics

00:13:00 : Outline

00:17:23 : Braess's Paradox: "Opening a highway can increase traffic congestion."

00:25:34 : Prisoner's Dilemma. We need social forcing mechanisms to avoid undesirable outcomes (traffic jams).

00:31:20 : What is a graph

00:36:33 : Graph bottlenecks. Practical situations: Task assignment, the economy, organizational management.

00:42:44 : Quantifying bottlenecks: Cheeger's constant

00:46:43 : Cheeger's constant sample computations

00:55:48 : Graph Laplacian

00:58:30 : Graph Laplacian: Relation to Laplacian from calculus

01:00:27 : Graph Laplacian: 1-dimensional example

01:01:22 : Graph Laplacian: Analyst's Laplacian vs Geometer's Laplacian (they differ by a minus sign)

01:04:44 : Graph Laplacian: Some history

01:07:35 : Cheeger's Inequality: Statement

01:09:37 : \*\*\*Cheeger's Inequality: A great example of beautiful mathematics\*\*\*

01:10:46 : Cheeger's Inequality: Computationally tractable approximation of Cheeger's constant

01:14:57 : Rayleigh quotient, discussion of proof of Cheeger's inequality

01:19:16 : Harmonic oscillators: Springs heuristic for lambda\_2 and Cheeger's inequality

01:22:20 : Interlude: Tutte's Spring Embedding Theorem (planar embeddings in terms of springs)

01:26:23 : Harmonic oscillators: Resume lambda\_2 discussion and spring tension

01:29:45 : Interlude: Graph drawing using eigenfunctions

01:33:17 : Harmonic oscillators: Resume lambda\_2 discussion: complete graph example and bottleneck is a perturbation of two disconnected components

01:38:26 : Summary thus far and graph bisection

01:42:44 : Graph bisection: Large eigenvalues for PCA vs low eigenvalues for spectral bisection

01:43:40 : Graph bisection: 1-dimensional intuition

01:44:40 : Graph bisection: Nodal domains

01:46:29 : Graph bisection: Aha, the 1-d example now makes sense. Splitting by level set of second eigenfunction is a good way to partition domain.

01:47:43 : Spectral graph clustering (complementary to graph bisection)

01:51:50 : Ng-Jordan-Weiss paper

01:52:10 : PageRank: Google's algorithm for ranking search results

01:53:44 : PageRank: Markov chain (Markov matrix)

01:57:32 : PageRank: Stationary distribution

02:00:20 : Perron-Frobenius Theorem

02:06:10 : Spectral gap: Analogy between bottlenecks for graphs and bottlenecks for Markov chain mixing

02:07:56 : Conclusion: State of the field, Urschel's recent results

02:10:27 : Joke: Two kinds of mathematicians
0 like 0 dislike
0 like 0 dislike
Been studying graph theory independently and when I saw this I went SAVE SAVE SAVE SAVE lol
0 like 0 dislike
0 like 0 dislike
For those who may be interested in the balance of life between being a pro football player and mathematician:  his book is a great read!
0 like 0 dislike
0 like 0 dislike
Most people would kill to be as good physically OR mentally as him
0 like 0 dislike
0 like 0 dislike
This is pure gold i'm so thankful
0 like 0 dislike
0 like 0 dislike
First time I’m hearing of this guy. Amazing.
0 like 0 dislike
0 like 0 dislike
Love these talks, thanks for uploading
0 like 0 dislike
0 like 0 dislike
He is also known in the chess community. For some time he streamed chess and did some events with chess.com even before the chess boom.
by

Related questions

0 like 0 dislike
0 like 0 dislike
2 answers
a_dalgleish asked Jun 21
Contributing to the right math area, If all areas are equally curious
a_dalgleish asked Jun 21
0 like 0 dislike
0 like 0 dislike
2 answers
ConradDubai asked Jun 21
How to “topologize” the fundamental group: a primer
ConradDubai asked Jun 21
0 like 0 dislike
0 like 0 dislike
3 answers
MattWoosie asked Jun 21
If you had to pick the best method for solving Poisson’s Equation, which would it be and why?
MattWoosie asked Jun 21
0 like 0 dislike
0 like 0 dislike
8 answers
UnShowNoTanLate asked Jun 21
Is there research on graphs where the edges can connect more than two nodes?
UnShowNoTanLate asked Jun 21
0 like 0 dislike
0 like 0 dislike
15 answers
marcuscallender asked Jun 21
Fixing the "I Must Prove This, Myself!" mindset
marcuscallender asked Jun 21

33.4k questions

135k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!