Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Independence complexes of claw-free graphs
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
2008 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 29, no 1, 234-241 p.Article in journal (Refereed) Published
Abstract [en]

We study the class of independence complexes of claw-free graphs. The main theorem gives good bounds on the connectivity of these complexes, given bounds for a few subcomplexes of the same class. Two applications are presented. Firstly, we show that the independence complex of a claw-free graph with n vertices and maximal degree d is (cn/d + epsilon)-connected, where c = 2/3. This can be compared with the result of Szabo and Tardos that c = 1/2 is optimal with no restrictions on the graphs. Secondly, we calculate the connectivity of a family of complexes used in Babson and Kozlov's proof of the Lovasz conjecture.

Place, publisher, year, edition, pages
2008. Vol. 29, no 1, 234-241 p.
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-10371DOI: 10.1016/j.ejc.2006.09.007ISI: 000251166600022Scopus ID: 2-s2.0-35548987051OAI: oai:DiVA.org:kth-10371DiVA: diva2:216351
Note
QC 20100712Available from: 2009-05-08 Created: 2009-05-08 Last updated: 2017-12-13Bibliographically approved
In thesis
1. Topological Combinatorics
Open this publication in new window or tab >>Topological Combinatorics
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis on Topological Combinatorics contains 7 papers. All of them but paper Bare published before.In paper A we prove that!i dim ˜Hi(Ind(G);Q) ! |Ind(G[D])| for any graph G andits independence complex Ind(G), under the condition that G\D is a forest. We then use acorrespondence between the ground states with i+1 fermions of a supersymmetric latticemodel on G and ˜Hi(Ind(G);Q) to deal with some questions from theoretical physics.In paper B we generalize the topological Tverberg theorem. Call a graph on the samevertex set as a (d + 1)(q − 1)-simplex a (d, q)-Tverberg graph if for any map from thesimplex to Rd there are disjoint faces F1, F2, . . . , Fq whose images intersect and no twoadjacent vertices of the graph are in the same face. We prove that if d # 1, q # 2 is aprime power, and G is a graph on (d+1)(q −1)+1 vertices such that its maximal degreeD satisfy D(D + 1) < q, then G is a (d, q)–Tverberg graph. It was earlier known that thedisjoint unions of small complete graphs, paths, and cycles are Tverberg graphs.In paper C we study the connectivity of independence complexes. If G is a graphon n vertices with maximal degree d, then it is known that its independence complex is(cn/d + !)–connected with c = 1/2. We prove that if G is claw-free then c # 2/3.In paper D we study when complexes of directed trees are shellable and how one canglue together independence complexes for finding their homotopy type.In paper E we prove a conjecture by Björner arising in the study of simplicial polytopes.The face vector and the g–vector are related by a linear transformation. We prove thatthis matrix is totaly nonnegative. This is joint work with Michael Björklund.In paper F we introduce a generalization of Hom–complexes, called set partition complexes,and prove a connectivity theorem for them. This generalizes previous results ofBabson, Cukic, and Kozlov, and questions from Ramsey theory can be described with it.In paper G we use combinatorial topology to prove algebraic properties of edge ideals.The edge ideal of G is the Stanley-Reisner ideal of the independence complex of G. Thisis joint work with Anton Dochtermann.

Place, publisher, year, edition, pages
Stockholm: KTH, 2009. vii, 16 p.
Series
Trita-MAT. MA, ISSN 1401-2278
National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-10383 (URN)978-91-7415-256-2 (ISBN)
Public defence
2009-05-08, Sal E2, KTH, Lindstedtsvägen 5, Stockholm, 13:00 (English)
Opponent
Supervisors
Note
QC 20100712Available from: 2009-05-08 Created: 2009-05-08 Last updated: 2010-07-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Engström, Alexander
By organisation
Mathematics (Dept.)
In the same journal
European journal of combinatorics (Print)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 58 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf