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
Set Partition Complexes
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
2008 (English)In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 40, 357-364 p.Article in journal (Refereed) Published
Abstract [en]

The Hom complexes were introduced by Lovasz to study topological obstructions to graph colorings. The vertices of Hom(G,K-n ) are the n-colorings of the graph G, and a graph coloring is a partition of the vertex set into independent sets. Replacing the independence condition with any hereditary condition defines a set partition complex. We show how coloring questions arising from, for example, Ramsey theory can be formulated with set partition complexes.

It was conjectured by Babson and Kozlov, and proved by Cukic and Kozlov, that Hom(G,K-n ) is (n - d - 2)-connected, where d is the maximal degree of a vertex of G. We generalize this to set partition complexes.

Place, publisher, year, edition, pages
2008. Vol. 40, 357-364 p.
Keyword [en]
set partition complex; Hom complex; topological combinatorics; Ramsey theory
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-10374DOI: 10.1007/s00454-008-9106-6ISI: 000259563600003Scopus ID: 2-s2.0-52949094244OAI: oai:DiVA.org:kth-10374DiVA: diva2:216358
Note
QC 20100712Available from: 2009-05-08 Created: 2009-05-08 Last updated: 2010-12-03Bibliographically 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.springerlink.com/content/t57581256641104h/

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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