The city of Mathlandia has $10$ politicians. Let $S$ denote the set containing all $\dbinom{10}{4}$ possible groups of $4$ of politicians.
Denote a subset, $M$, of $S$, as special if no two elements of $4$ politicians in $M$ share $3$ politicians. For example, if we label the politicians, $1, 2, 3, \cdots, 10$, then the subset: $\{ (1, 2, 3, 4), (2, 3, 5, 6) \}$ is special but the subset $\{(1, 3, 4, 10), (1, 3, 6, 9), (2, 3, 4, 10) \}$ is not because elements $1$ and $3$ share $3, 4, 10$.
What is the maximal size of a special subset?
My Understanding
This problem is similar to this: Largest set of 4 digit codes that do not share 3 digits
However, what makes it different is that the digit $0$ is not allowed, order does not matter, and we cannot put the same number twice in a set of $4$ politicians (we need $4$ distinct politicians).
Due to these distinctions, I was unable to use Mike Earnest's solution to the linked problem. Does anyone know how to solve it?
How could we generalize for $n$ politicians? Is there some clean combinatorial method?
My Current Idea for Solution: Why Is this Wrong?
There are $\dbinom{10}{3} = 120$ sets of $3$ politicians.
Each set of $4$ politicians in $M$ contains $4$ different of $3$ politicians. So, the total number of sets of $4$ must be $\frac{120}{4} = 30$.
I checked this via a Java code and saw that the answer of $30$ is incorrect: it should actually be $18$.
Furthermore, if we try another number instead of $10$, for example $6$, this solution gives $5$ sets of $4$. However, the maximal amount of sets is $3$ : $$(1234), (1256), (3456)$$
For $n = 5$, we don't even get an integer. We get $2.5$. What incorrect assuption is this solution making?
You observed that the four subsets of size $3$ derived from each subset of size four must be distinct from one another. This means that if $30$ sets were attainable, they would have to consist of all $4\cdot 30=120$ subsets of size $3$ exactly once. Therefore, you would need what is called a Steiner quadruple system (SQS) of order $10$. Fortunately, Steiner quadruple systems of order $n$ exist precisely when $n\equiv 2$ or $4\pmod 6$, so you can achieve $30$ sets.
It seems that constructing SQS's is a complicated matter, based on the abstract of this paper: A new existence proof for Steiner quadruple systems. However, in your case, you can find the $30$ sets of size four in the La Jolla covering repository: Covering design C(10, 4, 3). A covering design is more general then a Steiner system, but in this case they are the same.
What you are looking for is also known as a constant weight binary code with length $10$, weight $4$, and distance $4$. To translate this to the language of coding theory, you view subsets of $\{1,\dots,10\}$ of size $4$ as binary strings of length $10$ with $4$ ones. The condition that no two subsets share $3$ elements is equivalent to saying any two strings differ in at least four places, hence the distance of $4$.
In general, the number of strings in a code of length $n$, weight $w$, and distance $d=2e$ is at most $$ \left\lfloor \frac{n}{w}\left\lfloor \frac{n-1}{w-1}\cdots \left\lfloor \frac{n-w+e}{e}\right\rfloor\cdots\right\rfloor\right\rfloor $$ This is the Johnson bound. For length $n$, size $4$ and weight $4$, this bound is certainly achievable when $n\equiv 2,4$ by a Steiner system of order $n$. There are lots of ad hoc ways to construct codes like this, you can find more codes and known upper bounds on Andries Brouwer's website.