Task: Prove that there is no strict order on 14 elements in which there are exactly 50 pairs of adjacent elements.
Some clarifications: Elements x, y of order (X, <) are adjacent if x < y and there is no z such that x < z < y.
My thinking: (in this text: pair of adjacent elements = adjacent pair) In fact, the maximum number of adjacent pairs that we can get on 14 elements is 49. Let's build a bipartite graph in which both parts consist of 7 elements. As a result, this will give us 7 * 7 = 49 adjacent pairs. Bipartite graphs where there is not the same number of elements in each part are not suitable for us: 6 * 8 = 48, 5 * 9 = 45, etc., all these cases will give less than 49 pairs of adjacent elements.
But I have a problem: I can’t strictly prove that the maximum number of adjacent pairs that we can get will be exactly 49. I need to prove that besides a bipartite graph with 7 elements in each part, there is no other option for implementing strict partial order so that it reaches >= 49 adjacent pairs.
(in this text: pair of adjacent elements = adjacent pair)
In general, there is such a theorem or statement that tells us that any strict partial order corresponds to a graph H, which will be acyclic (it was proven on lectures in my university, you can also find this on the Internet). In essence, a strict order is a strict partial order, but with the additional property of linearity. Well, there is another theorem here that any graph is a bipartite graph if and only if all cycles of this graph are of even length. And since an acyclic graph corresponds to a strict partial order, and in it all cycles have length 0, and since 0 is an even number, we can already call this graph bipartite, because it satisfies all the conditions.
Now we translate all 14 elements of the original order into 14 vertices of a bipartite graph. An adjacent pair of elements in order in graph terms would mean two such distinct vertices that are the ends of one edge. It turns out that vertices from one partition connected by an edge to a vertex from another partition will form an adjacent pair. It turns out that the number of edges in a bipartite graph will be equal to the number of adjacent pairs in order. But we know that the maximum number of edges in a bipartite graph will be equal to the product of a and b, where a and b are the number of vertices in two partitions of a bipartite graph.
We get the function f(x) = x(x-14) -> here we actually count the maximum number of edges in a bipartite graph depending on the number of vertices in one of the partitions. Here is a very simple calculus, it is very simply proved that for this function the global maximum of the function is reached at the point x = 7 => f(7) = 49. It turns out that 49 is the maximum number of edges in a bipartite graph or the maximum number of adjacent pairs of elements in the original strict order on 14 elements.
We found that regardless of whether our strict order is linear or not, in both cases the maximum possible number of adjacent pairs will be 49. Finally: 49 < 50, therefore there is no such strict order on 14 elements that will have 50 adjacent pairs. Which was exactly what needed to be proved.
This task can also be solved using Turan's theorem.