Earlier today when I was looking for potential correspondences between Interval Graph Theory [1] and Flow Graph Theory [2] (Reducible Flow Graphs), I happened upon this 2017 blog post and paper [3] by Jacob Steinhardt: "Does Pigeonhole Degrade Gracefully?"...
The celebrated pigeonhole principle says...
If we have disjoint sets S_1, S_2, ..., S_m subsets in [n]
each of size s, then m (the number of sets) is at most [n/s].
Suppose that instead of being disjoint, we require that every
pair of sets has intersection at most 1. How much can this
change the maximum number of sets m? Is it still roughly n/s,
or could the number be much larger?
Interestingly, it turns out that there is a sharp phase
transition at s = √n .
[3] Does robustness imply tractability? A lower bound for planted clique in the semi-random model (2018) - Jacob Steinhardt, Stanford https://arxiv.org/pdf/1704.05120.pdf
[1] Interval (graph theory) https://en.wikipedia.org/wiki/Interval_(graph_theory)
[2] Flow Graph Theory http://infolab.stanford.edu/~ullman/dragon/w06/lectures/dfa3...
[3] Does robustness imply tractability? A lower bound for planted clique in the semi-random model (2018) - Jacob Steinhardt, Stanford https://arxiv.org/pdf/1704.05120.pdf