We'd love your feedback! Please take a minute to share your thoughts.

Summer of Math Exposition

From DNA to PQ-trees: a story of interval graphs

Audience: undergraduategraduate

Tags: graph-theoryalgorithms

What connects DNA and graph theory? Interval graphs can be represented by intervals where edges are encoded by their intersections. This video begins with the historical motivation from Seymour Benzer’s work on gene structures in DNA. It then explores how to decide whether a given graph has an interval representation. You’ll learn about two key characterizations: minimal forbidden induced subgraphs (Lekkerkerker & Boland) and consecutive orderings of maximal cliques (Fulkerson & Gross). The video also introduces PQ-trees, a data structure by Booth and Lueker used to test these orderings efficiently. It concludes with my 2010 research on when partial interval representations can be extended to full ones.



Analytics

7 Overall score*
24 Rank
19 Votes
9 Comments

Comments

7.2

I liked how the “magic” was more “I have not proved this yet” rather than “you should feel awestruck because my topic is wonderful”

8

Excellent video! I was fascinated the whole way through, and I learned a lot. My only suggestion would be to add a short outline slide at the start as a signpost for where the presentation is going.

5.5

This is a nice introduction to what seems like an interesting topic, and I think your speech is very fluid and compelling - I don’t know how to describe it but it does have a certain listenable quality to it.

That said, I do think that your video might have a weakness when it comes to prior motivation of certain ideas: there was a lot of time in the video where I sort of lost the thread of why we were talking about something, or had time understanding exactly what you were doing, and then later caught back up with you and everything snapped back into place. I don’t know how exactly to remedy that, but I think strengthening some of your introductions to new subtopics in some way might help. In particular, I also think it’s relevant that there’s never a concrete instantiation of exactly what kind of graph we’re talking about which relates to scheduling or gene expression: I think it isn’t too hard to imagine, but having a concrete example could help with the clarity a bit.

Anyway, good work overall, and I hope you keep it up! Good to have you onboard here

3.2

Video is not as good as thumbnail

8.5

Really great video! I had already watched some of it from the Discord, but I’m glad I got the chance to vote on it. I love how you layed out all the ideas into a big web. This video probably isn’t for anyone that doesn’t already have an interest in graph theory, but I think that’s totally fine. Very clear, novel, and memorable!

6

It would have been nice if the jargon was introduced in a bit more detail. Liked the enthusiasm of the presenter. Overall, nice video, but might only be suitable for someone with a fair bit of background knowledge about graphs.

3.3

This felt like a conference recording, not a video intended to be a video.

Having said that, the train of thought was clear with proper context for everything. Loved the visuals, and putting the slides on a graph was a nice touch. The added historical context was also nice. Still, I think the video format would have allowed for a more immersive final product.

7.5

Really excellent presentation—well spoken, clean visuals (love your software!) and interesting subject matter. Some of the details towards the end exceeded my familiarity with graph theory, so I imagine this is primarily geared towards viewers with some strong background in the subject matter.

Having said that, I was completely enthralled by the mini-history lesson on practical uses for interval graphs in genetic research! When you first introduced interval graphs, I thought to myself “When would that representation even be useful?” and you answered it beautifully. If you wanted to, I think you could spin off and make great “So what?” style videos on practical applications of some of this more abstract math, and make it engaging for general/more nontechnical viewers. Food for thought!

7

This is a high-quality conference talk. I wish this would be the standard at conferences. It is probably not for total beginners though.

I like the beginning of the video outdoors, and showing the Phd thesis.