BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Denis Krotov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.COInformation Theorymath.ITDiscrete Mathematicsmath.GR

Catalog footprint

Research overview

15works
5topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

15 publications

preprint2026arXiv

The punctured dodecacode is unique

The punctured dodecacode is an additive 44-ary code of length 1111 and distance 55 which is uniformly packed. We show that a code with the same weight distribution is equivalent to it. This code is also shown to be nonlinear. We also establish the nonexistence of analogues of the dodecacode and the punctured dodecacode in Doob graphs. To that end, we classify two-weight codes of weights 66 and 88 in Doob and 44-ary Hamming graphs of diameter 99 and the corresponding strongly regular graphs. Keywords: dodecacode, additive code, trace Hermitian duality, uniformly packed code, completely regular code, Doob graph, strongly regular graph

Open access
preprint2016arXiv

On the number of maximum independent sets in Doob graphs

The Doob graph D(m,n)D(m,n) is a distance-regular graph with the same parameters as the Hamming graph H(2m+n,4)H(2m+n,4). The maximum independent sets in the Doob graphs are analogs of the distance-22 MDS codes in the Hamming graphs. We prove that the logarithm of the number of the maximum independent sets in D(m,n)D(m,n) grows as 22m+n−1(1+o(1))2^{2m+n-1}(1+o(1)). The main tool for the upper estimation is constructing an injective map from the class of maximum independent sets in D(m,n)D(m,n) to the class of distance-22 MDS codes in H(2m+n,4)H(2m+n,4).

Open access
preprint2016arXiv

On the number of n-ary quasigroups of finite order

Let Q(n,k)Q(n,k) be the number of nn-ary quasigroups of order kk. We derive a recurrent formula for Q(n,4). We prove that for all n≥2n\geq 2 and k≥5k\geq 5 the following inequalities hold: (k−3/2)n/2(k−12)n/2<log2Q(n,k)≤ck(k−2)n({k-3}/2)^{n/2}(\frac{k-1}2)^{n/2} < log_2 Q(n,k) \leq {c_k(k-2)^{n}} , where ckc_k does not depend on nn. So, the upper asymptotic bound for Q(n,k)Q(n,k) is improved for any k≥5k\geq 5 and the lower bound is improved for odd k≥7k\geq 7. Keywords: n-ary quasigroup, latin cube, loop, asymptotic estimate, component, latin trade.

Open access
preprint2015arXiv

To the theory of qq-ary Steiner and other-type trades

We introduce the concept of a clique bitrade, which generalizes several known types of bitrades, including latin bitrades, Steiner T(k−1,k,v)T(k-1,k,v) bitrades, extended 11-perfect bitrades. For a distance-regular graph, we show a one-to-one correspondence between the clique bitrades that meet the weight-distribution lower bound on the cardinality and the bipartite isometric subgraphs that are distance-regular with certain parameters. As an application of the results, we find the minimum cardinality of qq-ary Steiner Tq(k−1,k,v)T_q(k-1,k,v) bitrades and show a connection of minimum such bitrades with dual polar subgraphs of the Grassmann graph Jq(v,k)J_q(v,k). Keywords: bitrades, trades, Steiner systems, subspace designs

Open access
preprint2014arXiv

Perfect codes in Doob graphs

We study 11-perfect codes in Doob graphs D(m,n)D(m,n). We show that such codes that are linear over GR(42)GR(4^2) exist if and only if n=(4g+d−1)/3n=(4^{g+d}-1)/3 and m=(4g+2d−4g+d)/6m=(4^{g+2d}-4^{g+d})/6 for some integers g≥0g \ge 0 and d>0d>0. We also prove necessary conditions on (m,n)(m,n) for 11-perfect codes that are linear over Z4Z_4 (we call such codes additive) to exist in D(m,n)D(m,n) graphs; for some of these parameters, we show the existence of codes. For every mm and nn satisfying 2m+n=(4t−1)/32m+n=(4^t-1)/3 and m≤(4t−5⋅2t−1+1)/9m \le (4^t-5\cdot 2^{t-1}+1)/9, we prove the existence of 11-perfect codes in D(m,n)D(m,n), without the restriction to admit some group structure. Keywords: perfect codes, Doob graphs, distance regular graphs.

Open access
preprint2014arXiv

Propelinear 1-perfect codes from quadratic functions

Perfect codes obtained by the Vasil'ev--Schönheim construction from a linear base code and quadratic switching functions are transitive and, moreover, propelinear. This gives at least exp⁡(cN2)\exp(cN^2) propelinear 11-perfect codes of length NN over an arbitrary finite field, while an upper bound on the number of transitive codes is exp⁡(C(Nln⁡N)2)\exp(C(N\ln N)^2). Keywords: perfect code, propelinear code, transitive code, automorphism group, Boolean function.

Open access
preprint2011arXiv

On a connection between the switching separability of a graph and that of its subgraphs

A graph of order n>3n>3 is called {switching separable} if its modulo-2 sum with some complete bipartite graph on the same set of vertices is divided into two mutually independent subgraphs, each having at least two vertices. We prove the following: if removing any one or two vertices of a graph always results in a switching separable subgraph, then the graph itself is switching separable. On the other hand, for every odd order greater than 4, there is a graph that is not switching separable, but removing any vertex always results in a switching separable subgraph. We show a connection with similar facts on the separability of Boolean functions and reducibility of nn-ary quasigroups. Keywords: two-graph, reducibility, separability, graph switching, Seidel switching, graph connectivity, nn-ary quasigroup

Open access
preprint2011arXiv

On connection between reducibility of an n-ary quasigroup and that of its retracts

An nn-ary operation Q:Sn→SQ:S^n\to S is called an nn-ary quasigroup of order ∣S∣|S| if in the equation x0=Q(x1,...,xn)x_0=Q(x_1,...,x_n) knowledge of any nn elements of x0,...,xnx_0,...,x_n uniquely specifies the remaining one. An nn-ary quasigroup QQ is (permutably) reducible if Q(x1,...,xn)=P(R(xs(1),...,xs(k)),xs(k+1),...,xs(n))Q(x_1,...,x_n)=P(R(x_{s(1)},...,x_{s(k)}),x_{s(k+1)},...,x_{s(n)}) where PP and RR are (n−k+1)(n-k+1)-ary and kk-ary quasigroups, ss is a permutation, and 1<k<n1<k<n. An mm-ary quasigroup RR is called a retract of QQ if it can be obtained from QQ or one of its inverses by fixing n−m>0n-m>0 arguments. We show that every irreducible nn-ary quasigroup has an irreducible (n−1)(n-1)-ary or (n−2)(n-2)-ary retract; moreover, if the order is finite and prime, then it has an irreducible (n−1)(n-1)-ary retract. We apply this result to show that all nn-ary quasigroups of order 5 or 7 whose all binary retracts are isotopic to Z5Z_5 or Z7Z_7 are reducible for n>3n>3. Keywords: nn-ary quasigroups, retracts, reducibility, latin hypercubes

Open access
preprint2011arXiv

On the binary codes with parameters of triply-shortened 1-perfect codes

We study properties of binary codes with parameters close to the parameters of 1-perfect codes. An arbitrary binary (n=2m−3,2n−m−1,4)(n=2^m-3, 2^{n-m-1}, 4) code CC, i.e., a code with parameters of a triply-shortened extended Hamming code, is a cell of an equitable partition of the nn-cube into six cells. An arbitrary binary (n=2m−4,2n−m,3)(n=2^m-4, 2^{n-m}, 3) code DD, i.e., a code with parameters of a triply-shortened Hamming code, is a cell of an equitable family (but not a partition) from six cells. As a corollary, the codes CC and DD are completely semiregular; i.e., the weight distribution of such a code depends only on the minimal and maximal codeword weights and the code parameters. Moreover, if DD is self-complementary, then it is completely regular. As an intermediate result, we prove, in terms of distance distributions, a general criterion for a partition of the vertices of a graph (from rather general class of graphs, including the distance-regular graphs) to be equitable. Keywords: 1-perfect code; triply-shortened 1-perfect code; equitable partition; perfect coloring; weight distribution; distance distribution

Open access
preprint2011arXiv

On weight distributions of perfect colorings and completely regular codes

A vertex coloring of a graph is called "perfect" if for any two colors aa and bb, the number of the color-bb neighbors of a color-aa vertex xx does not depend on the choice of xx, that is, depends only on aa and bb (the corresponding partition of the vertex set is known as "equitable"). A set of vertices is called "completely regular" if the coloring according to the distance from this set is perfect. By the "weight distribution" of some coloring with respect to some set we mean the information about the number of vertices of every color at every distance from the set. We study the weight distribution of a perfect coloring (equitable partition) of a graph with respect to a completely regular set (in particular, with respect to a vertex if the graph is distance-regular). We show how to compute this distribution by the knowledge of the color composition over the set. For some partial cases of completely regular sets, we derive explicit formulas of weight distributions. Since any (other) completely regular set itself generates a perfect coloring, this gives universal formulas for calculating the weight distribution of any completely regular set from its parameters. In the case of Hamming graphs, we prove a very simple formula for the weight enumerator of an arbitrary perfect coloring. Codewords: completely regular code; equitable partition; partition design; perfect coloring; perfect structure; regular partition; weight distribution; weight enumerator.

Open access
preprint2009arXiv

On the binary codes with parameters of doubly-shortened 1-perfect codes

We show that any binary (n=2m−3,2n−m,3)(n=2^m-3, 2^{n-m}, 3) code C1C_1 is a part of an equitable partition (perfect coloring) {C1,C2,C3,C4}\{C_1,C_2,C_3,C_4\} of the nn-cube with the parameters ((0,1,n−1,0)(1,0,n−1,0)(1,1,n−4,2)(0,0,n−1,1))((0,1,n-1,0)(1,0,n-1,0)(1,1,n-4,2)(0,0,n-1,1)). Now the possibility to lengthen the code C1C_1 to a 1-perfect code of length n+2n+2 is equivalent to the possibility to split the part C4C_4 into two distance-3 codes or, equivalently, to the biparticity of the graph of distances 1 and 2 of C4C_4. In any case, C1C_1 is uniquely embeddable in a twofold 1-perfect code of length n+2n+2 with some structural restrictions, where by a twofold 1-perfect code we mean that any vertex of the space is within radius 1 from exactly two codewords.

Open access
preprint2009arXiv

On the structure of non-full-rank perfect codes

The Krotov combining construction of perfect 1-error-correcting binary codes from 2000 and a theorem of Heden saying that every non-full-rank perfect 1-error-correcting binary code can be constructed by this combining construction is generalized to the qq-ary case. Simply, every non-full-rank perfect code CC is the union of a well-defined family of μμ-components KμK_μ, where μμ belongs to an "outer" perfect code C∗C^*, and these components are at distance three from each other. Components from distinct codes can thus freely be combined to obtain new perfect codes. The Phelps general product construction of perfect binary code from 1984 is generalized to obtain μμ-components, and new lower bounds on the number of perfect 1-error-correcting qq-ary codes are presented.

Open access
preprint2008arXiv

On reconstructing reducible n-ary quasigroups and switching subquasigroups

(1) We prove that, provided n>=4, a permutably reducible n-ary quasigroup is uniquely specified by its values on the n-ples containing zero. (2) We observe that for each n,k>=2 and r<=[k/2] there exists a reducible n-ary quasigroup of order k with an n-ary subquasigroup of order r. As corollaries, we have the following: (3) For each k>=4 and n>=3 we can construct a permutably irreducible n-ary quasigroup of order k. (4) The number of n-ary quasigroups of order k>3 has double-exponential growth as n tends to infinity; it is greater than exp exp(n ln[k/3]) if k>=6, and exp exp(n (ln 3)/3 - 0.44) if k=5.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.