Формулируемое ниже утверждение относится к разбиениям множеств в $% \mathbb R^n $% и выглядит очевидным. Однако в связи с тем, что в своем «несложном комбинаторном доказательстве» я давно нашел ошибку (есть контрпример для $%|X|=5$%) и не имею доказательств сформулированных утверждений, привожу этот вопрос в скорректированном виде.

Пусть $% I^n $% – дискретный [-1,1]-куб в $% \mathbb R^n $%, т. е. множество векторов из $% \mathbb R^n $% со значениями компонент из $% I= \lbrace -1,0,,1 \rbrace. $%

Для произвольных $% X \subseteq I^n; x,h\in I^n, x=(x_1,\dots,x_n) , h=(h_1,\dots,h_n) $% введем обозначения: $% X_{-1}(h)= \{ x \in X | (x,h) <0 \} $% , $%X_0(h)= \{ x \in X | (x,h)=0 \} $% , $%X_1(h)= \{ x \in X | (x,h)>0 \} ;$% $% N(X)= |X|, N(X,h)=\max_i |X_i(h)|. $%

Верны ли следующие утверждения.

У1. При всех $% X \subseteq I^n (|X| \ge 6) $% выполняется неравенство

$% \min_{h\in I^n} N(X,h)/ N(X) \le 1/2 $% .

У2. $%\lim \sup_{N \to \infty} \max_{|X|=N} \min_{h\in I^n} N(X,h)/ N =1/3. $%

Кроме того, хотелось бы иметь ответы на аналогичные вопросы для аналогичных утверждений при $%{h\in I_0^n}, $% где $% I_0^n=\{ h\in I^n | \sum h_i=0\}$%, а именно:

У3. При всех $% X \subseteq I^n (|X| \ge 12) $% выполняется неравенство

$% \min_{h\in I_0^n} N(X,h)/ N(X) \le 1/2 $% .

У4. $%\lim \sup_{N \to \infty} \max_{|X|=N} \min_{h\in I_0^n} N(X,h)/ N =1/3. $%

Для $%|X| \le 11 $% неравенство в У3 не выполняется, при этом для $%|X| = 10 $% и $%|X| = 11$% можно получить $%\max_{|X|=N} \min_{h\in I_0^n} N(X,h)=6. $%

Для пояснения приведу пример множества $% X\subset I^3 (|X|=5)$%, для которого $% N(X,h)\ge3$% при любом $% h \in I^3 $%: $%X=\{(0.0,0), (0,1,1), (1,0,1), (1,1,0), (1,1,1)\}.$%

задан 5 Май '13 2:20

изменен 29 Июн '16 18:08

Если $%X$% состоит из одного вектора $%x$%, то при любом $%h$% среди множеств $%X_i(h)$% будет два пустых и одно -- из одного элемента. Тогда максимум $%|X_i(h)|$% по $%i$% равен $%1$%, и так для каждого $%h$%. Я что-то не так понял, или в условии опечатка?

(5 Май '13 2:52) falcao

Спасибо, опечатка не n>=4, а |X|>=4. Я ее сейчас поправлю.

(5 Май '13 2:57) Urt

@Urt: я пытался думать над этой задачей (в том числе сегодня, когда ехал с работы). Какой-либо тривиальной конструкции придумать не удалось. Мне кажется, это утверждение нельзя отнести к категории очевидных. Кстати, что имеется в виду здесь под множеством $%E$%?

(7 Май '13 23:35) falcao

@Falcao, E^n - n-мерное евклидово пространство.

(8 Май '13 0:07) Urt

@Urt: теперь понятно! Я по смыслу сразу подумал на $%{\mathbb R}^n$%, но у меня возникла мысль, что буква $%E$% происходит не от "Euclidean", а от французского "ensemble". Дело в том, что в некоторых учебниках по дискретной математике такая буква довольно часто фигурирует для обозначения чего-нибудь типа $%E=\{0;1\}$% -- например, когда вводится понятие булевой функции.

(8 Май '13 2:23) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,924
×1,319
×32

задан
5 Май '13 2:20

показан
787 раз

обновлен
29 Июн '16 18:08

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru