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
Topological Combinatorics
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
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: urn:nbn:se:kth:diva-10383ISBN: 978-91-7415-256-2 (print)OAI: oai:DiVA.org:kth-10383DiVA: diva2:216411
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
List of papers
1. Upper bounds on the Witten index for supersymmetric lattice models by discrete Morse theory
Open this publication in new window or tab >>Upper bounds on the Witten index for supersymmetric lattice models by discrete Morse theory
2009 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 30, 429-438 p.Article in journal (Refereed) Published
Abstract [en]

The Witten index for certain supersymmetric lattice models treated by de Boer, van Eerten, Fendley, and Schoutens, can be formulated as a topological invariant of simplicial complexes, arising as independence complexes of graphs. We prove a general theorem on independence complexes, using discrete Morse theory: if G is a graph and D a subset of its vertex set such that G\D is a forest, then Sigma(i) dim (H) over bar (i)(Ind(G): Q) <= |Ind(G|D|)|. We use the theorem to calculate upper bounds on the Witten index for several classes of lattices. These bounds confirm some of the computer calculations by van Eerten on small lattices.

The cohomological method and the 3-rule of Fendley et al. is a special case of when G\D lacks edges. We prove a generalized 3-rule and introduce lattices in arbitrary dimensions satisfying it.

Keyword
COMPLEXES; GRAPHS
National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-10369 (URN)10.1016/j.ejc.2008.05.004 (DOI)000262526600011 ()2-s2.0-57049111046 (Scopus ID)
Note
QC 20100712Available from: 2009-05-08 Created: 2009-05-08 Last updated: 2017-12-13Bibliographically approved
2. Tverberg graphs
Open this publication in new window or tab >>Tverberg graphs
(English)Manuscript (Other academic)
Abstract [en]

The topological Tverberg theorem states that for any prime powerq and continuous map from a (d + 1)(q − 1)-simplex to Rd, there are qdisjoint faces Fi of the simplex whose images intersect. It is possible toput conditions on which pairs of vertices of the simplex that are allowed tobe in the same face Fi. A graph with the same vertex set as the simplex,and with two vertices adjacent if they should not be in the same Fi, iscalled a Tverberg graph if the topological Tverberg theorem still work. Aconsequence of our main theorem is that if the maximal degree of a graphis D, and D(D + 1) < q, then it is a Tverberg graph.

National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-10370 (URN)
Note
QC 20100712Available from: 2009-05-08 Created: 2009-05-08 Last updated: 2010-07-12Bibliographically approved
3. Independence complexes of claw-free graphs
Open this publication in new window or tab >>Independence complexes of claw-free graphs
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.

National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-10371 (URN)10.1016/j.ejc.2006.09.007 (DOI)000251166600022 ()2-s2.0-35548987051 (Scopus ID)
Note
QC 20100712Available from: 2009-05-08 Created: 2009-05-08 Last updated: 2017-12-13Bibliographically approved
4. Complexes of directed trees and independence complexes
Open this publication in new window or tab >>Complexes of directed trees and independence complexes
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.

National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-10372 (URN)10.1016/j.disc.2008.09.033 (DOI)000266654300038 ()2-s2.0-67349171932 (Scopus ID)
Note
QC 20100712Available from: 2009-05-08 Created: 2009-05-08 Last updated: 2017-12-13Bibliographically approved
5. The g-theorem matrices are totally nonnegative
Open this publication in new window or tab >>The g-theorem matrices are totally nonnegative
2009 (English)In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 116, 730-732 p.Article in journal (Refereed) Published
Abstract [en]

The g-theorem proved by Billera, Lee, and Stanley states that a sequence is the g-vector of a simplicial polytope if and only if it is an M-sequence. For any d-dimensional simplicial polytope the face vector is gM(d) where M-d is a certain matrix whose entries are sums of binomial coefficients. Bjorner found refined lower and upper bound theorems by showing that the (2 x 2)-minors of M-d are nonnegative. He conjectured that all minors of M-d are nonnegative and that is the result of this note.

Keyword
Simplicial polytope; g-theorem; f-vector; Totally nonnegative matrix
National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-10373 (URN)10.1016/j.jcta.2008.07.004 (DOI)000264406900015 ()2-s2.0-60649097921 (Scopus ID)
Note
QC 20100712Available from: 2009-05-08 Created: 2009-05-08 Last updated: 2017-12-13Bibliographically approved
6. Set Partition Complexes
Open this publication in new window or tab >>Set Partition Complexes
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.

Keyword
set partition complex; Hom complex; topological combinatorics; Ramsey theory
National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-10374 (URN)10.1007/s00454-008-9106-6 (DOI)000259563600003 ()2-s2.0-52949094244 (Scopus ID)
Note
QC 20100712Available from: 2009-05-08 Created: 2009-05-08 Last updated: 2017-12-13Bibliographically approved
7. Algebraic properties of edge ideals via combinatorial topology
Open this publication in new window or tab >>Algebraic properties of edge ideals via combinatorial topology
2009 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 16, no 2Article in journal (Refereed) Published
Abstract [en]

We apply some basic notions from combinatorial topology to establish various algebraic properties of edge ideals of graphs and more general Stanley-Reisner rings. In this way we provide new short proofs of some theorems from the literature regarding linearity, Betti numbers, and (sequentially) Cohen-Macaulay properties of edge ideals associated to chordal, complements of chordal, and Ferrers graphs, as well as trees and forests. Our approach unifies (and in many cases strengthens) these results and also provides combinatorial/enumerative interpretations of certain algebraic properties. We apply our setup to obtain new results regarding algebraic properties of edge ideals in the context of local changes to a graph (adding whiskers and ears) as well as bounded vertex degree. These methods also lead to recursive relations among certain generating functions of Betti numbers which we use to establish new formulas for the projective dimension of edge ideals. We use only well-known tools from combinatorial topology along the lines of independence complexes of graphs, (not necessarily pure) vertex decomposability, shellability, etc.

Keyword
COHEN-MACAULAY GRAPHS; CLAW-FREE GRAPHS; MONOMIAL IDEALS; COMPLEXES; HYPERGRAPHS; RESOLUTIONS; THEOREM; RINGS
National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-10375 (URN)000263259900002 ()
Note
QC 20100712Available from: 2009-05-08 Created: 2009-05-08 Last updated: 2017-12-13Bibliographically approved

Open Access in DiVA

fulltext(435 kB)993 downloads
File information
File name FULLTEXT01.pdfFile size 435 kBChecksum SHA-512
7d2a4fd561681d86ae0a2f5ed0f1f28577f65f5d3d81e3ca9eb704dd2c2be8631b7c2fe2fae62d2b99dc30df3046496dba7de64d7f5bbdbeb555a9abf7255645
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Engström, Alexander
By organisation
Mathematics (Dept.)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 993 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 625 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