Speaker:

Cris Moore

Title:

Rational marginals and maximal independent sets

Abstract:

For each vertex v in G(n,p=c/n), there is some probability mu_v that v is contained in a uniformly chosen maximal independent set. In other words, mu_v is the marginal probability that v is occupied in the Gibbs measure on independent sets in the limit of large fugacity \lambda.

I conjecture that there is a transition at c* = (1/sqrt(2)) e^(1/sqrt(2)) = 1.434... such that, if c < c*, then with high probability mu_v is rational, while for c > c* with positive probability mu_v is irrational. To be more precise, let q_m be the large-n limit of the probability, in G and v, that mu_v is rational with denominator m. I claim that \lim_{m \to \infty} q_m = 1 for c < c*, but that this limit is bounded below 1 if c > c*.

The reason for this conjecture is that, for c < c*, branching process arguments suggest that with high probability mu_v depends only on v's neighborhood within a constant number of steps, while if c > c* it depends, with probability bounded above zero, on vertices arbitrarily far away. Analytically, if we apply belief propagation with fugacity \lambda,

1-mu_v = 1 / (1+\lambda prod_{neighbors u} (1-mu_u)) ,

then in the limit of large lambda, the equilibrium distribution of mu is a bunch of delta functions at rational values for c < c*, while for c > c* I believe there is a continuous part of the distribution. Even proving this analytic conjecture would be interesting in its own right; we understand marginals on d-regular trees completely, but on Poisson random trees the situation is much more complicated.