RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискрет. матем., 2001, том 13, выпуск 1, страницы 56–62 (Mi dm276)  

Эта публикация цитируется в 22 научных статьях (всего в 22 статьях)

О числе независимых множеств в расширителях

А. А. Сапоженко


Аннотация: Уточняется и обобщается на случай почти регулярных графов верхняя оценка для числа независимых множеств в регулярных графах, полученная Н. Алоном. Найдена верхняя оценка числа независимых множеств, размер которых существенно отличен от четверти числа вершин. Для числа независимых множеств в расширителях получена верхняя оценка вида $2^{n(1/2-c+o(1))}$, где $c$ — положительная постоянная.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 01–01–00206.

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

Полный текст: PDF файл (630 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Discrete Mathematics and Applications, 2001, 11:2, 155–161

Реферативные базы данных:

УДК: 519.1
Статья поступила: 15.12.2000

Образец цитирования: А. А. Сапоженко, “О числе независимых множеств в расширителях”, Дискрет. матем., 13:1 (2001), 56–62; Discrete Math. Appl., 11:2 (2001), 155–161

Цитирование в формате AMSBIB
\RBibitem{Sap01}
\by А.~А.~Сапоженко
\paper О числе независимых множеств в~расширителях
\jour Дискрет. матем.
\yr 2001
\vol 13
\issue 1
\pages 56--62
\mathnet{http://mi.mathnet.ru/dm276}
\crossref{https://doi.org/10.4213/dm276}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1846037}
\zmath{https://zbmath.org/?q=an:1048.05065}
\transl
\jour Discrete Math. Appl.
\yr 2001
\vol 11
\issue 2
\pages 155--161


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm276
  • https://doi.org/10.4213/dm276
  • http://mi.mathnet.ru/rus/dm/v13/i1/p56

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. К. Г. Омельянов, А. А. Сапоженко, “О числе множеств, свободных от сумм, в отрезке натуральных чисел”, Дискрет. матем., 14:3 (2002), 3–7  mathnet  crossref  mathscinet  zmath; K. G. Omel'yanov, A. A. Sapozhenko, “On the number of sum-free sets in an interval of natural numbers”, Discrete Math. Appl., 12:4 (2002), 319–323
    2. Sapozhenko A.A., “Asymptotics of the number of sum-free sets in Abelian groups of even order”, Doklady Mathematics, 65:2 (2002), 235–238  mathscinet  zmath  isi
    3. К. Г. Омельянов, А. А. Сапоженко, “О числе и структуре множеств, свободных от сумм в отрезке натуральных чисел”, Дискрет. матем., 15:4 (2003), 141–147  mathnet  crossref  mathscinet  zmath; K. G. Omel'yanov, A. A. Sapozhenko, “On the number and structure of sum-free sets in a segment of positive integers”, Discrete Math. Appl., 13:6 (2003), 637–643  crossref
    4. Сапоженко А.А., “Гипотеза Камерона–Эрдëша”, Докл. РАН, 393:6 (2003), 749–752  mathnet  mathscinet; Sapozhenko A.A., “The Cameron-Erdős conjecture”, Dokl. Math., 68:3 (2003), 438–441  mathscinet  isi
    5. Т. Г. Петросян, “О числе множеств, свободных от произведений, в группах четного порядка”, Дискрет. матем., 17:1 (2005), 89–101  mathnet  crossref  mathscinet  zmath  elib; T. G. Petrosyan, “On the number of product-free sets in groups of even order”, Discrete Math. Appl., 15:1 (2005), 47–58  crossref
    6. Sapozhenko A., “Systems of containers and enumeration problems”, Stochastic algorithms: foundations and applications, Third International Symposium, SAGA 2005 (Moscow, Russia, October 20–22, 2005 \finlbookinfo Proceedings), Lecture Notes in Computer Science, 3777, Springer, Berlin–Heidelberg, 2005, 1–13  crossref  zmath  isi  scopus
    7. Sapozhenko A.A., “Independent sets in quasi-regular graphs”, European Journal of Combinatorics, 27:7 (2006), 1206–1210  crossref  mathscinet  zmath  isi  scopus
    8. Т. Г. Петросян, “Верхняя оценка числа множеств, свободных от произведений, в одном классе групп”, Дискрет. матем., 19:1 (2007), 76–88  mathnet  crossref  mathscinet  zmath  elib; T. G. Petrosyan, “An upper bound for the number of product-free sets in a class of groups”, Discrete Math. Appl., 17:1 (2007), 57–70  crossref
    9. А. Б. Дайняк, “О числе независимых множеств в графах с фиксированным числом независимости”, Дискрет. матем., 19:2 (2007), 63–66  mathnet  crossref  mathscinet  zmath  elib; A. B. Dainiak, “On the number of independent sets in graphs with fixed independence number”, Discrete Math. Appl., 17:3 (2007), 249–252  crossref
    10. Sapozhenko A.A., “Upper bound for the number of independent sets in graphs”, Doklady Mathematics, 75:3 (2007), 447–448  crossref  mathscinet  zmath  isi  elib  scopus
    11. Sapozhenko A.A., “The Cameron-Erdős conjecture”, Discrete Math., 308:19 (2008), 4361–4369  crossref  mathscinet  zmath  isi  elib  scopus
    12. А. А. Сапоженко, “О числе множеств, свободных от сумм”, Учён. зап. Казан. гос. ун-та. Сер. Физ.-матем. науки, 151, № 2, Изд-во Казанского ун-та, Казань, 2009, 139–146  mathnet
    13. Georgakopoulos, A, “A short proof of Fleischner's theorem”, Discrete Mathematics, 309:23–24 (2009), 6632  crossref  mathscinet  zmath  isi  scopus
    14. Galvin D., “An upper bound for the number of independent sets in regular graphs”, Discrete Mathematics, 309:23–24 (2009), 6635–6640  crossref  mathscinet  zmath  isi  elib  scopus
    15. Zhao Yu., “The Number of Independent Sets in a Regular Graph”, Combinatorics Probability & Computing, 19:2 (2010), 315–320  crossref  mathscinet  zmath  isi  scopus
    16. Balogh J., Das Sh., Delcourt M., Liu H., Sharifzadeh M., “Intersecting Families of Discrete Structures Are Typically Trivial”, J. Comb. Theory Ser. A, 132 (2015), 224–245  crossref  mathscinet  zmath  isi  scopus
    17. Saxton D., Thomason A., “Hypergraph Containers”, Invent. Math., 201:3 (2015), 925–992  crossref  mathscinet  zmath  isi  elib  scopus
    18. Samotij W., “Counting Independent Sets in Graphs”, Eur. J. Comb., 48:SI (2015), 5–18  crossref  mathscinet  zmath  isi  scopus
    19. А. Б. Дайняк, А. А. Сапоженко, “Независимые множества в графах”, Дискрет. матем., 28:1 (2016), 44–77  mathnet  crossref  mathscinet  elib; A. B. Dainiak, A. A. Sapozhenko, “Independent sets in graphs”, Discrete Math. Appl., 26:6 (2016), 323–346  crossref  isi
    20. Saxton D., Thomason A., “Online containers for hypergraphs, with applications to linear equations”, J. Comb. Theory Ser. B, 121:SI (2016), 248–283  crossref  mathscinet  zmath  isi  elib  scopus
    21. Kang D.Y., Kim J., Kim Y., Law H.-F., “On the Number of R-Matchings in a Tree”, Electron. J. Comb., 24:1 (2017), P1.24  mathscinet  zmath  isi
    22. Falgas-Ravry V. O'Connell K. Uzzell A., “Multicolor Containers, Extremal Entropy, and Counting”, Random Struct. Algorithms, 54:4 (2019), 676–720  crossref  isi
  • Дискретная математика
    Просмотров:
    Эта страница:565
    Полный текст:190
    Литература:52
    Первая стр.:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019