-1
$\begingroup$

On the set $[n]:= \{1,\ldots,n\}$ we consider the set $${\cal P}_2([n]) = \big\{\{a,b\}: a,b \in [n], a\neq b\big\}.$$ Since $$|{\cal P}_2([n])| =2^{n \choose 2}$$ there are exactly $2^{n\choose 2}$ graphs on $n$ points.

We set the clique number $\omega(G)$ to be the largest $n$ such that the complete graph $K_n$ is a subgraph of $G$. For $n \geq 1$, let $$R_n = \{ G = ([n], E): E\in {\cal P}_2([n]) \text{ and } \omega(G) = \chi(G)\},$$ and set $q_n = \frac{R_n}{2^{n\choose 2}}$.

Does $\lim_{n\to\infty} q_n$ exist, and is its value equal to $1$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Is your notation slightly off? It looks like $\mathcal P_2([n])$ is just the set of pairs from $[n]$. In any case, a random graph has clique number $\log n$ and chromatic number $n/\log n$ (up to constants) with high probability, so $q_n \to 0$. $\endgroup$
    – Ben Barber
    Commented Nov 20, 2015 at 15:10
  • $\begingroup$ That's right, I intended ${\cal P}_2([n])$ to be the set of (unordered) pair sets from $[n]$. What's the standard notation? And thanks for your argument -> could you post it as an answer? $\endgroup$
    – Dominic van der Zypen
    Commented Nov 20, 2015 at 15:33

2 Answers 2

Reset to default
6
$\begingroup$

I would say that this limit is zero. Most of the graphs on $n$ vertices have $\sim n^2/4$ edges. For such graph, the expected number of complete subgraphs of size $k\sim2\log_2n$ is $$ {n\choose k}\cdot \frac1{2^{k\choose 2}}\approx C\left(\frac{ne}{k2^{(k-1)/2}}\right)^k\to 0. $$ So most of our graphs have $\omega(G)\lesssim 2\log_2n$. Their complements $G^c$ also have $\sim n^2/4$ edges, and the same estimate for $\omega(G^c)$ holds. This means that most of such graphs have $\chi(G)\gtrsim n/(2\log_2n)$.

Improve this answer
$\endgroup$
3
$\begingroup$

As @Ilya says, the limit is zero due to the asymptotic size of maximum cliques/independent sets. However, there is another way to see this using endomorphisms (homomorphisms from a graph to itself).

It is known that asymptotically almost surely the endomorphism monoid of any graph contains only the identity map. However, any graph with $\omega(G) = \chi(G)$ has an endomorphism to a maximum clique, which is clearly not an identity map. Therefore, the proportion of graphs with clique and chromatic number equal must go to zero asymptotically.

The proof of the result about the endomorphism monoid of graphs is in "Graphs and Homomorphisms" by Hell and Nesetril. I'm not sure if that is the original source though.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .