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$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.