Шарики, ниточки...

[Circiter]

2Someone

Цитата:

Но "ниточки" при необходимости сквозь сферы проходят, а не огибают их?

Верно, материальны только шары. Нитки -- это всего-лишь ограничители максимального расстояния между центрами шаров.

[gris]

Я ниточки представляю расположенными в параллельном пространстве. Например, для плоскости шары это диски, а ниточки привязаны сверху и не мешают. Но ниточки это ерунда, хотя в действительности существуют некоторые аналоги. Я про них спросил чисто для прояснения ситуации.
У меня вопросы именно по наглядному представлению модели. Я представляю себе точки окружённые непроницаемыми шарами радиуса $\alpha/2$, и как бы условными окрестностями - шарами радиуса $\beta$ или $\beta+\alpha/2$. В первом случае мы предполагаем, что центр каждого шара лежит в пересечении условных окрестностей остальных шаров. Во втором – что шар целиком лежит в этом пересечении.
Не хотелось бы оффтопить в математической теме, так как дальнейшее касается скорее микробиологии.
Кстати, англоязычные учёные уже не употребляют термин "Circitter set". Уже давно в ходу сокращение "c-set" или просто "cet" (не знаю, как это произносится).
У нас тоже стали употреблять слово "цет" (или цэт?), по крайней мере в неформальном общении. Чтобы не растягивать текст и я его стану употреблять. Цет - это просто цирциттерово множество.
У микробиологов своя терминология. У них цеты это компактные агломерации некоторых белков, в которых действуют законы цирциттеровости. Тут надо сказать, что в цетах участвуют, как правило, белки двух-трёх типов, для которых определены различные альфа. Это, естественно, усложняет математическую модель. У белков есть свойство "чувствовать" параметр бета. Никакой мистики, дело в обычной химии. Так же, как и свойство стремиться в ненасыщенный цет. И вот тут начинается самое интересное.
10-12 белков могут образовать максимальный цет, в котором нет места ещё одному белку. Но такой цет будет ригидным, то есть он может двигаться только как единое целое. Отдельные белки могут совершать только микроколебания возле своих мест расположения. 4 белка тоже могут образовать максимальный цет, но он тоже будет ригидным, хотя по другой причине. При движении белков внутри цета, он может перестать быть максимальным.
А вот 6-8 белков могут образовывать максимальные цеты с некоторой подвижностью белков внутри цета при сохранении его максимальности.
Интересно, что существуют ненасыщенные цеты с пустым местом внутри самого цета, в которое извне белок попасть не может. При некоторых уловиях "двери" открываются и цет захватывает внешний белок.
Я пытаюсь строить различные цеты на плоскости, хотя это всего лишь рисунки без всякой математики. Уверен, что это направление перспективное и что тут копать и копать. Завидую Вам, Circiter!

[master]

Circiter
А каждый шар должен быть связан как минимум с двумя шарами?

[gris]

Пара картинок по теме. Первая - шуточная из какого-то журнала. Вторая - мои попытки визуализации параметров.



Разумеется, имеет практическое значение изучение цетов в трёхмерном пространстве. На плоскости - это игра, не больше. Ну может быть поиск аналитических методов решения.
Мне интересны полные неригидные насыщенные цеты из промежуточного количества точек (то есть не максимальные и не минимальные цеты). Цеты с ненасыщенными внутренними областями, не допускающими внешней инвазии. Цеты с элементами трёх и более типов с различающимися параметрами альфа.

Напомню, что цет - это неформальное название цирциттерова множества в евклидовом пространстве.

[master]

gris в сообщении #251577 писал(а):

Цеты с ненасыщенными внутренними областями, не допускающими внешней инвазии.

Вокруг любого шара можно разместить 14(максимум) таких-же шаров касающихся его.
Если центрального шара нет, это к какому классу относится?

[gris]

master, конфигурации цетов сильно зависят от параметров. Шары можно разместить, но это может и не быть цирциттеровым множеством.
А насчёт "вынутого" центрального шара Вы абсолютно правы.
Только это будет ригидный цет. А он может сформироваться только искусственно. То есть это всего лишь игрушка. Хотя при увеличении параметра $\beta$ он будет подвижным. Но при этом он может стать ненасыщенным во внешней области. Вот и хотелось бы узнать интервал $\beta$, при котором возможно построение полного неригидного цета с насыщенной внешней областью. Автора неспроста интересуют именно минимальные значения параметра $\beta$ и максимальные $\alpha$.
Ведь сделав $\alpha$ слишком маленьким по сравнению с $\beta$, мы будем получать плотную упаковку большого шара маленькими шариками, а при $\alpha=0$ просто получим в качестве плотного цета внутренность шара радиуса $\beta$. Это такой же вырожденный и неинтересный случай, как при$\beta=\infty$
Интересны только конечные и небольшие цеты. Состоящие не более, чем из сотни точек, а ещё интереснее - из десяти - двадцати.
Тогда они являются моделями некоторых реальных физических явлений.
Кстати, с удивлением узнал, что в этологии при исследовании стайного и прайдового поведения, тоже используют некие аналоги цирциттеровых множеств.
И в психологии общения рассматриваемой сквозь призму НЛП. Только там, по-моему, многое за уши притянуто.

[master]

gris
Как я понимаю шары не могут пересекаться, или могут?
$\alpha$ и $\beta$ как связаны с радиусом шаров и расстоянием между центрами?

[gris]

Да шаров вообще нет. Задаётся минимальное расстояние между точками $\alpha$. Это эквивалентно тому, чтобы вместо точек рассматривать шары радиуса $\alpha/2$ в случае, если альфа одинакова для всех точек. В случае, если для каждой точки задано своё минимальное и максимальное расстояние до другой точки, то это уже другая постановка задачи.
При единых значениях параметров задача масштабируется, и можно принять значение $\alpha=1$. Тогда $\beta>1$. Вопрос в том, при каких значениях параметров возможны определённые конфигурации цетов.

[master]

gris
Пока на прямой, максимальное $n$,$n=\beta\mod\alpha +1$(количество точек).
$N=n-1$(количество структур)

[Circiter]

2gris
Огромное спасибо за невероятно интересные химико-микробиологические аналогии!

Цитата:

Я ниточки представляю расположенными в параллельном пространстве. Например, для плоскости шары это диски, а ниточки привязаны сверху и не мешают.

Да. При решении задачи в $m$-мерном пространстве, можно вложить её в $m+n^2$-мерное, чтобы каждая ниточка существовала в отдельном измерении и не мешала остальным объектам.

Цитата:

Разумеется, имеет практическое значение изучение цетов в трёхмерном пространстве. На плоскости - это игра, не больше.

Нет, что вы. В $\mathbb{R}^2$ тоже не все ясно и это тоже перспективное направление.

Предположение. В $\mathbb{R}^2$ при $\alpha=2$ и $\beta=4$, параметр $n<10$. Доказать это не так-то просто.

Цитата:

Задаётся минимальное расстояние между точками $\alpha$

Ну это если неравенства нестрогие использовать, а так лучше, наверное, говорить $\inf \rho(\xi_i,\ \xi_j)=\alpha$.

2master

Цитата:

А каждый шар должен быть связан как минимум с двумя шарами?

Каждый связан с каждым, т.е. всего $n^2$ связей.

Цитата:

Вокруг любого шара можно разместить 14(максимум) таких-же шаров касающихся его.

Нет. Максимум 12 в $\mathbb{R}^3$. В $\mathbb{R}^4$ -- уже 24 шара. Но, ещё раз повторюсь, есть предположение о том, что некоторые частные случаи задачи проще чем задача о контактном числе. Кстати, проблема контактного числа ещё сложнее чем наиплотнешие регулярные упаковки. Количество одинаковых шаров, касающихся центрального того-же радиуса известно (точно) только для размерностей (пространства) 1-4, 8 и 24 (в $\mathbb{R}^{24}$ вокруг центрального шара могут столпиться 196 560 таких-же шариков). Не густо!

Цитата:

Как я понимаю шары не могут пересекаться, или могут?

Шары материальны и пересекаться не могут. N.B.: по некоторым причинам я рассматриваю именно открытые шары, поэтому под материальностью, наверное, стоит понимать запрет пересечения (и даже касания, если под касанием понимать существование общей точки) именно замыканий шаров (или границ, i.e. сфер радиуса $\alpha/2$). В общем, имеет место быть топологическая путаница (замыкания шаров могут касаться лишь асимптотически). В прикладном отношении это не так уж и важно. К тому-же формулировка в терминах системы неравенств ($\alpha<\rho(\xi_i,\ \xi_j)<\beta$) передает точный смысл затеи.

Цитата:

$\alpha$ и $\beta$ как связаны с радиусом шаров и расстоянием между центрами?

Радиусы шариков равны $\alpha/2$. Параметр $\beta$ -- супремум расстояния между центрами. К тому же, как уже подметил gris, значения параметров-ограничителей могут "плавать", приводя к эквивалентным задачам (с точностью до масштабирования; $n$ при этом сохраняется).

Цитата:

Пока на прямой, максимальное $n$,$n=\beta\mod\alpha +1$(количество точек).
$N=n-1$(количество структур)

Поясните пожалуйста. Я, к сожалению, не понял.
P.S.: $\alpha,\ \beta\in \mathbb{R}$, $\alpha,\ \beta>0$, $\alpha<\beta$, $n\in\mathbb{N}$.

-- Чт окт 15, 2009 04:46:05 --

2master
Ой, из соображений экономии, достаточно рассматривать $(n^2-n)/2$ связей. Т.е. $n^2-n$ неравенств.

-- Чт окт 15, 2009 06:29:49 --

Ага, master попробовал применить ранее упомянутый подход с оценкой отношения объемов для вывода формулы в пространстве $\mathbb{R}$. В этом случае берется целая часть отношения $\alpha+\beta$ к $\alpha$ (объем шара в $\mathbb{R}$ очевидно равен его диаметру), т.е. $n=1+[\beta/\alpha]$ ($[\cdot]$ -- взятие целой части). Тогда $(\alpha;\ \beta)=(2;\ 4)\Rightarrow n=3$.

[master]

Circiter в сообщении #251783 писал(а):

Нет. Максимум 12

Спасибо. Эка меня понесло.
А на плоскости заданный вами интервал дает $n=7$
Но четкой аналитики пока не вижу.

[Circiter]

2master

Цитата:

А на плоскости заданный вами интервал дает $n=7$

Распишите поподробнее, как вы получили этот результат.

-- Чт окт 15, 2009 12:15:25 --

У меня для евклидовой плоскости получилась другая оценка. Напомню, что ранее я переформулировал задачу в терминах оценки отношения объемов шаров, в соответствующей постановке требовалось поместить как можно больше шаров диаметра $\alpha$ внутрь сферы диаметра $\alpha+\beta$. Однако, впоследствии мне стало ясно, что число $\alpha+\beta$ занижено и диаметр сферы может быть больше.

Как я получил оценку $\alpha+\beta$? Я просто представил себе два шара диаметра $\alpha$, находящихся на расстоянии между их центрами $\beta$ (с точностью до бесконечно малого), а затем описал около этой конструкции из шаров ограничивающую сферу; её диаметр, очевидно, как раз-таки и составил $\alpha+\beta$.

Но, вместе с тем, ясно, что условиям задачи при $\mathbb{V}=\mathbb{R}^m$ также удовлетворяет затравочное расположение шаров в вершинах правильного $m$-симплекса с ребром длины $\beta$. Так, в $\mathbb{R}^2$ диаметр сферы, описанной около тройки шаров, находящихся в вершинах равностороннего треугольника (со стороной $\beta$) равен $\alpha+2\beta/\sqrt{3}$.

Каким смыслом может быть наделено отношение объема шара, ограниченного этой сферой к объему шара диаметра $\alpha$? Понятно, что целая часть этого отношения суть очень грубая, завышенная оценка количества малых шаров без учета объема, незанятого ими.

Давайте посчитаем. Площадь круга радиуса $r$ равна $\pi r^2$, тогда искомый ответ (оценка для максимума $n$) таков:

$$n\approx \left[1+\frac{4\beta}{\sqrt{3}\alpha}+\frac{4\beta^2}{3\alpha^2}\right].$$

Подстановка конкретных значений $\alpha=2$ и $\beta=4$ дает $n\approx [10,9]\approx 10$.

Ещё раз подчеркну, что это верхняя оценка. Попробуем её улучшить. Воспользуемся тем, что объем промежутков, очевидно, больше нуля (по крайней мере для евклидовой метрики ), т.е. как минимум один шар явно лишний и расходуется на промежутки. Это наблюдение можно использовать для улучшения текущей оценки для $n$ до $n<10$, т.е. почти доказано ранее мной сделанное предположение.

Смущает, что такое улучшение, вообще говоря, некорректно. Ведь целая часть бралась от $\approx 10,9$, и этого $\approx 0,9$ вполне могло хватить на промежутки. Таким образом, по-прежнему $n\leqslant 10$.

[gris]

Circiter писал(а):

целая часть этого отношения суть очень грубая, завышенная оценка количества малых шаров

А в трёхмерном пространстве она будет ещё грубее.
Мне вроде бы удалось показать, что для параметров 2-4 на плоскости не существует цета из 8 точек. Или это настолько очевидно, что не требует доказательства?
И всё же я не согласен насчёт касания! Рассмотрение системы нестрогих неравенств даёт возможность свести её к системе уравнений, то есть по существу к задачам линейного программирования.
Помещение шаров в указанную Вами сферу даёт, разумеется, достаточный, но не необходимый признак существования цета.
В общем, есть над чем размышлять даже для простейших случаев.

[master]

Circiter
$n=[\frac{\beta^2}{\alpha^2}]+[\frac{\beta}{\alpha}]+1$
возможно ошибаюсь...

-- Чт окт 15, 2009 13:57:46 --

gris в сообщении #251817 писал(а):

Или это настолько очевидно, что не требует доказательства?

очевидно.

[Circiter]

2gris

Цитата:

Мне вроде бы удалось показать, что для параметров 2-4 на плоскости не существует цета из 8 точек. Или это настолько очевидно, что не требует доказательства?

Неочевидно.

Предположение. Максимальный цет на плоскости при параметрах 2-4 содержит как раз 8 точек. Но мои доводы пока смутные, надо ещё подумать.