In Memory of Svatopluk Poljak

miscellaneous files (including 9 gifs-pictures)

(This tribute has appeared in the special issue on Semidefinite Programming in Mathematical Programming, volume 77, 1997.)

Svata Poljak was born in Prague on October 9, 1951. He did his training at Charles University in Prague and received his PhD in 1980 under the supervision of Zdenek Hedrlin. Upon completion of his PhD he first took a position at Ceske Vysoke Uceni Technicke, the Technical University in Prague, in the Department of Operations Research, and next, in 1986, at Charles University in the Department of Applied Mathematics. In April 1994 he moved to the University of Passau to take up a position in the Faculty of Mathematics and Computer Science. He died on April 2, 1995 in a car accident. Svata is survived by his wife Jana and their two sons Honza and Vitek.

Svata had a very broad interest and a wide mathematical knowledge. This is best illustrated by his many important contributions in diverse areas of discrete mathematics and combinatorial optimization such as matroid theory, matching theory, the max-cut and stable set problem, spectral approaches to graph problems, convex and polyhedral relaxations, semidefinite programming, and various other integer programming related problems. The fast approximation algorithms for finding a maximum cut by semidefinite programming, which are currently in the spotlight and play a major role in the popularity of semidefinite programming, find their root in work of Svata on eigenvalue methods for graph problems. In addition, Svata's early work included pioneering contributions to the area of neural networks.

Svata was involved in a fatal car accident. This occurred 62 kms from Prague on Sunday evening April 2, 1995. Svata was on his way back to Prague from his summer house in Nove Hute. This is a village in the mountains, very conveniently located about halfway between Passau and Prague. Svata had just bought the cottage and he was really thrilled with it. In winter you can go skiing, starting right from the front door. It was one of Svata's longstanding dreams to have a place like that ... He was in the car with Standa Tyle, one of his best friends from Prague, two women including Standa's wife, and two children. They were hit by a car that came the other way, but on their side. There was no way to escape. Svata and his friend must have been dead instantly. The children recovered quickly from their physical injuries, but the two women had to undergo treatment for a long time.

Svata and Standa belonged to a group of four very good friends, who were engaged in fencing from the age of 10. The four of them and, later also their families, have remained inseparable throughout the years. They shared, among other things, a common love for hiking, canoeing, cross-country skiing, mountain trips, biking, etc...

This tragic accident happened at a moment which may have been among the happiest in Svata's life. Svata was indeed very happy with his new professional activity in Passau; he liked very much his work and the university environment, as well as living in Passau with his family. During the winter of 1995, he enjoyed fully the snowy weekends in Nove Hute, where he could happily mix work and leisure.

Svata will remain a point of reference in our community in many respects. We regret deeply the loss of a colleague and friend.

Following are a few memories by some of his collaborators and friends.

See also the Notice in: Opt-Net Digest v95w15

This home page, several of Svata's publications and the following (long) list of his publications can be found over WWW with URL:

BIBLIOGRAPHY follows: (5 ps files of papers are available)

Svatopluk Poljak
February 1994

  1. A note on stable sets and colouring of graphs, Comment. Math. Univ. Carolinae 15 (1974) 307-309. MR 50#4369; Zbl 284.05105

  2. (with M. Boguszak and J. Tuma) Note on homomorphism interpolation theorem, Comment. Math. Univ. Carolinae 17 (1976) 105-109. MR 53#12964; Zbl 335.05007

  3. (with D. Turzik) On amalgamation of graphs and essential sets of generators, Comment. Math. Univ. Carolinae 19 (1979) 359-369. MR 80a:05171; Zbl 276.05053

  4. (with D. Turzik) Some equivalent formulations of the intersection problem of finitely generated classes of graphs, Acta Sci. Math. 41 (1979) 357-374. MR 81c:05035; Zbl 427.05049

  5. (with V. Rödl) Orthogonal partitions and covering of graphs, Czechoslovak Mathematical Journal 105 (1980) 475-485. MR 82j:05088; Zbl 456.05051

  6. (with D. Turzik) Weak join of matroids, Proc. 8th Winter School on Abstract Analysis, Math. Institute Czech. Acad. Sci. 1980, pp.130-133.

  7. (with J. Nesetril) Geometric and algebraic aspects of combinatorial optimization (in Czech), SOFSEM 1980, pp.35-77.

  8. (with J. Nesetril and D. Turzik) Amalgamation of matroids and its applications, J. Combinatorial Theory Ser.B 31 (1981) 9-22. MR 82k:05080; Zbl 473.05021

  9. (with V. Rödl) On the arc-chromatic number of a digraph, J. Combinatorial Theory Ser.B 31 (1981) 190-198. MR 82j:05059; Zbl 472.05024

  10. (with A. Pultr) On the dimension of trees, Discrete Mathematics 34 (1981) 165-171. MR 82m:05040; Zbl 476.05075

  11. (with V. Rödl) On set systems determined by intersections, Discrete Mathematics 34 (1981) 173-184. MR 82e:05105; Zbl 474.05060

  12. (with V. Rödl and D. Turzik) Complexity of representing graphs by set systems, Discrete Applied Mathematics 3 (1981) 301-312. MR 83j:68054; Zbl 473.68064

  13. (with A. Pultr and V. Rödl) On the dimension of Kneser graphs, in: Algebraic Methods in Graph Theory, eds. L. Lovász and V. T. Sós, Colloq. Math. Soc. János Bolyai 25, North-Holland, Amsterdam 1981, pp. 631-646. Zb 476.05077

  14. (with D. Turzik) A note of dimension of Czechoslovak Mathematical Journal 106 (1981) 484-487. Zb 476.05076

  15. (with A. Pultr) Representing graphs by means of strong and weak products, Comment. Math. Univ. Carolinae 22 (1981) 449-466. MR 83d:05085 Zb 476.05074

  16. (with D. Turzik and P. Pudlák) Extension of k-subsets to - existence versus constructability, Comment. Math. Univ. Carolinae 23 (1982) 337-349. MR 83h:68045 Zb 495.68059

  17. (with D. Turzik) A polynomial algorithm for constructing a large bipartite subgraph with an application to satisfiability problem, Canadian Mathematical J. 24 (1982) 519-524. MR 83j:05048; Zbl 487.68058

  18. (with D. Turzik) A note on sticky matroids, Discrete Mathematics 42 (1982) 119-123. MR 84d:05059; Zbl 491.05020

  19. (with M. Sura) An algorithm for graceful labelling of trees, Ars Combinatoria 14 (1982) 57-66. MR 84d:05150; Zbl 504.05029

  20. (with A. Pultr and V. Rödl) On qualitatively independent partitions and related problems, Discrete Applied Mathematics 6 (1983) 193-205. MR 85d:05024; Zbl 515.05009

  21. (with V. Rödl) On classes of graphs determined by forbidden subgraphs, Czechoslovak Mathematical Journal 108 (1983) 27-33. MR 84d:05129; Zbl 528.05054

  22. (with M. Sura) On periodical behaviour in societies with symmetrical relations, Combinatorica 3 (1983) 119-121. MR 85a:90022; Zbl 561.90008

  23. (with M. Sura) On a construction of graceful trees, in: Graphs and Other Combinatorial Topics (M. Fiedler ed.), Proc. of the Third Czech.Symp. on Graph Theory (Prague 1982), Teubner Texte zur Math. 59, Leipzig 1983, pp. 220-222. Zbl 528.05021

  24. (with A. Pultr and V. Rödl) On a product dimension of bipartite graphs, Journal of Graph Theory 7 (1983) 475-486. MR 85i:05202; Zbl 531.05038

  25. (with D. Turzik) On systems, periods and semipositive mappings, Comment. Math. Univ. Carolinae 25 (1984) 597-614. Zbl 576.05059

  26. (with D. Turzik) Amalgamation over uniform matroids, Czechoslovak Mathematical Journal 109 (1984) 239-246. MR 85i:05075; Zbl 553.05029

  27. (with D. Turzik) Amalgamation of matroids along hypergraphs, in: Finite and Infinite Sets ( eds. A. Hajnal, L. Lovász and V. T. Sós), Colloq. Math. Soc. Janos Bolyai 37, North-Holland, Amsterdam 1984, pp. 607-620. MR 87a:05048; Zbl 567.05015

  28. (with J. Nesetril and D. Turzik) Some remarks on the Ramsey matroids, Supplemento ai Rendiconto del Circolo Matematico di Palermo, Serie II, n.3 (1984), Proceeding of the 11th Winter School on Abstract Analysis, pp. 185-189. Zbl 543.05021

  29. (with D. Turzik) On social influence models with ranking alternatives and local election rules, Mathematical Social Sciences 10 (1985) 189-198.

  30. (with J. Pelant) Extensions of cyclically monotone mappings, Supplemento ai Rendiconto del Circolo Matematico di Palermo, Serie II, n.11 (1985), Proceeding of the 13th Winter School on Abstract Analysis, pp. 81-88. Zbl 586.90005

  31. (with J. Nesetril) On the complexity of the subgraph problem , Comment. Math. Univ. Carolinae 26 (1985) 415-419. Zbl 571.05050

  32. (with J. Nesetril and D. Turzik) Special amalgams of matroids, in: Matroid Theory, eds. L. Lovász and A. Recski, Colloq. Math. Soc. János Bolyai 40, North-Holland, Amsterdam 1985, pp. 267-298. MR 87k:05053

  33. (with J. Nesetril) A note on max-cut problem with an application to discrete-analogue convertors, Operations Research Letters 4 (1986) 289-191. Zbl 585.90085

  34. (with D. Turzik) On an application of convexity to discrete systems, Discrete Applied Mathematics 13 (1986) 27-32. MR 87k:58133; Zbl 588.93048

  35. (with D. Turzik) On pre-periods of discrete influence systems, Discrete Applied Mathematics 13 (1986) 33-39. MR 87k:58134;

  36. (with D. Turzik) A polynomial heuristic for certain subgraph optimization problems with guaranteed lower bound, Discrete Mathematics 58 (1986) 99-104. Zbl 585.05032

  37. (with J. Pelant and D. Turzik) Limit behaviour of trajectories involving subgradients of convex functions, Comment. Math. Univ. Carolinae 28 (1987) 457-466.

  38. (with D. Turzik) On a facet of the balanced subgraph polytope, Cas. pest. matem. 112 (1987) 373-380.

  39. (with M. Chrobak) A generalization of Smith's Theorem, Zastosowania Matematyki (Applic. Math.) XIX (1987) 371-374.

  40. (with Zs. Tuza) Maximum bipartite subgraphs of Kneser graphs, Graphs and Combinatorics 3 (1987) 191-199.

  41. Transformations on graphs and convexity, Complex Systems 1 (1987) 1021-1033.

  42. (with M. Loebl) Matroids induced by packing subgraphs, J. Combinatorial Theory Ser.B 44 (1988) 338-354.

  43. (with D. Turzik) Subgradients of convex functions and periodical behaviour of finite automata, Proc. of Inst. Chem. Tech. (Prague), M 2 (1988), 75-86.

  44. (with M. Loebl) On the union of matching matroids, Mathematica Slovaca 38 (1988) 301-304.

  45. (with M. Loebl) Bipartite packing, in: Combinatorics, Eger (Hungary) 1987, Colloq. Math. Soc. János Bolyai 52, North-Holland, Amsterdam 1988, pp. 375-384.

  46. (with M. Chrobak) On common edges in optimal solutions to travelling salesman and and other optimization problems, Discrete Applied Mathematics 20 (1988) 101-111.

  47. (with V. Rödl and J. Spencer) Polynomial time algorithm for tournament ranking that ensures the expected profit, SIAM J. on Discrete Mathematics, 1 (1988) 372-376.

  48. (with Zs. Tuza) Improved bounds for the number of qualitatively independent partitions, J. Combinatorial Theory Ser.A 51 (1989) 111-116.

  49. Maximum rank of powers of a matrix of a given pattern, Proceedings AMS 106 (1989) 1137-1144.

  50. (with M. Loebl) A hierarchy of totally unimodular matrices, Discrete Mathematics 76 (1989) 241-246.

  51. (with P. Alles) Long induced paths and cycles in Kneser graphs, Graphs and Combinatorics 5 (1989) 303-306.

  52. On the generic dimension of controllable subspaces, IEEE Transactions on Automatic Control, March 1990, Vol.35, No.3, 367-369.

  53. (with M. Loebl) Subgraph packing - a survey. Topics in Combinatorics and Graph Theory: Essays in Honour of Gerhard Ringel, Physica-Verlag Heidelberg 1990, pp.491-503.

  54. (with K. Murota) Note on a graph-theoretic criterion for structural output controllability, IEEE Transactions on Automatic Control vol. 35, No 8 August 1990, 939-942.

  55. (with B.Mohar) Eigenvalues and the max-cut problem, Czechoslovak Mathematical Journal 40(115) (1990) 343-352.

  56. (with M. Kano) Graphs with the Balas-Uhry property, Journal of Graph Theory 14 (1990) 623-628.

  57. (with P. Alles and J. Nesetril) Extendability, dimensions and diagrams for cyclic orders, SIAM J. on Discrete Mathematics 4 (1991) 453-471.

  58. (with M. Schlegel) Computing generic Jordan canonical form, Linear and Multilinear Algebra 28 (1991) 241-249.

  59. (with T. Ibaraki) Weak three-linking in Eulerian digraphs, SIAM J. on Discrete Mathematics, 4 (1991) 84-98

  60. Coloring digraphs by iterated antichains, Comment. Math. Univ. Carolinae 32,2 (1991) 209-212.

  61. Polyhedral and eigenvalue approximations of the max-cut problem. in: "Sets, Graphs and Numbers" (eds. G. Halász, L. Lovász, D. Miklós and T. Szönyi), Colloq. Math. Soc. János Bolyai 60, North-Holland, Amsterdam 1992, pp. 569-581.

  62. (with M. Loebl) Packing by families of subgraphs, in Forth Czechoslovakian Symposium on Combinatorics, Graph Theory and complexity, (M. Fiedler and J. Nesetril eds.), Annals of Discrete Mathematics 51, North-Holland 1992, pp. 181-186.

  63. (with Y. Crama and M. Loebl) On line balancing of strongly unimodular matrices, Discrete Applied Mathematics, 102 (1992) 143-147.

  64. (with M. Deza and M. Laurent) Facets of the cut cone III: The role of triangle facets, Graphs and Combinatorics 8 (1992) 125-142.

  65. (with M. Laurent) The metric polytope, Proc of IPCO 1992, (eds. E. Balas, G. Cornuejols and R. Kannan), 1992, pp. 274-286.

  66. Minimum spectral radius of a weighted graph, Linear Algebra and Its Applications, 171 (1992) 53-63.

  67. (with J. Kratochv´l) Compatible two-factors, Discrete Applied Mathematics, 36 (1992) 253-266.

  68. (with D. Turzik) Maximum cut in circulant graphs, Discrete Mathematics, 108 (1992) 379-392.

  69. On the gap between structural controllability of time-invariant and time-varying systems, IEEE Transactions on Automatic Control, 37 (1992) 1961-1965.

  70. (with Ch. Delorme) The performance of an eigenvalue bound in some classes of graphs, in Proceedings of the Conference on Combinatorics, Marseille 1990. Discrete Mathematics, 111 (1993) 145-156.

  71. On existence theorems, in Proceedings of the Conference on Combinatorics, Marseille 1990. Discrete Mathematics, 122 (1993) 423-434.

  72. (with B. Mohar) Eigenvalue methods in combinatorial optimization, in: Combinatorial and Graph-Theoretic Problems in Linear Algebra, (eds. R. Brualdi, S. Friedland and V. Klee), The IMA Volumes in Mathematics and its Applications, vol. 50, Springer-Verlag 1993, pp. 107-151.

  73. (with J. Bang-Jensen) Eulerian trails through a set of terminals in specific, unique and all orders. In: "Graph Structure Theory", Proc. AMS-IMS-SIAM Joint Summer Conf. (Seattle 1991), eds. N. Robertson and P. Seymour, Contemporary Mathematics vol. 147, Amer. Mat. Soc. 1993, pp. 247-258.

  74. (with Ch. Delorme) Combinatorial properties and the complexity of an eigenvalue approximation of the max-cut problem, Europ. J. Combinatorics 14 (1993) 313-333.

  75. (with J. Rohn) Checking robust nonsingularity is NP-hard, Mathematics of Control, Signals and Systems 6 (1993) 1-9.

  76. (with Ch. Helmberg, B. Mohar, and F. Rendl) A spectral approach to bandwidth and separator problems in graphs, Third IPCO Conference (G. Rinaldi and L. Wolsey, eds.), 1993 pp. 183-194.

  77. (with M. Loebl) Efficient subgraph packing. J. Combinatorial Theory Ser.B, 59 (1993) 106-121.

  78. (with Ch. Delorme) Laplacian eigenvalues and the maximum cut problem, Mathematical Programming 63 (1993) 557-574.

  79. (with T.Nishizeki) K-connectivity and decomposition of graphs into forests, Discrete Applied Mathematics, 55 (1994) 295-301.

  80. (with Zs. Tuza) Bipartite subgraphs of triangle free graphs, SIAM J. Discrete Math. 7 (1994) 307-314.

  81. (with F. Rendl) Computational experiments with node and edge relaxations of the max-cut problem, Computing 52 (1994) 123-137.

  82. (with Zs. Tuza) On the expected relative error of the polyhedral approximation of the max-cut, Oper. Res. Letters 16 (1994) 191-198.

  83. (with F. Rendl) Computing the max-cut by eigenvalues, to appear in a special volume of Annals of Operation Research.

  84. (with F. Rendl) Nonlinear relaxation of the graph-bisection problems, to appear in SIAM J. Opt.

  85. (with Ch. Helmberg, B. Mohar, and F. Rendl) A spectral approach to bandwidth and separator problems in graphs, to appear in Linear and Multilinear Algebra.

  86. (with G. Hahn and P. Hell) On the ultimate independence ratio of a graph, Report No. 91717-OR (Institut für Diskrete Mathematik, Universität Bonn), Europ. J. Combinatorics 16 (1995). to appear.

  87. (with M. Laurent) One-third integrality in the metric polytope, Mathematical Programming, 71 (1996) 29-50.

  88. Integer linear programs and local search, SIAM J. Comp. 24 (1995) 822-839.

  89. (with H. Wolkowicz) Convex relaxations of 0-1 quadratic programming, Mathematics of Operation Research, 20:550-561, 1995.

  90. (with M. Laurent) On a positive semidefinite relaxation of the cut polytope, Linear Algebra and Its Applications, 223/224:439-461, 1995.

  91. (with Zs. Tuza) Max-cut - a survey, preprint Academia Sinica, 1993.

  92. (with Zs. Tuza) Maximum cuts and largest bipartite subgraphs. In W. Cook, L. Lovasz, and P. Seymour, editors, Combinatorial Optimization, volume 20 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 181--244, American Mathematical Society, 1995.

  93. (with M. Laurent) On the facial structure of the correlation matrices, SIAM J. Matrix Analysis, 17:530--547, 1996.

  94. (with M. Laurent and F. Rendl) Connections between semidefinite relaxations of the max-cut and stable set problems, Mathematical Programming, to appear.

  95. (with F. Rendl and H. Wolkowicz) A recipe for semidefinite relaxation for (0,1)-quadratic programming, J. Global Optimization, 7:51-73, 1995.

  96. (with M. Laurent) On the gap inequalities Europ. J. Comb., 1996, to appear.

  97. (with D. Turzik) The probability of exact graphs, in preparation.

  98. (F. Rendl and H. Wolkowicz) A semidefinite programming approach to integer programming, Proceedings of the 4th International IPCO Conference, Egon Balas and Jens Clausen (Eds.), Lecture Notes in Computer Science 920, Springer 1995, pp. 124-134.

  99. Neural Networks via Convexity and Linear Programming, submitted

  100. (with Ch. Delorme) Nonlinear relaxation of graph partition problems, in preparation.

  101. (with V.Rödl) Average discrepancy of a set system, in preparation.

  102. (with C. DeSimone, Ch. Helmberg, F. Rendl and G. Rinaldi) Polyhedral and semidefinite relaxations for the max-cut problem, in preparation.

    Henry's Home Page