|
Проблемы передачи информации, 2014, том 50, выпуск 4, страницы 22–42
(Mi ppi2151)
|
|
|
|
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)
Теория кодирования
Верхние границы наименьшего размера полных дуг в $PG(2,q)$ при некотором вероятностном предположении
Д. Бартолиa, А. А. Давыдовb, Дж. Фаинаa, А. А. Крещукb, С. Маркуджиниa, Ф. Памбьянкоa a Университет Перуджи, Италия, факультет математики и компьютерных наук
b Институт проблем передачи информации им. А. А. Харкевича РАН
Аннотация:
В проективной плоскости $PG(2,q)$ рассматривается итеративная конструкция полных дуг, добавляющая одну новую точку на каждом шаге. Доказано, что непокрытые точки равномерно распределены на плоскости. Для более чем половины шагов итеративного процесса доказана оценка числа новых покрытых точек. Сделано естественное (и обоснованное) предположение, что эта оценка справедлива и для остальных шагов. В результате получены верхние границы наименьшего размера $t_2(2,q)$ полных дуг в $PG(2,q)$, в частности,
\begin{align*}
&t_2(2,q)<\sqrt q\sqrt{3\ln q+\ln\ln q+\ln 3}+\sqrt{\frac q{3\ln q}}+3,\\
&t_2(2,q)<1{,}87\sqrt{q\ln q}.
\end{align*}
Рассмотрены нестандартные типы верхних границ для $t_2(2,q)$, один из которых является новым. Эффективность новых границ проиллюстрирована сравнением с наименьшими известными размерами полных дуг, полученными в недавних работах авторов и в данной статье путем компьютерного поиска в широком диапазоне значений $q$. Отмечена связь рассматриваемых вопросов с так называемым парадоксом дней рождения.
Поступила в редакцию: 19.04.2014 После переработки: 25.08.2014
Образец цитирования:
Д. Бартоли, А. А. Давыдов, Дж. Фаина, А. А. Крещук, С. Маркуджини, Ф. Памбьянко, “Верхние границы наименьшего размера полных дуг в $PG(2,q)$ при некотором вероятностном предположении”, Пробл. передачи информ., 50:4 (2014), 22–42; Problems Inform. Transmission, 50:4 (2014), 320–339
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi2151 https://www.mathnet.ru/rus/ppi/v50/i4/p22
|
Статистика просмотров: |
Страница аннотации: | 536 | PDF полного текста: | 78 | Список литературы: | 54 | Первая страница: | 8 |
|