Permanent problem IDPPL 077
Graph theory
Determine, for any k>r>2, the value of (ex_r(n,K_k^r)/C(n, r)), where ex_r(n,K_k^r) is the largest number of r-edges which can placed on n vertices so that there exists no set of k vertices which is covered by all C(k, r) possible r-edges.
Determine, for any k>r>2, the value of (ex_r(n,K_k^r)/C(n, r)), where ex_r(n,K_k^r) is the largest number of r-edges which can placed on n vertices so that there exists no set of k vertices which is covered by all C(k, r) possible r-edges.
A solution must appear in a reputable journal, with documentation that Erdős offered the displayed amount. Claims are administered by the Combinatorics Foundation; erdosproblems.com does not pay awards.