Topics in algorithmic, enumerative and geometric combinatorics

This thesis presents five papers, studying enumerative andextremal problems on combinatorial structures.The first paper studies Forman\u27s 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. As an application, we determine the S_2xS_{n-2}-homotopy type of the complex of non-connected graphs on n nodes. In the introduction, connections are drawn between the first paper and the evasiveness conjecture for monotone graph properties.In the second paper, we investigate Hansen polytopes of split graphs. By applying a partitioningtechnique, the number of nonempty faces is counted, and in particular we confirmKalai\u27s 3^d-conjecture for such polytopes. Furthermore, a characterization ofexactly which Hansen polytopes are also Hanner polytopes is given. We end byconstructing an interesting class of Hansen polytopes having very few faces andyet not being Hanner.The third paper studies the problem of packing a pattern as densely as possible into compositions. We are able to find thepacking density for some classes of generalized patterns, including all the three letter patterns.In the fourth paper, we present combinatorial proofs of the enumeration of derangements with descents in prescribed positions. To this end, weconsider fixed point lambda-coloured permutations, which are easilyenumerated. Several formulae regarding these numbers are given, aswell as a generalisation of Euler\u27s difference tables. 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.The fifth paper solves a partially ordered generalization of the famous secretary problem. The elements of a finite nonempty partially ordered set are exposed in uniform random order to a selector who, at any given time, can see the relative order of the exposed elements. The selector\u27s task is to choose online a maximal element. We describe a strategy for the general problem that achieves success probability at least 1/e for an arbitrary partial order, thus proving that the linearly ordered set is at least as difficult as any other instance of the problem. To this end, we define a probability measure on the maximal elements of an arbitrary partially ordered set, that may be interesting in its own right