1
$\begingroup$

Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ so that $(v_i,u_i)$ is an edge in $G.$

The book Fractional Graph Theory by Scheinerman and Ullman has a number of wonderful results connecting graph theory to fractional graph theory, some of them having a flavor illustrated by the following result:

If $\chi(G), \chi_f(G)$ are the chromatic number and fractional chromatic number of a graph respectively, then

$$\chi_f(G) = \lim_{n\to\infty} \chi(G^n)^{\frac 1n}.$$

I am interested in the rate of convergence in this and other results of this kind. What can we say about how fast the sequence

$$\log \chi_f(G) - \frac 1n \log\chi(G^n)$$

goes to zero? I suspect it goes as $\frac{1}{\sqrt{n}}.$ If this is true, then what is

$$\limsup_n \sqrt{n}\left(\log \chi_f(G) - \frac 1n \log\chi(G^n)\right)?$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.