Search

In the present paper, the enumeration of a certain class of directed lattice paths is based on the analysis of dynamical correlation functions of the exactly solvable XX0 model. This model is the zero anisotropy limit of one of the basic models of the theory of integrable systems, the XXZ Heisenberg magnet. It is demonstrated that the considered correlation functions under different boundary conditions are the exponential generating functions of various types of paths, in particular, Dyck and Motzkin paths. [ABSTRACT FROM AUTHOR]

In this paper, we examine the value m(n, r) in the Erdős–Hajnal problem. Using various methods, we obtain the estimate 27 ≤ m(3) ≤ 35. [ABSTRACT FROM AUTHOR]

This paper is a review of results on multiple flag varieties, i.e., varieties of the form G/P1×· · ·×G/Pr. We provide a classification of multiple flag varieties of complexity 0 and 1 and results on the combinatorics and geometry of B-orbits and their closures in double cominuscule flag varieties. We also discuss questions of finiteness for the number of G-orbits and existence of an open G-orbits on a multiple flag variety. [ABSTRACT FROM AUTHOR]

The classical results by Kräuter and Seifter concerning the divisibility of permanents for (±1)-matrices by large powers of 2 are useful in testing whether the permanent function is nonvanishing. This paper suggests a new approach to this problem, allowing one to obtain a short combinatorial proof of the results by Kräuter and Seifter. [ABSTRACT FROM AUTHOR]

In a recent paper, A. M. Vershik and the author started the study of representation-theoretic aspects of well-known combinatorial functions on the symmetric groups n. The note presents a series of further results in this direction. [ABSTRACT FROM AUTHOR]

The paper presents a shortcut introduction to the theory of hyperbolic virtual polytopes from the point of view of combinatorial rigidity. (It is assumed that the reader is acquainted with the notions of Laman graph, 3D lifting, and pointed tiling.) From this point of view, a hyperbolic virtual polytope is a stressed pointed graph embedded in the sphere S. The advantage of such a presentation is that it gives an alternative and most convincing proof of existence of hyperbolic virtual polytopes. Bibliography: 20 titles. [ABSTRACT FROM AUTHOR]

In this paper, in the context of the 'dessins d'enfants' theory, we give a combinatorial criterion for a plane tree to cover a tree from the classes of 'chains' or 'stars.' We also discuss some applications of this result that are related to the arithmetical theory of torsion on curves. [ABSTRACT FROM AUTHOR]

The study of the relationship between the Hasse diagrams and motives of projective homogeneous varieties is continued. The paper contains a combinatorial description of some multilinear invariants and a description of the Chernousov-Gille-Merkurjev method of motivic decompositions. Bibliography: 17 titles. [ABSTRACT FROM AUTHOR]

Rational functions on algebraic curves, which have a single zero and a single pole, are considered. A pair consisting of such a function and a curve is called an Abel pair; a special case of an Abel pair is a Belyi pair. In the present paper, moduli spaces of Abel pairs for curves of genus one are studied. In particular, a number of Belyi pairs over the fields ℂ and $$ \overline{{\mathbb{F}}_p} $$ is computed. This approach could be fruitfully used in studying Hurwitz spaces and modular curves for fields of finite characteristics. [ABSTRACT FROM AUTHOR]

In the present paper, we study derivations of a ( n, 2 , 1)-nilpotent Lie algebra. [ABSTRACT FROM AUTHOR]

Connections between certain types of categories (logoses and toposes) and intuitionistic predicate logic was established in 1960-1970 by Lowvere. The possibility of extending this connection to some types of modal logics by using the internal structure of categories of particular type (logos) was also established. Category-theoretical constructs were hence used as one of the possible semantic interpretations of intuitionistic logic. This interpretation has also included intuionistic modal logics using different semantical tools such as adjoint pair of functors. In this paper, we discuss one of the possible extension of intuitionistic logic. [ABSTRACT FROM AUTHOR]

The paper studies the notion of imprimitivity index of a semigroup of nonnegative matrices, introduced by Protasov and Voynov. A new characterization of the imprimitivity index in terms of the scrambling rank of a nonnegative matrix is suggested. Based on this characterization, an independent combinatorial proof of the Protasov-Voynov theorem on the interrelation between the imprimitivity index of a semigroup of stochastic matrices and the spectral properties of matrices in the semigroup is presented. [ABSTRACT FROM AUTHOR]

Many invariants of knots rely upon smoothing the knot at its crossings. To compute them, it is necessary to know how to count the number of connected components the knot diagram is broken into after the smoothing. In this paper, it is shown how to use a modification of a theorem of Zulli together with a modification of the spectral theory of graphs to approach such problems systematically. We give an application to counting subdiagrams of pretzel knots which have one component after oriented and unoriented smoothings. [ABSTRACT FROM AUTHOR]

In this paper, we consider the functions on algebraic curves whose divisors have the form nA−nC. Combinatorial-topological and algebraic descriptions are introduced for exploring such functions. All Belyi functions with such divisors are described. The case of curves of genus 1 is considered in more detail. The number of Belyi functions with divisor nA − nC is explicitly calculated. For general functions of this type on a curve of genus 1, we consider the space of the parameters and a method of its calculation that uses the Padé approximation. [ABSTRACT FROM AUTHOR]

The paper suggests a combinatorial proof of the Protasov-Voynov theorem on an irreducible semigroup of nanonegative matrices free of positive matrices. This solves the problem posed by the authors of the theorem. Bibliography: 6 titles [ABSTRACT FROM AUTHOR]

J. S. Birman and W. W. Menasco [ Topology, 33, 525-556 (1994)] introduced and studied a class of imbedded tori in closed braid complements that admit a standard tiling. K. Y. Ng [ J. Knot Theory Ramifications, 7, 205-216 (1998)] showed that each essential torus in a closed braid complement that admits standard tiling possesses a staircase pattern. The combinatorial and geometric description of the tori from this class was partially given in [ Fund. Math., 189, 195-226 (2006)]. In the present paper, we continue the study of the decomposition of tiled tori into building blocks and show that they are similar in a certain sense. In particular, for the class of geometric tiled tori described by Ng in [ J. Knot Theory Ramifications, 7, 205-216 (1998)], we show that each torus of this type consists only of elementary blocks. [ABSTRACT FROM AUTHOR]

We survey recent results concerning the combinatorial size of subsets of groups. For a cardinal κ, according to its arrangement in a group G, a subset of G is distinguished as κ-large, κ-small, κ-thin, κ-thick, and P-small. By analogy with topology, there arise the following combinatorial cardinal invariants of a group: density, cellularity, resolvability, spread, etc. The paper consists of 7 sections: Ballean context, Amenability, Ideals, Partitions, Packings, Around thin subsets, and Colorings. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to construct a duality theory for finite commutative multivalued groups and to demonstrate its connection with the classical duality in the theory of ordinary groups and the Kawada-Delsarte duality in algebraic combinatorics. We study in detail the case of multivalued groups of order three, construct a parameterization of the set of these groups, and obtain explicit formulas for the duality. In future, we plan to use this duality in the study of the coset problem. Bibliography: 26 titles. [ABSTRACT FROM AUTHOR]

The paper studies the problem indicated in the title, which arises in connection with the well-known Nelson–Erdös–Hadwiger problem of finding the chromatic number of the Euclidean space. [ABSTRACT FROM AUTHOR]

The combinatorial classification of plane trees by the number of realizations of their valency sets has distinguished some special classes of plane trees. One of them, the plane trees of diameter 4, turned out to be a very interesting object of investigation from the Galois action point of view. In this paper, we present equation sets for some subclasses of trees of diameter 4, calculate discriminants of the corresponding generalized Chebyshev polynomials, some related polynomials, and their fields of definitions, and use this to get some information about the Galois action on plane trees. [ABSTRACT FROM AUTHOR]

This paper deals with Grothendieck dessins d'enfants, i.e., tamely embedded graphs on surfaces, and Belyi pairs, i.e., rational functions with at most three critical values on algebraic curves. The relationship between these objects was promoted by Grothendieck. We investigate combinatorics of systems of equations determining a Belyi pair corresponding to a given dessin. Some properties of extra, or so-called parasitic, solutions of such systems are described. As a corollary, we obtain some applications concerning anti-Vandermonde systems. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with identity. Any order on terms of the polynomial algebra R[ x 1, ..., x k] induces in a natural way the notion of a leading term. An order on terms is called multiplicative if and only if the leading term of a product equals the product of leading terms. In this paper, we present a procedure for the construction of multiplicative orders. We obtain some characterizations of rings for which such orders exist. We give conditions sufficient for the existence of such orders. [ABSTRACT FROM AUTHOR]

Informally, a family $$\mathcal{F} \subseteq S_n $$ of permutations is k-restricted min-wise independent if for any $$X \subseteq [n]$$ with |X| ⩽ k, each x ∈ X has an equal chance of being mapped to the minimum among π(X). In the second section of this paper, the connection of min-wise independent families of permutations and independence on lth minimum is studied. In the third section, we present a method of constructing a (k + 1)-restricted min-wise independent family from a k-restricted min-wise independent family when k is odd. As a corollary, we improve the existing upper bound on the minimum size of a 4-restricted min-wise independent family. In the last section, we consider min-wise independent groups of permutations. Bibliography: 12 titles. [ABSTRACT FROM AUTHOR]

A function $f(z)=\backslash sum^\backslash infty\_\{k=0\}a\_kz^\{n\_k\}$ analytic in the unit disk is called (p, A)-lacunary if the inequalities nk ≥ Akp hold for all k ≥ 0 with some 1 < p < ∞ and A > 0. In this paper, for 1 < p < 2 and A > 0, we construct a (p, A)-lacunary function f1,p,A(z) decreasing as x → 1 – 0 at a rate close to the optimal rate for (p, A)-lacunary functions. Bibliography: 6 titles. [ABSTRACT FROM AUTHOR]

The class of locally strongly primitive semigroups of nonnegative matrices is introduced. It is shown that, by a certain permutation similarity, all the matrices of a semigroup of the class considered can be brought to a block monomial form; moreover, any matrix product of sufficient length has positive nonzero blocks only. This shows that the following known property of an imprimitive nonnegative matrix in Frobenius form is inherited: If such a matrix is raised to a sufficiently high power, then all its nonzero blocks are positive. A combinatorial criterion of the locally strong primitivity of a semigroup of nonnegative matrices is found. Bibliography: 6 titles. [ABSTRACT FROM AUTHOR]

In the paper, a purely combinatorial description of the orbit of e1 under the action of the elementary unitary group is given. Bibliography: 3 titles. [ABSTRACT FROM AUTHOR]

We make an attempt to portray the current situation in the probabilistic combinatorics field, where the so-called generalized allocation scheme has been utilized. We give a series of limit theorems for sums of independent identically distributed non-negative integer-valued random variables that find their application in the generalized allocation scheme. We say a word about the phenomenon of transition of the distribution of sums of independent identically distributed integer-valued random variables from one lattice to another in the context of the generalized allocation scheme, and give several examples of how to reduce a combinatorial problem to some kind of generalized scheme of allocating particles to cells. [ABSTRACT FROM AUTHOR]

We present a local combinatorial formula for the Euler class of an n-dimensional PL spherical fiber bundle as a rational number eCH associated to a chain of n + 1 abstract subdivisions of abstract n-spherical PL cell complexes. The number eCH is a combinatorial (or matrix) Hodgetheoretic twisting cochain in Guy Hirsch's homology model of the bundle associated with the PL combinatorics of the bundle. [ABSTRACT FROM AUTHOR]

We consider the XY Heisenberg spin 1 2 chain in the fermion representation. The construction of the ground-state vector is based on the group-theoretical approach. An exact expression for the ground-state vector will allow one to study the combinatorics of the correlation functions of the model. [ABSTRACT FROM AUTHOR]

The following generalization of the theorem on forming a matroid from parts is proved: If a finite set is subdivided into some blocks, each of which is supplied with a matroid structure, and the ranks of every union of certain blocks are prescribed and satisfy the conditions on the rank function of a matroid, then the rank function can be extended to all the subsets of the original set in such a way that the latter becomes a matroid. [ABSTRACT FROM AUTHOR]

Spaces of double cosets of infinite symmetric groups with respect to some special subgroups admit natural structures of semigroups. Elements of such semigroups can be interpreted in combinatorial terms. We present a description of such constructions in a relatively wide degree of generality. [ABSTRACT FROM AUTHOR]

For the Schur Q-functions there is a Cauchy identity, which shows a duality between the Schur P- and Q-functions. We will be interested in the multiparameter Schur Q-functions, which were introduced by V. N. Ivanov, and we will give dual analogs of the multiparameter Schur Q(P)-functions, with a corresponding multiparameter Cauchy identity. [ABSTRACT FROM AUTHOR]

The notion of a W-exponential Hall group is introduced and the limiting theorems on w-complete groups are proved. [ABSTRACT FROM AUTHOR]

We discuss the connection between quantum integrable models and some aspects of enumerative combinatorics and the theory of partitions. As a basic example, we consider the spin XXZ Heisenberg chain in the limiting cases of zero and infinite anisotropy. The representation of the Bethe wave functions via Schur functions allows us to apply the theory of symmetric functions to calculating the thermal correlation functions as well as the form factors in the determinantal form. We provide a combinatorial interpretation of the correlation functions in terms of nests of self-avoiding lattice paths. The suggested interpretation is in turn related to the enumeration of boxed plane partitions. The asymptotic behavior of the thermal correlation functions is studied in the limit of small temperature provided that the characteristic parameters of the system are large enough. The leading asymptotics of the correlators are found to be proportional to the squared numbers of boxed plane partitions. [ABSTRACT FROM AUTHOR]

We describe a new combinatorial-algebraic transformation on graphs which we call 'chip removal.' It generalizes the well-known Urban Renewal trick of Propp and Kuperberg. The chip removal is useful in calculations of determinants of adjacency matrices and matching numbers of graphs. A beautiful example of this technique is a theorem on removing four-contact chips, which generalizes Kuo's graphical condensation method. Numerous examples are given. Bibliography: 10 titles. [ABSTRACT FROM AUTHOR]

The main results are as follows. Let T be a Euclidean tetrahedron such that the ratio of lengths in each pair of edges of T is at least $$ \left(\sqrt{8/3}+1\right)/3<0.878 $$. Then each three-dimensional real normed space contains an isometrically embedded set of vertices of T . Let E be a three-dimensional normed space, and let x be a preassigned real number greater than $$ \sqrt{2/3} $$. Then E contains an affine image Π of a regular quadrangular pyramid such that the lateral edges of Π have equal length, the base edges of Π have equal length, the base diagonals also have equal length, and the ratio between the length of the lateral edges and the length of the base edges is equal to x. Bibliography: 5 titles. [ABSTRACT FROM AUTHOR]

We construct families of homogeneous linear differential equations (with coefficients continuously depending on a parameter) possessing certain topologically generic (in the sense of R. Baire) properties, such as the absence of various types of semicontinuity of their various conditional stability characteristics. [ABSTRACT FROM AUTHOR]

We describe a new combinatorial-algebraic transformation on graphs which we call the 'chip removal.' It generalizes the well-known urban renewal trick of Propp and Kuperberg. The chip removal is useful in calculations of the determinants of adjacency matrices and matching numbers of graphs. A beautiful example of applying this technique is a theorem on removing 4-contact chips, which generalizes Kuo's graphical condensation method. Numerous examples are given. Bibliography: 6 titles. [ABSTRACT FROM AUTHOR]

Generalizations of the Protasov-Voynov theorem on the structure of irreducible semigroups of nonnegative matrices free of zero rows and columns are obtained. The theorem is extended to semigroups that are allowed to be reducible and to matrices that may have zero columns. The main results concern the semigroups called entire. In the definitions and proofs, only combinatorial properties of nonnegative matrices are exploited. Bibliography: 7 titles [ABSTRACT FROM AUTHOR]

We discuss a stochastic particle system consisting of a two-dimensional array of particles living in one space dimension. The stochastic evolution bears a certain similarity to Hammersley's process, and the particle interaction is governed by the combinatorics of Young tableaux. Bibliography: 7 titles. [ABSTRACT FROM AUTHOR]

We introduce a notion of the tangent bundle of a poset. In the case where the poset is the poset of simplices of a combinatorial manifold, the construction produces the best possible combinatorial model for the geometric compactified tangent bundle. [ABSTRACT FROM AUTHOR]

Let $ \mathbb{F} $ be the finite field of q elements and let $ \mathcal{P}\left( {\mathrm{n},\mathrm{q}} \right) $ denote the projective space of dimension n − 1 over $ \mathbb{F} $. We construct a family $ \mathrm{H}_{\mathrm{k},\mathrm{i}}^{\mathrm{n}} $ of combinatorial homology modules associated to $ \mathcal{P}\left( {\mathrm{n},\mathrm{q}} \right) $ for coefficient fields of positive characteristic co-prime to q. As FGL(n, q)-representations these modules are obtained from the permutation action of GL(n, q) on the Grassmannians of $ {{\mathbb{F}}^{\mathrm{n}}} $. We prove a branching rule for $ \mathrm{H}_{\mathrm{k},\mathrm{i}}^{\mathrm{n}} $ and use this to determine the homology representations completely. Our results include a duality theorem and the characterization of $ \mathrm{H}_{\mathrm{k},\mathrm{i}}^{\mathrm{n}} $ through the standard irreducibles of GL(n, q) over F. [ABSTRACT FROM AUTHOR]

Let p be a prime integer, F a field of characteristic not p, T the norm torus of a degree p extension field of F, and E a T-torsor over F such that the degree of each closed point on E is divisible by p (a generic T-torsor has this property). We prove that E is p-incompressible. Moreover, all smooth compactifications of E (including those given by toric varieties) are p-incompressible. The main requisites of the proof are: (1) A. Merkurjev's degree formula (requiring the characteristic assumption), generalizing M. Rost's degree formula, and (2) combinatorial construction of a smooth projective fan invariant under an action of a finite group on the ambient lattice due to J.-L. Colliot- Thélène-D. Harari-A. N. Skorobogatov, produced by refinement of J.-L. Brylinski's method with the help of an idea of K. Künnemann. [ABSTRACT FROM AUTHOR]

A random recursive circuit is a combinatorial structure with a stochastic growth rule. These models are profusely used in computer science as data structures and in other fields, such as biostatistics, to model the spread of epidemics. The evolution of this random structure can be described by means of a generalized Pólya urn model where different colors of balls represent different kind of nodes of the circuit. We prove that the process that represents the proportion of balls of each color fits a Robbins-Monro stochastic recurrence scheme and, then, sufficient conditions are established in order to obtain almost sure convergence and a central limit theorem for this process. [ABSTRACT FROM AUTHOR]

The present monograph is devoted to low-dimensional topology in the context of two thriving theories: parity theory and theory of graph-links, the latter being an important generalization of virtual knot theory constructed by means of intersection graphs. Parity theory discovered by the second-named author leads to a new perspective in virtual knot theory, the theory of cobordisms in two-dimensional surfaces, and other new domains of topology. Theory of graph-links highlights a new combinatorial approach to knot theory. [ABSTRACT FROM AUTHOR]

construction of 'sparse potentials,' suggested by the authors for the lattice $ {\mathbb{Z}^d} $, d > 2, is extended to a large class of combinatorial and metric graphs whose global dimension is a number D > 2. For the Schrödinger operator − Δ − αV on such graphs, with a sparse potential V, we study the behavior (as α → ∞) of the number N_(−Δ − αV) of negative eigenvalues of − Δ − αV. We show that by means of sparse potentials one can realize any prescribed asymptotic behavior of N_(−Δ − αV) under very mild regularity assumptions. A similar construction works also for the lattice $ {\mathbb{Z}^2} $, where D = 2. Bibliography: 13 titles. [ABSTRACT FROM AUTHOR]

The diameter-constrained minimum spanning tree problem is an NP-hard combinatorial optimization problem that seeks a minimum cost spanning tree with a limit D imposed upon the length of any path in the tree. We begin by presenting four constructive greedy heuristics and, secondly, we present some second-order heuristics, performing some improvements on feasible solutions, hopefully leading to better objective function values. We present a heuristic with an edge exchange mechanism, another that transforms a feasible spanning tree solution into a feasible diameter-constrained spanning tree solution, and finally another with a repetitive mechanism. Computational results show that repetitive heuristics can improve considerably over the results of the greedy constructive heuristics, but using a huge amount of computation time. To obtain computational results, we use instances of the problem corresponding to complete graphs with a number of nodes between 20 and 60 and with the value of D varying between 4 and 9. [ABSTRACT FROM AUTHOR]

The article presents the chromatic numbers of metric spaces. The author considers one of the best known problems of combinatorics, the problem posed in 1950. The author states that the finiteness of chromatic numbers is obvious. The formulation of a nontrivial problem concerning precisely finite geometric graphs in the metric spaces considered is discussed.

Nonlinear corrections to some classical solutions of the linear diffusion equation in cylindrical coordinates are studied within quadratic approximation. When cylindrical coordinates are used, we try to find a nonlinear correction using quadratic polynomials of Bessel functions whose coefficients are Laurent polynomials of radius. This usual perturbation technique inevitably leads to a series of overdetermined systems of linear algebraic equations for the unknown coefficients (in contrast with the Cartesian coordinates). Using a computer algebra system, we show that all these overdetermined systems become compatible if we formally add one function on radius W( r). Solutions can be constructed as linear combinations of these quadratic polynomials of the Bessel functions and the functions W( r) and W′( r). This gives a series of solutions to the nonlinear diffusion equation; these are found with the same accuracy as the equation is derived. [ABSTRACT FROM AUTHOR]