Итак, наша проблема состоит в том, можно ли улучшить оценки, связанные с Проблемой 2 (стр. 5) из этой статьи.
Похоже, что и наша проблема, и Проблема 2 уже не актуальны, поскольку мы заметили, что
\sigma =\lim\inf \log_a c = \inf \log_a c = \inf \log_{a-1} (c-1).
Кроме того, \log_{b-1} (c-1)\ge\sigma для любой (a,b,c)-триангуляции. Csaba Toth с нами согласился.
Статистика:Добавлено Весельчак Ы — 12.11.2011, 10:44
]]>
Учитель начальных классов Ирина Яковлевна Матюхина разработала для первоклашек на основе мультфильма "Тайна Третьей планеты" урок математики "Космическое путешествие", посвящённый числам 1-5.
Статистика:Добавлено tktyf — 07.11.2011, 11:24
]]>
я начал читать одну новую статью [CTU] по нашей тематике, и теперь у нас тоже есть проблема, связанная с раскраской.
Дочитал. Итак, наша проблема состоит в том, можно ли улучшить оценки, связанные с Проблемой 2 (стр. 5) из этой статьи. Ее авторы [CTU] пишут, что «Our upper bounds for f(n) depend on the value \log_b c* of an (a; b; c)-triangulation. The (a; b; c)-triangulations we considered are all derived from counterexamples for Tait's conjecture. Since these are counterexamples for Hamiltonicity, they all have a = b > c > 0. It is conceivable, though, that there are better constructions for (a; b; c)-triangulations in which a > b**».
Кажется, все планарные триангуляции, имеющие больше 3-х вершин, 3-связны, а дуальные графы к ним это в точности кубические (т. е. со степенью каждой вершины 3) полиэдральные (т. е., в данном случае, 3-связные) графы. Таким образом, для случая a=b, искомые примеры графов, с возможно меньшими значениями выражения \log_{b-1} (c-1) тесно связаны с примерами графов, с возможно меньшими значениями выражения \log_a c, т. е. с возможно меньшим отношением логарифма длины своего наибольшего цикла к логарифму количества своих вершин. Lim-inf этого отношения по всем графам некоторого бесконечного класса графов называется shortness exponent для этого класса. В частности, известны следующие оценки shortness exponent \sigma для класса кубических 3-связных графов: 0.694…=\log_2(1+\sqrt5)-1\le\sigma [Jac] и \sigma\le\frac{\log26}{\log27}=0.988… [GruWal].
Однако, авторы [CTU] вместо графов с малым значением своей «shortness exponent», дающих соответствующие оценки сверху на \sigma, используют пример Bernette, Bosák и Lenderberg [CTU, c.4], дающий, видимо, более слабую оценку \log_{b-1} (c-1)=\frac{\log36}{\log37}.
* Я подозреваю, что выражение «\log_b c» здесь и в доказательстве Теоремы 1 является систематической опиской, а вместо него должно быть выражение «\log_{b-1} (c-1)», поскольку в статье в начале конструкции в доказательстве Теоремы 1 появляется оценка O(n^{\kappa \log_b c}) на количество граней, которые могут пересекаться прямой (со ссылкой на Лемму 2), хотя в самой Лемме 2 есть лишь оценка O(n^{\kappa \log_{b-1} (c-1)}), а выражение «\log_{b-1} (c-1)}» опять появляется в Conclusion.
** Также я подозреваю, что условие a > b не даст конструкций с меньшими значениями соответствующих выражений \log_{b-1} (c-1) и \log_b c.
[GruWal] B. Grünbaum, H. Walther. Shortness exponents of families of graphs. J. Combin. Theory A 14:364--385 (1973).
[Jac] B. Jackson. Longest cycles in 3-connected cubic graphs. J. Combin. Theory B 41:17--26 (1986).
Статистика:Добавлено Весельчак Ы — 06.11.2011, 13:00
]]>
Например, для случая, когда мы имеем граф «два квадрата с общей стороной» (6 вершин, 2 внутренних грани, 7 ребер), триангуляция внутренности вроде не делает его трехсвязным.
Да, тут я погорячился оба раза. Но для случая выпуклой внешней грани согласно приведенной Вами теореме Татта все хорошо. И хорды не мешают.Если допускать циклы с хордами, то контрпример, кажется, придумать несложно. Например, вроде, такой:
Вероятно, есть шансы зацепиться за этот факт при доказательстве гипотезы о смещении точек вдоль прямой. По крайней мере для случая, когда в исходном изображении ребра не пересекают прямую \ell, все вроде бы нетрудно получается.
Статистика:Добавлено Алексей Н. — 06.11.2011, 02:49
]]>
За время нашего обсуждения, я начал читать одну новую статью [CTU] по нашей тематике, и теперь у нас тоже есть проблема, связанная с раскраской.Мы то, раскрасочники, этими проблемами прямолинейности не грузимся.
Я собираюсь на днях дочитать эту статью, вникнуть в эту проблему, а также начать переписку с авторами статьи и своими соавторами. Также в этой статье, вроде, доказывается аналог равенства f(G)=c(G*) для плоских прямолинейных изображений планарных триангуляций.
Это естественное и разумное замечание. Как-то мы его, в явном виде, не сформулировали.На мой взгляд дилетанта в вопросах прямолинейных реализаций, трудности, возникающие при построении плоских реализаций, совсем иные, чем при построении полиэдральных реализаций. Если в первом случае надо бороться за непересекаемость отрезков, то во втором это само по себе уже не актуально (в ge 3-мерном пространстве), а все упирается в компланарность вершин каждой грани. В этом смысле, есть ощущение, что строить полиэдральные реализации триангуляций проще всего (ведь треугольник всегда в одной плоскости), а вот строить их плоские реализации максимально трудно.
Точно будет? Мне кажется, что нет. Например, для случая, когда мы имеем граф «два квадрата с общей стороной» (6 вершин, 2 внутренних грани, 7 ребер), триангуляция внутренности вроде не делает его трехсвязным. Или что Вы понимаете под простым циклом? Если Вы имеете в виду цикл без хорд, то добавим вершину в центр симметрии предыдущего графа.мы всегда можем достроить внутренность внешнего цикла H до триангуляции, а такой граф будет трехсвязным.
Опять таки, у нас есть гипотеза и на случай цикла без хорд: «Let C be a chordless cycle in a planar graph G. Then G can be drawn so that all but one vertices of C are collinear». В частности, эта гипотеза вроде верна, когда C является границей грани: «Recall that a triangulation is a plane graph where every face (including the outer face) is a triangle, and a near-triangulation is a plane graph where every face except possibly the outer face is a triangle. Tutte [12] proved that every near-triangulation has a straight-line embedding such that the outer face is mapped to a given convex polygon». [CTU]
верна ли теорема HN для любых (не трехсвязных) плоских графов, у которых внешняя грань ограничена простым циклом? Если да, то неужели не удается ее применить для положительного решения гипотезы? Если нет, то каковы контрпримеры?
Честно говоря, самого доказательства теоремы HN я не видел. Если допускать циклы с хордами, то контрпример, кажется, придумать несложно. Например, вроде, такой:
---
[CTU] Javier Cano, Csaba D. Tóth, Jorge Urrutia «Upper bound constructions for untangling planar geometric graphs»
Статистика:Добавлено Весельчак Ы — 03.11.2011, 23:35
]]>
Добавлено спустя 2 дня 4 часа 6 минут 13 секунд:
Re: Занимательные математические задачи про Алису и не только...
На мой взгляд дилетанта в вопросах прямолинейных реализаций, трудности, возникающие при построении плоских реализаций, совсем иные, чем при построении полиэдральных реализаций. Если в первом случае надо бороться за непересекаемость отрезков, то во втором это само по себе уже не актуально (в ge 3-мерном пространстве), а все упирается в компланарность вершин каждой грани. В этом смысле, есть ощущение, что строить полиэдральные реализации триангуляций проще всего (ведь треугольник всегда в одной плоскости), а вот строить их плоские реализации максимально трудно.
Вот не очень сложная задачка, слегка по теме:
8. (8 баллов) На плоскости даны 1004 попарно непересекающихся отрезка и 2011 точек, не лежащих на этих отрезках. Никакие три из данных точек не лежат на одной прямой. Докажите, что найдется треугольник с вершинами в данных точках, не пересекающийся ни с одним из данных отрезков.
Добавлено спустя 14 минут 16 секунд:
Re: Занимательные математические задачи про Алису и не только...
Есть вопрос: верна ли теорема HN для любых (не трехсвязных) плоских графов, у которых внешняя грань ограничена простым циклом? Если да, то неужели не удается ее применить для положительного решения гипотезы? Если нет, то каковы контрпримеры? Вроде неясно, с чего ей быть неверной, ведь мы всегда можем достроить внутренность внешнего цикла H до триангуляции, а такой граф будет трехсвязным.
Статистика:Добавлено Алексей Н. — 03.11.2011, 12:14
]]>
Подход Грюнбаума непосредственно основан не на топологии, а на геометрии (см. предпоследний абзац на с. 5 его статьи).Нарисуем на поверхности многогранника G замкнутый контур Z, проходящий через наибольшее число его граней (т.е. через c(G*) граней). По теореме Жордана Z делит поверхность G на две области D1, D2, гомеоморфные дискам. Непрерывно преобразуем поверхность G в сферу так, чтобы Z перешел в большую окружность этой сферы, а области D1, D2 (вместе с содержащимися в них вершинами и ребрами) - в две полусферы с общей границей Z.
Кстати, зафиксировав концы этих ребер также можно было пробовать доказать, что v(G)\ge c(G*)\ge f(G).Теперь единственная проблема - реализовать все так, чтобы ребра были отрезками прямых, но по-моему, это должно решаться в стиле теорем о существовании плоских реализаций планарных графов с прямыми ребрами.
Собственно, прямолинейными изображениями (straight-line drawings) графов мы и занимаемся. Но, в то время как теорема Вагнера-Фари-Стейна (Wagner-Fáry-Stein) о существовании прямолинейного изображения планарного графа, доказывается, видимо, относительно нетрудной индукцией, наверное, по числу вершин, в предлагаемой Вами идее есть ограничение на расположение вершин (в данном случае внешних граней). А доказательство подобных теорем может быть довольно трудным (например, следующая проблема открыта:
Suppose that $\pi$ is a crossing-free drawing of a graph $G$. A set of vertices $S\subseteq \pi(V_G)$ in $\pi$ is \emph{collinear} if all of them lie on a line $\ell$. By a \emph{conformal displacement} of $S$ we mean a relocation $\delta\function S\ell$ preserving the relative order in which the vertices in $S$ lie in $\ell$. We call $S$ \emph{free} if every conformal displacement $\delta\function S\ell$ is extendable to a mapping $\delta\function{\pi(V_G)}{\reals^2}$ so that $\delta\circ\pi$ is a crossing-free drawing of $G$ (i.e., whenever we shift vertices in $S$ along $\ell$ without breaking their relative order, then all edge crossings that may arise can be eliminated by subsequently moving the vertices in $\pi(V_G)\setminus S$). Is every collinear set in any straight line drawing free?
Вроде доказано, что ответ положителен для прямолинейных изображений специального вида (так называемых folded drawings)) С другой стороны, есть теорема Хонга и Нагамочи [HN]: Given a triconnected plane graph H, every drawing δ* of the outer facial cycle of H on a star-shaped polygon P can be extended in linear time to a plane drawing of H (even one where all inner faces are convex).
Кроме того, есть проблема с двухстороннестью связи между выпуклыми многогранниками и прямолинейными изображениями на плоскости. Вот что пишет мой соавтор по этой тематике, занимающийся графами и доктор наук: «Proposition … is based on the fact that a polyhedron can be projected to a straight line drawing. It seems that for the backward inequality we would need a kind of the converse, say, that any straight line drawing of a polyhedral graph can be “lifted” to a polyhedron. I do not know if this is true and am pessimistic about this: this statement is even stronger than Steinitz's theorem, whose known proofs are fairly uneasy».
[HN] Seok-Hee Hong and Hiroshi Nagamochi. «Convex drawing of graphs with non-convex boundary». In Fedor V. Fomin, editor, Proc. 32nd Internat. Workshop Graph-Theoretic Concepts in Comput. Sci. (WG’06), volume 4271 of Lecture Notes Comput. Sci., pages 113–124. Springer-Verlag, 2006.
Статистика:Добавлено Весельчак Ы — 31.10.2011, 11:28
]]>
Скажем, если G* гамильтонов, т. е. с(G*) = |F(G)|, то внутри областей D1 и D2 будут находиться деревья из вершин и ребер G (так называемое древесное 2-разбиение вершин G), а все грани G (и вообще все циклы) будут пересекать экваториальную плоскость, проходящую через Z.
Статистика:Добавлено Алексей Н. — 30.10.2011, 19:13
]]>
Но мы рассматриваем другую проблему. Согласно теореме Стейнитца (Steinitz), граф G изоморфен 1-скелету выпуклого многогранника, тогда и только тогда, когда G планарный и 3-связный. Такие графы называются полиэдральными. Для полиэдрального графа G нас интересуют наибольшее количество вершин v(G) (соответственно, граней f(G)) которые могут находиться в одной плоскости (соответственно, пересекаться одной плоскостью) в некоторой реализации графа G в виде 1-скелета выпуклого многогранника (т. е. v(G) и f(G) это соответствующие максимумы по реализациям и плоскостям), и, в особенности, асимптотические (в зависимости от числа вершин графа) оценки наименьших значений v и f в различных классах графов. (Откуда взялся наш интерес к этой проблеме – это отдельный вопрос).
Ясно, что f(G)\le c(G*), где G* – дуальный граф к G, а с(G*) – длина наибольшего цикла в G*. У нас есть гипотеза, что Грюнбаум в статье «Cutting convex polyhedra by planes» доказал, что f(G)=c(G*). Но этот результат мне кажется странным, поскольку, например, в этом случае должна существовать реализация 1-скелета глобуса в виде выпуклого многогранника, в котором можно пересечь почти все грани одной плоскостью. Поэтому мы сейчас разбираемся в доказательстве Грюнбаума и основном результате статьи Барнетта, на которую оно опирается.
Статистика:Добавлено Весельчак Ы — 30.10.2011, 18:12
]]>
Gr¨unbaum B. Gr¨otzsch’s theorem on 3-coloring, Michigan Math. J., 10:3 (1963), 303–310.
было дырявое доказательство того, что любой планарный граф с не более чем тремя 3-циклами является вершинно 3-раскрашиваемым (т. н. теорема Грюнбаума, обобщающая результат Грёцша о з-раскрашиваемости планарных графов без 3-циклов). Дыра, насколько я помню, заключалась в том, что в лемме о продолжении раскраски утверждалось, что в план. графе с одним треугольником любая 3-раскраска вершин 5-грани продолжается на весь граф. Это, конечно, неверно, и класс контрпримеров фактически описан в моей задаче 6 (только там общее ребро 5-грани и треугольника выброшено так, что получается предокрашенная 6-грань с непродолжаемой раскраской, дополнение которой четыреангулировано). Дыра оставалась незакрытой вплоть до работы Аксенова
Аксенов В. А. О продолжении 3-раскраски на плоских графах, Дискретный анализ: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, Вып. 26 (1974), 3–19.
(Aksionov V. A. On continuation of 3-colouring of planar graphs (in Russian), Diskret. Anal. Novosibirsk 26 (1974), 3–19.)
Там он дал правильную формулировку и доказательство теоремы о продолжении. Теперь уже и буржуи на это ссылаются в работах по плоским графам. Такая вот история. Поэтому в статьях с 1963 по 1974 (да и позже) могли появляться проколы, связанные с использованием той работы Грюнбаума.
Статистика:Добавлено Алексей Н. — 30.10.2011, 16:08
]]>