?
Independence numbers of Johnson-type graphs
Kiselev S., Cherkashin D.
We consider a family of distance graphs in R n and find its independent numbers in some cases. Define graph J±(n, k, t) in the following way: the vertex set consists of all vectors from {−1, 0, 1} n with k nonzero coordinates; edges connect the pairs of vertices with scalar product t. We find the independence number of J±(n, k, t) for n > n0(k, t) in the cases t = 0 and t = −1; these cases for k = 3 are solved completely. Also the independence number is found for negative odd t and n > n0(k, t).
Levashev V., / Series arXiv "math". 2026. No. 2609.06010.
We prove that continuous A-bilinear pairings on the ring of Laurent series that are invariant under continuous automorphisms coincide, up to a constant, with the pairing given by the residue of a differential form over any commutative associative ring with identity. ...
Added: September 24, 2026
Pyatov P. N., Pivovarov P. A., / Series math "arxiv.org". 2026. No. 2609.06274.
We investigate a special ansats that allows for an iterative solution of the constant Yang-Baxter equation. Testing this ansatz, we construct four sequences of the constant R-matrices. In each sequence the R-matrices act on the tensor squares of vector spaces of linearly growing dimensions. Each R-matrix also depends on a single complex parameter.
By analyzing the ...
Added: September 24, 2026
Medvedev V., / Series arXiv "math". 2026.
We study complete static manifolds with boundary admitting a nowhere-vanishing static potential. Our main result shows that, under a natural lower bound relating the scalar curvature and the boundary mean curvature, a simple static manifold with boundary must in fact have positive scalar curvature, negative boundary mean curvature, and be compact; we also obtain explicit ...
Added: September 19, 2026
Poddiakov A., / Series Social Science Research Network "Social Science Research Network". 2026. No. 7437658.
Clarity of knowledge and reasoning is necessary in many cases. Yet vagueness in scientific thinking related to surprise, curiosity, "ability to engage with not-knowing" (de Freitas) and abductive reasoning is also a crucially important source of scientific creativity which supplements combinatorial logic when dealing with the already known. Starting from studies by C. S. Peirce ...
Added: September 15, 2026
Glutsyuk A., / Series arXiv "math". 2026.
B.Josephson (Nobel Prize, 1973) predicted a tunnelling effect for a system of two superconductors separated by a narrow dielectric (such a system is called Josephson junction): existence of a supercurrent through it and equations governing it. The overdamped Josephson junction is modeled by the family of differential equations on the 2-torus, dθdτ=1ω(cosθ+B+Acosτ), which is known as ...
Added: September 8, 2026
Pochinka O., Shmukler V., / Series math.RT "arXiv:1808.06395 [math.RT]". 2026.
Anosov flows have a long and rich history, firstly motivated by the
study of geodesic flows in negative curvature surface by Anosov and Sinai.
Not every closed manifold admits an Anosov flow for well-known reasons:
the fundamental group of a 3-manifold M admitting an Anosov flow must
have exponential growth, and M must be universally covered by R3. Nevertheless,
there ...
Added: August 31, 2026
Loubenets E. R., / Series arxiv.org "quant-ph". 2026. No. 2607.18050.
In many quantum applications it is important to know whether or not a Bell nonlocal two-qudit state exhibits its nonlocality under correlation scenarios with some given numbers S1,S2≥1 of generalized quantum measurements at two sites. In the present article, we find analytically a new general locality condition sufficient for a nonseparable Werner state with a ...
Added: July 21, 2026
Bolbachan V., / Series math "arxiv.org". 2024.
Chow polylogarithms are some special functions arising in explicit description of the Beilinson regulator map. The most interesting functional equation for this function reflects its vanishing on the boundary in the Bloch's cycle complex. We show that this functional equation formally follows from more simple ones, namely skew-symmetry, functoriality and multiplicativity.
To prove this, we study ...
Added: July 16, 2026
Bolbachan V., / Series math "arxiv.org". 2024.
Let K be a field of characteristic zero. We prove that its motivic cohomology in degree m−1 and weight m is rationally isomorphic to the cohomology of the polylogarithmic complex. This gives a partial extension of A. Suslin theorem describing the indecomposable K3 of a field. ...
Added: July 16, 2026
Panov V., Ryabchenko A., / Series arXiv "stat.ME". 2026. No. 2607.05048.
This paper investigates the problem of statistical inference for a mixture distribution consisting of a discrete and a continuous component, with a particular focus on the class of rational-infinitely divisible distributions. We consider non-parametric estimation of both components of the mixture as well as the quasi-L{é}vy measure, assuming that the mixture belongs to the class ...
Added: July 9, 2026
Konakov V., Kucher D., Mammen E., / Series arXiv "math". 2026. No. 2606.11142v1.
In this paper, we construct strong approximations for discrete-time Markov chains weakly converging to continuous diffusion processes, as well as for their perturbed counterparts. Under the assumption of bounded coefficients, we construct closely coupled versions of these processes on a shared probability space. In particular, for both non-degenerate and degenerate cases, we maximize the probability ...
Added: June 11, 2026
Dorovskiy A., / Series arXiv "math". 2026.
In this paper the structural stability of generic families of vector fields of the PC-HC class on the two-dimensional sphere is proved. A classification of these families up to moderate equivalence in neighborhoods of their large bifurcation supports is presented, based on such invariants as the configuration and the characteristic set. The realization lemma is proved. ...
Added: May 14, 2026
Taletskii D., / Series arXiv "math". 2026.
A vertex subset of a graph is called a \textit{distance-$k$ independent set} if the distance between any two of its distinct vertices is at least $k + 1$. For all $n,k \geq 1$, we determine the minimum possible number of inclusion-wise maximal distance-$k$ independent sets among all $n$-vertex trees. It equals~$n$ if $n \leq k ...
Added: May 1, 2026
Ovcharenko M., / Series arXiv "math". 2026.
We introduce an explicit class of tempered Laurent polynomials in the sense of Villegas and Doran--Kerr in n⩽4 variables including all Landau--Ginzburg models for smooth Fano threefolds with very ample anticanonical class. We check that it contains Landau--Ginzburg models for various Fano fourfolds which are complete intersections in smooth toric varieties and Grassmannians of planes, ...
Added: April 30, 2026
Zlotnik Alexander, / Series arXiv "math". 2026. No. 2602.03481v1.
We deal with the global in time weak solutions to the 1D compressible Navier-Stokes system of equations for large discontinuous initial data and nonhomogeneous boundary conditions of three standard types. We prove the Lipschitz-type continuous dependence of the solution $(\eta,u,\theta)$, in a norm slightly stronger than $L^{2,\infty}(Q)\times L^2(Q)\times L^2(Q)$, on the initial data $(\eta^0,u^0,e^0)$ in a ...
Added: April 18, 2026
Дистель Р., М.: МЦНМО, 2024.
С момента выхода первого издания на английском языке в 1997 году книга известного математика, профессора Гамбургского университета Рейнгарда Дистеля стала основным учебником по теории графов во многих университетах, выдержав к настоящему времени пять изданий, перевод последнего из которых предлагается читателю. Уникальность учебника в его глубине при относительно небольшом объёме: в книге найдутся задачи как доступные ...
Added: January 25, 2026
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
Zelenova S. A., Zelenov S. V., Proceedings of the Institute for System Programming of the RAS 2017 Vol. 29 No. 6 P. 183–202
In the paper, we address mission critical systems, such as automobile, avionic, mobile robotic, telecommunication, etc. Such systems must meet hard real-time constraints in order to avoid catastrophic consequences. To meet the real-time constraints, strict periodicity is used (i.e. for any periodic task, time between release points is constant). Sensors, actuators and feedback control functions ...
Added: August 11, 2018
Cherkashin Danila, Kulikov A., Andrei Raigorodskii, Discrete Applied Mathematics 2018 Vol. 243 P. 125–131
This paper is devoted to the study of the graph sequence Gn = (Vn, En), where Vn is the set of all vectors v ∈ R n with coordinates in {−1, 0, 1} such that |v| = √ 3 and En consists of all pairs of vertices with scalar product 1. We find the exact ...
Added: August 6, 2018
Zelenov S. V., Зеленова С. А., Программирование 2018 Т. 44 № 3 С. 3–16
A new look at the problem of constructing a scheduler in the case of a group of strictly periodic tasks is proposed. The structure of the system of periods is represented in terms of graph theory. A criterion for the existence of a conflict-free schedule based on this representation is obtained, and generic schemes of ...
Added: March 15, 2018
Sirotkin D., Журнал Средневолжского математического общества 2017 Т. 19 № 2 С. 98–104
В данной работе вводится некоторый класс замен подграфов в графах, причем замены из этого класса сохраняют $k$-раскрашиваемость. Каждое такое локальное преобразование графов определяется некоторым шаблоном – набором разбиений множества на его подмножества. Показывается, что заменяющий подграф существует для любого шаблона, а также приводится оценка на количество его вершин от размера шаблона. Данный результат является основным ...
Added: August 23, 2017
Shitov Y., Theoretical Computer Science 2017 Vol. 671 P. 116–118
For any integer k>2, we consider the following decision problem. Given a simple graph, does there exist a partition of its vertices into two disjoint sets such that every simple k-cycle of G contains vertices in both of these sets? This problem is NP-hard because it admits a polynomial reduction from NAE 3-SAT. We construct ...
Added: March 15, 2017
Komosko L. F., Batsyn M. V., Информационные технологии 2015 № 7 С. 488–494
Graph coloring problem is one of the classical combinatorial optimization problems. This problem consists in finding the minimal number of colors in which it is possible to color vertices of a graph so that any two adjacent vertices are colored in different colors. The graph coloring problem has a wide variety of applications including timetabling ...
Added: July 13, 2015
Evgeny Maslov, Mikhail Batsyn, Panos M. Pardalos, , in: Models, Algorithms, and Technologies for Network AnalysisVol. 59.: NY: Springer, 2013. Ch. 7 P. 93–99.
In this chapter, we present our enhancements of one of the most efficient exact algorithms for the maximum clique problem—MCS algorithm by Tomita, Sutani, Higashi, Takahashi and Wakatsuki (in Proceedings of WALCOM’10, 2010, pp. 191–203). Our enhancements include: applying ILS heuristic by Andrade, Resende and Werneck (in Heuristics 18:525–547, 2012) to find a high-quality initial solution, fast detection ...
Added: November 19, 2013