Задача по геометрии на плоскости.

[markvs]

Вот задача, которую я сегодня услышал. Задача вполне олимпиадного типа, но решения ни кто вроде бы не знает. Задачу предлагает Bruce Kleiner, но я не уверен, что он ее автор. Итак, рассмотрим произвольный граф G, у которого вершины - все узлы квадратной решетки. Считаем длину каждого ребра равной единице. Расстояние между вершинами графа - длина

Comments

edges

[falcao]

Хотелось бы уточнить условие на G. Сказано, каковы его вершины. Так ли я понимаю, что его рёбра -- это какая-то часть рёбер обычной решётки, и вопрос в том, какие рёбра этой решётки желательно выбросить, не включая их в G?

Re: edges

[markvs]

Нет, разрешается соединять любые две точки решетки ребром. Все ребра в графе - длины 1.

Re: edges

[_wep_]

Скорее добавить.

[lightjedi]

Я правильно понимаю, что граф бесконечный?

[french_man]

Гм. A вот более простой вопрос. Существует ли граф, для которого

limsup dG(A,B)/|A-B| · limsup |A-B|/dG(A,B) < √2

[french_man]

Здесь limsup - верхний предел при |A-B|→∞

[flaass]

Из шестиугольной решетки легко строится. Вроде, там будет 2/√3

[french_man]

Да, но у нас квадратная.

[markvs]

По-моему, ответ "не существует". Идея доказательства может быть такая. Предположим, что такой граф G есть. Берем любую неогр. возрастающую послeдовательность чисел d_n, и рассмотрим метрические пространства G/d_n (то есть делим расстояние на d_n).

Выбираем отмеченную вершину О в G и строим предел Громова-Хаусдорфа (асимптотический конус) C=Con(G, О, (d_n)). Ясно, что метрическое пространство C должно быть изометрично плоскости R^2. "Остаётся" доказать, что R^2 не может быть конусом никакого локально конечного графа (ясно, что G локально конечный ограниченной валентности). Это можно доказать одним из двух способов. Во-первых C - подпространство (связная компонента) ультрастепени G, и можно воспользоваться элементарной теорией. Еще вариант: использовать однозначность геодезических в R^2.

[vdohnovitel]

Это уже два месяца назад было, но вы не могли бы уточнить?
Что такое "ультрастепень G"?
И как нам может помочь однозначность геодезических в R^2?
Вообще, я очень удивлюсь, если R^2 не может быть конусом никакого локально конечного графа.
Спасибо!

[markvs]

I'll use English. Hope it is OK. The asymptotic cone can be described as follows (without Gromov-Hausdorff distance). Pick an ultrafilter D on N, that is a finitely additive measure on all subsets in N with two values, 0 and 1. We assume that the measure of a finite set is 0. Such measures exist by the Zorn lemma. Then consider the graph G and a sequence of "scaling constants" d_n --> \infty. We shall view G as a metric space with the path metric. Consider the direct power P=Prod G, i.e. the set of infinite sequences of vertices of G. Define a (pseudo)-distance on the set of these sequences by letting dist((x_n), (y_n)) = lim_D dist(x_n,y_n)/d_n. Here a D-limit of a sequence of numbers is the (unique) number a such that for every epsilon, D-almost all members of the sequence are in the epsilon-neighborhood of a. It is easy to show that the limit of any sequence of numbers exists (it can be infty). We identify two sequences if the distance between them is 0. The asymptotic cone of G is a connected component of the resulting metric

[markvs]

Что такое "ультрастепень G"?

It is the infinite power of G with two sequences identified when they coincide D-almost everywhere. The cone of G can be "extracted" from its ultrapower (see Kramer and others).

И как нам может помочь однозначность геодезических в R^2?

Graphs don't have unique geodesics unless they are trees. For every sequence of geodesics in G, one can consider its limit in the cone, which is again a geodesic. So to have unique geodesics in the cone, different geodesics connecting the same pair of points must be very close to each other.