First of all to avoid misunderstanding i am going to describe what will i call a algorithm in my graph-theoretic problem.
- algorithm is a set of pairs, where first coordinate is natural number - a number of step. The second coordinate is a instruction - it tells which edge schould be marked.
Let: $n,k$ are natural numbers, $A=K_{n}$ is a complete graph, $\mathbb{B}$ is a set of all $k$-cliques in $A$. And $f(X)$ is a measure such counts how many marked edges are in graph $X$
Let $$L=\max_{a\in \mathbb{B}}f(a)$$
The algorithm that is interesting is determined by the following:
- At each step it choose new $k$-clique in $A$ and marks some edge of that clique so that $L$ would be as small as possible.
Finally:
After how many steps algorithm will be finished? I mean : when all $k$-cliques will have at least one marked edge? Let denote that number of steps as a $F(n,k)$.
I tried to solve this problem by finding a reccurence formula for $F(n,k)$, but i can not find.
Here is my related question:Special algorithm related to complete graph.
But it asks about something different however i am fascinated with problems including cliques.
If someone will show me at least one small hint, i will be grateful anyway.
Regards.
Hint / Ideas
Your algorithm is not fully deterministic, because at each step, the choice of which clique, and in particular the choice of which edge in the chosen clique to mark, might matter...
Anyway, the "global" solution is known: the Turan graph has the max number of edges under the constraint being free of $k$-cliques. In your context this means you need to mark at least as many edges to reduce the initial $K_n$ to become the Turan graph, i.e. this gives a lower bound on the number of marked edges. However, whether your algorithm (which is not only not fully determined, but also "greedy" in a sense) can achieve this lower bound is unclear.