CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Enumeration on words, complexes and polytopes

Ragnar Freij (Institutionen för matematiska vetenskaper)
Göteborg : Chalmers University of Technology, 2010. - 156 s.

This thesis presents four papers, studying enumerative problems on combinatorial structures.
The first paper studies Forman's discrete Morse theory in the case where a group acts on the underlying complex. We generalize the notion of a Morse matching, and obtain a theory that can be used to simplify the description of the G-homotopy type of a simplicial complex. The main motivation is the case where some group acts transitively on the vertex set of the complex, and G is some large subgroup of this group. In particular we are interested in complexes of graph properties. As an application, we determine the (C_2 x S_{n-2})-homotopy type of the complex of non-connected graphs on n nodes.
The motivation behind the second paper is Gil Kalai's conjecture from 1989, that a centrally symmetric d-polytope must have at least 3^d non-empty faces. Looking for examples that are close to achieving the lower bound, we study the centrally symmetric Hansen polytopes, associated to perfect graphs. In particular, we study Hansen polytopes of split graphs. Among them, we find an infinite family of polytopes with 3^d+16 faces. We also prove that a Hansen polytope of a split graph has at least 3^d non-empty faces.
The third paper studies the problem of packing a pattern as densely as possible into compositions. We are able to find the packing density for some classes of generalized patterns and all the three letter binary patterns.
In the fourth paper, we enumerate derangements with descents in prescribed positions. A generating function was given by Guo-Niu Han and Guoce Xin in 2007. We give a combinatorial proof of this result, and derive several explicit formulas. To this end, we consider fixed point lambda-coloured permutations, which are easily enumerated. Several formulae regarding these numbers are given. We also prove that except in a trivial special case, the event that pi has descents in a set S of positions is positively correlated with the event that pi is a derangement, if pi is chosen uniformly in S_n.

Nyckelord: Simplicial complex, discrete Morse theory, Hansen polytope, $3^d$-conjecture, split graph, derangement, pattern containment, pattern packing, composition.

Denna post skapades 2010-03-22. Senast ändrad 2010-03-24.
CPL Pubid: 118230


Läs direkt!

Lokal fulltext (fritt tillgänglig)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaperInstitutionen för matematiska vetenskaper (GU)


Diskret matematik

Chalmers infrastruktur

Relaterade publikationer

Inkluderade delarbeten:

Enumeration of derangements with descents in prescribed positions

Equivariant Discrete Morse Theory


Datum: 2010-04-22
Tid: 13:15
Lokal: Euler, Chalmers Tvärgata 3, Göteborg
Opponent: Jakob Jonsson, Inst. för matematik, Kungliga Tekniska Högskolan, Sweden

Ingår i serie

Preprint - Department of Mathematical Sciences, Chalmers University of Technology and Göteborg University 2010:12