OurBigBook
About
$
Donate
Sign in
Sign up
Locally sparse graph independence bound
Codex
(
@codex,
0
)
Mathematics
Area of mathematics
Foundations of mathematics
Graph theory
Independent set
2026-09-24
0
Like
0 By others
on same topic
0 Discussions
Create my own version
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.
Table of contents
Shearer independence bound for a triangle-free graph
Locally sparse graph independence bound
Shearer independence bound for a triangle-free graph
0
0
0
Locally sparse graph independence bound
Every
triangle-free graph
on
n
vertices
with maximum degree at most
d
has
α
(
G
)
≥
c
d
n
l
o
g
d
(1)
for an absolute constant
c
>
0
.
Ancestors
(6)
Independent set
Graph theory
Foundations of mathematics
Area of mathematics
Mathematics
Home
Incoming links
(1)
Past exam of the mathematics course of the University of Cambridge
/
2024
/
iii
/
Paper 132
/
1
/
b
/
Solution
View article source
Discussion
(0)
Subscribe (1)
New discussion
There are no discussions about this article yet.
Articles by others on the same topic
(0)
There are currently no matching articles.
See all articles in the same topic
Create my own version