Search

We consider a model of stable edge sets (``matchings'') in a bipartite graph $G=(V,E)$ in which the preferences for vertices of one side (``firms'') are given via choice functions subject to standard axioms of consistence, substitutability and cardinal monotonicity, whereas the preferences for the vertices of the other side (``workers') via linear orders. For such a model, we present a combinatorial description of the structure of rotations and develop an algorithm to construct the poset of rotations, in time $O(|E|^2)$ (including oracle calls). As a consequence, one can obtain a ``compact'' affine representation of stable matchings and efficiently solve some related problems. (The paper is written in Russian.), Comment: 28 pages, in Russian language

The monography examines the problem of constructing a group of automorphisms of a graph. A graph automorphism is a mapping of a set of vertices onto itself that preserves adjacency. The set of such automorphisms forms a vertex group of a graph or simply a graph group. The basis for constructing a group of graph automorphisms is the concept of orbit. The construction of an orbit is closely related to the quantitative assessment of a vertex or edge of a graph, called weight. To determine the weight of an element, graph invariants built on the spectrum of edge cuts and the spectrum of edge cycles are used. The weight of the graph elements allows identifying generating cycles and forming orbits. Examples are given of constructing a group of automorphisms for some types of graphs., Comment: 123 pages, in Russian language, 304 figures, a preprint of monography

In this expository note we show how combinatorial Nullstellensatz by N. Alon naturally appears in solutions of elementary problems. Simple ideas gradually and naturally appear in such solutions, thus bringing a reader to generalizations. The note is accessible to mathematicians not specialized in the area, and to students familiar with polynomials., Comment: 10 pages; in Russian; exposition improved

The main result of the article says that the formal power series equal to the ratio of two neighboring Chebyshev polynomials, after some renormalization, approximates the generating function of the Catalan numbers. We present a proof of this result using continued fractions. Also, for completeness of the presentation, we recall the basic properties of Chebyshev polynomials and formal power series that we use., Comment: 8 pages, in Russian. Comments are welcome!

Meromorphic differentials on Riemann surfaces are said to be real-normalized if all their periods are real. Moduli spaces of real-normalized differentials on Riemann surfaces of given genus with prescribed orders of their poles and residues admit stratification by orders of zeroes of the differentials. Subsets of real-normalized differentials with the fixed polarized module of periods compose isoperiodic subspaces, which also admit this stratification. In this work we prove the connectedness of the principal stratum for the isoperiodic subspaces in the space of real-normalized differentials with a single pole of order two when all the periods are incommesurable., Comment: the article in Russian

For fixed $k$, we consider the subgraph $YF_k=(V_k,E_k)$ of the famous Young--Fibonacci graph formed by the words with at most $k$ 2-s. The jump graph is a graded graph is defined as follows: each level is identified with $V_k$, and an edge between two vertices $(v_1,i)$ and $(v_{2},i+1)$, $v_1,v_2\in V_k$, of neighbouring levels us drawn iff $v_2$ is a descendant of $v_1$ in $YF_k$. The goal of this paper is to describe all central measures on the path space of $YF_k$., Comment: 24 pages, in Russian

Our previous paper shows that the (vertex) spanning tree degree enumerator polynomial of a connected graph $G$ is a real stable polynomial (id est is non-zero if all variables have positive imaginary parts) if and only if $G$ is distance-hereditary. In this note we generalize the result on weighted graphs. This generalization allows us to define the class of weighted distance-hereditary graphs., Comment: in Russian

The method is based on the preliminary transformation of the traditionally used matrices or adjacency lists in the graph theory into refined projections free from redundant information, and their subsequent use in constructing shortest paths. Unlike adjacency matrices and lists based on enumerating binary adjacency relations, the refined projection is based on enumerating more complex relations: simple paths from a given graph vertex that are shortest. The preliminary acquisition of such projections reduces the algorithmic complexity of applications using them and improves their volumetric and real-time characteristics to linear ones for a pair of vertices. The class of graphs considered is extended to mixed graphs., Comment: 7 pages, in Russian language, 1 figures, 2 table

The paper is devoted to the study of combinatorial determinacy properties of a family of substitution complexes consisting of quadrilaterals glued side-to-side with each other. These properties are useful in constructing algebraic structures with a finite number of defining relations. In particular, this method was used when constructing a finitely presented infinite nisemigroup satisfying the identity x^9 =0. This construction responds to the problem of L. N. Shevrin and M. V. Sapir. In this paper, we investigate the possibility of coloring the entire sequence of complexes into a finite number of colors, in which the property of weak determinism is fulfilled: if the colors of the three vertices of a certain quadrilateral are known, then the color of the fourth side is uniquely determined, except in some cases of a special arrangement of the quadrilateral., Comment: in Russian language

The topic of stable matchings (marriages) in a bipartite graph has become widely popular, starting with the appearance of the classical work by Gale and Shapley. We give a detailed survey on selected known results in this field that demonstrate structural, polyhedral and algorithmic properties of such matchings and their sets, providing our description with relatively short proofs., Comment: 24 pages, in Russian language, 3 figures

We prove the simultaneous multiplication formulas for Apostol-Bernoulli polynomials and generalized Frobenius-Euler polynomials. These formulas contain Dedekind-Rademacher sums, Apostol-Dedekind sums and Fourier-Dedekind sums., Comment: in Russian

In this paper, we propose a general construction of linear perfect codes over infinite skew fields and quasi skew fields with right (left) unity. A complete classification of such codes over associative skew fields is given. Since the cardinality of the considered skew fields is infinite, the constructed codes have an infinite length. In the previous work, we considered codes over infinite countable fields, the length of which was also countable. We now remove this restriction and consider that the cardinality of the skew field and the length of the codes can be arbitrary (not necessarily countable)., Comment: In Russian

In 2010s Fleiner introduced a notion of stable flows in directed networks and showed that such a flow always exists and can be found by use of a reduction to the stable allocation problem due to Baiou and Balinski. Recently Cseh and Matuschke devised a direct strongly polynomial algorithm. In this paper we give an alternative algorithm to find a stable flow in a network with several sources and sinks. It is based on an idea of preflows (appeared in 1970s in a faster algorithm for the classical max-flow problem), and runs in $O(nm)$ time for a network with $n$ vertices and $m$ edges. The results are further generalized to a larger class of objects, so-called stable quasi-flows with bounded excesses in non-terminal vertices. (The paper is written in Russian.), Comment: 19 pages, in Russian language. Compared with the previous version, the reference to a grant is removed

We are interested in finding combinatorial criteria for embedding graphs into torus and using them in the embedding check algorithm. It is a well-known fact that any connected graph can be reduced to a one-vertex graph with loops and is homotopy equivalent to such a graph. If a connected graph has intersection of some edges, then some loops of one-vertex graph will also intersect. Therefore the problem of embedding graphs into some surface is equivalent to the question of embedding one-vertex graph in given surface. This paper considers a graph with rotations or rotation system called hieroglyph. The equivalence of four conditions is proved: (1) embedding hieroglyph into torus; (2) the absence of forbidden subgraphs in a hieroglyph; (3) some condition for the graph of loops; (4) the existence of a reduction of hieroglyph to one of the list of hieroglyphs. We also prove the existence of an algorithm with complexity $O(n)$ that recognizes embedding hieroglyph into torus., Comment: 6 pages, in Russian language, 4 figures

A graph $\Gamma$ is called locally finite if, for each vertex $v$ of $\Gamma$, the set $\Gamma(v)$ of all neighbors of $v$ in $\Gamma$ is finite. For any locally finite graph $\Gamma$ with vertex set $V(\Gamma)$ and for any field $F$, let $F^{V(\Gamma)}$ be the vector space over $F$ of all functions $V(\Gamma) \to F$ (with natural componentwise operations) and let $A^{({\rm alg})}_{\Gamma,F}$ be the linear operator $F^{V(\Gamma)} \to F^{V(\Gamma)}$ defined by $(A^{({\rm alg})}_{\Gamma,F}(f))(v) = \sum_{u \in \Gamma(v)}f(u)$ for all $f \in F^{V(\Gamma)}$, $v \in V(\Gamma)$. In the case of finite graph $\Gamma$ the mapping $A^{({\rm alg})}_{\Gamma,F}$ is the well known operator defined by the adjacency matrix of $\Gamma$ (over $F$), and the theory of eigenvalues and eigenfunctions of such operator is a well-developed (at least in the case $F = \mathbb{C}$) part of the theory of finite graphs. In this paper we develope a theory of eigenvalues and eigenfunctions of $A^{({\rm alg})}_{\Gamma,F}$ for arbitrary infinite locally finite graphs $\Gamma$ (although a few results may be of interest for finite graphs) and fields $F$ with a special emphasis on the case when $\Gamma$ is connected with uniformly bounded vertex degrees and $F = \mathbb{C}$. By the author opinion, previous attempts in this direction were not quite satisfactory since were limited by consideration of rather special eigenfunctions and corresponding eigenvalues., Comment: 52 pages, in Russian; a few minor corrections; published version

For the first time proposed: a method for representing the projections of a graph in computer memory and a description based on it of a quick search for shortest paths in unweighted dynamic graphs. The spatial complexity of the projection description does not exceed $(d + 1)\times n$ words, where $d$ is the diameter and $n$ is the number of vertices of the graph. The temporal difficulty of finding one shortest path between two vertices does not exceed d steps with the duration of elementary time of sampling a machine word. The solution can be applied in time delay-critical routing protocols of computer networks and supercomputers., Comment: 4 pages, in russian language, 2 figures, 6 tables

The article introduces some ideas for solving special cases of the following problem, proposed in a somewhat generalized form by Marcus Hutter in 2000. Given two Turing machines $A$ and $C$, it is required to build a Turing machine $B$, such that after interacting of $A$ and $B$ on a shared tape for a fixed number of iterations, the machine $C$ outputs 1 on the communication protocol of $A$ and $B$. Details in the introduction., Comment: in Russian

We give a new elementary proof of the theorem by Ambainis et al. that for a quantum walk, the probability amplitudes of absorption at the initial point after 4n steps are proportional to the Catalan numbers. We also calculate the absorption probabilities at points close to the initial one for the first time., Comment: in Russian

The paper answers the question posed in a joint paper by A. A. Klyachko and N. M. Luneva about the optimality of the estimate for the cost of symmetry in graphs. The original estimate says that if n vertices can be removed from a connected graph so that there is no connected subgraph of isomorphic $\Gamma$ left in it, then at most $n|V(\Gamma)|$ vertices that form a set invariant under all automorphisms of the graph so that the graph does not contain a subgraph isomorphic to $\Gamma$. We will prove that there exists a graph $\Gamma$ for which this estimate is not optimal., Comment: in Russian language

In this expository note we present simple proofs of the lower bound of Ramsey numbers (Erd\"os theorem), and of the estimation of discrepancy. Neither statements nor proofs require any knowledge beyond high-school curriculum (except a minor detail). Thus they are accessible to non-specialists, in particular, to students. Our exposition is simpler than the standard exposition because no probabilistic language is used. In order to prove the existence of a `good' object we prove that the number of `bad' objects is smaller than the number of all objects., Comment: 4 pages; in Russian; exposition improved

We generalize Gassert-Shor formula for numerical semigroups., Comment: in Russian

Among central measures on the path space of the Young--Fibonacci lattice the so-called Plancherel measure has a special role. Its ergodicity was proved by Kerov and Gnedin. The goal of this cycle of two articles is to prove that remaining measures from the Martin boundary of this graph (which were described by Kerov and Goodman) are also ergodic. The measures are parametrized with an infinite word of digits 1 and 2 and the parameter $\beta\in(0,1]$ (the case $\beta=0$ corresponds to the Plancherel measure). In this article we finish the proof of their ergodicity using the statements proved in the first paper as a "black box"., Comment: 168 pages, in Russian

Among central measures on the path space of the Young--Fibonacci lattice the so-called Plancherel measure has a special role. Its ergodicity was proved by Kerov and Gnedin. The goal of this cycle of two articles is to prove that remaining measures from the Martin boundary of this graph (which were described by Kerov and Goodman) are also ergodic. The measures are parametrized with an infinite word of digits 1 and 2 and the parameter $\beta\in(0,1]$ (the case $\beta=0$ corresponds to the Plancherel measure). In this article we prove the statements which correspond to the case $\beta=1$., Comment: 50 pages, in Russian

The Young--Fibonacci graph is the Hasse diagram of one of the two (along with the Young lattice) 1-differential graded modular lattices. This explains the interest to path enumeration problems in this graph. We obtain a formula for the number of paths between two vertices of the Young--Fibonacci graph which is polynomial with respect to the minimum of their ranks., Comment: 105 pages, Russian, short English version avaible at https://link.springer.com/article/10.1007/s10958-020-04829-7

We present an accurate detailed exposition of the proof of existence of the Alexander-Conway polynomial (of links in 3-dimensional space). Other proofs were given by J. Alexander, J. Conway, V. Mantourov and L. Kauffman., Comment: 9 pages, in Russian, 7 figures

An hieroglyph on n letters is a cyclic sequence of the letters 1,2, . . . , n of length 2n such that each letter appears in the sequence twice.Take an hieroglyph H. Take a convex polygon with 2n sides. Put the letters in the sequence of letters of the hieroglyph on the sides of the convexpolygon in the same order. For each letter i glue the ends of a ribbon to thepair of sides corresponding to the letter i. Call the resulting surface a disk with ribbons corresponding to the hieroglyph H. An hieroglyph H is weakly realizable on the M\"obius strip if some disk with ribbons corresponding to H can be cut out of the M\"obius strip. We give a criterion for weak realizability, which gives a quadratic (in the number of letters) algorithm. Our criterion is based on the Mohar criterion for realizability of a disk with ribbons in the M\"obius strip., Comment: in Russian

If a regular graph of degree $k$ and diameter $d$ has $v$ vertices then $$v\le 1+k+k(k-1)+\dots+k(k-1)^{d-1}.$$ Graphs with $v=1+k+k(k-1)+\dots+k(k-1)^{d-1}$ are called Moore graphs. Damerell proved that a Moore graph of degree $k\ge 3$ has diameter $2$. If $\Gamma$ is a Moore graph of diameter $2$, then $v=k^2+1$, $\Gamma$ is strongly regular with $\lambda=0$ and $\mu=1$, and one of the following statements holds{\rm:} $k=2$ and $\Gamma$ is the pentagon, $k=3$ and $\Gamma$ is the Petersen graph, $k=7$ and $\Gamma$ is the Hoffman-Singleton graph, or $k=57$. The existence of a Moore graph of degree $57$ was unknown. Jurishich and Vidali have proved that the existence of a Moore graph of degree $k>3$ is equivalent to the existence of a distance-regular graph with intersection array $\{k-2,k-3,2;1,1,k-3\}$ (in the case $k=57$ we have a distance-regular graph with intersection array $\{55,54,2;1,1,54\}$). In this paper we prove that a distance-regular graph with intersection array $\{55,54,2;1,1,54\}$ does not exist. As a corollary, we prove that a Moore graph of degree $57$ does not exist., Comment: 7 pages, in Russian

We prove that one can cover the $1 \times b$ rectangle by equal squares on both sides in one layer iff $b = p \pm \sqrt{p^2 - r^2} $, where $p \ge r \ge 0$ and $p,q \in \mathbb{Q}$., Comment: 3 pages, in Russian

We present a motivated exposition of the proof of the following Tverberg Theorem: For every integers $d,r$ any $(d+1)(r-1)+1$ points in $\mathbb R^d$ can be decomposed into $r$ groups such that all the $r$ convex hulls of the groups have a common point. The proof is by well-known reduction to the B\'ar\'any Theorem. However, our exposition is easier to grasp because additional constructions (of an embedding $\mathbb R^d\subset\mathbb R^{d+1}$, of vectors $\varphi_{j,i}$ and statement of the Bara\'ny Theorem) are not introduced in advance in a non-motivated way, but naturally appear in an attempt to construct the required decomposition. This attempt is based on rewriting several equalities between vectors as one equality between vectors of higher dimension., Comment: 2 pages, in Russian

The paper provides an elementary proof of Kenyon's necessary condition for the existence of a periodic tiling of the plane by squares with given periods. A similar new result on covering both sides of a rectangle by nonoverlaping squares is proved., Comment: 8 pages, in Russian

We consider the problem of estimating the distance between two bodies of volume $\varepsilon$ located inside a $n$-dimensional ball $U$ of unit volume for $n\to\infty$. Let $A$ be a closed set with a smooth boundary of the volume $\varepsilon$ ($0 \leq \varepsilon \leq 1/2$) inside a $n$-dimensional ball $U$ of unit volume that implements among all the sets of volume $\varepsilon$ is a set with the smallest possible free surface area, lying in one half-space with respect to a certain hyperplane that passes through the center of the ball. Then $A$ has the same free surface area as the set representing the intersection of a ball perpendicular to $U$ and the ball $U$ itself., Comment: 6 pages, in Russian, The work was carried out with the help of the Russian Science Foundation Grant N 17-11-01377, to appear in Math. Notes

The article provides a criterion for the substitution of symmetric Sturm words infinite on both sides and its proof. This work was carried out with the help of the Russian Science Foundation Grant N 17-11-01377., Comment: 6 pages, in Russian, to appear in Bull of Moscow State University

This paper (written in Russian) presents a survey of new and earlier results on fine zonotopal tilings (briefly, cubillages) of cyclic zonotopes. The combinatorial theory of these objects is of interest in its own right and also has a connection to higher Bruhat orders, triangulations of cyclic polytopes, and Tamari-Stasheff posets applied in the study of Kadomtsev--Petviashvily equations, and etc., Comment: in Russian, 61 pages

We prove that, for every $\ell\geq 4$, there exists an $\ell$-vertex graph and a first order sentence having a quantifier depth at most $\ell-1$ defining the property of having an induced subgraph isomorphic to the given one. We prove that a first order sentence defining the property of containing an induced subgraph on $\ell$ vertices isomorphic to a given disjoint union of isomorphic complete multipartite graphs has a quantifier depth at least $\ell$. Finally, we prove that, for every graph on $\ell\leq 5$ vertices a sentence defining the property of containing an induced subgraph isomorphic to the given one has a quantifier depth at least $\ell-1$., Comment: in Russian

Harer-Zagier generating functions for Euler characteristics of moduli spaces of curves contain $n$-necklace polynomials. Taylor expansions for these polynomials depend on numbers of solutions of Cohen semilinear congruences., Comment: in Russian

The paper proves the existence of monochrome standard simplexes of a given volume on a multidimensional rational lattice painted in a finite number of colors., Comment: 15 pages, in Russian. This work was carried out with the help of the Russian Science Foundation Grant N 17-11-01377

By a (latin) unitrade, we call a set of vertices of the Hamming graph that is intersects with every maximal clique in $0$ or $2$ vertices. A bitrade is a bipartite unitrade, that is, a unitrade splittable into two independent sets. We study the cardinality spectrum of the bitrades in the Hamming graph $H(n,k)$ with $k=3$ (ternary hypercube) and the growth of the number of such bitrades as $n$ grows. In particular, we determine all possible (up to $2.5\cdot 2^n$) and large (from $14\cdot 3^{n-3}$) cardinatities of bitrades and prove that the cardinality of a bitrade is compartible to $0$ or $2^n$ modulo $3$ (this result has a treatment in terms of a ternary code of Reed--Muller type). A part of the results is valid for any $k$. We prove that the number of nonequivalent bitrades is not less than $2^{(2/3-o(1))n}$ and is not greater than $2^{\alpha^n}$, $\alpha<2$, as $n\to\infty$., Comment: 18 pp. In Russian

A graph {\it has cutwidth at most 2} if one can number its vertices by $1,\ldots n$ so that for every $i=1,\ldots,n-1$ there are at most 2 edges $(u,v)$ such that $u\le i

Let a polygon be composed of equal rectangles. We find all quadratic irrationals r for which the polygon can be tiled by similar rectangles with given side ratio r., Comment: In Russian, 6 pages, 4 figures. v2: minor additions and corrections

Let $G$ be a group and $S\subseteq G$ its subset such that $S=S^{-1}$, where $S^{-1}=\{s^{-1}\mid s\in S\}$. Then {\it the Cayley graph ${\rm Cay}(G,S)$} is an undirected graph $\Gamma$ with the vertex set $V(\Gamma)=G$ and the edge set $E(\Gamma)=\{(g,gs)\mid g\in G, s\in S\}$. A graph $\Gamma$ is said to be {\it integral} if every eigenvalue of the adjacency matrix of $\Gamma$ is integer. In the paper, we prove the following theorem: {\it if a subset $S=S^{-1}$ of $G$ is normal and $s\in S\Rightarrow s^k\in S$ for every $k\in \mathbb{Z}$ such that $(k,|s|)=1$, then ${\rm Cay}(G,S)$ is integral.} In particular, {\it if $S\subseteq G$ is a normal set of involutions, then ${\rm Cay}(G,S)$ is integral.} We also use the theorem to prove that {\it if $G=A_n$ and $S=\{(12i)^{\pm1}\mid i=3,\dots,n\}$, then ${\rm Cay}(G,S)$ is integral.} Thus, we give positive solutions for both problems 19.50(a) and 19.50(b) in "Kourovka Notebook"., Comment: in Russian

In this work authors significantly improved previous estimates of the number of edges in subgraphs of the special distance graph., Comment: in Russian

The set of all avoidable patterns in n or fewer letters can be avoided on an alphabet with 2(n+2) letters., Comment: In Russian. The proof of this theorem was discovered long ago, in this version it was sent to the journal in 1996, but it was not published. I thank D. McNulty, K.Adaricheva for finding me and advising me to publish this result

We prove several formulas for the distribution of positive roots., Comment: in Russian

Question when rectangle can be tiled with similar copies of rectangles witch quetient of sides quadratic irrationalities. New proof of one part F. Sharov's theorem. Other close result., Comment: in Russian

We give a new simple proof of Dehn's theorem by generalizing the notion of area. The method proposed in the present article is actually the "translation" of the method of additive functions into the elementary math language., Comment: In Russian; 6 pages; 4 figures

Here I present several theorems about trapezoids tilings. The first one is related to trapezoids with rational base relation, the other ones are related to those with base relation from quadratic number field., Comment: In Russian

We obtain a recurrence relation for the f-polynomial of Gelfand-Zetlin polytopes by analyzing geometric properties of a linear projection of the Gelfand-Zetlin polytope onto a cube. We apply this recurrence relation to find explicit formulas for the f-polynomials and h-polynomials of Gelfand-Zetlin polytopes that belong to several simplest one-parameter families., Comment: 25 pages, 5 figures (new!), in Russian. Revised introduction, added more material to section 3

We present two sets of 12 integers that have the same sets of 4-sums. The proof of the fact that a set of 12 numbers is uniquely determined by the set of its 4-sums published 50 years ago is wrong, and we demonstrate an incorrect calculation in it., Comment: Published in Zapiski Nauchn. Semin. POMI, Vol. 448, 2016 (in Russian). To appear in Journal of Mathematical Sciences (English translation)

In previous papers, threshold probabilities for the properties of a random distance graph to contain strictly balanced graphs were found. We extend this result to arbitrary graphs and prove that the number of copies of a strictly balanced graph has asymptotically Poisson distribution at the threshold., Comment: in Russian

A short survey about combinatorics on words and algorithmic methods in a ring. Special attention is given to Shirshov's results. Adopted for undegraduate students., Comment: 6 pages, in Russian