Sobolev Institute of Mathematics

output

19932026

most citedPhysics Interplay of the LHC and the ILC

408 citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing math.COShow all

140 papers · 1 filter

math.CO2025

On tropical knapsack-type problems

I. M. Buchinskiy, M. V. Kotov, A. V. Treier

In this paper, we investigate the computational complexity of the knapsack problem and subset sum problem for the following tropical algebraic structures. We consider the semigroup…

math.CO2025

On the number of partitions of the hypercube $Z_{q}^{n}$ into large subcubes

Yuriy Tarannikov

We prove that the number of partitions of the hypercube $Z_{q}^{n}$ into $q^{m}$ subcubes of dimension $n - m$ each for fixed $q$ , $m$ and growing $n$ is asymptotically equal to $n^{…

math.CO2024

Generalizing the Bierbrauer-Friedman bound for orthogonal arrays

Denis S. Krotov, Ferruh Özbudak, Vladimir N. Potapov

We characterize mixed-level orthogonal arrays in terms of algebraic designs in a special multigraph. We prove a mixed-level analog of the Bierbrauer-Friedman (BF) bound for pure-le…

math.CO2024

Characterization of polystochastic matrices of order $4$ with zero permanent

A. L. Perezhogin, V. N. Potapov, A. A. Taranenko +1

A multidimensional nonnegative matrix is called polystochastic if the sum of its entries over each line is equal to $1$ . The permanent of a multidimensional matrix is the sum of pr…

math.CO2024

Triangle decompositions of PG(n-1,2)

Minjia Shi, Xiaoxiao Li, Denis S. Krotov

We define a triangle design as a partition of the set of lines of a projective space into triangles, where a triangle consists of three pairwise intersecting lines with no common p…

math.CO2024

Asymptotic bounds on the numbers of vertices of polytopes of polystochastic matrices

Vladimir N. Potapov, Anna A. Taranenko

A multidimensional nonnegative matrix is called polystochastic if the sum of entries in each line is equal to $1$ . The set of all polystochastic matrices of order $n$ and dimension…

math.CO2024★ 8 cited

Combinatorial designs, difference sets and bent functions as perfect colorings of graphs and multigraphs

V. N. Potapov, S. V. Avgustinovich

It is proved that 1) the indicator function of some onefold or multifold independent set in a regular graph is a perfect coloring if and only if the set attain the Delsarte--Hoffma…

math.CO2023★ 1 cited

On directed and undirected diameters of vertex-transitive graphs

Saveliy V. Skresanov

A directed diameter of a directed graph is the maximum possible distance between a pair of vertices, where paths must respect edge orientations, while undirected diameter is the di…

math.CO2023★ 1 cited

Every latin hypercube of order 5 has transversals

A. L. Perezhogin, V. N. Potapov, S. Yu. Vladimirov

We prove that for all n>1 every latin n-dimensional cube of order 5 has transversals. We find all 123 paratopy classes of layer-latin cubes of order 5 with no transversals. For eac…

math.CO2023

On degree- $3$ and $(n - 4)$ -correlation-immune perfect colorings of $n$ -cubes

Denis S. Krotov, Alexandr A. Valyuzhenich

A perfect $k$ -coloring of the Boolean hypercube $Q_{n}$ is a function from the set of binary words of length $n$ onto a $k$ -set of colors such that for any colors $i$ and $j$ every w…

math.CO2023

The classification of orthogonal arrays OA(2048,14,2,7) and some completely regular codes

Denis S. Krotov

We describe the classification of orthogonal arrays OA $(2048, 14, 2, 7)$ , or, equivalently, completely regular ${14; 2}$ -codes in the $14$ -cube ( $30848$ equivalence classes). In part…

math.CO2023

Non-canonical maximum cliques without a design structure in the block graphs of 2-designs

Sergey Goryainov, Elena V. Konstantinova

In this note we answer positively a question of Chris Godsil and Karen Meagher on the existence of a 2-design whose block graph has a non-canonical maximum clique without a design…

math.CO2023★ 3 cited

Quasi-cyclic perfect codes in Doob graphs and special partitions of Galois rings

Minjia Shi, Xiaoxiao Li, Denis S. Krotov +1

The Galois ring GR $(4^{Δ})$ is the residue ring $Z_{4} [x] / (h (x))$ , where $h (x)$ is a basic primitive polynomial of degree $Δ$ over $Z_{4}$ . For any odd $Δ$ larger than $1$ , we construct…

math.CO2022

An upper bound on the number of frequency hypercubes

Denis S. Krotov, Vladimir N. Potapov

A frequency $n$ -cube $F^{n} (q; l_{0}, ..., l_{m - 1})$ is an $n$ -dimensional $q$ -by-...-by- $q$ array, where $q = l_{0} + ... + l_{m - 1}$ , filled by numbers $0, ..., m - 1$ with the property that each…

math.CO2022★ 3 cited

Multifold 1-perfect codes

Denis S. Krotov

A multifold $1$ -perfect code ( $1$ -perfect code for list decoding) in any graph is a set $C$ of vertices such that every vertex of the graph is at distance not more than $1$ from ex…

math.CO2022★ 4 cited

Singleton mesh patterns in multidimensional permutations

Sergey Avgustinovich, Sergey Kitaev, Jeffrey Liese +2

This paper introduces the notion of mesh patterns in multidimensional permutations and initiates a systematic study of singleton mesh patterns (SMPs), which are multidimensional me…

math.CO2022★ 1 cited

Projective tilings and full-rank perfect codes

Denis S. Krotov

A tiling of a vector space $S$ is the pair $(U, V)$ of its subsets such that every vector in $S$ is uniquely represented as the sum of a vector from $U$ and a vector from $V$ . A til…

math.CO2022★ 1 cited

On the coset graph construction of distance-regular graphs

Minjia Shi, Denis S. Krotov, Patrick Solé

We show that no more new distance-regular graphs in the tables of the book of (Brouwer, Cohen, Neumaier, 1989) can be produced by using the coset graph of additive completely regul…

math.CO2022★ 3 cited

Spectrum of the Transposition graph

Elena V. Konstantinova, Artem Kravchuk

Transposition graph $T_{n}$ is defined as a Cayley graph over the symmetric group generated by all transpositions. It is known that all eigenvalues of $T_{n}$ are integers. However, an…

math.CO2022★ 5 cited

Self-dual Hadamard bent sequences

Minjia Shi, Yaya Li, Wei Cheng +3

A new notion of bent sequence related to Hadamard matrices was introduced recently, motivated by a security application ( Solé et al, 2021). We study the self dual class in length…

math.CO2021★ 4 cited

An enumeration of 1-perfect ternary codes

Minjia Shi, Denis S. Krotov

We study codes with parameters of the ternary Hamming $(n = (3^{m} - 1) /2, 3^{n - m}, 3)$ code, i.e., ternary $1$ -perfect codes. The rank of the code is defined to be the dimension of its af…

math.CO2021★ 2 cited

On $q$ -ary shortened- $1$ -perfect-like codes

Minjia Shi, Rongsheng Wu, Denis S. Krotov

We study codes with parameters of $q$ -ary shortened Hamming codes, i.e., $(n = (q^{m} - q) / (q - 1), q^{n - m}, 3)_{q}$ . Firstly, we prove the fact mentioned in 1998 by Brouwer et al. that such…

math.CO2021★ 1 cited

Embedding in MDS codes and Latin cubes

Vladimir N. Potapov

An embedding of a code is a mapping that preserves distances between codewords. We prove that any code with code distance $ρ$ and length $d$ can be embedded into an MDS code with t…

math.CO2021★ 10 cited

An asymptotic lower bound on the number of bent functions

V. N. Potapov, A. A. Taranenko, Yu. V. Tarannikov

A Boolean function $f$ on $n$ variables is said to be a bent function if the absolute value of all its Walsh coefficients is $2^{n /2}$ . Our main result is a new asymptotic lower bo…

On tropical knapsack-type problems

On the number of partitions of the hypercube Zqn​ into large subcubes

Generalizing the Bierbrauer-Friedman bound for orthogonal arrays

Characterization of polystochastic matrices of order 4 with zero permanent

Triangle decompositions of PG(n-1,2)

Asymptotic bounds on the numbers of vertices of polytopes of polystochastic matrices

Combinatorial designs, difference sets and bent functions as perfect colorings of graphs and multigraphs

On directed and undirected diameters of vertex-transitive graphs

Every latin hypercube of order 5 has transversals

On degree-3 and (n−4)-correlation-immune perfect colorings of n-cubes

The classification of orthogonal arrays OA(2048,14,2,7) and some completely regular codes

Non-canonical maximum cliques without a design structure in the block graphs of 2-designs

Quasi-cyclic perfect codes in Doob graphs and special partitions of Galois rings

An upper bound on the number of frequency hypercubes

Multifold 1-perfect codes

Singleton mesh patterns in multidimensional permutations

Projective tilings and full-rank perfect codes

On the coset graph construction of distance-regular graphs

Spectrum of the Transposition graph

Self-dual Hadamard bent sequences

An enumeration of 1-perfect ternary codes

On q-ary shortened-1-perfect-like codes

Embedding in MDS codes and Latin cubes

An asymptotic lower bound on the number of bent functions

On the number of partitions of the hypercube $Z_{q}^{n}$ into large subcubes

Characterization of polystochastic matrices of order $4$ with zero permanent

On degree- $3$ and $(n - 4)$ -correlation-immune perfect colorings of $n$ -cubes

On $q$ -ary shortened- $1$ -perfect-like codes