Range Avoidance

Let \(f\) be a function mapping binary strings of length \(m\) to strings of length \(n\) with \(n>m\). Since there are more strings of length \(n\) than \(m\), \(f\) is not onto. Can you find a string not in the range? This is known as the range avoidance problems, or AVOID for short Let's do an example. Consider \(f\) that outputs an undirected graph on \(n\) nodes and takes as input:\(n\)A set \(S\) of \(k\) vertices \(v_1,\ldots,v_k\)For each \(i\) and \(j\), \(i<j\), where at least one of \(i\) and \(j\) are not in \(S\), whether or not there is an edge between \(i\) and \(j\).A bit \(b\)If \(b=1\) output the graph \(G\) which consists of the given edges plus a clique on \(S\). If \(b=0\) the same but an independent set on \(S\).For an appropriate choice of \(k\), about \(2 \log n\), the output of \(f\) is longer than the input. Any graph not in the range is a Ramsey graph, i.e., no clique or independent set of size \(k\).You can use AVOID to capture other probabilistic method…