What is the most interesting graph you've ever come across?
Interesting in the sense of shape of the graph, or properties (edges, vertices, faces).
Posted Sep 18, 2020, 2:56 AM UTC
Interesting in the sense of shape of the graph, or properties (edges, vertices, faces).
Posted Sep 18, 2020, 2:56 AM UTC
The null graph. It's the only acyclic graph with the same number of edges as vertices, and it's the only graph with a constant chromatic polynomial!
I love this paper, I even own a physical copy of a book that includes it. It’s also got the greatest figure ever published, which is a blank image captioned ‘the null graph’.
Gah, I don’t have institutional access.
I often refuse to say anything is the "the most ___" because I simply don't rank things like that, but put a gun to my head and it's the Petersen graph, any day. I don't even care it's the most obvious or vanilla answer.
It comes up so many places, in so many weird ways. It's the "projective" dodecahedron, it's hidden in the E8 lattice, if you draw it as a unit distance graph it has a bunch of golden ratios in it. The list goes on.
It's also connected to a lot of other really interesting particular graphs.
I also am fascinated by the Moore graph problem. The only known k-regular graphs with diameter 2, girth 5, and k^2 +1 vertices are the 5-cycle, and the Petersen graph, and the Hoffman-Singleton graph, and their unique (up to isomorphism) with respect to these properties. Hoffman and Singleton proved the only possibilities are {2,3,7,57}, so 57 is still open. We haven't been able to build such a graph, and we haven't shown it's impossible.
I have an almost numerlogy-crank belief that this problem is tied to deep and interesting geometric structures, though not all my madness is unjustified.
EDIT: Typo
Well that was a really fun rabbit hole. All I have under my belt is a 1 semester graph theory course, but is it just me or does that hypothetical graph seem almost obtainable. Diameter 2 and order 3250? Sign me and my supercomputer up
Speaking of 57, have you ever counted the 5-cycles in the Petersen graph?
The Petersen graph is interesting.
I probably wouldn't say most interesting, but rather the most aesthetic ones I've ever come across are the Turán graphs. They are so satisfying to look at.
That being said, they are also very interesting and extremal graph theory has some of my favourite graph theoretical proofs.
The Moore graph of girth 5 and degree 57, because it's not even known if such a graph exists! Get on it people
Hey, I'm trying.
Stern-Brocot tree. Couldn't find a good picture of it, but it comes from the Farey sequence which is more visually appealing.
any erdos-reyni model i guess. so stupid simple but it's the basis of statistics on graphs
for those who don't know, an erdos-reyni model is a random (undirected) graph with n nodes where any two nodes have a probability p of have an edge between them. the two mathematicians worked out a lot of the necessary axioms and theorems for random graph theory using this simple framework
on its own it's not very useful for modeling real world data but it is (of course) a special case of more general models that are useful like the stochastic block model
I love Lissajou patterns
Not that type of graph.
Thanks for the Wiki-ish disambiguation 😀
Paley graphs are so satisfying to look at.
And their connection to algebra is pretty awesome as well
[deleted]
The Rado graph is definitely my favorite, but someone else already posted it. Another cool one is the Frucht graph, a 3-regular graph with no nontrivial symmetries. You can identify any vertex in the graph just by it's location in the overall structure.
Two: the complete graph K5 and the complete bipartite graph K3,3, because Kuratowski's theorem says that these are important for deciding if an arbitrary graph is planar. Specifically, a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 or K3,3.
I have no idea what it's called, but the smallest graph whose automorphism group is trivial has six vertices, and looks like:
* --- * --- * --- * --- *
\ /
*
Most graphs have nontrivial automorphisms, so this one's a little bit special.
The Shrikhande Graph!
The n by n rooks graph is strongly regular with certain parameters, that depend on n. These parameters are uniquely attained by the rooks graph for all n except 4. When n=4, the parameters admit two graphs: the 4x4 rooks graph and the Shrikhande graph.
f(x) = x
The graph of zeta fuction.
The Rado graph (https://en.m.wikipedia.org/wiki/Rado_graph). In a sense (made precise on the Wikipedia page) it has every property that almost all (100%) of the finite graphs have.
This is really cool! I assume that when you generate this graph randomly that (with prob 1) any two constructions are graph isomorphic?
If I remember correctly, it has a property that I think is even stronger (though I might be wrong and it doesn't imply this). That property is that if you remove any finite number of vertices from the Rado graph, the resulting graph is isomorphic to it with probability 1.
The Rado graph is the unique countable graph satisfying the property
E_n,m: For any vertices x_1,...,x_n,y_1,...,y_m, such that non of the x_i are equal to any of the y_j, there is a vertex v, such that there is an edge between x_i and v for all i, and there is no edge between v and any of the y_1
for all n and m. This will basically allow you to easily construct isomorphisms by a back and forth argument. Further, the nice property u/inversegalois mentioned directly follows from this: For fixed n,m, a random graph satisfies E_n,m with probability 1. If the Rado graph satisfies some property then, by the completeness theorem, that property must be provably from the E_n,m, but every prove can only use finitely many of those axioms and, therefore, the property must already follow from one particular E_n,m for sufficiently large n and m.
it is not finite, so you are missing a property.
He never said it was finite. The Rado graph apparently has the property that if it satisfies a first order formula then almost all finite graphs satisfy that formula (and likewise if it doesn't satisfy that formula). That's what he's talking about
being finite is a property, but it was a joke my dude
Oh shit, I'm dumb lmao. To be fair, iirc finiteness isn't a first order property.
[deleted]