RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды по дискретной математике // Архив

Тр. по дискр. матем., 2006, том 9, страницы 377–400 (Mi tdm154)

Эта публикация цитируется в 4 статьях

Пороговые функции совместности случайных систем уравнений

А. В. Шаповалов


Аннотация: Рассматривается случайная система уравнений относительно $n$ неизвестных, состоящая из $M=M(n)$ уравнений. Функции в уравнениях выбираются случайно и могут зависеть не более чем от $m$ переменных. Получены оценки вероятности совместности случайной системы уравнений при $n\to\infty$, $m=\operatorname{const}$. Выявлено влияние, которое оказывают пороговые функции для гипердеревьев в случайных гиперграфах и полузапреты функций в уравнениях случайной системы уравнений на вид предельных оценок вероятности ее совместности. В частности, сформулирован критерий того, что при $M-cn^{1-1/l}=o(n^{1-1/l})$, $n\to\infty$, предельное значение вероятности совместности случайной системы, уравнений убывает от единицы до нуля, принимая все промежуточные значения, с ростом $c$ от нуля до $\infty$ ($l\ge2$ – константа).



© МИАН, 2024