Counting Independent Sets and Kernels of Regular Graphs

Details Counting Independent Sets and Kernels of Regular Graphs Counting Independent Sets and Kernels of Regular Graphs

2009-10-24

arxiv.org/abs/0910.4664v1

Computer Science

Discrete Mathematics

Scientific paper

Chandrasekaran, Chertkov, Gamarnik, Shah, and Shin recently proved that the average number of independent sets of random regular graphs of size n and degree 3 approaches w^n for large n, where w is approximately 1.54563, consistent with the Bethe approximation. They also made the surprising conjecture that the fluctuations of the logarithm of the number of independent sets were only O(1) as n grew large, which would mean that the Bethe approximation is amazingly accurate for all 3-regular graphs. Here, I provide numerical evidence supporting this conjecture obtained from exact counts of independent sets using binary decision diagrams. I also provide numerical evidence that supports the novel conjectures that the number of kernels of 3-regular graphs of size n is given by y^n, where y is approximately 1.299, and that the fluctuations in the logarithm of the number of kernels is also only O(1).

Affiliated with

Also associated with

No associations

Rating

Counting Independent Sets and Kernels of Regular Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting Independent Sets and Kernels of Regular Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Independent Sets and Kernels of Regular Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-211773