An Introduction to Graph Theory | Hacker News Reader

An Introduction to Graph Theory

arxiv.org

255 pointsAnon8426 comments

I navigated to the course site and turns out the professor directly links to pirated copies of comprehensive sources on libgen. Thought it was pretty funny that he doesn't care about copyright being a professor at a public university :-). The linked sites are down since the main site libgen.rs is down but if you know libgen you know how to get to other places.

https://www.cip.ifi.lmu.de/~grinberg/t/22s/

Usually people don't explicitly post links to libgen in their public website, but the vast majority of mathematicians makes ample use of libgen and sci-hub without thinking twice

shhh

I pose this question as an industrial mathematics practitioner who does not specialize in graph theory: are there specific classes of problems that are only solvable (or best solved) using graph theory? AFAIK, from computation perspective, graph problems are often recasted into linear algebra, in which you have tools of both analysis and algebra. What are some results from graph theory that engender unique insights?

Data is often stored in structures which are based on graphs. And searching within these data structures does not nicely reduce to linear algebra. For instance, I don't think there is any nice way of reducing binary search to linear algebra.

binary search is essentially an algorithm to find zeros, which is just algebra/analysis.

I suppose it depends what you mean by graph theory without linear algebra. Graphs can be represented as matrices without losing anything, so as such you can go from graphs to matrices and do everything you would do with graphs alone.

For describing algorithms sticking with just the notion of graphs is convenient however, as it allows you to speak of edges, nodes, colours etc. keeping things easier to grasp.

Also, there are notions such as planar graphs which probably don't have a nice interpretation in the linear algebra point of view only.

I have been working with homology theory applies to planar graphs this month. A procedure for which I could not see a nice compact algorithm in just graph theory terms reduced to simple matrix multiplication with the help of homology.

I'm certainly not saying linear algebra is useless with planar graphs.

It really depends on what is meant by graph theory vs. linear algebra here. If GT means we can fix an embedding to the space, then we have additional information such as number of crossings. However, it seems like a bit arbitrary restriction.

Pathfinding algorithms?

P.s. what does being an industrial mathematician involve? Sounds like a role I would have dreamed about in undergrad.

Maybe program optimization?

https://egraphs-good.github.io/

Addendum: many algorithms book describe algorithmic solutions to a multitude of graph problems without linear algebra at all, like connected components, network flow, shortest paths, etc, etc

Network flow optimization and its many particular cases (bipartite matching, transportation problem, nonintersecting paths) are usually defined in terms of directed graphs with arc weights. You can package the arc capacities as a matrix, but you don't do the usual matrix things with it (like multiplying matrices, Gaussian elimination, QR, SVD), except perhaps if you do your matrix algebra over the tropical semiring (but that's often graph theory by another name). So you need new methods even if you shoehorn the problems into matrix language.

Hi, generationP! Excuse me for the unrelated question but it may be the only way to ask you. I've found you comment from a while ago: https://news.ycombinator.com/item?id=30316156 Could you tell a little bit more about thing named "Plato"? It is more a history question and I cannot find any references in the Internet about it. If you are more comfortable with private messages, I can be reached at ultranymous at proton dot me

I know very little about it. I referred to it as "Plato" only because it used to show a picture of Plato sitting on a rock when it downloaded a new paper into its library. My guess is that it used someone's donated account to do that.

Tropical semiring looks fascinating. Link for the curious: https://www.wikiwand.com/en/Tropical_geometry

I think graph theory is undoubtedly one of the most important subjects for anyone working in the field of computer software. Speaking of which, back in university I made a website [1] that allows you to interactively draw graphs and animate a few algorithms on them, as my design project. Doesn't have a lot going for it feature-wise (no directed edges, no weights, just a few algorithms) but it was a fun project to work on. [2]

[1] https://ahmetsait.com/interactive-graph-theory/

[2] https://github.com/ahmetsait/interactive-graph-theory

That was quite fun and a very satisfying experience on mobile! It would definitely be a good base to expand on for further demos.

Thanks! I'm really happy to hear that since we tried to make drawing as user friendly as possible and spent some extra time on touch screen support. I had this vision in my mind where the discrete math lecturer would show a QR code (links to my website) on the screen and students would be able to fiddle with graphs and see all those things they learn interactively right there on their phone which.. could make the class more distracting or more engaging depending on how you look, but I liked the idea.

Thanks for sharing the introduction, I find this topic really interesting & previously had the thought that I would love to just download it to my brain. (Unfortunately I couldn't find any sites or open directories with the correct .zip file)

So, in case it's helpful to anybody else, I asked ChatGPT to help me explore a bit of graph theory based on my experience with mind mapping:

> I am used to making mind maps. What are some concepts related to mind maps that might help me expand into graph theory? What about the fact that there's always this central node? Is there counter-theory? Is there a name for this type of graph, and are there associated weaknesses and strengths?

This turned into a really fascinating discussion of sorts, based on quickly identifying and remedying some early gaps in what I know about graph theory. It was a lot of fun.

Voting this up for a spirit of curiosity and learning while having fun

Talking with the matrices, you sometimes get made up nonsense or overly verbose trite answers, but I think it's really valuable having a conversation partner with infinite patience for explaining things, and an almost accurate memory of just about anything you might find on en.wikipedia.org

You do have to be careful and to spot check any fact with other sources, but where I find it's great is helping understand complicated or abstract concepts. Having an actual conversation can be so much more efficient that banging your head against the dry definition until it starts to make sense. Anyone who's tried reading math articles on Wikipedia as a layperson and ended 15 tabs deep into very abstract foundational definitions (like "closed" and "open" sets, along with the eternal gift upon the world that is the world "clopen".)

So having a large pile of numbers standing by can genuinely make learning math a lot more fun, and it's one of the few topics where there is a provable right and wrong, so you'll notice pretty quickly if you're being fed contradictory nonsense

Thanks, it's already useful in seeing how a more normalized mind map would be really cool given my normal mind mapping activities.

That made me want to find a data-focused mapping API, start building & connecting nodes, and...wait a minute, what about just a database ;-) But sticking with mind-maps and a locally-scoped enhancement to the practice, instead of "let's completely jump concepts, mind maps are just a cheap DB" is really fascinating in its own way.

The new "Custom Instructions" for ChatGPT are pretty neat here, kinda similar to your pile of numbers, because I asked it what e.g. "fostering connections" meant in context, and it gave me a deep example based on one of my career fields. That led me to a really interesting back & forth regarding how to exploit the concept of betweenness centrality.

> I think it's really valuable having a conversation partner with infinite patience for explaining things

This is what keeps me coming back. So much knowledge is just unapproachable because of the domain-specific semantics used, even in introductory/help contexts. From the opening text of the man page for "cat," arguably the most basic command in Linux:

> By default, sparse SOURCE files are detected by a crude heuristic and the corresponding DEST file is made sparse as well. That is the behavior selected by --sparse=auto. Specify --sparse=always to create a sparse DEST file whenever the SOURCE file contains a long enough sequence of zero bytes. Use --sparse=never to inhibit creation of sparse files.

I've been using Linux for 20 years and have no idea what the fuck any of this means. Slapping an "ELI5" prefix on it and feeding it to GPT makes this stuff intelligible, even if it's wrong (for unfamiliar concepts about not-code, I'll ask the same question three different ways and see if/how much it differs).

I know a bit of graph theory, followed some courses at the university and worked on some graph problems [1], but the third definition in the book for 'n-th coprimality graph' was something I had never heard about. Then I also noticed that the author takes the natural numbers as the edges of his graph definition, which I think is not a common approach [2]

[1] https://www.iwriteiam.nl/counting.html

[2] https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#G...

The author is using the usual definition where vertices are an arbitrary (finite) set and edges are pairs of vertices. From the book:

Definition 2.1.1. A simple graph is a pair (V, E), where V is a finite set, and where E is a subset of P_2(V).

Sure in some examples V happens to be a set of natural numbers and then edges must be pairs if natural numbers, but there's nothing weird with that as any set would do. (Incidentally in model theory countably infinite graphs are often assumed to have as underlying set the naturals because it is convenient notationwise)

I agree, I am wrong, I comment too soon, not noticing that these were examples, not definitions.

Nah, those edges are not natural numbers, at least not until multigraphs (whose edges can be anything, including natural numbers, though they rarely are). You might have missed the convention to write the edge {i,j} as ij.

Reply on news.ycombinator.com