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

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

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

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 

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

 SHARE:

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
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
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
4. M. V. Alekhnovich, A. A. Razborov, “Lower Bounds for Polynomial Calculus: Nonbinomial Case”, Proc. Steklov Inst. Math., 242 (2003), 18–35
5. Wintzell, O, “Asymptotic analysis of superorthogonal turbo codes”, IEEE Transactions on Information Theory, 49:1 (2003), 253
6. J. Math. Sci. (N. Y.), 140:3 (2007), 461–471
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
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
9. Golubev K., Parzanchevski O., “Spectrum and Combinatorics of Two-Dimensional Ramanujan Complexes”, Isr. J. Math., 230:2 (2019), 583–612
10. I. D. Shkredov, “On the Spectral Gap and the Diameter of Cayley Graphs”, Proc. Steklov Inst. Math., 314 (2021), 307–324
•  Number of views: This page: 1638 Full text: 780 First page: 3