วีดีโอ

No worries, I hope the following can help you: Geodesic means shortest path between two points. The two terms are completely equivalent, so when I said geodesic between vertices u and v for instance, it just means to take the shortest path between u and v. Let me know if that helps enough, or if there was anything else unclear I'd be glad to provide further clarification.

Hmm, that's a great question. The k-th strong product has applications to information theory, see: en.wikipedia.org/wiki/Shannon_capacity_of_a_graph. A communications channel can be represented by a (confusion) graph whose vertices are the elements of your alphabet, adjacent when they can be confused for each other. Independent sets are codewords that cannot be confused for each other, and k-th product powers and limits of product powers come into the definition of Shannon capacity.

@@VitalSine Thank you for the response. If a unweighted undirected graph G is given as an adjacency matrix A, then B=A^k ( boolean matrix multiplication performed k times over A) has 1 for B[u][v], if there is a path of length at most k , between u and v. Is there something similar to infer from this kth strong product or cartesian product or tensor product?

​@@jvarunkumar Yes, there is a similar insight from kth strong product in the information theory example. The independence number of the kth strong product, is the maximum number of codewords of length k formed from your alphabet (vertices in the initial graph) that you can use without confusion. This is all using the interpretation of a vertex in the k-th strong product as a codeword of length k from the alphabet = vertices of the initial graph. Good question for cartesian/tensor products. Nothing comes to mind right now regarding applications of the k-th product power for cartesian/tensor products, but I'm sure there could be applications similar to the Shannon capacity example for strong products. Something to think about is that k-th product powers are about relating tuples of vertices to each other, so if you have some objects (ex. an alphabet of symbols), some way those objects are related together (ex. symbols that can be confused for each other are "related") and a way of "concatenating" those objects (ex. concatenation of symbols to form codewords), then a k-th product power could make sense in that application for describing how concatenations relate to each other (ex. how codewords of length > 1 can be confused with each other). The strong product adjacency rules encode the way that length-k codewords being confused for each other works (sharing some symbols in the same positions and having the rest of the positions with symbols different but confusable with each other). Cartesian/tensor product don't encode that, instead the Cartesian product encodes: (one position has symbols confusable with each other, the rest of the positions have the same symbols) , and Tensor product encodes (all positions have symbols different but confusable with each other).

@@jvarunkumar A paper you may be interested in, it discusses an application of cartesian product powers: arxiv.org/abs/1506.08564

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 !