There is a complete graph $K_{n}$ and natural number $k:k<n$.
My goal is to study marked edges.
Let:
- $f(G)$ is a set of marked edges of graph $G$
- $\mathbb{A}$ is a set of $k$-cliques in $K_{n}$
- algorithm in this case is a finite set of steps. In every step we mark some new edge.
- $AL$ is a set of algorithms such they mark at least one edge of every $k$-clique
I would like to calculate: $$X=min\{|f(K_{n})|:max\{A_{i}\in \mathbb{A}:|f(A_{i})|\}={k\choose2},f(K_{n})\in AL\}$$
It may seems familiar to the following:
$Y=min\{|f(K_{n})|:max\{A_{i}\in \mathbb{A}:|f(A_{i})|\}={k\choose2}\}=|E(T(n,k-1))|+1$
The term of the right side of equation is cardinatlity of set of edges of Turan's graph.
Is it possible to colearate $X$ and $Y$?
I have an idea to take techniques from theory of condinational extremum and use it in discrete world. Also it seems useful to study how Turan figured out his idea with maximalisation edges in graph. Do you know such PDF-s?
Finally i suspect that the best algorithm such satisfy these conditions is following.
- Mark maximal independent set of edges.
- Mark next edges so that number of cliques already marked would by minimalised.
Regards.