Some research interests
My research concerns so far various aspects of discrete mathematics and applications to theoretical computer science. The theoretical basis of this research is strongly related to graph theory and combinatorics, complexity theory and algorithms, algebra and probabilistic techniques. My present research interests in discrete mathematics mostly focus on discrete extremal problems. Below I briefly describe three topics where my contribution is particularly essential.
Isoperimetric problems on graphs
I am dealing with vertex and edge isoperimetric problems. The vertex isoperimetric problem (VIP) consists of finding a set of vertices in a given graph, which has minimum number of vertices at distance 1 from the set, among all sets of the same cardinality. In my Ph. D. Thesis I studied VIP for the n-dimensional unit cube. One of the solutions to this problem was found by L.H. Harper more than 30 years ago, but I was interested in specification of all solutions. My results provide a complete description of the solution set for (3/4)2n possible values of the set size, and up to now no other series of solutions have been published. Later this description was used for specification of all maximal subsets of the n-cube with a fixed diameter.
VIP arises in many extremal problems and has numerous applications. Among such examples is the problem of finding a family of subsets of a finite set, such that the intersection of any two subsets contains at least t elements. My specification of all solutions of the diameter problem mentioned above provides a complete characterization of all maximal intersecting families for t > 1 and, thus, simplifies a known solution to this problem given by G. Katona.
I have also studied the VIP for some other graphs, such as the n-dimensional grid, torus, cartesian product of stars, the Johnson scheme and the set of vertices of the n-cube with an even number of ones. A solution of the last problem was a part of my Diploma thesis in the Moscow State University and was used by my advisor Prof. A.A. Sapozhenko for deriving an asymptotic for the number of binary codes with code distance 2. Our recent paper on VIP (written with O. Serra) gives a power tool for solving VIP on the cartesian products. This tool is so-called local-global principle, that was previously known for the edge-isoperimetric problems only.
The edge-isoperimetric problem (EIP) consists of finding a set of vertices in a graph with minimum cut separating this set from its complement among all sets of the same size. I developed a special theory for the EIP on the cartesian products of graphs. Briefly speaking, my approach is in establishing an equivalence relation on the set of all graphs and, thus, in partitioning graphs into equivalence classes. It turns out that if one has n pairs of equivalent graphs, then their cartesian products are also equivalent. Thus, one can emphasize on solving the problem for simplest representatives of an equivalence class. Having this theory in hands and combining it with some extremal poset problems, I have shown that all known results on the EIP for particular graph families known so far, are special cases of my approach.
Among our new results on the EIP is a solution of this problem for the cartesian products of Petersen graphs (joint research with R. Elsässer and S. Das and for the products of regular graphs of large degree. We also study other approaches to the EIP, e.g. spectral, algebraic and analytic methods, so-called local-global principles (see my publication list) and poset techniques. In particular, our lower bounds for the bisection width of regular graphs based on the eigenvalues of some related matrices, significantly improve known general lower bounds.
Shadow minimization problems on posets
Let (P,<) be a ranked poset and Pi be the set of all of its elements of rank i. For a subset A of Pi and i > 0 define the shadow of A as
Consider the shadow minimization problem (SMP) consisting of finding a set A of Pi, such that |S(A)| is minimum among all subsets of Pi of the same size.
I pay particular attention to constructing Macaulay posets, where the SMP has nested solutions which can be represented by initial segments of a certain total order on P. Almost all examples of Macaulay posets known in the literature are cartesian products of some posets. I studied the cartesian products of trees which, in particular, include all known Macaulay posets of the considered type and can specify all Macaulay posets of this class. This general result includes, in particular, the famous theorems of Kruskal and Katona and of Clements and Lindström as well as some other results. One of our recent results on SMP (with O. Serra and X. Portas) is a local-global principle. We have found almost necessary and sufficient conditions for a poset to satisfy this princile.
I have also studied the SMP on posets which are not cartesian products of other posets. Among such results is a solution of the SMP for the poset of all words of a binary alphabet ordered by the subword relation and the poset of linear subspaces of PG(n,2) ordered by inclusion (joint research with A. Blokhuis). In our research with A. Sali we study the poset of submatrices of a matrix and also some other kinds of poset products.
A few years ago I discovered deep relations between the EIP on graphs and the SMP on posets. It turned out that for any graph one can construct a representing poset so that a solution of the SMP on this poset implies a solution for the EIP on the original graph. This unifies the approach to the both problems and unites two research directions which were developed completely independently. My approach is to look at the EIP from a more general viewpoint of posets.
Graph embedding and partitioning
The problems mentioned above have natural applications to some problems of Computer Science. Partitioning of graphs is one of them. The problem is to partition the vertex set of a graph into k sets A1,...,Ak of almost the same size, i.e. ||A_i|-|A_j|| < 2 so that the number of edges connecting these parts is minimum. We got so far exact results concerning the partitioning of n-dimensional grids, hypercubes and cartesian products of cliques. Our constructions provide optimal or asymptotically optimal results. Lower bounds for the size of the cut are provided by the edge-isoperimetric problems.
As to embedding problems, I dealt for a certain time with the problem of specifying trees which span the graph of the n-cube. The problem is more than 30 years old and no satisfactory answer is known even for caterpillars. In our approach we developed a new embedding technique which implies all but one known results in this area and works for many new types of caterpillars. Another problem in this direction is to find for a given tree T the minimum n so that T is a subgraph of the n-cube. Even for complete t-ary trees with k levels the answer is not known. For t=1 and t=2, the minimum n is equal to t and (asymptotically) (3/2)t respectively. I proved that the minimum n for t=3 asymptotically equals (227/120)t. This result and a new technique improve a known upper bound for general k and t, and provide a new bound which is up to now the best known.
Presently just a few papers deal with implicit constructions for embedding of graphs into grids and tori. Grids are important interconnection networks and are used in a number of industrial computing system (e.g. Parsytec). We studied embedding of hypercubes into grids and obtained exact results concerning the dilation, edge-congestion and their mean values. We proposed new cost measures for embedding, showed their practical importance in realization of normal algorithms and constructed corresponding optimal embeddings of hypercubes into grids. In two other papers we study embedding of graphs arising in finite elements methods into grids, propose various heuristics and compare their performance.
Another interesting, important and insufficiently deep studied network architecture is a cycle. Surprisingly enough, for some graph classes the minimum dilation (resp. the edge-congestion) of an embedding of a graph into a path or a cycle is the same. In our recent paper we show that the minimum average dilation (and resp. average edge-congestion) of embeddings of trees into a path and cycle is also the same.