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
The g-theorem matrices are totally nonnegative
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
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.

Place, publisher, year, edition, pages
2009. Vol. 116, 730-732 p.
Keyword [en]
Simplicial polytope; g-theorem; f-vector; Totally nonnegative matrix
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-10373DOI: 10.1016/j.jcta.2008.07.004ISI: 000264406900015Scopus ID: 2-s2.0-60649097921OAI: oai:DiVA.org:kth-10373DiVA: diva2:216356
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.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHS-4THJ68Y-1&_user=4478132&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000034958&_version=1&_urlVersion=0&_userid=4478132&md5=7054fb4214d133ed72342134d953afe3

Search in DiVA

By author/editor
Björklund, MichaelEngström, Alexander
By organisation
Mathematics (Dept.)
In the same journal
Journal of combinatorial theory. Series A (Print)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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