Hang on… is graph theory literally just the theory of binary relations? That’s crazy general.
I guess if you have an undirected graph, then the binary relation is symmetric. And if you have labeled edges, it’s a binary operation. And if you don’t allow self-loops, it’s anti-reflexive, etc.
But perhaps the main thing that makes it not so general in practice is that graph theory is largely concerned with paths. I guess paths are like… if you close the binary relation under its own composition? Then you’ve generated the “is connected to” relation.
A graph is a concept with an attitude, i.e. a graph (V, E) is simply a set V with a binary relation E but you call this a graph to emphasize a specific way of thinking about it.
Definition 1. Let I be the set of all people and a,b∈I. Define the relation “♡” by
a♡b⟺a loves b.
Remark 2. There are many mutually equivalent definitions for the notion “a loves b”. Invent and prove equivalent definitions.[1]
Remark 3. “♡” is not an equivalence relation.
Proof. It would suffice to observe the lack of reflexivity, symmetry, or transitivity, but we’ll do them all to highlight how difficult a relation we’re dealing with.
Not reflexive: Clearly “a/♡/a” for some self-destructive a∈I.
Not symmetric: From a♡b it does not necessarily follow that b♡a. Think about it.
Not transitive: From a♡b and b♡c does not follow that a♡c, since if it did, nearly all of us would be bisexual. □
Remark 4. The lack of transitivity also implies that the relation “♡” is not an order.
For it to work well in practice, the relation “♡” would need at least symmetry and transitivity. Reflexivity is not necessary, but a rather desirable property. However, as is common in mathematics, we can forget practice and study partitions of sets via the relation. We soon notice that the lack of symmetry allows very different kinds of sets.
2. Inward-Warming Sets
We begin our investigation by looking at inward-warming sets. Then we can restrict ourselves to sets whose size is greater than two. To simplify definitions we assume that no one loves themselves. In other words, we silently assume that everyone loves themselves, so it can be left unmarked separately.
Convention 5. From now on, assume A⊂I and #A≥3, unless otherwise stated. Also assume that for all a∈A we have a/♡a.
If the notation in this section feels complicated, read Section 3 and then take another look. Drawing pictures often helps. In mathematics it’s really just about representing complicated things with simple notations—whose understanding nonetheless requires several years of study.
Definition 6. We say that a set A is
1. inward-warming if, for
B=b∈I:∃a∈Awitha≠banda♡b,
we have A∩B≠∅.
2. strongly inward-warming if the set
B=b∈I:∃a∈Awitha≠banda♡b
is a nonempty subset of A.
3. together if for every a∈A there exists b∈A with a♡b and a≠b, and in addition the set
B=b∈I:∃a∈Awitha≠banda♡b
is a subset of A.
4. a hippie commune if for all a,b∈A we have a♡b.
Remark 7. i) A set that is together is strongly inward-warming. Conversely, a strongly inward-warming set is inward-warming. ii) In a hippie commune, the relation “♡” is an equivalence relation.
3. Basic Notions
The definitions in the previous section admittedly look a bit complicated. For that we develop a bit of terminology:
Convention 8. From now on, also assume a,b∈A with a≠b, unless otherwise stated.
Definition 9. We say that a is, in the set A,
cold if there is no b∈A with a♡b.
lonely if there is no b∈A with b♡a.
popular if there exists b∈A with b♡a.
warm if there exists b∈A with a♡b.
a recluse if it is cold and lonely in A.
a player if it is popular and warm in A.
a slut if there exist b,c∈A with b≠c and a♡b as well as a♡c.
a hippie if a♡b for all b∈A.
loyal in A if there exists exactly one b∈A with a♡b. Then we say that a is loyal to b.
b’s partner in A if a♡b and b♡a. Then (a,b) is called a couple, and A contains a couple. The couple (a,b) is a strong couple in A if a is loyal to b in A and b is loyal to a in A.
Remark 10. Every hippie is a slut.
Using these definitions, we can rewrite the earlier concepts:
Theorem 11. A set A is
inward-warming if and only if there exists at least one a∈A that is warm in A.
strongly inward-warming if every a∈A is cold in I∖A and there exists at least one a∈A that is warm in A.
together if every a∈A is warm in A and cold in I∖A.
a hippie commune if (a,b) is a couple in A for all a,b∈A.
Proof. Exercise. □
[...]
7. Connection to Graph Theory
It becomes easier to visualize different sets when the relationships between elements are represented as graphs. We call the elements of the set the vertices of the graph and say that there is an edge between vertices a and bb if a♡b. Since “♡” is not symmetric, the graphs become directed. Thus we draw the set’s elements as points and edges as arrows. In the situation a♡b, we draw an arrow from vertex a to vertex b. Figure 1 shows a simple situation where a loves b, and Figure 2 shows the definitions from Section 3 and a few more complicated situations.
Convention 28. We will henceforth call the graphs formed via ♡ simply graphs.
[...]
8. Graph Colorings, Genders, and Hetero-ness
In many cases it is helpful for visualization to color the vertices of graphs so that “neighbors” always differ in color. Since blue is the boys’ color and red the girls’ color, we want to color graphs with only two colors.
Definition 33. A vertex b is a neighbor of a vertex a if a♡b.
Definition 34. A vertex a∈G is hetero if all its neighbors are of a different gender than a. A pair (a,b) is a hetero couple if a and b are of different genders.
Definition 35. A graph G is a rainbow if it contains a vertex that is not hetero.
Remark 36. The name “rainbow” comes from the fact that a rainbow graph cannot be colored with two colors so that neighbors always differ in color.
Definition 37. A path (from a1 to an) in a graph G is an ordered set {a1,…,an} whose elements satisfy ai♡ai+1 or ai+1♡ai for all i=1,2,…,n−1. The path is a cycle if a1=an. The length of a path/cycle is n.
Theorem 38. If a graph contains a cycle of odd length, it contains a vertex that is not hetero.
Yep, that all sounds right. In fact, a directed graph can be called transitive if… well, take a guess. And k-uniform hypergraphs (edit: not k-regular, that’s different) correspond to k-ary relations.
Here’s another thought for you: Adjacency matrices. There’s a one-to-one correspondence between matrices and edge-weighted directed graphs. So large chunks of graph theory could, in principle, be described using matrices alone. We only choose not to do that out of pragmatism.
(I’ve also heard of something even more general called matroid theory. Sadly, I never took the time to learn about it.)
Graphs studied in graph theory are usually more sparsely connected than those studied in binary relations.
Also I have a not-too-relevant nerd snipe for you: You have a trillion bitstrings of length 1536 bits each, which you must classify them into a million buckets of approximately a million vectors each. Given a query bitstring, you must be able to identify a small number of buckets (let’s say 10 buckets) that contain most of its neighbours. Distance between two bitstrings is their Hamming distance.
At a certain point, graph theory starts to include more material—planar graph properties, then graph embeddings in general. I haven’t ever heard someone talking about a ‘planar binary relation’.
Hang on… is graph theory literally just the theory of binary relations? That’s crazy general.
I guess if you have an undirected graph, then the binary relation is symmetric. And if you have labeled edges, it’s a binary operation. And if you don’t allow self-loops, it’s anti-reflexive, etc.
But perhaps the main thing that makes it not so general in practice is that graph theory is largely concerned with paths. I guess paths are like… if you close the binary relation under its own composition? Then you’ve generated the “is connected to” relation.
Does that all sound right?
A graph is a concept with an attitude, i.e. a graph (V, E) is simply a set V with a binary relation E but you call this a graph to emphasize a specific way of thinking about it.
Ooh, I love this.
Reminds me of the classic “Rakkaus matemaattisena relaationa” (Love as a mathematical relation).
Partial English translation by GPT-5
1. The Love Relation
Definition 1. Let I be the set of all people and a,b∈I. Define the relation “♡” by
a♡b⟺a loves b.
Remark 2. There are many mutually equivalent definitions for the notion “a loves b”. Invent and prove equivalent definitions.[1]
Remark 3. “♡” is not an equivalence relation.
Proof. It would suffice to observe the lack of reflexivity, symmetry, or transitivity, but we’ll do them all to highlight how difficult a relation we’re dealing with.
Not reflexive: Clearly “a/♡/a” for some self-destructive a∈I.
Not symmetric: From a♡b it does not necessarily follow that b♡a. Think about it.
Not transitive: From a♡b and b♡c does not follow that a♡c, since if it did, nearly all of us would be bisexual. □
Remark 4. The lack of transitivity also implies that the relation “♡” is not an order.
For it to work well in practice, the relation “♡” would need at least symmetry and transitivity. Reflexivity is not necessary, but a rather desirable property. However, as is common in mathematics, we can forget practice and study partitions of sets via the relation. We soon notice that the lack of symmetry allows very different kinds of sets.
2. Inward-Warming Sets
We begin our investigation by looking at inward-warming sets. Then we can restrict ourselves to sets whose size is greater than two. To simplify definitions we assume that no one loves themselves. In other words, we silently assume that everyone loves themselves, so it can be left unmarked separately.
Convention 5. From now on, assume A⊂I and #A≥3, unless otherwise stated. Also assume that for all a∈A we have a/♡a.
If the notation in this section feels complicated, read Section 3 and then take another look. Drawing pictures often helps. In mathematics it’s really just about representing complicated things with simple notations—whose understanding nonetheless requires several years of study.
Definition 6. We say that a set A is
1. inward-warming if, for
B=b∈I:∃a∈A with a≠b and a♡b,
we have A∩B≠∅.
2. strongly inward-warming if the set
B=b∈I:∃a∈A with a≠b and a♡b
is a nonempty subset of A.
3. together if for every a∈A there exists b∈A with a♡b and a≠b, and in addition the set
B=b∈I:∃a∈A with a≠b and a♡b
is a subset of A.
4. a hippie commune if for all a,b∈A we have a♡b.
Remark 7.
i) A set that is together is strongly inward-warming. Conversely, a strongly inward-warming set is inward-warming.
ii) In a hippie commune, the relation “♡” is an equivalence relation.
3. Basic Notions
The definitions in the previous section admittedly look a bit complicated. For that we develop a bit of terminology:
Convention 8. From now on, also assume a,b∈A with a≠b, unless otherwise stated.
Definition 9. We say that a is, in the set A,
cold if there is no b∈A with a♡b.
lonely if there is no b∈A with b♡a.
popular if there exists b∈A with b♡a.
warm if there exists b∈A with a♡b.
a recluse if it is cold and lonely in A.
a player if it is popular and warm in A.
a slut if there exist b,c∈A with b≠c and a♡b as well as a♡c.
a hippie if a♡b for all b∈A.
loyal in A if there exists exactly one b∈A with a♡b. Then we say that a is loyal to b.
b’s partner in A if a♡b and b♡a. Then (a,b) is called a couple, and A contains a couple. The couple (a,b) is a strong couple in A if a is loyal to b in A and b is loyal to a in A.
Remark 10. Every hippie is a slut.
Using these definitions, we can rewrite the earlier concepts:
Theorem 11. A set A is
inward-warming if and only if there exists at least one a∈A that is warm in A.
strongly inward-warming if every a∈A is cold in I∖A and there exists at least one a∈A that is warm in A.
together if every a∈A is warm in A and cold in I∖A.
a hippie commune if (a,b) is a couple in A for all a,b∈A.
Proof. Exercise. □
[...]
7. Connection to Graph Theory
It becomes easier to visualize different sets when the relationships between elements are represented as graphs. We call the elements of the set the vertices of the graph and say that there is an edge between vertices a and bb if a♡b. Since “♡” is not symmetric, the graphs become directed. Thus we draw the set’s elements as points and edges as arrows. In the situation a♡b, we draw an arrow from vertex a to vertex b. Figure 1 shows a simple situation where a loves b, and Figure 2 shows the definitions from Section 3 and a few more complicated situations.
Convention 28. We will henceforth call the graphs formed via ♡ simply graphs.
[...]
8. Graph Colorings, Genders, and Hetero-ness
In many cases it is helpful for visualization to color the vertices of graphs so that “neighbors” always differ in color. Since blue is the boys’ color and red the girls’ color, we want to color graphs with only two colors.
Definition 33. A vertex b is a neighbor of a vertex a if a♡b.
Definition 34. A vertex a∈G is hetero if all its neighbors are of a different gender than a. A pair (a,b) is a hetero couple if a and b are of different genders.
Definition 35. A graph G is a rainbow if it contains a vertex that is not hetero.
Remark 36. The name “rainbow” comes from the fact that a rainbow graph cannot be colored with two colors so that neighbors always differ in color.
Definition 37. A path (from a1 to an) in a graph G is an ordered set {a1,…,an} whose elements satisfy ai♡ai+1 or ai+1♡ai for all i=1,2,…,n−1. The path is a cycle if a1=an. The length of a path/cycle is n.
Theorem 38. If a graph contains a cycle of odd length, it contains a vertex that is not hetero.
Proof. Exercise.
Hint: Help can be sought from rock lyrics or lager beer.
Yes, pretty much it. Concern with path-connectedness is equivalent to considering the transitive closure of the relation.
Yep, that all sounds right. In fact, a directed graph can be called transitive if… well, take a guess. And k-uniform hypergraphs (edit: not k-regular, that’s different) correspond to k-ary relations.
Here’s another thought for you: Adjacency matrices. There’s a one-to-one correspondence between matrices and edge-weighted directed graphs. So large chunks of graph theory could, in principle, be described using matrices alone. We only choose not to do that out of pragmatism.
(I’ve also heard of something even more general called matroid theory. Sadly, I never took the time to learn about it.)
And then when we do that, its called spectral graph theory, and its the origin of many clustering algorithms among other things.
Graphs studied in graph theory are usually more sparsely connected than those studied in binary relations.
Also I have a not-too-relevant nerd snipe for you: You have a trillion bitstrings of length 1536 bits each, which you must classify them into a million buckets of approximately a million vectors each. Given a query bitstring, you must be able to identify a small number of buckets (let’s say 10 buckets) that contain most of its neighbours. Distance between two bitstrings is their Hamming distance.
At a certain point, graph theory starts to include more material—planar graph properties, then graph embeddings in general. I haven’t ever heard someone talking about a ‘planar binary relation’.