Problemy Peredachi Informatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Probl. Peredachi Inf.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Problemy Peredachi Informatsii, 2019, Volume 55, Issue 4, Pages 52–75
DOI: https://doi.org/10.1134/S0555292319040028
(Mi ppi2303)
 

This article is cited in 2 scientific papers (total in 2 papers)

Coding Theory

On the cardinality spectrum and the number of latin bitrades of order $3$

D. S. Krotov, V. N. Potapov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia
Full-text PDF (362 kB) Citations (2)
References:
Abstract: By a (Latin) unitrade of order $k$, we call a subset of vertices of the Hamming graph $H(n, k)$ that intersects any maximal clique at either $0$ or $2$ vertices. A bitrade is a bipartite unitrade, i.e., a unitrade that can be split into two independent subsets. We study the cardinality spectrum of bitrades in the Hamming graph $H(n, k)$ with $k = 3$ (ternary hypercube) and the growth of the number of such bitrades as $n$ grows. In particular, we determine all possible small (up to $2.5\cdot 2^n$) and large (from $14\cdot 3^{n-3}$) cardinalities of bitrades of dimension n and prove that the cardinality of a bitrade takes only values equivalent to $0$ or $2^n$ modulo $3$ (this result can be treated in terms of a ternary Reed–Muller type code). A part of the results are valid for an arbitrary $k$. For $k = 3$ and $n\to\infty$ we prove that the number of nonequivalent bitrades is not less than $2^{(2/3-o(1))n}$ and not greater than $2^{\alpha^n}$, $\alpha < 2$ (the growth order of the double logarithm of this number remains unknown). Alternatively, the studied set $B_n$ of bitrades of order $3$ can be defined as follows: $B_0$ consists of three rationals $- 1, 0, 1$; $B_n$ consists of ordered triples $(a, b, c)$ of elements from $B_{n-1}$ such that $a+b+c=0$.
Keywords: Latin bitrades, unitrades, Reed–Muller codes, combinatorial configurations, Boolean functions.
Funding agency Grant number
Russian Science Foundation 14-11-00555
18-11-00136
The research was carried out at the expense of the Russian Science Foundation, project nos. 14-11-00555 (results of Sections 2, 3, 4.1, 4.5, and 5.2) and 18-11-00136 (results of Sections 4.2–4.4, 4.6, and 5.1).
Received: 24.12.2018
Revised: 19.09.2019
Accepted: 12.11.2019
English version:
Problems of Information Transmission, 2019, Volume 55, Issue 4, Pages 343–365
DOI: https://doi.org/10.1134/S0032946019040021
Bibliographic databases:
Document Type: Article
UDC: 621.391.1 : 519.1
Language: Russian
Citation: D. S. Krotov, V. N. Potapov, “On the cardinality spectrum and the number of latin bitrades of order $3$”, Probl. Peredachi Inf., 55:4 (2019), 52–75; Problems Inform. Transmission, 55:4 (2019), 343–365
Citation in format AMSBIB
\Bibitem{KroPot19}
\by D.~S.~Krotov, V.~N.~Potapov
\paper On the cardinality spectrum and the number of latin bitrades of order~$3$
\jour Probl. Peredachi Inf.
\yr 2019
\vol 55
\issue 4
\pages 52--75
\mathnet{http://mi.mathnet.ru/ppi2303}
\crossref{https://doi.org/10.1134/S0555292319040028}
\elib{https://elibrary.ru/item.asp?id=39180349}
\transl
\jour Problems Inform. Transmission
\yr 2019
\vol 55
\issue 4
\pages 343--365
\crossref{https://doi.org/10.1134/S0032946019040021}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000520150600002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85078134798}
Linking options:
  • https://www.mathnet.ru/eng/ppi2303
  • https://www.mathnet.ru/eng/ppi/v55/i4/p52
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Проблемы передачи информации Problems of Information Transmission
    Statistics & downloads:
    Abstract page:294
    Full-text PDF :30
    References:26
    First page:4
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024