?
Combinatorics and Algorithms for Quasi-Chain Graphs
Algorithmica. 2023. Vol. 85. No. 3. P. 642–664.
The class of quasi-chain graphs is an extension of the well-studied class of chain
graphs. This latter class enjoys many nice and important properties, such as bounded
clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc.
The class of quasi-chain graphs is substantially more complex. In particular, this class
is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded
in it. In the present paper, we show that the universe of quasi-chain graphs is at least as
complex as the universe of permutations by establishing a bijection between the class
of all permutations and a subclass of quasi-chain graphs.This implies, in particular, that
the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs.
On the other hand, we propose a decomposition theorem for quasi-chain graphs that
implies an implicit representation for graphs in this class and efficient solutions for
some algorithmic problems that are generally intractable.
Селянин Ф. И., Moscow Mathematical Journal 2026 Vol. 26 No. 2 P. 167–187
Minkowski mixed volume of n subpolytopes D1,…,Dn of a polytope P⊂Rn clearly does not exceed the normalized volume n!Vol(P). Equality holds if and only if the subpolytopes are interlaced, i.e., each proper face F⊊P intersects at least dim(F)+1 of the polytopes Di. Efficiently computing mixed volumes for more general collections of subpolytopes is crucial for estimating the complexity of numerically solving polynomial systems.
Motivated by relaxing the bound dim(F)+1 to dim(F), we ...
Added: August 31, 2026
Kazaryan M., Dunin-Barkowski P., Bychkov B. et al., International Mathematics Research Notices 2026 Vol. 14 Article rnag146
We prove a recent conjecture of the fourth named author with P. Norbury that states a system of universal polynomial relations among the kappa classes on the moduli spaces of algebraic curves. The proof involves localization and materialization analysis of the spin Gromov–Witten theory of the projective line and is dictated by Z 2 -equivariant ...
Added: August 31, 2026
Kazaryan M., Dunin-Barkowski P., Bychkov B. et al., Communications in Mathematical Physics 2026 Vol. 407 No. 69
We prove that for any initial data on a genus zero spectral curve the cor responding correlation differentials of topological recursion are KP integrable. As an application we prove KP integrability of partition functions associated via ELSV-type formulas to the r-th roots of the twisted powers of the log canonical bundles ...
Added: August 31, 2026
Gromov V., Переслегин С. Б., Переслегина Е. Б. et al., СПб.: Полакс, 2026.
Механизм происходящих в мире изменений носит эволюционный, а не экологический характер. Иначе говоря, Человечество столкнулось с кризисом развития, который имеет три независимые составляющие: кризис индустриального общества (фазовый кризис), кризис научного мышления (эпистемный кризис) и кризис формата существования разума (социосистемный кризис). Доклад посвящён аспектам этого триединого кризиса и возможным путям его преодоления, не сводящимся к первичному ...
Added: August 31, 2026
Devyatov R. A., Mathematical notes 2026 Vol. 119 No. 3 P. 782–786
Let G/B be a flag variety over ℂ, where G is a simple algebraic group with a simply laced Dynkin diagram, and B is a Borel subgroup. We say that the product of classes of Schubert divisors in the Chow ring is multiplicity free if it is possible to multiply it by a Schubert class ...
Added: August 30, 2026
Bayer A., Kuznetsov A., Macrì E., Journal fuer die reine und angewandte Mathematik 2026 Vol. 2026 No. 836 P. 111–162
We give a self-contained and simplified proof of Mukai’s classification of prime Fano threefolds of index 1 and genus g ≥ 6 with at most factorial terminal singularities, and of its extension to higher dimension. ...
Added: August 30, 2026
Bayer A., Kuznetsov A., Macrì E., Compositio Mathematica 2026 Vol. 162 No. 1 P. 59–99
We give a proof of Mukai’s theorem on the existence of certain exceptional vector bundles on prime Fano threefolds. To our knowledge this is the first complete proof in the literature. The result is essential for Mukai’s biregular classification of prime Fano threefolds, and for the existence of semiorthogonal decompositions in their derived categories. Our ...
Added: August 30, 2026
Guseva L., Novikov A., Advances in Mathematics 2026 Vol. 503 Article 111211
We prove that the Kuznetsov–Polishchuk exceptional collections on rational homogeneous spaces of the symplectic groups Sp(2n,C) are full and consist of vector bundles. To achieve this, we construct several classes of complexes, which we call generalized staircase complexes, symplectic staircase complexes and secondary staircase complexes — each of which may be of independent interest. ...
Added: August 30, 2026
Polishchuk A., Rains E., Journal of the Institute of Mathematics of Jussieu 2026 Vol. 25 No. 1 P. 339–373
We prove that for every relatively prime pair of integers (d,r) with r>0, there exists an exceptional pair (O,V) on any del Pezzo surface of degree 4, such that V is a bundle of rank r and degree d. As an application, we prove that every Feigin-Odesskii Poisson bracket on a projective space can be ...
Added: August 30, 2026
Kazhdan D., Polishchuk A., Pure and Applied Mathematics Quarterly 2026 Vol. 22 No. 3 P. 1115–1166
We continue the study of automorphic functions associated with a curve C over the ring k[ε]/(ε²), where k is a finite field, begun in arXiv:2303.16259. Namely, we study an example of theta-lifting in this framework and show that it can be understood in terms of the orbit decomposition of the space of automorphic functions S(SL₂(F)\SL₂(A_C)) ...
Added: August 30, 2026
Kuznetsov A. P., Sataev I. R., Stankevich N., Chaos 2026 Vol. 36 No. 8 Article 083131
A radio-physical system, namely, a two-mode van der Pol generator, is considered. It is shown that this system demonstrates two types of chaos: with one and two zero Lyapunov exponents. The regions of the second type of chaos are surrounded by bifurcation lines of invariant tori doubling. Quasi-periodic structures of various shapes are embedded within ...
Added: August 30, 2026
Shirokov N. A., Rozenblum G., Israel Journal of Mathematics 2026 P. 1–30
We establish that a generalized H\¨older continuous function on an (m−2)-Ahlfors regular compact set in Rm can be approximated by solutions of an elliptic equation, with the rate of approximation determined by the continuity modulus of the function ...
Added: August 29, 2026
Avdoshin S.M., Patrushev K. A., Proceedings of the Institute for System Programming of the RAS 2026 No. 4 часть 2 P. 245–256
The cardinality-constrained Markowitz problem is NP-hard and traditionally solved with commercial MIQP solvers. Following the 2022 export restrictions that rendered both commercial MIQP software and cloud quantum platforms (IBM Quantum, D-Wave Leap) inaccessible from the Russian Federation, practitioners require open-source alternatives. This paper systematically compares three solver families for the discrete mean-variance problem: two open-source ...
Added: August 27, 2026
Zaikin A., Vlasenko D., Zakharov D. et al., Diagnostics 2026 Vol. 16 No. 17 P. 1–15
Background/Objectives: Synolitic graphs (SGs) were developed for task-based fMRI, where
edge weights encode the discriminative power of pairwise regional features; whether similar
information can be recovered from resting-state data was untested. We benchmarked
SGs for autism spectrum disorder (ASD) classification using the multisite ABIDE-I dataset
(871 subjects: 403 subjects with ASD, 468 typical controls; 17 sites; CC200 atlas). Methods:
Using ...
Added: August 27, 2026
Melnikov I., Pelinovsky E., Nonlinear Dynamics 2026 No. 114 Article 934
Pyramidal solitons (solitons with more than two inflection points) of the generalized Korteweg–de Vries (KdV) equation are investigated. Necessary and sufficient conditions for the existence of such structures are presented. Within the framework of the generalized Gardner equation — the simplest model that admits pyramidal solitons as solutions — it is shown that these solutions ...
Added: August 27, 2026
Тула: Тульский государственный педагогический университет им. Л.Н. Толстого, 2025.
Сборник содержит материалы, представленные на XXIV Международной конференции «Алгебра, теория чисел, дискретная геометрия и многомасштабное моделирование: современные проблемы, приложения и проблемы истории», посвящённой 110-летию со дня рождения академика Юрия Владимировича Линника и 110-летию со дня рождения профессора Андрея Борисовича Шидловского и 80-летию со дня рождения профессора Геннадия Ивановича Архипова. Материалы конференции будут полезны научным работникам, ...
Added: August 27, 2026
Nadutkina A., Tikhomirov A., Timushev D., Siberian Advances in Mathematics 2024 Vol. 34 No. 2 P. 146–153
We study the spectra of random weighted bipartite graphs. We establish that, under specific assumptions on the edge probabilities, the symmetrized empirical spectral distribution function of the graph’s adjacency matrix converges to the symmetrized Marchenko-Pastur distribution function. ...
Added: January 26, 2026
El-Mesady A., Farahat T., El-Shanawany R. et al., Algorithms 2023 Vol. 16 No. 7 Article 320
Nowadays, graph theory is one of the most exciting fields of mathematics due to the tremendous developments in modern technology, where it is used in many important applications. The orthogonal double cover (𝑂𝐷𝐶) is a branch of graph theory and is considered as a special class of graph decomposition. In this paper, we decompose the complete bipartite ...
Added: July 30, 2023
Grinblat A., Lopatkin V., Journal of Algebra and its Applications 2020 Vol. 20 No. 5 Article 2150083
The aim of this paper is to show that any finite undirected bipartite graph can be considered as a polynomial p∈N[x], and any directed finite bipartite graph can be considered as a polynomial p∈N[x,y], and vise verse. We also show that the multiplication in semirings N[x], N[x,y] correspondences to a operations of the corresponding graphs which looks like a ``perturbed'' ...
Added: September 27, 2021
Alecu B., Atminas A., Loozin V. V. et al., , in: International Workshop on Combinatorial Algorithms, 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021Vol. 12757.: Springer, 2021. P. 49–62.
The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. The latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is
not well-quasi-ordered by induced subgraphs, and the ...
Added: July 1, 2021
Boros E., Gurvich V., Milanic M., Journal of Graph Theory 2020 Vol. 94 No. 3 P. 364–397
A hypergraph is said to be 1-Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of 1-Sperner hypergraphs to graphs. First, we consider several ways of associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For ...
Added: September 7, 2020
Zinder Y., Lazarev A. A., Musatova E. G., Automation and Remote Control 2020 Vol. 81 No. 6 P. 955–966
The paper presents a polynomial-time algorithm for rescheduling traffic when one track of a double-track railway becomes unavailable, the remaining track has a siding, and there are two categories of trains—priority trains such as passenger trains and ordinary trains such as the majority of freight trains. The presented algorithm minimises the negative effect, caused by ...
Added: September 1, 2020
Avdoshin S. M., Набебин А. А., М.: ДМК Пресс, 2019.
The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms, operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite ...
Added: August 24, 2018
Malyshev D., Discrete Applied Mathematics 2018 Vol. 247 P. 423–432
We show that the weighted coloring problem can be solved for {P5,banner}-free graphs and for {P5,dart}-free graphs in polynomial time on the sum of vertex weights. ...
Added: April 23, 2018