Yesterday I cycled to work and was struck by the number of e-bikes passing me. I grumbled to myself: does everyone bike electrical nowadays? Can’t they move forward on their own? When I arrived at work and complained about this with my colleagues, they appeared to experience the same problem: while they ride normal bikes themselves, they observe more e-bikes. That is weird. Why do there seem to be more people biking on regular bikes (at least among my colleagues), but do I see around me mostly e-bikes? How do I know whether what I see is a good representation of reality?
We can see all those people as nodes (points) in a network. The edges (connections) between the nodes in the network are determined by who meets who. Since I am not connected to everyone in the network (I don’t meet everyone), I cannot see all nodes of the network. I see only my direct neighbors in the network: the people that I meet. We can think of many different kinds of such networks between people. For example: a friendship network, in which two nodes (people) are connected if they are friends. Or the network of people living in a village, where two people are neighbors if they are actually neighbors in real life. Some of such networks have inherent randomness, like the network of people running into each other in a morning commute.
The people in the network in the example, which we call for now the ‘bicycle-network’, all ride normal bikes or e-bikes. I only saw people cycling on e-bikes. Translated to the network: my neighbors in the network are mostly e-bikers.
Because I only saw e-bikes, I assumed that the majority of all people in the bicycle-network ride an e-bike. Talking to my colleagues about their bikes, however, leads me to believe that this assumption is wrong. Suppose that it is proven, perhaps by someone counting somewhere along the bicycle path, that the majority of people use a regular, non-electric, bike. Then my assumption that there is a majority of e-bikers is an illusion! We say I am under majority illusion.
An example graph in which the node marked "me" is under majority illusion
This term is used when someone observes a wrong majority. For example, when the people on your office floor drink only tea but actually most of your colleagues prefer coffee. Or when you see only young people in your neighborhood but there are actually more old people in the village.
This phenomenon can occur in different gradations and for different reasons. Can you think of a logical reason why, in my example, I saw many e-bikers, even though the majority of people ride a normal bike?
I think that the reason for my misobservation is that I cycle slower than e-bikes tend to do, so they surpass me a lot. Normal bikes are more likely to cycle the same speed as me, so I don’t meet them as often. This causes my bicycle-network to contain mainly e-bikers as my direct neighbors, while in the entire bike-population there might be more regular bikes. Likewise, I am probably not the only one under majority illusion regarding bike types. I know I’m not, since I asked my colleagues. In fact, since many old-fashioned cyclists experience the same illusion, and there are many old-fashioned cyclists, it might be the case that a majority of people in the network are under majority illusion, in which case we have a Majority-majority illusion!
But wait. This is kind of strange, right? When there are more people of a certain type, or having a certain trait, or with a certain opinion, is it really possible that a majority of people observes a majority of the opposite type/trait/opinion?
The answer is: it depends. On the network.
Consider the very simple network below:
Can you assign bike types in such a way that most of the nodes observe the wrong majority? Or, since it is sometimes easier to talk about colors than about bike types: Can you color it with two colors in such a way that most nodes see a wrong majority color?
We can, for example like this:
Both normal bikes (blue) see only an e-bike (red), so they think there are more normal bikes, while in fact they form a majority themselves.
And what about this network?
And this one?
In this last case we can’t. All possible ways to color it (assign bike types) are the following (and the ones we get by rotating or mirroring the following), in which most nodes see the correct majority, or at least a tie.
In these example networks, it is quite easy to just try all possibilities to find out whether it is possible or not to color the network in such a way that a majority of people observe a wrong majority. However, you can imagine that in larger and more complex networks, it takes you a lot of time to try out all possibilities. At this point, you would probably expect me to give you a clever trick that tells us for larger networks whether it is possible or not to color them in such a Majority-majority illusion, but I have to disappoint you. Unfortunately, some very smart people who tried exactly this found out that this is a very hard problem.1
However, there is something odd about the two middle examples above. Let’s have a closer look at this one:
Even though no one is completely wrong about the majority, the two people with normal bikes are also not really correct about the majority. They see just as many normal bikes as e-bikes, while there are actually more normal bikes. This ‘not seeing the correct majority’, we call a weak majority illusion. Just as with the normal majority illusion, we could ask ourselves whether it is possible to assign bike types, or colors, to a given network such that most nodes are under weak majority illusion. And, surprise, this problem is not hard! Actually, we can prove that on any network, however complicated or large you make it, it is possible to assign colors to the nodes such that most nodes do not observe the correct majority.
Statement: On all networks it is possible to color the nodes such that a majority of nodes see a wrong majority. That is: if the true majority is blue, most nodes see red or tie, and if the true majority is red, most nodes see blue or tie. Furthermore, if there is an actual tie, most nodes see a majority of red or blue.
To prove this statement, we need some ingredients. First, we have to define some terms.
A monochromatic edge is an edge between two nodes of the same color:
A weak majority 2-coloring of a network is a coloring where all nodes have a majority of neighbors of the opposite color, or a tie among the neighbors.
Then, we need another small statement that will help us prove the main statement, a Lemma.
Lemma: Any coloring of a network that minimizes the number of monochromatic edges in the network is a ‘weak majority 2-coloring’
That means: if you have a network:
And you color it such that it is not possible to color it with less monochromatic edges, for instance as follows:
(It has one monochromatic edge here, and I bet you cannot color it with less than one monochromatic edge, try it out.)
Then, all nodes have a majority of neighbors of the other color than the node itself, or a tie among the neighbors (as you can check).
I will not prove the Lemma here, but you could potentially check out the proof in this paper. Now we have all ingredients for the proof of the main statement.
Proof. We take a network, let’s call it (for Network…). We do not assume anything about the nodes or connections in , since we want to prove something about all networks, and not only about one specific one. Now, color with red and blue such that the number of monochromatic edges is minimal. Because of our Lemma, we know that this coloring is a ‘weak majority 2-coloring’.
The rest of the proof consists of two cases: one where there is a red or blue majority among all nodes, and one where there is a tie. Let’s start with the case where there is a red or blue majority. We assume for now that it is blue, if you prefer it red just swap the words ‘blue’ and ‘red’ everywhere.
Case 1: There is a blue majority.
Then, because the coloring was a ‘weak majority 2-coloring’, all blue nodes see either more red nodes, or a tie. Oh, but that means they do not see the correct blue majority. And, since there was a blue majority, this is the case for a majority of nodes. Hence, we already arrived at our goal: a majority of nodes see a wrong majority.
Case 2: There are as many red as blue nodes in N.
This case consists of two subcases.
Case 2a: most nodes do not see a tie.
Then, since there is a global tie but most nodes do not see a tie, most nodes see a wrong majority already.
Case 2b: at least half of the nodes do see a tie.
In this case, at least half of the nodes correctly see that there is a tie, so it is not yet the case that most nodes see an incorrect majority. But we can easily make this the case: we pick one node that sees a tie, and swap its color.
Since we started with an equal number of red and blue nodes but swapped the color of one node, we do not have a global tie anymore. However, swapping the color of a node with an equal number of red and blue neighbors does not change the number of monochromatic edges (convince yourself). Therefore, the new coloring has the same number of monochromatic edges as the previous coloring: the minimum number possible in . This means, according to our Lemma, that also this new coloring is a ‘weak majority 2-coloring’. Therefore, we are back in Case 1: we have a weak majority 2-coloring with more blue than red nodes (or more red than blue but then we just swap the names of the colors in the proof). And therefore, the same logic applies and also in this case a majority of nodes see a wrong majority.
In all cases (indeed, case 1, 2a, and 2b are all possible cases), we showed that there is a way to color the nodes such that a majority of nodes sees a wrong majority, which proves our statement.
Also, although the original Majority-majority illusion problem is hard in general, there are some types of networks where it is easy to see how to color them such that a majority of nodes see a (true) wrong majority. Take for example a network where you can divide the nodes into two groups, such that there are only links between the groups and not within the groups, like this:
In mathematics, we call such a network properly two-colorable. In such properly two-colorable networks, we can just give all the people in the largest group a normal bike and all the people in the smallest group an e-bike. Then, everyone in the largest group (with normal bikes) will see only people from the other group (with e-bikes), since there were no links within each group. They will observe that there are more people with e-bikes, meaning they are under majority illusion! And since this group of people with normal bikes is a majority, there is a Majority-majority illusion in this network.
At this point, you might think: “Very interesting, and nice little puzzles, but why should I care? I didn’t really mind that I saw so many e-bikes,” or even worse, if you ride an e-bike yourself: “I could have told you that there are more old-fashioned bicycles, I overtake them all the time!”. Well, for the theory it does not matter what the colors mean. They can refer to bikes and e-bikes, coffee and tea, red and blue, old and young, or left-wing and right-wing. And especially this last example shows why majority illusions can be relevant for society. If you are surrounded by people with some political opinion A, then you might think that opinion A is indeed very popular. This, in turn, might influence your own political choices. However, we just learned that seeing many people with opinion A does not necessarily mean that opinion A is indeed the majority opinion. And hence, in case of majority illusion you might base your political choices on incorrect information.
Then, how likely is it actually that I am in majority illusion with respect to a relevant topic such as political opinions? Unfortunately, that is hard to say. We have evidence that on some types of large random networks with random colorings, majority illusions are very unlikely2, but real social networks are not exactly like such random graphs, and not ‘colored’ randomly. There is, therefore, a lot we can still discover about majority illusions and their relevance for our daily life.
For now, the main point is to be aware of the existence of majority illusions, and to take into account that what you observe might not be a good representation of reality. A nice thing to discuss with your colleagues when you cycle to work together.
The scientific world would not be what it is today without normal distribution. It is the foundation of many statistical models for several good reasons. Most importantly, it appears commonly in nature. But this is only the tip of the iceberg.
A conjecture of Erdős and Hajnal from 1989 says that forbidding any specific substructure results in existence of a very large homogeneous one! In this article you will have a look into one of the most fascinating problems in modern graph theory.
If, after reading the title, your immediate response is to shout "1/6-th", then you have correctly answered the question. Well done! However, in this article we will focus on the meaning of this question. What exactly is this "chance" of which you've just exclaimed it equals 1/6-th?
Have you ever found yourself less popular when compared to your friends? Interestingly, in any group of individuals, on average, people have fewer friends than their friends do, or at the very most, an equal number. Not more!
(for Network…). We do not assume anything about the nodes or connections in 
