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


Probl. Peredachi Inf., 1988, Volume 24, Issue 1, Pages 51–60 (Mi ppi686)  

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

Communication Network Theory

Explicit Group-Theoretical Constructions of Combinatorial Schemes and Their Application to the Design of Expanders and Concentrators

G. A. Margulis


Abstract: For every prime $p$, we construct an infinite sequence $\{Y_m\}$ of finite undirected regular graphs of degree $p+1$ such that
$$ c(Y_m)\ge(4/3+o(1))\log_pn(\mathbf Y_m), $$
where $c(X)$ and $n(X)$ are respectively the girth and the number of vertices in the graph $X$. We show that the graphs $\{Y_m\}$ may be applied for explicit construction of expanders and concentrators. Similar constructions are noted for regular graphs of degree $p^l+1$, where $p$ is prime and $l\ge 1$ is a natural number.

Full text: PDF file (1235 kB)

English version:
Problems of Information Transmission, 1988, 24:1, 39–46

Bibliographic databases:

UDC: 621.395.34:512.8
Received: 09.12.1985

Citation: G. A. Margulis, “Explicit Group-Theoretical Constructions of Combinatorial Schemes and Their Application to the Design of Expanders and Concentrators”, Probl. Peredachi Inf., 24:1 (1988), 51–60; Problems Inform. Transmission, 24:1 (1988), 39–46

Citation in format AMSBIB
\Bibitem{Mar88}
\by G.~A.~Margulis
\paper Explicit Group-Theoretical Constructions of Combinatorial Schemes and Their Application to the Design of Expanders and Concentrators
\jour Probl. Peredachi Inf.
\yr 1988
\vol 24
\issue 1
\pages 51--60
\mathnet{http://mi.mathnet.ru/ppi686}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=939574}
\zmath{https://zbmath.org/?q=an:0708.05030}
\transl
\jour Problems Inform. Transmission
\yr 1988
\vol 24
\issue 1
\pages 39--46


Linking options:
  • http://mi.mathnet.ru/eng/ppi686
  • http://mi.mathnet.ru/eng/ppi/v24/i1/p51

    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. K. Sh. Zigangirov, M. Lentmaier, “Mathematical Analysis of an Iterative Decoding Algorithm for Low-Density Codes”, Problems Inform. Transmission, 36:4 (2000), 314–324  mathnet  mathscinet  zmath
    2. D. V. Trukhachev, M. Lentmaier, K. Sh. Zigangirov, “Some Results Concerning the Design and Decoding of Turbo-Codes”, Problems Inform. Transmission, 37:3 (2001), 190–205  mathnet  crossref  mathscinet  zmath
    3. M. Lentmaier, D. V. Trukhachev, K. Sh. Zigangirov, “To the Theory of Low-Density Convolutional Codes. II”, Problems Inform. Transmission, 37:4 (2001), 288–306  mathnet  crossref  mathscinet  zmath
    4. M. V. Alekhnovich, A. A. Razborov, “Lower Bounds for Polynomial Calculus: Nonbinomial Case”, Proc. Steklov Inst. Math., 242 (2003), 18–35  mathnet  mathscinet  zmath
    5. Wintzell, O, “Asymptotic analysis of superorthogonal turbo codes”, IEEE Transactions on Information Theory, 49:1 (2003), 253  crossref  mathscinet  zmath  isi
    6. J. Math. Sci. (N. Y.), 140:3 (2007), 461–471  mathnet  crossref  mathscinet  zmath
    7. Woodruff D.P., “Revisiting the efficiency of malicious two-party computation”, Advances in Cryptology - EUROCRYPT 2007, Lecture Notes in Computer Science, 4515, 2007, 79–96  crossref  isi
    8. Frolov A., Zyablov V., “Upper and Lower Bounds on the Minimum Distance of Expander Codes”, 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), 2011, 1397–1401  crossref  isi
    9. Golubev K., Parzanchevski O., “Spectrum and Combinatorics of Two-Dimensional Ramanujan Complexes”, Isr. J. Math., 230:2 (2019), 583–612  crossref  mathscinet  zmath  isi  scopus
    10. I. D. Shkredov, “On the Spectral Gap and the Diameter of Cayley Graphs”, Proc. Steklov Inst. Math., 314 (2021), 307–324  mathnet  crossref  crossref  isi  elib
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:1638
    Full text:780
    First page:3

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022