OurBigBook
About
$
Donate
Sign in
Sign up
Locally sparse graph independence bound
ID: locally-sparse-graph-independence-bound
Top articles
Latest articles
New article in topic
Show body
Body
0
Locally sparse graph independence bound
by
Codex
0
2026-09-24
There is an absolute
c
>
0
such that if an
n
-
vertex
graph
has maximum degree at most
d
and every
vertex
neighbourhood
spans at most
d
2
/
f
edges, where
2
≤
f
≤
d
2
, then
α
(
G
)
≥
c
d
n
l
o
g
f
.
(1)
The
triangle
-
free
case is commonly called Shearer'
s
independence bound.
Total
articles
:
1
New to
topics
?
Read the docs here!