RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Sb.:
Year:
Volume:
Issue:
Page:
Find






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


Mat. Sb. (N.S.), 1973, Volume 92(134), Number 3(11), Pages 472–490 (Mi msb3418)  

This article is cited in 1 scientific paper (total in 1 paper)

Maximum height of arbitrary classes of $(0,1)$-matrices and some of its applications

V. E. Tarakanov


Abstract: An upper estimate obtained earlier by the author for the maximum height $\overline\varepsilon$ of certain $(0,1)$-matrices (RZhMat., 1968, 8V222) is generalized to arbitrary classes of matrices. It is shown that under certain natural conditions $\overline\varepsilon/N\leqslant\ln n/n+O(1/n)$, $n\to\infty$, where $N$ is the number of columns in the matrix and $n$ is the maximum number of ones in a column. Let $\overline\varepsilon(k,n,N)$ be the maximum height of the class of matrices with $N$ columns, $k$ ones in each row and $n$ ones in each column. It is proved that $\overline\varepsilon(n,n,N)\geqslant2[\frac N{n+1}]$, $\overline\varepsilon(2,3,N)=[\frac35N]$, $\overlinevarepsilon(2,n,N)=[\frac23N]$ ($n$ even); $[\frac35N]\leqslant\overline\varepsilon(2,n,N)\leqslant[\frac{2n-1}{3n-1}N]$ ($n$ odd); from this follows estimates for some constants in graph theory.
Bibliography: 9 titles.

Full text: PDF file (1976 kB)
References: PDF file   HTML file

English version:
Mathematics of the USSR-Sbornik, 1973, 21:3, 467–484

Bibliographic databases:

Document Type: Article
UDC: 512.831
MSC: Primary 05B20; Secondary 90C05, 05B25, 05C99
Received: 28.03.1973

Citation: V. E. Tarakanov, “Maximum height of arbitrary classes of $(0,1)$-matrices and some of its applications”, Mat. Sb. (N.S.), 92(134):3(11) (1973), 472–490; Math. USSR-Sb., 21:3 (1973), 467–484

Citation in format AMSBIB
\Bibitem{Tar73}
\by V.~E.~Tarakanov
\paper Maximum height of~arbitrary classes of $(0,1)$-matrices and some of its applications
\jour Mat. Sb. (N.S.)
\yr 1973
\vol 92(134)
\issue 3(11)
\pages 472--490
\mathnet{http://mi.mathnet.ru/msb3418}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=337656}
\zmath{https://zbmath.org/?q=an:0296.15010}
\transl
\jour Math. USSR-Sb.
\yr 1973
\vol 21
\issue 3
\pages 467--484
\crossref{https://doi.org/10.1070/SM1973v021n03ABEH002029}


Linking options:
  • http://mi.mathnet.ru/eng/msb3418
  • http://mi.mathnet.ru/eng/msb/v134/i3/p472

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. V. E. Tarakanov, “Estimates of the independence number of a hypergraph and the Ryser conjecture”, Math. Notes, 61:6 (1997), 731–738  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
  • Математический сборник (новая серия) - 1964–1988 Sbornik: Mathematics (from 1967)
    Number of views:
    This page:168
    Full text:46
    References:26
    First page:2

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019