วีดีโอ

Good catch, e_4 should have included vertex 'b' in order for the hypergraph to be an intersecting family and not a star.

@@VitalSine That make sense, thank you so much!

Yes. Tensor product is another name for Direct product.

Thank you, I'm glad to hear you like the playlist!

Thank you so much for the kind words! It's a great idea to make a prep course, I haven't been able to make any new videos recently, but I'll definitely make more preparatory content in the near future. I also wanted to let you know I have a couple of introductory graph theory videos on the channel in case you haven't studied introductory graph theory and have not found them yet, but there is definitely more to be done along the lines of prerequisite content. Also, I'm not sure what level of mathematics you are studying right now, but if you're interested, a great textbook for all the prerequisites of graph theory would be "Discrete Mathematics" by Susanna Epp, it's a very good introduction to logic, sets, functions, combinatorics, (a whole bunch of other concepts too) and also has a section introducing graph theory. If you want to get into the math that graph operations, such as graph products, are built from, see the book "A Book of Abstract Algebra" by Pinter, that book is fantastic and if you like graph products you will quickly see the relevance to graph theory while reading it.

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

​@@VitalSine TH-cam 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

@@VitalSine TH-cam 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.

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

It would be possible for a fractional coloring where we allow for sets of a different number of colors to be used on each vertex, but it would not be under the category of a b-fold coloring. The b-fold chromatic number of the complete graph on 2 vertices would be 2*b.

Hi, great question. If the intersection is more than 1 vertex, in the line graph e_1 and e_2 are still made adjacent. The definition of adjacency in a line graph only requires that the edges share at least one incident vertex.

Very interesting thoughts! I agree that hypergraphs are useful in describing graph transformations. Another interesting thing to think about is how we can generalize graph transformations, and since you mentioned graph powers, I think it's that we can combine the graph k-th power and the simplex graph operation to give us a generalization of the simplex graph, where two cliques are adjacent when they differ by the addition/deletion of k vertices.

Sure thing, here it is: drive.google.com/file/d/1MBhqmHa6rgg1q0xqze4llHf_PXhNLSo1/view?usp=sharing

Great question. The difference is in the adjacency rules. All three products take two graphs, G and H, as input, and all three products output a graph whose vertex set is the set cartesian product of the vertex sets of G and H. In the graph cartesian product, the vertices (u, v) and (u', v') are adjacent if either u = u' and v is adjacent to v', OR u is adjacent to u' and v = v'. That is the adjacency rule for cartesian products. In the strong product, the vertices (u, v) and (u', v') are adjacent if either u = u' and v is adjacent to v', OR u is adjacent to u' and v = v', OR u is adjacent to u' and v is adjacent to v'. It is the same as cartesian product but with one extra condition (the last one). In the lexicographic product, the vertices (u, v) and (u', v') are adjacent if either u = u' and v is adjacent to v', OR if u is adjacent to u' (regardless of the relationship between v and v'). The lexicographic product will generally be the most dense of the three. Hope this helps!

You're very welcome, and interesting question! If I understand correctly, the sets of vertices that make up an (intersection with 3+ vertices) of hyperedges in your original hypergraph become your new hyperedges, and the vertices of the new hypergraph are still the same as the vertices of the original hypergraph?

@@VitalSine Yes exactly!

​@@pswjt1266 Hello again! I looked around but could not find anything matching the operation you described, but this is similar and may be of interest: arxiv.org/abs/1901.06292 I think you could perform their "edge intersection hypergraph" operation and then weakly delete any edges with exactly 2 vertices to get the same result as your new operation, except you would miss all of the submaximal intersecting sets of vertices of size 3+ present in your original hypergraph.

​@@VitalSine This does indeed seem close to what I have in mind! Thank you so much!

@@pswjt1266 You're very welcome, and thank you for sharing this new operation with me.

Most welcome!

You are very welcome! I wish you success with your PhD.

I'm very glad to hear that!

Glad it helped!

Glad it helped!

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: th-cam.com/video/N_tJo3XwY-M/w-d-xo.htmlsi=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!

Hello, I'm not familiar with that concept, sorry. However, it does look interesting from what I've read since searching for it online!

Very cool video :) I do share @darklordvadermort intuition concerning the relevance of percolation measures in HNSW (as a tool for optimisation of vector database). Indeed, the more "percolative" is a node in a knowledge graph, the more it will have an impact on the efficiency of query, and the more it will help to find a nearest neighbor. Could be a very interesting topic though !

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

@@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!

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

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]}.

I do not have any videos on cluster hypergraphs yet, but I will see if I can make some new videos about them 👍

Great question! For larger n, you could use an algorithm to generate a list of integer partitions, convert to the m_i and step through the list, plugging each element into the formula and summing. This link has some information on creating a list of integer partitions: stackoverflow.com/questions/400794/generating-the-partitions-of-a-number

I'm happy to hear you enjoyed the hypergraph videos. Good catch, that was a mistake on my part, v_4 should connect to e_1 in the bipartite graph.