6 comments

• 

  Mike Malone

  1 year ago

  Awesome post Jesse. I'm very interested in using computers to work on this sort of problem, but my math background is a little weak (at least compared to yours). I think one of the biggest stumbling blocks to understanding complex mathematics is the notation. There are similar problems in almost every field/industry, but the notation and lingo in math is both powerful and complex. If you don't understand all of the notation, you have absolutely no hope of understanding the equation. Oftentimes when a complex equation is explained to me in simple English (I know that's often tough to do) it becomes incredibly obvious and simple to understand.
  
  I look forward to the rest of this series of posts. I really enjoy reading your blog man, keep up the good work! Another area I'd love to see you write about that's also closely related to set theory is neural networks and other learning algorithms. Particularly as they apply to collaborative filtering. I think there's huge potential in collaborative filtering for web 2.0ish websites, but there are few sites that are really focused on the problem (perhaps because it's very complicated).
  
  Also, one completely unrelated side note: I was at Facebook a few days ago and they all knew of you/your blog! Your reputation precedes you =p.
  reply
• 

  Jesse

  1 year ago

  Mike,
  
  Glad to hear people at Facebook know my name! Too bad they didn't want to hire me. :P
  reply
• 

  Andy

  1 year ago

  I think you wanted to say
  "Vertices could be cities and edges could be interstate highways."
  instead of
  "Edges could be cities and edges could be interstate highways."
  reply
• 

  grant

  1 year ago

  I have a question about what you might, I suppose, call transitivity. For example, consider the last image of a graph in your post. Could you say there is an edge E(v1,v2) since there is a path from v1 to v2 via v3?
  
  Perhaps you could write E(v1, v3, v2), which might reduce to E(v1, v2)?
  
  I hope you understand what I'm trying to ask...(also, I'm sorry to ask an elementary question. you're not here to teach math. I'm trying to find an answer to it myself right now.)
  reply
• 

  Jesse

  1 year ago

  grant,
  
  You'd say there is a path from v₁ to v₂, but not that there is an edge between them. IOW, the edge relationship is not necessary transitive. In fact, the edge set doesn't even need to be represented by ordered pairs, so it's not even necessarily a "relation" in the strict mathematical sense of the word, e.g., you might have multiple edges between two vertices.
  
  Most people mean "simple graph" when they say graph, so these "pathological" cases (i.e., loops, multiple edges, etc.) are excluded from the outset.
  
  That said, if you have a graph G = (V,E) you could define another graph G' = (V,E') whose edge relationship is v ~ w iff there is a path between v and w in G.
  
  I'm not sure this is a very interesting graph, though. You'd basically take the connected components of G and turn them into complete graphs. So G' is always a disjoint union of some number of complete graphs. I don't think it tells you anything particularly useful about G.
  
  Hope that helps.
  
  - Jesse
  reply
• 

  grant

  1 year ago

  That helps a bunch, thanks.
  reply