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
Complexes of directed trees and independence complexes
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
2009 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 309, no 10, 3299-3309 p.Article in journal (Refereed) Published
Abstract [en]

First we prove that certain complexes on directed acyclic graphs are shellable. Then we study independence complexes. Two theorems used for breaking and gluing such complexes are proved and applied to generalize the results by Kozlov.An interesting special case is anti-Rips complexes: a subset P of a metric space is the vertex set of the complex, and we include as a simplex each subset of P with no pair of points within distance r. For any finite subset P of R the homotopy type of the anti-Rips complex is determined.

Place, publisher, year, edition, pages
2009. Vol. 309, no 10, 3299-3309 p.
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-10372DOI: 10.1016/j.disc.2008.09.033ISI: 000266654300038Scopus ID: 2-s2.0-67349171932OAI: oai:DiVA.org:kth-10372DiVA: diva2:216353
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 textScopushttp://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V00-4TVY5J1-1&_user=4478132&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000034958&_version=1&_urlVersion=0&_userid=4478132&md5=22d5d36a5c2304a2f5c2c3e03e6f306c

Search in DiVA

By author/editor
Engström, Alexander
By organisation
Mathematics (Dept.)
In the same journal
Discrete Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 53 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