Гипотеза Кэмерона — Эрдёша: различия между версиями

Интерактивная навигация по истории

[отпатрулированная версия]

← Предыдущая правка

Содержимое удалено Содержимое добавлено

ВизуальныйВики-текст

Линейный

Текущая версия от 00:59, 4 августа 2023

Гипотеза Кэмерона — Эрдёша — доказанная в 2003 году комбинаторная гипотеза.

Формулировка

Число $s(N)$ свободных от сумм подмножеств в $\{1,\ldots ,N\}$ равно $O\left({2^{N/2}}\right)$ .

Замечания

Сумма двух нечётных чисел всегда чётна, так что любое множество нечётных чисел всегда свободно от сумм. Имеется $\lceil N/2\rceil$ нечётных чисел в $|N|$ , соответственно получается $2^{N/2}$ подмножеств нечётных чисел в $|N|$ . Гипотеза утверждает, что эта величина с точностью до константы определяет асимптотическое поведение количества свободных от сумм множеств.

История

Гипотеза была предложена Питером Кэмероном и Палом Эрдёшом в 1988 году^[1], в 2003 году доказана Беном Грином^[2] и независимо — Александром Сапоженко^[3]^[4].

Сапоженко показал, что $s(N)=C_{0}2^{N/2}$ при четных N и $s(N)=C_{1}2^{(N+1)/2}$ при нечётных N, где $C_{0}=6.0...,C_{1}=5.0....$ ^[5]

Ссылки

↑ Кэмерон, Питер Джефсон; Эрдёш, Пал (1990), "On the number of sets of integers with various properties", Number theory: proceedings of the First Conference of the Canadian Number Theory Association, held at the Banff Center, Banff, Alberta, April 17-27, 1988, Berlin: de Gruyter, pp. 61—79, MR 1106651 {{citation}}: Проверьте значение даты: |year= (справка)CS1 maint: year (ссылка) Источник (неопр.). Дата обращения: 27 марта 2022. Архивировано 27 июня 2014 года.
↑ Грин, Бен Джозеф (2004), "The Cameron-Erdős conjecture", The Bulletin of the London Mathematical Society, 36 (6): 769—778, arXiv:math.NT/0304058, doi:10.1112/S0024609304003650, MR 2083752 {{citation}}: Проверьте значение даты: |year= (справка)CS1 maint: year (ссылка)
↑ Сапоженко, Александр Антонович (2003), "The Cameron-Erdős conjecture", Доклады Академии наук, 393 (6): 749—752, MR 2088503 {{citation}}: Проверьте значение даты: |year= (справка)CS1 maint: year (ссылка)
↑ Сапоженко, Александр Антонович (2008), "The Cameron-Erdős conjecture", Discrete Mathematics, 308 (19): 4361—4369, doi:10.1016/j.disc.2007.08.103, MR 2433862 {{citation}}: Проверьте значение даты: |year= (справка)CS1 maint: year (ссылка)
↑ Spectral and Evolution problems: Proceedings of the Fourteenth Crimean Autumn Mathematical School-Symposium. Vol. 15. /Group of authors.

[1] Кэмерон, Питер Джефсон; Эрдёш, Пал (1990), "On the number of sets of integers with various properties", Number theory: proceedings of the First Conference of the Canadian Number Theory Association, held at the Banff Center, Banff, Alberta, April 17-27, 1988, Berlin: de Gruyter, pp. 61—79, MR 1106651 {{citation}}: Проверьте значение даты: |year= (справка)CS1 maint: year (ссылка) Источник (неопр.). Дата обращения: 27 марта 2022. Архивировано 27 июня 2014 года.

[2] Грин, Бен Джозеф (2004), "The Cameron-Erdős conjecture", The Bulletin of the London Mathematical Society, 36 (6): 769—778, arXiv:math.NT/0304058, doi:10.1112/S0024609304003650, MR 2083752 {{citation}}: Проверьте значение даты: |year= (справка)CS1 maint: year (ссылка)

[3] Сапоженко, Александр Антонович (2003), "The Cameron-Erdős conjecture", Доклады Академии наук, 393 (6): 749—752, MR 2088503 {{citation}}: Проверьте значение даты: |year= (справка)CS1 maint: year (ссылка)

[4] Сапоженко, Александр Антонович (2008), "The Cameron-Erdős conjecture", Discrete Mathematics, 308 (19): 4361—4369, doi:10.1016/j.disc.2007.08.103, MR 2433862 {{citation}}: Проверьте значение даты: |year= (справка)CS1 maint: year (ссылка)

[5] Spectral and Evolution problems: Proceedings of the Fourteenth Crimean Autumn Mathematical School-Symposium. Vol. 15. /Group of authors.

[1]

[2]

[3]

[4]

[5]

@@ Строка 11: / Строка 11: @@
 ==История==
-Гипотеза была предложена Питером Кэмероном и [[Эрдёш, Пал|Палом Эрдёшом]] в [[1988 год в науке|1988 году]]<ref>{{Citation|last1=Кэмерон|first1=Питер Джефсон|author1-link=Кэмерон, Питер|last2=Эрдёш|first2=Пал|author2-link=Эрдёш, Пал|contribution=On the number of sets of integers with various properties|location=Berlin|mr=1106651|pages=61–79|publisher=de Gruyter|title=Number theory: proceedings of the First Conference of the Canadian Number Theory Association, held at the Banff Center, Banff, Alberta, April 17-27, 1988|url=https://books.google.Com/books?id=68g0Ds4FNM0C&pg=PA61&lpg=PA61|year=[[1990 год в науке|1990]]}}</ref>, в [[2003 год в науке|2003 году]] доказана Беном Грином<ref>{{Citation|last=Грин|first=Бен Джозеф|author-link=Грин, Бен|arxiv=math.NT/0304058|doi=10.1112/S0024609304003650|issue=6|journal=The Bulletin of the London Mathematical Society|mr=2083752|pages=769–778|title=The Cameron-Erdős conjecture|volume=36|year=[[2004 год в науке|2004]]}}</ref> и независимо — Александром Сапоженко<ref>{{Citation|last=Сапоженко|first=Александр Антонович|author-link=Сапоженко, Александр Антонович|issue=6|journal=[[Доклады Академии наук]]|mr=2088503|pages=749–752|title=The Cameron-Erdős conjecture|volume=393|year=[[2003 год в науке|2003]]}}</ref><ref>{{Citation|last=Сапоженко|first=Александр Антонович|author-link=Сапоженко, Александр Антонович|doi=10.1016/j.disc.2007.08.103|issue=19|journal=[[Discrete Mathematics]]|mr=2433862|pages=4361–4369|title=The Cameron-Erdős conjecture|volume=308|year=[[2008 год в науке|2008]]}}</ref>.
+Гипотеза была предложена Питером Кэмероном и [[Эрдёш, Пал|Палом Эрдёшом]] в [[1988 год в науке|1988 году]]<ref>{{Citation|last1=Кэмерон|first1=Питер Джефсон|author1-link=Кэмерон, Питер|last2=Эрдёш|first2=Пал|author2-link=Эрдёш, Пал|contribution=On the number of sets of integers with various properties|location=Berlin|mr=1106651|pages=61–79|publisher=de Gruyter|title=Number theory: proceedings of the First Conference of the Canadian Number Theory Association, held at the Banff Center, Banff, Alberta, April 17-27, 1988|url=https://books.google.Com/books?id=68g0Ds4FNM0C&pg=PA61&lpg=PA61|year=[[1990 год в науке|1990]]}} {{Cite web |url=https://books.google.com/books?id=68g0Ds4FNM0C&pg=PA61&lpg=PA61 |title=Источник |access-date=2022-03-27 |archive-date=2014-06-27 |archive-url=https://web.archive.org/web/20140627021919/https://books.google.com/books?id=68g0Ds4FNM0C&pg=PA61&lpg=PA61 |deadlink=unfit }}</ref>, в [[2003 год в науке|2003 году]] доказана Беном Грином<ref>{{Citation|last=Грин|first=Бен Джозеф|author-link=Грин, Бен|arxiv=math.NT/0304058|doi=10.1112/S0024609304003650|issue=6|journal=The Bulletin of the London Mathematical Society|mr=2083752|pages=769–778|title=The Cameron-Erdős conjecture|volume=36|year=[[2004 год в науке|2004]]}}</ref> и независимо — [[Сапоженко, Александр Антонович|Александром Сапоженко]]<ref>{{Citation|last=Сапоженко|first=Александр Антонович|author-link=Сапоженко, Александр Антонович|issue=6|journal=[[Доклады Академии наук]]|mr=2088503|pages=749–752|title=The Cameron-Erdős conjecture|volume=393|year=[[2003 год в науке|2003]]}}</ref><ref>{{Citation|last=Сапоженко|first=Александр Антонович|author-link=Сапоженко, Александр Антонович|doi=10.1016/j.disc.2007.08.103|issue=19|journal=[[Discrete Mathematics]]|mr=2433862|pages=4361–4369|title=The Cameron-Erdős conjecture|volume=308|year=[[2008 год в науке|2008]]}}</ref>.
 Сапоженко показал, что <math>s(N) = C_0 2^{N/2}</math> при четных N и <math>s(N) = C_1 2^{(N+1)/2}</math> при нечётных N, где <math>C_0 = 6.0 . . ., C_1 = 5.0 . . .. </math>
@@ Строка 23: / Строка 23: @@
 [[Категория:Аддитивная теория чисел]]
 [[Категория:Комбинаторика]]
-[[Категория:Пол Эрдёш]]
+[[Категория:Пал Эрдёш]]

Гипотеза Кэмерона — Эрдёша: различия между версиями

Текущая версия от 00:59, 4 августа 2023

Содержание

Формулировка

Замечания

История

Ссылки

Навигация

Гипотеза Кэмерона — Эрдёша: различия между версиями

Текущая версия от 00:59, 4 августа 2023

Формулировка

Замечания

История

Ссылки

Навигация

Поиск