Top
Best
New

Posted by ibobev 5 days ago

Start Doing Graph Theory(vertex.degree)
529 points | 116 commentspage 2
igleria 12 hours ago|
not super fond of my memories of having to come up with a graph demonstration on a fixed time on a paper exam, but at least I can say I was once a person that could do that!
paaloeye 6 hours ago||
Topp quality content!

I would even say that "Everyone Should Start Doing Graph Theory", but it's only my opinion of course. Take it or leave it.

ianbooker 7 hours ago||
https://vertex.degree/beginning/degrees#the-hypercube-graphs

I remember to this day the exact location I was when being introduced to construct hypercubes, to the exact bench in our uni cafeteria. It changed my understanding of multidimensionality completely.

wholinator2 7 hours ago|
Thanks for that, i was initials skeptical i would understand but this very clearly resembles the candidate paths for walkers in variatonal monte carlo simulation of spin systems. The edge set can be different, requiring "half filled" and flipping both a 1 and a 0 simultaneously. I'd not thought of these processes in terms of a graph, much less graphs which denote very high dimensional cubes with strange edges.
holdingunsteady 7 hours ago||
Feel like there's so much opportunity to combine great educational material with more interactive visualizations, given how easy it is to create great visualizations (with Claude, etc) nowadays. Especially in graph theory.
Lichtso 23 minutes ago|
You would be surprised how hard it is to visualize arbitrary graphs. Basically, we can only render small highly regular ones in a neat way. Everything beyond that turns into a ball of wool.

Graphs in general are high dimensional structures and don't lend themselves to 2D projections. That is not a problem with coding the layouting algorithm. There simply is no good geometric arrangement for most graphs / networks because they are not planar [0], or even close to it (with few intersections).

[0]: https://en.wikipedia.org/wiki/Planar_graph

matt_daemon 10 hours ago||
If you like graph theory Dijkstra’s in Disguise is a great read: https://blog.evjang.com/2018/08/dijkstras.html

Related HN thread: https://news.ycombinator.com/item?id=17745779

the__alchemist 9 hours ago||
Hah Ok, added to Zenodo. I historically struggle with disciplines which have "Theory" in the name. The materials feel to me as an easy intro, then rapid cliff. We'll see! (I think my brain is genetically or otherwise not good at this level of abstracting)
the__alchemist 2 hours ago|
*Zotero

AHH. Definition 1.4 and the questions after did it. It went from "Tracking all" to "I don't understand how this follows at all, and this makes no sense to me" 1.3b is a graph, not a union of two graphs?. What are the "two graphs"? What is this operator-like algebra, and what does it have to do with the rest of the definition or the text before and after it? A question about the complement which was never defined? Why are we probably agreeing that {1, 2} contain 3?

Update: Better phrasing I can understand:

"Definition 1.4. The union of two graphs G and H, denoted <>, is a single graph containing all vertices and edges from both. If G and H share no vertices in common, <> is a disjoint union."

For 1.5, I had no idea what the written definition meant, but this does: ``` Definition 1.5. The complement of graph G is the one that has the same vertices, two vertices are connected in G_complement if and only if they are not connected in G.

vorobeez 12 hours ago||
It's unfortunate that the book doesn't have solutions for practice problems. Which makes it hard to use for self-learning.
OgsyedIE 11 hours ago||
The book you want in this case is Gross, Yellen & Anderson, Graph Theory and its Applications, 3rd Edition.

There are plenty of ways to get a copy.

eru 11 hours ago||
You can ask Claude for the solutions?
vorobeez 11 hours ago|||
Sure I can. But from my experience solutions in math books usually continue learning process and can provide even more insight to a problem. Solutions from ChatGPT or Claude barely can replace that.

(Edit) But I understand that goal of a book can be completely different. So it's just problem of my expectations.

karmakurtisaani 10 hours ago|||
For elaborating something unclear they're great tho.
fl4regun 6 hours ago|||
all of the books I had in university basically just gave me the final result at the back of the book with no explanation, so I am quite jealous if this was your experience with textbooks. Could you name some of these books? They might be nice to buy!
Gormo 11 hours ago|||
If you don't have the solutions, how do you verify Claude's work?
DecoPerson 11 hours ago|||
Everything, except the bleeding edge and situations requiring the context window to be more than 60% filled, are elementary to Opus 5.5 . If you provide the questions completely, you can be very sure that Claude’s solutions will be correct. The world has changed; AI is reliable; we need to adapt.
adamddev1 10 hours ago|||
> The world has changed; AI is reliable; we need to adapt.

Yes, but I think it's important to state that it's only reliable for things that are very well known and extensively written about.

V__ 9 hours ago|||
I get a lot of obviously wrong or slightly wrong answers from all LLMs across the board. If you don't double-check you just don't know or you might miss it.

And for the bleeding edge part: My godchild wanted to know the name of a Pokémon from his licensed shirt. One of the first ones, found in every training set. Couldn't get it right, was certain it was the wrong one.

chasd00 7 hours ago||
> wanted to know the name of a Pokémon from his licensed shirt.

how did you even ask an AI this question? Took a picture of the shirt, uploaded it, and asked the AI what it was? That's a different class of problem than "answer this graph theory question and include your references: <paste text here>"

bmacho 9 hours ago||||
?

You don't ask for proofs to print them out, put them in your drawer, and brag around that you own the proofs for these exercises.

You ask Claude for proofs to help your understanding. Understanding is the exact same activity as verifying.

deredede 11 hours ago||||
According to current practices, you ask ChatGPT or DeepSeek to verify it.
Gormo 10 hours ago||
Turtles all the way down, I guess.
russfink 9 hours ago||||
If you don’t understand the solutions, how can you verify textbook solutions? And sometimes they’re wrong, maybe subtle typos, causing hours of grief and feelings of inferiority.
BeetleB 6 hours ago|||
The same way you'd verify a textbook's solution.

(Assuming it's a proof or something - if it's just a number - oh well).

jmspring 9 hours ago||
Oh this was a descent into past memories. I had the pleasure to take Graph Theory at UC Santa Cruz with Gerhard Ringel [1] way back when. Excellent instructor with some great stories.

[1] - https://en.wikipedia.org/wiki/Gerhard_Ringel

satnhak 8 hours ago||
Looks like an excellent book, and the author is right that graph theory is a very useful and practical branch of mathematics. If only I could persuade my son to read it.
throwaw12 12 hours ago|
that background is so annoying to my eyes when scrolling the content, would be great if author can fix it
yandrypozo 8 hours ago|
agreed, even as a graph background :(
More comments...