Publications and software

Dmitrii V. Pasechnik

1  Publications in refereed journals and proceedings.

  1. Distance transitive graphs of type q.Kq,q and projective planes. (with I.V. Chuvaeva) Eur. J. Comb., 11(1990), 341-346
  2. Dual linear extensions of generalised quadrangles, Eur. J. Comb., 12(1991), 541-548
  3. Skew-symmetric association schemes with two classes and strongly regular graphs of type L(2n-1,4n-1), Acta Applicandae Mathematicae, 29(1992), 129-138
  4. Affine extensions of the Petersen graph and 2-arc transitive graphs of girth 5, Eur. J. Comb., 13(1992), 279-290
  5. New examples of finite [C\tilde]2-geometries, Geom. Ded., 46(1993), 161-164
  6. Geometric characterization of graphs from the Suzuki chain, Eur. J. Comb., 14(1993), 491-499
  7. On some locally 3-transposition graphs, in Proc. of Second Deinze Conf. "Finite geometries and combinatorics", LMS Lect. Notes Ser. 191, Cambridge Univ. Press, 1993, 319-326
  8. Characterization of the graphs of alternating forms and the graphs of quadratic forms over GF(2), (with A. Munemasa and S.V. Shpectorov), in Proc. of Second Deinze Conf. "Finite geometries and combinatorics", LMS Lect. Notes Ser. 191, Cambridge Univ. Press, 1993, 303-318
  9. The automorphism group and the convex subgraphs of the quadratic forms graph in characteristic 2, (with A. Munemasa and S.V. Shpectorov) J. Algebraic Comb., 2(1993), 411-419
  10. Subsets close to invariant subsets for group actions, (with L. Brailovsky and C.E. Praeger) Proc. of AMS 123(1995) 2283-2295
  11. Classification of 2-quasi-invariant subsets, (with L. Brailovsky and C.E. Praeger) Ars Comb. 42(1996) 65-75
  12. Geometric characterization of the sporadic groups Fi22, Fi23 and Fi24. Jour. Comb. Th. (A) 68(1994) 100-114
  13. Nonabelian representations of some sporadic geometries, (with A.A. Ivanov and S.V. Shpectorov). J. of Algebra 181(1996) 523-557
  14. Multiple extensions of generalized hexagons related to the simple groups McL and Co3, (with Hans Cuypers and A.I. Kasikova). J. London Math. Soc. (2) 54(1996) 16-24
  15. The triangular extensions of a generalized quadrangle of order (3,3). Bull. Belg. Math. Soc. 2(1995) 509-518
  16. Extended generalized octagons and the group He. Geom. Ded. 56(1995) 85-101
  17. Extending polar spaces of rank at least 3. J. Comb. Th. (A) 71(1995) 232-242
  18. Universal covers of the sporadic semibiplanes, (with B. Baumeister). Eur. J. Comb. 17(1996) 595-604
  19. The extensions of the generalized quadrangle of order (3,9). Eur. J. Comb. 17(1996) 751-755
  20. The universal covers of certain semibiplanes, (with B. Baumeister). Eur. J. Comb. 18(1997) 491-496
  21. A new family of extended generalized quadrangles, (with A.Del Fra and A.Pasini). Eur. J. Comb. 18(1997) 155-169
  22. On transitive permutation groups with primitive subconstituents, (with C.E. Praeger). Bull. London Math. Soc. 31(1999) 257-268
  23. Computing the Hilbert base via the Elliott-MacMahon algorithm. Th. Computer Science 263 (2001) 37-46
  24. On the number of inductively minimal geometries (with P. Cara and S. Lehman), Th. Computer Science 263 (2001) 31-35
  25. A characterization of the Petersen-type geometry of the McLaughlin group, (with B. Baumeister and A.A. Ivanov), Math. Proc. Cambridge Phil. Soc. 128 (2000) 21-44
  26. On equicut graphs, (with M. Deza), Multi. Val. Logic 7 (2001) 363-377
  27. Extended F4-buildings and the Baby Monster.
    (with A.A. Ivanov and S.V. Shpectorov). Invent. Math. 144(2001) 399-433
  28. On the skeleton of the metric polytope. (with A.Deza, K.Fukuda, and M.Sato). Lecture Notes in Computer Science 2098 125-136, Springer-Verlag 2001, Berlin.
  29. Approximate graph colouring and MAX-k-CUT algorithms based on the q-function. (with E. de Klerk and J.P. Warners). J. Comb. Opt. 8(2004) 267-294
  30. Approximation of the stability number of a graph via copositive programming. (with E. de Klerk). SIAM J. Opt. 12(2002) 875-892
  31. c-extensions of the F4(2)-building. (with A.A. Ivanov). Discr. Math. 264(2003) 91-110
  32. Complexity of semi-algebraic proofs. (with D.Grigoriev and E.A.Hirsch), Proceedings STACS'02, Lect. Notes in Computer Science 2285 419-430, Springer-Verlag 2002, Berlin
  33. Exponential lower bound for static semi-algebraic proofs. (with D.Grigoriev and E.A.Hirsch). Proceedings ICALP 2002, Lect. Notes in Computer Science, 2380, 257-268, Springer-Verlag 2002, Berlin
  34. Complexity of semi-algebraic proofs. (with D.Grigoriev and E.A.Hirsch). Moscow Math. Journal, 2(2002) 647-679.
  35. Products of positive forms, linear matrix inequalities, and Hilbert 17-th problem for ternary forms. (with E. de Klerk), European J. on O.R., 157(2004) 39-45
  36. Minimal representations of locally projective amalgams. (with A.A. Ivanov). J. London Math. Soc. (2) 70(2004) 142-164, available at http://stuwww.uvt.nl/~dpasech/misc/amalgams.ps
  37. Polynomial-time computing over quadratic maps I: sampling in real algebraic sets. (with D. Grigoriev). Computational Complexity 14(2005) 20-52, available at http://arXiv.org/abs/cs.SC/0403008
  38. On the irreducibility of a truncated binomial expansion. (with M. Filaseta and A. Kumchev) Preprint 2004, available at http://arXiv.org/abs/math.NT/0409523, to appear in Rocky Mountains J. Math.
  39. The isometries of the cut, metric and hypermetric cones. (with A. Deza and B. Goldengorin) Preprint 2003, available at http://arXiv.org/abs/math.MG/0306049, to appear in J. Algebraic Comb.
  40. Improved bounds for the crossing numbers of Km,n and Kn. (with E. de Klerk, J. Maharry, R.B. Richter, and G. Salazar) Preprint 2004, available at http://arXiv.org/abs/math.CO/0404142, to appear in SIAM J. Discr. Math.
  41. Reduction of symmetric semidefinite programs using the regular *-representation. (with E. de Klerk and A. Schrijver) e-print nr. 2005-03-1083 at Optimization Online, available at http://www.optimization-online.org/DB_HTML/2005/03/1083.html, to appear in Math. Prog. (B)

2  Preprints.

  1. Local Characterizations of Geometries. PhD thesis, The University of Western Australia, 1994, available at http://arXiv.org/abs/math.GR/0103121
  2. Computing covariants of binary forms and related topics. Preprint 1995,
    available at http://stuwww.uvt.nl/~dpasech/misc/impl.dvi
  3. On the nullcone and Hironaka decompositions of the invariants of a torus.
    Preprint 1996, available at http://stuwww.uvt.nl/~dpasech/misc/torus.ps
  4. A construction of locally homogeneous graphs ("Weetman's construction"). (with A. Kasikova). Preprint 1996.
  5. Algebraic combinatorics in mathematical chemistry. Methods and algorithms. II. Program implementation of the Weisfeiler-Leman algorithm. (with L. Babel, I.V. Chuvaeva and M. Klin). Report TUM-M9701, 1997, Fakultät für Mathematik, TU München, available electronically at
    http://www-lit.ma.tum.de/veroeff/html/960.68019.html
  6. An interior point approximtion algorithm for a class of combinatorial optimization problems: implementation and enhancements, Preprint 1998,
    available at http://stuwww.uvt.nl/~dpasech/misc/fap.ps
  7. Bipartite sandwiches. Preprint 1999,
    available at http://arXiv.org/abs/math.CO/9907109
  8. Generating vertices with symmetries. (with A. Deza, K. Fukuda, and M. Sato) Proc. of the 5th Workshop on Algorithms and Computation, Tokyo (2000) 1-8, Tokyo University.
    available at  http://www.is.titech.ac.jp/~deza/WAAC_DFPS.ps
  9. CGAL Installation Guide. (with M.Hoffmann and W.Wesselink), in CGAL Reference Manual. available at  http://www.cgal.org/Manual/doc_html/frameset/fsInstallation.html
  10. On c([`G])-a(G) > 0 gap recognition and a(G)-upper bounds. (with S. Busygin) Electronic Colloquium on Computational Complexity Report TR03-052, available at ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2003/TR03-052/index.html, submitted for publication.
  11. Optimal disjoint prefect matchings on a pair of weighted bipartite graphs. (with B. Goldengorin and F. Sharifov) Preprint 2003, available at http://stuwww.uvt.nl/~dpasech/misc/disjointmatchings.ps
  12. Solving SDP's in non-commutative algebras part I: the dual-scaling algorithm. (with E. de Klerk) CentER Discussion Paper 2005, nr. 17, available at http://greywww.kub.nl:2080/greyfiles/center/2005/17.html
  13. A linear programming reformulation of the standard quadratic optimization problem. (with E. de Klerk) CentER Discussion Paper 2005-24, available at http://greywww.kub.nl:2080/greyfiles/center/2005/24.html, submitted for publication.
  14. A note on the stability number of an orthogonality graph. (with E. de Klerk) CentER Discussion Paper 2005-66, available at http://arXiv.org/abs/math.CO/0505038, submitted for publication.

3  Some (scientific) software authored.

A selection of links and downloads is available online at
http://stuwww.uvt.nl/~dpasech/software.html
  1. In [1-23]1 I developed an algorithm for finding the Hilbert basis for a system of linear homogeneous Diophantine equations. The accompanying implementation is available for download at http://stuwww.uvt.nl/~dpasech/code/hb.tgz. It should run on any Unix platform with an ANSI C compiler.
  2. I implemented in GAP 3 and GRAPE a classical algorithm to check if a given graph is an edge graph, that was instrumental in [1-26]. This GAP 3 code can be downloaded at ftp://ftp-gap.dcs.st-and.ac.uk/pub/gap/gap-3.4.4/deposit/gap/invling.g
  3. In [1-28] a part of a project to develop and implement algorithms to enumerate (orbiwise) the vertices of polytopes is described. My (programming) task there was to build an interface between Nauty (a program to compute automorphisms of graphs, also used in GRAPE by L. Soicher) and CDD (a suite of programs to enumerate vertices of polytopes, see http://www.cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html).
  4. CGAL (see http://www.cgal.org) is a large general-purpose computational geometry library written in C++. In 1999-2000 I worked full-time on CGAL, and was mostly involved in porting the library to Microsoft Windows platform. That included adopting STL implementation from http://www.stlport.org as a replacement for the standard STL of Microsoft VC++ compiler, porting GNU MP package (see http://www.gnu.org/software/gmp/gmp.html) to the latter compiler, developing an installation procedure for Windows.
  5. In [2-6] an implementation of a non-linear non-convex programming heuristic for a class of combinatorial optimization algorithms is decribed. It can be downloaded at http://stuwww.uvt.nl/~dpasech/code/fap.tar.gz.
  6. In [2-2] an implementation of a classical algorithm to construct a full system of covariants of binary forms of a given degree is described. A part of it, an implementation in C of a generalisation to systems of equations of an algorithm described in M.Clausen and A.Fortenbacher Ëfficient solutions of linear Diophanitine equations" J. Symb. Comp. 6(1988) 113-115, can be downloaded at http://stuwww.uvt.nl/~dpasech/code/dio.tgz.

Footnotes:

1The references are of the form ["sub-section number"- "item"] in this document.

File translated from TEX by TTH, version 3.70.
On 3 Oct 2005, 00:17.