Introduction to Hypergraphs [Graph Theory]

[@TwentyNineJP]

I just came across the concept of hypergraphs yesterday, and I think they're exactly the solution I've been looking for for project I've been stuck on

[@VitalSine]

Awesome! I'm curious, what kind of project are you working on if you are able to share?

[@TwentyNineJP]

​@@VitalSine KZbin filtered my reply because I linked to the site, which is frustrating 😅 It's a tool that evaluates the output function of simplified digital integrated circuit topologies ("stick diagrams"), primarily intended for students. Through a lot of trial and error, the internal model has converged on something that is essentially a directed hypergraph, but the evaluation algorithm (stepping through vertices and determining their logic levels) is very complex and has a deeply rooted bug that sometimes manifests when VDD (logic high) and GND (logic low) are shorted together. I think that applying existing hypergraph theory might help me greatly simplify and debug the algorithm. Since I can't post a link, I'll describe the URL. The domain name is "stixu", the TLD is "io". If you go to "/test", it'll run the testbench so you can click on the individual test cases to see example circuits. Most of the test cases have 8 results - that's for all rotations and reflections of the circuit. The failing tests (aside from the intentionally failed test case intended to make sure the testbench itself works) are rotation and reflection dependent

[@TwentyNineJP]

@@VitalSine KZbin filtered my reply *twice*, which is frustrating 😅 I'll try again without referencing how to get to the project It's a tool that evaluates the output function of simplified digital integrated circuit topologies ("stick diagrams"), primarily intended for students. Through a lot of trial and error, the internal model has converged on something that is essentially a directed hypergraph, but the evaluation algorithm (stepping through vertices and determining their logic levels) is very complex and has a deeply rooted bug that sometimes manifests when VDD (logic high) and GND (logic low) are shorted together. I think that applying existing hypergraph theory might help me greatly simplify and debug the algorithm.

[@VitalSine]

@@TwentyNineJP Fascinating, best of luck with your project!

[@Channel-nu1bv]

Mindblowing! Ultra clear and helpful! Thanks a lot!

[@klausprinoth4364]

Awesome video! Great explanation on stuff I never heard about.

[@VitalSine]

Glad you enjoyed it!

[@kevon217]

Clutch video. Thanks!

[@RadhaKrishnan-ru8py]

This videos help me to understand very easly this concept 🎉🎉

[@florianwicher]

A hidden gem! Thanks!

[@bigredone1030]

Excellent video

[@RadhaKrishnan-ru8py]

Thanqq.... So much sir your attempt help me to complete my project successfuly.... Thanks alode❤❤

[@VitalSine]

I'm very glad to hear that!

[@shei_dark]

Very helpful and informative video, Thanks! I was looking for a video to understand hypertrees and constructing them when there is an order and I came across this video which gave me a good understanding of hypergraphs. I am wondering if you have specific video about hypertrees!? I have searched and I couldn't find any. Thanks!

[@VitalSine]

Glad it was helpful! I'm actually working on a hypertree video right now, should be out soon 👍

[@shei_dark]

@@VitalSine looking forward to it 🤩 Thanks!

[@amitozazad1584]

Nice effort man, kudos ! At 2:29: (what vertices are incident to edge e3?) shouldn't it be a, c, d, e ? As I see that e3 circles around these 4 vertices, right ?

[@VitalSine]

Thank you! I drew the hypergraph poorly there, but if you look really closely e3 is incident to c, d, e, and e2 is incident to a, c, d, and e1 is incident to a, b, but I can see how it looks like e3 should be a, c, d, e. I just edited in a note to the video to clarify that fact, thanks for letting me know about this issue

[@naamantan3692]

this is really helpful, thank you!

[@VitalSine]

Glad it was helpful!

[@eldhaelizabeth4856]

Thank you so much... Very helpful..

[@navneetsinha451]

I want to create a hypergraph in Python which contains 100s of nodes, and user defined edges. Is it possible to do this ?

[@VitalSine]

This is certainly possible, I would suggest you look into HyperNetX for an existing Python library for working with hypergraphs, pnnl.github.io/HyperNetX/index.html

[@navneetsinha451]

@@VitalSine Thanks for your reply. If I want to draw a hypergraph having hundreds of nodes then I can use Matrices may be, however it will be a sparse matrix. Also space consuming code!

[@navneetsinha451]

@@VitalSine Can you suggest any other Data structure I can use. That would be of great help!!

[@VitalSine]

You could use a list for the nodes, you can use a dictionary to represent your collection of edges, such as {"e1" : [1 , 2, 3], "e2" : [2, 3]}.

[@prathamkolhe2582]

Can you please share your PPT's for reference ? Thanks for the video !!

[@VitalSine]

Will do, I'll put them out on a Google drive or dropbox very soon.

[@VitalSine]

Just finished putting them on a Google drive, here is the link: drive.google.com/drive/folders/1Y2pvBVGbYkfZamX1Ne0Ewz2XAXQIjI2O?usp=sharing

[@rimbika9201]

Please explain Eulerian and Hamiltonian graph using the concept of hyper graph

[@VitalSine]

Great suggestion, will do!

[@piotrlezanski5156]

great

[@rajapushpam3214]

kindly explain semi graph sir

[@VitalSine]

Thank you for the suggestion, I'll cover semi graphs in the near future 🙂

[@kipling1957]

Fell at the first post. Can’t you just describe something in simple language for the non-mathematician? Vertices? Edges?

[@VitalSine]

Sorry if this was confusing, the video was intended for those familiar with graph theory, I have a video explaining the terminology from graph theory and introducing graph theory if you are interested: kzbin.info/www/bejne/hJDXe6JpjdyMY68si=HO26ugLZhg9DEI-J Basically, you can think of vertices as objects we're interested in, they can be anything (people for example), and edges as relationships between those objects. Vertices are visually shown as dots, edges (in hypergraph theory) are visually shown as some kind of shape, usually an oval or circle, enclosing dots. The "hypergraph" is just the vertices and the edges: it's the objects you're interested in AND the relationships between them that you're interested in. For example, maybe you want to study a group of 100 people as your objects, and the relationship that we are interested in is whether one person went to the same high school as another person. If they did, then we'll call those people "related". If you draw a dot for each person, then you draw an oval that contains/envelopes all of the dots that represent people that went to high school A, then you draw an oval that contains all of the dots that represent people that went to high school B, and so on. So if two dots appear inside the same oval as each other, that's just a way of representing the following information: "the people these dots represent went to the same high school as each other." The dots are always your vertices, your objects of interest. The ovals are always your edges, your relationships between objects of interest. I hope this helps!