Поперечники, связанные с псевдоразмерностью
Ю. В. Малыхин Московский государственный университет им. М. В. Ломоносова
Аннотация:
Рассмотрены два поперечника, связанные с понятием псевдоразмерности. Первый из них,
$\rho_n$, определяется аналогично колмогоровскому поперечнику, но с заменой линейной размерности на псевдоразмерность;
$\rho_n$ оценивается снизу через поперечник
$s_n$, определяемый как
$1/2$ длины максимального ребра
$(n+1)$-мерного “координатного” куба, специальным образом вписанного в данное множество. Построены примеры множеств со сколь угодно большими отношениями
$\rho_n/s_n$ (при
$n\geqslant2$) и
$\rho_{10n}/s_{9n}$ (при достаточно большом
$n$). В терминах комбинаторной размерности основной результат означает, что для любого
$C>0$ и достаточно больших
$n$ существует множество
$W$ размерности
$\mathrm{vc}(W,1)\leqslant9n$, которое не может быть приближено по равномерной норме с точностью
$C$ множеством
$V$ размерности
$\mathrm{vc}(V,0)\leqslant10n$.
Библиография: 8 наименований.
Ключевые слова:
размерность Вапника–Червоненкиса, комбинаторная размерность, поперечники.
УДК:
519.1+517.5
MSC: Primary
41A46; Secondary
54F45 Поступило в редакцию: 11.04.2007
DOI:
10.4213/im2648