RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
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. Zametki:
Year:
Volume:
Issue:
Page:
Find






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


Mat. Zametki, 2016, Volume 99, Issue 2, Pages 288–297 (Mi mz10762)  

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

Independence Numbers of Random Subgraphs of a Distance Graph

M. M. Pyaderkin

Lomonosov Moscow State University

Abstract: We consider the so-called distance graph $G(n,3,1)$, whose vertices can be identified with three-element subsets of the set $\{1,2,…,n\}$, two vertices being joined by an edge if and only if the corresponding subsets have exactly one common element. We study some properties of random subgraphs of $G(n,3,1)$ in the Erdős–Rényi model, in which each edge is included in the subgraph with some given probability $p$ independently of the other edges. We find the asymptotics of the independence number of a random subgraph of $G(n,3,1)$.

Keywords: distance graph, random subgraph, independence number, Erdős–Rényi model.

Funding Agency Grant Number
Russian Foundation for Basic Research 15-01-03530


DOI: https://doi.org/10.4213/mzm10762

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

English version:
Mathematical Notes, 2016, 99:2, 312–319

Bibliographic databases:

UDC: 519.179.4
Received: 03.04.2015

Citation: M. M. Pyaderkin, “Independence Numbers of Random Subgraphs of a Distance Graph”, Mat. Zametki, 99:2 (2016), 288–297; Math. Notes, 99:2 (2016), 312–319

Citation in format AMSBIB
\Bibitem{Pya16}
\by M.~M.~Pyaderkin
\paper Independence Numbers of Random Subgraphs of a~Distance Graph
\jour Mat. Zametki
\yr 2016
\vol 99
\issue 2
\pages 288--297
\mathnet{http://mi.mathnet.ru/mz10762}
\crossref{https://doi.org/10.4213/mzm10762}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3462709}
\elib{https://elibrary.ru/item.asp?id=25707668}
\transl
\jour Math. Notes
\yr 2016
\vol 99
\issue 2
\pages 312--319
\crossref{https://doi.org/10.1134/S000143461601034X}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000373228900034}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84962407595}


Linking options:
  • http://mi.mathnet.ru/eng/mz10762
  • https://doi.org/10.4213/mzm10762
  • http://mi.mathnet.ru/eng/mz/v99/i2/p288

    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. M. M. Pyaderkin, “Independence Numbers of Random Subgraphs of Distance Graphs”, Math. Notes, 99:4 (2016), 556–563  mathnet  crossref  crossref  mathscinet  isi  elib
    2. M. M. Pyaderkin, A. M. Raigorodskii, “On random subgraphs of Kneser graphs and their generalizations”, Dokl. Math., 94:2 (2016), 547–549  crossref  mathscinet  zmath  isi  elib  scopus
    3. A. M. Raigorodskii, “Combinatorial geometry and coding theory*”, Fundam. Inform., 145:3 (2016), 359–369  crossref  mathscinet  zmath  isi  elib  scopus
    4. A. M. Raigorodskii, “On the stability of the independence number of a random subgraph”, Dokl. Math., 96:3 (2017), 628–630  crossref  zmath  isi  scopus
    5. S. G. Kiselev, A. M. Raigorodskii, “On the chromatic number of a random subgraph of the Kneser graph”, Dokl. Math., 96:2 (2017), 475–476  crossref  mathscinet  zmath  isi  scopus
    6. D. D. Cherkashin, A. M. Raigorodskii, “On the chromatic numbers of low-dimensional spaces”, Dokl. Math., 95:1 (2017), 5–6  crossref  mathscinet  zmath  isi  scopus
    7. N. M. Derevyanko, S. G. Kiselev, “Independence numbers of random subgraphs of some distance graph”, Problems Inform. Transmission, 53:4 (2017), 307–318  mathnet  crossref  isi  elib
    8. Ph. A. Pushnyakov, “The Number of Edges in Induced Subgraphs of Some Distance Graphs”, Math. Notes, 105:4 (2019), 582–591  mathnet  crossref  crossref  isi  elib
    9. M. M. Pyaderkin, “On Threshold Probability for the Stability of Independent Sets in Distance Graphs”, Math. Notes, 106:2 (2019), 274–285  mathnet  crossref  crossref  isi  elib
    10. Ph. A. Pushnyakov, A. M. Raigorodskii, “Estimate of the Number of Edges in Special Subgraphs of a Distance Graph”, Math. Notes, 107:2 (2020), 322–332  mathnet  crossref  crossref  isi  elib
  • Математические заметки Mathematical Notes
    Number of views:
    This page:185
    Full text:33
    References:57
    First page:39

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