3 ms·

Can someone explain why we care so much about graphs in various branches of science? Like, why model the problems mentioned in the video as graphs that need to

Can someone explain why we care so much about graphs in various branches of science? Like, why model the problems mentioned in the video as graphs that need to be colored?

teraflop 2y ago
It's not so much that we want to model problems as graphs, it's that many problems and situations naturally correspond to graphs. Anything with a collection of objects, where some subset of pairs of objects are "related" to each other, is a graph. In mathematical terms, graphs are essentially the same as binary relations on a set (a generalization of functions). And any time you can think of something as a graph, you can benefit from the wealth of available mathematical and computational tools that apply to all graphs.
- eru 2y ago
  Graphs are also really simple structures mathematically. After all, an (undirected) graph is nothing more than a ground set and a collection of its two-element subsets. It's the same reason why groups crop up so often: groups are also really simple structures, so it's really easy to satisfy their axioms 'by accident'. Same for numbers in general.
  - whatshisface 2y ago
    I don't think that's a full explanation for groups, because groups other than the free or permutation groups are rather "unlikely," in the sense that they're much smaller.
    - eru 2y ago
      Oh, I mean they crop up in lots and lots of applications, because their structure is so simple to satisfy. Not that they would crop up, if you somehow randomly generated mathematical structure. The real world, and especially the part of the real world that people engage with, seems to have a lot of simple structures.
- ForTheKidz 2y ago
  Graphs don't really capture the entirety of hashmaps and other indexing concerns. Other than that yea I agree.
  - magicalhippo 2y ago
    GP was talking about modelling your problem. A hashmap is seldom a good model for a given problem. Typically they're "just" an implementation detail. For example, in some cases it can be useful to consider triangles in a 3D model as cyclic graphs of vertices. The edges of the triangle correspond to the edges in the graph. However I can't think of any case where it's useful to think of a triangle as a hashmap.
jon_richards 2y ago
There is a huge category of computer science problems that can be solved with the same algorithm (and a conversion). Graph coloring is probably the easiest of those problems to explain.
Ar-Curunir 2y ago
Because in this case we have a relatively simple ZKP for 3-coloring. However what you gain in the simplicity of the ZKP, you lose in the reduction to 3-coloring. So nowadays people use ZKPs that work with more realistic computation representations, like arithmetic circuits
jrndcnfh 2y ago
Not sure if I grasp your question. It's like asking "why do we care about lists or any data structure for that matter" Graphs are just a very simple generalization of lists. And many problems can be easily modelled as graphs
carra 2y ago
I'd say this was done mainly to help visualize the problems better, since this is a learning video. But often problems are converted into graphs because it is a well studied field and that way you can apply many theorems and traversal algorithms.

Can someone explain why we care so much about graphs in various branches of science? Like, why model the problems mentioned in the video as graphs that need to be colored?

teraflop 2y ago

It's not so much that we want to model problems as graphs, it's that many problems and situations naturally correspond to graphs. Anything with a collection of objects, where some subset of pairs of objects are "related" to each other, is a graph. In mathematical terms, graphs are essentially the same as binary relations on a set (a generalization of functions). And any time you can think of something as a graph, you can benefit from the wealth of available mathematical and computational tools that apply to all graphs.

eru 2y ago
Graphs are also really simple structures mathematically. After all, an (undirected) graph is nothing more than a ground set and a collection of its two-element subsets. It's the same reason why groups crop up so often: groups are also really simple structures, so it's really easy to satisfy their axioms 'by accident'. Same for numbers in general.
- whatshisface 2y ago
  I don't think that's a full explanation for groups, because groups other than the free or permutation groups are rather "unlikely," in the sense that they're much smaller.
  - eru 2y ago
    Oh, I mean they crop up in lots and lots of applications, because their structure is so simple to satisfy. Not that they would crop up, if you somehow randomly generated mathematical structure. The real world, and especially the part of the real world that people engage with, seems to have a lot of simple structures.
ForTheKidz 2y ago
Graphs don't really capture the entirety of hashmaps and other indexing concerns. Other than that yea I agree.
- magicalhippo 2y ago
  GP was talking about modelling your problem. A hashmap is seldom a good model for a given problem. Typically they're "just" an implementation detail. For example, in some cases it can be useful to consider triangles in a 3D model as cyclic graphs of vertices. The edges of the triangle correspond to the edges in the graph. However I can't think of any case where it's useful to think of a triangle as a hashmap.

jon_richards 2y ago

There is a huge category of computer science problems that can be solved with the same algorithm (and a conversion). Graph coloring is probably the easiest of those problems to explain.

Ar-Curunir 2y ago

Because in this case we have a relatively simple ZKP for 3-coloring. However what you gain in the simplicity of the ZKP, you lose in the reduction to 3-coloring. So nowadays people use ZKPs that work with more realistic computation representations, like arithmetic circuits

jrndcnfh 2y ago

Not sure if I grasp your question. It's like asking "why do we care about lists or any data structure for that matter" Graphs are just a very simple generalization of lists. And many problems can be easily modelled as graphs

carra 2y ago

I'd say this was done mainly to help visualize the problems better, since this is a learning video. But often problems are converted into graphs because it is a well studied field and that way you can apply many theorems and traversal algorithms.