Habilitation Thesis

To have a scientific career at a German University, two dissertations are needed: the Ph.D. thesis and the "Habilitation" thesis. There is no American equivalent to the German Habilitation, as the academic certification is awarded to an individual who already has a Ph.D. Habilitation is the highest scientific distinction in Germany.

Discrete Extremal Problems on Graphs and Posets

University of Paderborn, Department of Mathematics and Computer Science, 1996.

Referees :

Prof. M. Aigner (Free University of Berlin)
Prof. W. Mader (University of Hannover)
Prof. E.W. Mayr (Technical University of Munich)
Prof. F. Meyer auf der Heide (University of Paderborn)
Prof. B. Monien (University of Paderborn)

Brief summary :

The Thesis consists of five main chapters (excluding the introductory chapter) and is devoted to various discrete extremal problems on graphs and posets (partially ordered sets) and their applications.

The first chapter is devoted to isoperimetric problems on graphs. This results concerning the vertex version of the problem for the n-dimensional unit cube can be considered as a continuation of research on this subject [d] started in the Ph.D. Thesis. A classification of all solutions is proposed and some new solutions are constructed [k]. The main part of the chapter is devoted to the edge version of the problem consisting in constructing a set of m vertices in a graph (m is fixed) with minimal cut. A new approach to the problem is proposed for the cartesian products of graphs [p]. The approach is based on an equivalence relation and allows to solve the problem for a class of graphs if it is solved for a representative of this class. Deep relations of this problem and the problem of minimization of shadows in posets are described and applications for maximization of more general functions on cartesian products of graphs are presented (see [r]).

The second chapter deals with the shadow minimization problem in posets. For a ranked poset P and its k-th level Pk the problem is to find an m-element subset A of Pk with minimal shadow (i.e. the number of elements of Pk-1, which are less in the partial order than the elements of A). This problem is solved for some concrete posets such as the star poset [b], the binary subword poset [g] and the linear lattice [o]. Moreover, a class of posets is considered and a two-parametrical family of posets of this class is found for which the problem has a nested structure of solutions [s].

The problems studied in the first two chapters are applied in the third chapter to a number of related extremal problems. Among them are problem of specification of all subsets of the n-cube with a fixed diameter which have maximal cardinality [a], scheduling problems which involve constructing optimal in a sense edge numberings of graphs [i], a problem arising in encoding of analog signals [c] and constructing ideals in posets with maximal weight [e]. The last problem has direct relations with minimization of the edge-cut in graphs [p].

The fourth chapter is devoted to embedding of trees into the n-cube. We deal with a hypothesis of Havel concerning embedding binary trees into the n-cube as subgraphs and present new technique for embedding caterpillars [q]. The approach is based on embedding of ladders, covers all but one known results on caterpillars and provides embedding of many new types of them. Furthermore, we study embedding complete t-ary trees as subgraphs into the n-cube of minimal dimension. Our constructions [m] improve known bounds for n. Preserving orientation embedding of binary oriented trees into oriented n-cube are studied as well [l].

Solution of four more particular discrete extremal problems is presented in the fifth chapter (see [f,h,j,n]).

References :

  1. Specification of the maximal sized subsets of the unit cube with respect to given diameter, Problems of Information Transmission, vol. XXIII, 1987, No. 1, 106-109.
  2. Minimization of the shadows in the partial mappings semilattice, Discrete Analysis, Novosibirsk, vol. 46, 1988, 3-16.
  3. Encoding of analog signals for discrete binary channel, in: Proceedings Int. Conf. Algebraic and Combinatorial Coding Theory, Varna 1988, 12-16.
  4. On the construction of solutions of a discrete isoperimetric problem in Hamming space, Math. USSR Sbornik, vol. 63, 1989, No. 1, 81-96.
  5. Extremal ideals of the lattice of multisets with respect to symmetric functionals, (with Voronin V.P.), Discretnaya Matematika, vol. 2, 1990, No. 1 50-58.
  6. On superspherical graphs, (with Sali A.), Colloq. Math. Soc. Janos Bolyai, vol. 60, 1991, 89-95.
  7. A Kruskal-Katona type theorem, (with Gronau H.-D.), Rostock Math. Kolloq., vol. 46, 1992, 71-80.
  8. Two extremal problems for oriented trellises, Problems of Information Transmission, vol. 28, 1992, No. 2, 109-111.
  9. On edge numberings of the n-cube graph, (with Weber K., Grünwald N.), Discr. Appl. Math., vol. 46, 1993, No. 2, 99-116.
  10. On partitioning the n-cube into sets with mutual distance 1, (with Ahlswede R., Blokhuis A., Metsch K., Moorhouse E.), Appl. Math. Lett., vol. 6, 1993, 17-19.
  11. Isoperimetric problems in discrete spaces, in: Extremal Problems for Finite Sets. Bolyai Soc. Math. Stud. 3, P. Frankl, Z. Füredi, G. Katona, D. Miklos eds., Budapest 1994, 59-91.
  12. On oriented embedding of the dichotomic tree into the hypercube, Combinatorics, Probability and Computing, Cambridge, vol. 3, 1994, 27-38.
  13. Embedding complete trees into the hypercube, Discrete Appl. Math., vol. 110, 2001, no. 2-3, 101-119.
  14. Properties of graded posets preserved by some operations, (with Engel K.), in: Mathematics of Paul Erdös (ed. R.L. Graham, J. Nesetril), Springer Verlag, 1996, 79-85.
  15. A Kruskal-Katona theorem for the linear lattice, (with Blokhuis A.), Europ. J. Combin., vol. 20, 1999, no. 2, 123-130.
  16. On an equivalence in discrete extremal problems, Discr. Math., vol. 203, 1999, no. 1, 9-22.
  17. Embedding ladders and caterpillars into the hypercube, (with Monien B., Unger W., Wechsung G.), Discrete Appl. Math., vol. 82, No. 1-3 (1998), 19-27.
  18. Edge isoperimetric problems of graphs, in: Graph Theory and Combinatorial Biology, Bolyai Soc. Math. Stud. 7, L. Lovasz, A. Gyarfas, G.O.H. Katona, A. Recski, L. Szekely eds., Budapest 1999, 157-197.
  19. On posets whose products are Macaulay, J. Combin. Theory, vol. A-84, 1998, No. 2, 157-170.