Counting independent sets in triangle-free graphs

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

Ajtai, Koml\'os, and Szemer\'edi proved that for sufficiently large $t$ every triangle-free graph with $n$ vertices and average degree $t$ has an independent set of size at least $\frac{n}{100t}\log{t}$. We extend this by proving that the number of independent sets in such a graph is at least \[ 2^{(1/2400)\frac{n}{t}\log^2{t}}. \] This result is sharp for infinitely many $t,n$ apart from the constant. An easy consequence of our result is that there exists $c'>0$ such that every $n$-vertex triangle-free graph has at least \[ 2^{c'\sqrt n \log n} \] independent sets. We conjecture that the exponent above can be improved to $\sqrt{n}(\log{n})^{3/2}$. This would be sharp by the celebrated result of Kim which shows that the Ramsey number $R(3,k)$ has order of magnitude $k^2/\log k$.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Counting independent sets in triangle-free 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 in triangle-free graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting independent sets in triangle-free graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-67906

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.