Department of Mathematical
Sciences
Olney Hall 428K,
Curriculum Vitae in PDF (as of February 2008)
Geometry of Numbers,
Discrete Geometry and Convexity,
Computational Geometry and Topology,
Graph Rigidity & Flexibility with a View towards Molecular Modeling,
Topological and Geometric Graph Theory,
Stochastic Geometry and Percolation Theory,
Statistics.
I am willing and interested in supervising
student research and advanced directed learning at undergraduate, Masters, and
doctoral levels in some of the above areas and in implementation of geometric
and topological algorithms. Interested students email to krybniko@cs.uml.edu . You can also
contact me if you are interested in doctoral program administered jointly by
departments of Mathematical Sciences and Computer Science called D. Sc. in Computer Science -
Computational Mathematics Option (this
might also be called Mathematics of
Computing and Computational Statistics). While the paperwork
should go thought the
I am also willing to do summer undergraduate
research (similar to National Science Foundation's REU) with students living /
working / studying in
This is not an regular RA/TA position ad -- please do not contact me if you are only looking for supplementing your income with a TA or RA contract, but your interests lie in other areas.
(posted in February of 2008)
Abstract: In the Hyperbolic space Hn (n >2) there are uncountably many topological types of convex hypersurfaces. When is a locally convex hypersurface in Hn globally convex, that is, when does it bound a convex set? We prove that any locally convex proper embedding of an (n-1)-dimensional connected manifold is the boundary of a convex set whenever the complement of (n-1)-flats of the resulting hypersurface is connected.
Abstract: We observe that for small n the ball packing density does not have suboptimal local maxima on the reduced Voronoi graph, whose vertices are the arithmetic equivalence classes of perfect quadratic forms and whose edges are the walls between the corresponding perfect domains.
An Efficient Local Approach to Convexity
Testing of Piecewise-Linear Hypersurfaces (to appear in Computational Geometry: Theory and
Applications)
(updated in January of 2008)
Abstract: We show that a closed connected bounded
piecewise-linear hypersurface in the Euclidean space
of dimension at least 3 is the boundary of a convex body if and only if every
point in the interior of each (n-3)-face
has a neighborhood that lies on the boundary of some convex body; no
assumptions about the hypersurface topology are
needed. We derive this criterion from our generalization of
Contemporary
Mathematics 452 (2008).
Abstract: A polytope D whose vertices belong to a lattice of
rank d is
In Proceedings of ISVD-07, pp. 182-189, IEEE International Symposium on Voronoi Diagrams in Science and Engineering, Pontypridd,
Abstract: A lattice
INTEGERS: ELECTRONIC JOURNAL
OF COMBINATORIAL NUMBER THEORY 7 (2007),
#A39
http://www.westga.edu/~integers
Abstract: A lattice
Local Minimax
Learning of Approximately Polynomial Functions (with
In Proceeding of Dagstuhl
Seminar 06201 "Combinatorial and Algorithmic Foundations of Pattern and
Association Discovery", held in May of 2006 in the International
Conference and Research Center (IBFI),
A shorter version, under the title ``A Study
of Conway's Thrackle Conjecture", appeared
in Proceedings of 18th Canadian Conference on Computational Geometry,
August 14-16, 2006, Queen's University,
Abstract: A thrackle is a
drawing of a simple graph on the plane, where each edge is drawn as a smooth
arc with distinct end-points, and every two arcs have exactly one common point,
at which they have distinct tangents.
Abstract:
Determination of the geometry and topology of a
3-dimensional body is an important problem appearing in areas such as
computer-aided design, medical tomography, crystallography, and molecular
biology. This paper estimates the
Release 2 notes:
A bug in the parser part of main.ccp
was fixed (the bug resulted in the program refusing correctly formatted test
description files).
No changes to the algorithms have been made.
Abstract: A perfect (
Discrete and Computational Geometry, Volume 34, No. 2, (2005), 251--268
Abstract: A
gain (a.k.a. voltage) graph is a triple (Γ,g,G), where Γ is a graph
with arbitrary, but fixed orientations of edges, and g is a homomorphism
from the free group on the edges of Γ to some group G. (Γ,g,G)
is called balanced if all closed walks on Γ lie in the kernel of g.
Thomas Zaslavsky and I derived a computationally
efficient test, formulated in terms of the binary cycle space of (Γ,g,G), that can be used to detect if (Γ,g,G) is balanced for some choices of G,
in particular when G is Abelian. Consider a
gain graph with Abelian gain group having no odd
torsion. If there is a basis of the graph’s binary cycle space, each of whose
members can be lifted to a closed walk whose gain is the identity, then the
gain graph is balanced, provided that the graph is finite or the group has no
non-trivial infinitely 2-divisible elements. In discrete geometry,
there is a number of local-to-global results dealing with tilings
of spaces of constant curvature and PL-realizations of manifolds in Rn. Several examples are: Coxeter classification of groups generated by reflections; Venkov-McMullen characterization of parallelohedra;
Journal of Graph Theory, Volume 51, No. 1, (2006), 1--21 ;
published on line
Abstract: We examine two criteria for balance of a gain graph,
one based on binary cycles and one on circles. The graphs for which each
criterion is valid depend on the set of allowed gain groups. The binary cycle
test is invalid, except for forests, if any possible gain group has an element
of odd order. Assuming all groups are allowed, or all Abelian
groups, or merely the cyclic group of order 3, we characterize, both
constructively and by forbidden minors, the graphs for which the circle test is
valid. It turns out that these three classes of groups have the same set of
forbidden minors. The exact reason for the importance of the ternary cyclic
group is not clear.
Proceedings of Steklov Mathematical Institute, Volume 239, No. 4, (2002), 159--167
Abstract:
This compressed version appeared in the
Rendiconti del Circolo Matematiko di Palermo,
A longer version available as math.MG/0112098 on http://arXiv.org
.
Abstract:
The text contains a concise introduction to Voronoï's theories of perfect forms and L-types.
Advances in Applied Probability, Volume 34, (2002), 292--312
Abstract: What is the effect of punching holes at random
in an infinite tensed membrane? When will the membrane still support tension?
This problem was introduced by
Journal of Statistical Physics, Volume 105, No. 1/2, (2001), 145--173
Abstract: We introduce a new class of bootstrap percolation
models where the local rules are of a geometric nature as opposed to simple
counts of standard bootstrap percolation. Our geometric bootstrap percolation
comes from rigidity theory and convex geometry. We outline two percolation
models: a Poisson model and a lattice model. Our Poisson model describe show
defects---holes is one of the possible interpretations of these
defects---imposed on a tensed membrane result in a redistribution or loss of
tension in this membrane; the lattice model is motivated by applications of Hooke spring networks to problems in material sciences. An
analysis of the Poisson model is given by Menshikov,
Rybnikov, and Volkov (2002). In the discrete set-up we consider regular
and generic triangular lattices on the plane where each bond is removed with
probability 1-p. The problem of the existence of tension on such lattice
is solved by reducing it to a bootstrap percolation model where the set of
local rules follows from the geometry of stresses. We show that both regular
and perturbed lattices cannot support tension for any p<1. Moreover,
the complete relaxation of tension -- as defined in Section 3 -- occurs in a
finite time almost surely. Furthermore, we underline striking similarities in
the properties of the Poisson and lattice models.
European Journal of Combinatorics, Volume 22, No. 6, (2001), 801--820
Abstract: We show how a d-stress on a piecewise-linear realization of an oriented (non-simplicial, in general) d-manifold in Rd naturally induces stresses of lower dimensions on this manifold, and discuss implications of this construction to the analysis of self-stresses in spatial frameworks. The mappings we construct are not linear, but polynomial. In the 1860-70s J. C. Maxwell described an interesting relationship between self-stresses in planar frameworks and vertical projections of polyhedral 2-dimensional surfaces from R3 . We offer a spatial analog of Maxwell's correspondence based on our polynomial mappings. By applying our main result we derive a class of 3-dimensional spider webs similar to the 2-dimensional spider webs described by Maxwell. We also conjecture an important property of our mappings that is based on the lower bound theorem ( g2(d+1) = dim Stress2 ≥ 0 ) for d-pseudomanifolds generically realized in Rd +1 proved by Fogelsanger.
This paper is probably the best source (on this web-site) on Maxwell correspondence.
Pre-publication version:
Discrete and Computational Geometry, Volume 21, (1999), 481--517
Abstract: This paper introduces a general notion of stress on cell-complexes immersed in Rd and reports on connections between stresses and liftings (generalization of C10-splines) of d-dimensional cell-complexes immersed in Rd . New sufficient conditions for the existence of a sharp lifting for a "flat" piecewise-linear realization of a manifold are given. Our approach also gives some new results on the equivalence between spherical complexes and convex and star polytopes. As an application, two algorithms are given that determine whether a piecewise-linear realization of a d-manifold in Rd admits a lifting to Rd+1 , which satisfies given affine constraints. We also demonstrate connections between stresses and Voronoï-Dirichlet decompositions and show that any weighted Voronoï-Dirichlet decomposition, without non-compact cells, can be seen a weighted Delaunay decomposition and vice versa.
This paper is a
good source on generalized Maxwell-Cremona
correspondence
Corrigendum:
1. Please note that Lemma 4.1 actually holds for the case when the graph is finite and the group G is Abelian without odd torsion. If the graph is infinite, the homomorphic image of the fundamental group of the graph should not be 2-divisible for Lemma 4.1 to hold true. Only torsion-free Abelian groups are used in the theorems of this paper.
2. All results on splines (Section 8) hold not only for Crr-1-splines,but also for Ckr-1-splines, for any k<r (only the dimensions of spline spaces should be recalculated). The given proof goes through without modifications.
European
Journal of. Combinatorics 18, (1997),
431 – 444.
Abstract: In this paper, we consider a broad class of simply
connected complexes that includes, for example, the face-to-face tilings of En
and Sn
. Along with a complex (or tiling) we consider a set Q of qualities that individually can be assigned to the various
cells or tiles of the complex, and a group G
which permutes the elements of Q.
These qualities might be, for example, colors,
positive real numbers, or affine functions . If each ordered pair of
adjacent cells is associated with a group element g from G, and a quality q of Q is assigned to any particular cell of
the complex, qualities can be assigned to adjacent cells using the action of
the group G on Q. In fact, since the complex is assumed to be simply connected
(and therefore connected), a quality can be assigned to any cell of the complex
by translating (in retrospect, ``transferring" would be a better word)
qualities along paths of adjacent cells using the group action. Our main theorem
gives sufficient conditions that the quality assigned to a cell in this manner
is independent of the particular path used for the translation, and is
therefore uniquely determined. As applications of this theorem we establish an
n -dimensional generalization of the converse of
Doklady Mathematics, Volume 54, (1996), 614--617.
Abstract: The problem of determining whether a given tiling of the Euclidean space can be obtained as the projection of a convex surface has at least two origins -- Maxwell correspondence in Rigidity Theory and Voronoï's Generatrice in Geometry of Numbers and Mathematical Crystallography. We give a few necessary conditions for the plane and for the general dimension, including the theorem that for any (d-3)-simple tiling can be lifted to a convex surface. We also introduce the projective notion of a dual tiling that generalizes the notion of dual graph. It turns out that a convex tiling can be lifted to a convex surface if and only if a dual convex tiling exists. Unfortunately this work is available only in paper form. Email your requests.
(Degree granted in the spring of 2000)
Includes: generalized Maxwell-Cremona, partial Maxwell-Cremona correspondence for graph realized in 3-space, fast algorithm for lifting a (d-3)-simple tiling of Rd (equivalently, Schlegel diagram) to a convex hypersurface in Rd+1 , stochastic geometry models motivated by rigidity theory and statistical physics.
Corrigendum:
1. Please note that Lemma 4.1 actually holds for the case when the graph is finite and the group G is Abelian without odd torsion. If the graph is infinite, the homomorphic image of the fundamental group of the graph should not be 2-divisible for Lemma 4.1 to hold true. Only torsion-free Abelian groups are used in the theorems of this paper.
2. All results on splines (Section 8) hold not only for Crr-1-splines,but also for Ckr-1-splines, for any k<r (only the dimensions of spline spaces should be recalculated). The given proof goes through without modifications.
Work in
progress: C++ Library for Analysis of Infinitesimal (i.e. First-Order) Rigidity
of Structures in Euclidean Space.
Currently only
linear-algebraic part is publicly available.
FORMAMENTUM - release 2 (zip file)
FORMAMENTUM - release 2 (bzip2ed tar file)
Brief Description (updated 04 May 2007)
In all experiments on (scalar) rigidity matrices of size 3|V| x |E| = 550 x 13600 or less the rank was found correctly. (Note that the bound of 36 x 106 previously stated here was a typo.) This code can be compiled with g++, any version from 2.96 and up. It was tested with g++ 2.96.X, 3.4.3 and 4.0.2 20050901 (prerelease: SUSE Linux).
For random (for any i , j in V the edge (ij) exists with probability p) graphs on 350-550 vertices the average vertex degree of 5.5 or higher always resulted in a rigid graph.
Updated 19 February 2008