Algebraic Graph Theory Seminar - Lord KaviExport this event to calendar

Monday, July 5, 2021 — 11:30 AM EDT

Title: The $k$-Independence Number

Speaker: Lord Kavi
Affiliation: University of Ottawa
Zoom: Contact Soffia Arnadottir

Abstract:

An independent set, also known as a stable set or coclique, in a graph is a set of vertices, no two of which are adjacent. The size of a largest independent set is called the independence number. Two classical eigenvalue bounds on the independence number, proved using eigenvalue interlacing are the Hoffman's ratio bound and the Cvetkovi\'{c}'s inertia bound. There are a number of generalizations of the notion of independence set of a graph; of interest to us is the following. A $k$-independent set in a graph is a set of vertices such that any two vertices in the set are at distance at least $k+1$ in the graph. The $k$-independence number of a graph, denoted $\alpha_k$, is the size of a largest $k$-independent set in the graph.
Using interlacing, Abiad et al generalized the Hoffman and Cvetkovi\'{c}  spectral bounds on $k$-independence, which involves taking polynomials of degree at most $k$. A good bound therefore depends on making the right choice of a polynomial. For the generalized Hoffman bound for $\alpha_k$, the polynomial $p(x)=x$ gives the standard Hoffman bound for the independence number $\alpha_1$. Abiad et al also gave the right choice of polynomial for $k=2$ and proposed a polynomial for a general $k$. This polynomial, however, is often not the best choice. Finding an appropriate polynomial that yields the best bound possible for any $k\geq 3$ is still an open problem. In this talk, we present the best polynomial for the case $k=3.$

Event tags 

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
  1. 2022 (143)
    1. December (1)
    2. November (18)
    3. October (15)
    4. September (11)
    5. August (2)
    6. July (17)
    7. June (17)
    8. May (10)
    9. April (12)
    10. March (18)
    11. February (10)
    12. January (13)
  2. 2021 (103)
    1. December (3)
    2. November (7)
    3. October (6)
    4. September (12)
    5. August (6)
    6. July (10)
    7. June (12)
    8. May (7)
    9. April (9)
    10. March (13)
    11. February (8)
    12. January (10)
  3. 2020 (119)
  4. 2019 (167)
  5. 2018 (136)
  6. 2017 (103)
  7. 2016 (137)
  8. 2015 (136)
  9. 2014 (88)
  10. 2013 (48)
  11. 2012 (39)
  12. 2011 (36)
    1. December (2)
    2. November (3)
    3. October (2)
    4. September (3)
    5. August (1)
    6. July (4)
    7. June (5)
    8. May (3)
    9. April (4)
    10. March (3)
    11. February (4)
    12. January (2)
  13. 2010 (40)
  14. 2009 (40)
  15. 2008 (39)
  16. 2007 (15)