Problem 500 — Visual explainer (undergrad)
==========================================

Problem statement
---------------
What is $\mathrm{ex}_3(n,K_4^3)$? That is, the largest number of $3$-edges which can placed on $n$ vertices so that there exists no $K_4^3$, a set of 4 vertices which is covered by all 4 possible $3$-edges.

Picture
-------
Graph picture:

o---o
|\  |
| \ |
o---o    K4 is the complete graph on 4 vertices (all connections)

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Benchmarks / known results (from comments)
----------------------------------------
- Tur\'{a}n observed that dividing the vertices into three equal parts
  $X_1,X_2,X_3$, and taking the edges to be those triples that either have
  exactly one vertex in each part or two vertices in $X_i$ and one vertex in
  $X_{i+1}$ (where $X_4=X_1$) shows
  that\[\mathrm{ex}_3(n,K_4^3)\geq\left(\frac{5}{9}+o(1)\right)\binom{n}{3}.\]This
  is probably the truth.
- The current best upper bound is\[\mathrm{ex}_3(n,K_4^3)\leq
  0.5611666\binom{n}{3},\]due to Razborov.