Thursday, January 28, 2010

3-хслойные посеты

3-хслойные посеты (авторский перевод термина "3-layer posets") это тот класс частично упорядоченных множеств, которому принадлежат почти все из них [1]. Из чего следует, если вы докажите некоторое свойство об этом классе, значит докажите о почти всех.

"Графы линейных расширений (ГЛР) инвариантны относительно операции последовательной альтерации на порождающем его посете". Так звучит следствие теоремы, доказанной в [2]. В связи с этим результатом возникает следующие вопросы:
  1. Относительно какой (-их) операции (-ий) остается неизменным данное свойство некоторого класса ГЛР.
  2. Какое (-ие) свойство (-ва) некоторого класса ГЛР инвариантно (-ы) относительно данного набора операций.
Можно, например, рассмотреть операцию прямой суммы посетов. При этом наиболее простой случай, когда берутся два операнда, один из которых цепь, состоящая из одного элемента.

  1. D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205 (1975), pp. 205–220. (114)
  2. Massow MLinear Extension Graphs and Linear Extension Diameter. PhD Dissertation, Technischen Universität Berlin. - Berlin: 2009.

Wednesday, January 27, 2010

Две статьи и диссертация

Где-то в начале этого января удалось узнать о двух статьях, в которых были рассмотрены вопросы, над которыми я тогда работал. Сегодня, благодаря профессору Стефану Фельснеру, удалось получить доступ к их электронным версиям. Дело в том, что это препринты, которые нигде не публиковались. Стефан отсканировал эти препринты и теперь они доступны в сети:
  1. Reuter K. The Comparability Graph and the Graph of Linear Extensions of a Poset. Hamburger Beiträge zur Mathematik, Heft 57 (1996).
  2. Reuter K. Linear Extensions of a Poset as Abstract Convex Sets. Hamburger Beiträge zur Mathematik, Heft 56 (1996).
Кроме того, стала доступна электронная версия диссертации, которая явлется последним, если так можно выразиться, словом в исследованиях графов линейных расширений:

Massow MLinear Extension Graphs and Linear Extension Diameter. PhD Dissertation, Technischen Universität Berlin. - Berlin: 2009.

В данный момент читаю диссертацию, а препринты Ройтера оставил на десерт.

Наибольший интерес вызвали результаты об операциях на частично упорядоченных множествах (посетах) относительно которых графы линейных расширений (ГЛР) инвариантны. Также интересно было увидеть контрпример гипотезе о том, что ГЛР зависят только от графа сравнимости.

Интересно заметить, что диссертация защищена 11 декабря прошлого (2009) года, а опубликована при этом на текущую дату одна статья и еще одна статья подана на рассмотрение. Больше статей у автора по теме диссертации нет.

Tuesday, January 26, 2010

Перелік наукових фахових видань з фізико-математичних наук

В Википедии соорудил список ваковских изданий по физ.-мат. наукам.

Отличие от аналогичных списков по другим отраслям науки в том, что есть ссылки на соответствующие разделы на сайте библиотеки им. Вернадского.

Со временем, думаю, стоит добавить комментарии и какую-то статистику к этому списку.

Список является копией оригинала с сайта ВАК Украины, включая все ошибки, которые там содержатся, например: дублирование изданий, неправильные названия.

Вторая статья

В номере 2 за 2009 год журнала "Таврический вестник информатики и математики" напечатана статья моего руководителя и вашего покорного слуги. Эта статья была отослана в редакцию год назад.

Bondarenko O.S., Kozin I.V. Evolutionary fragmentary algorithm for permutation flow shop problem // Таврический вестник информатики и математики. - 2009. - №2. - С. 47-51.

Friday, January 22, 2010

Препринт

В некоторых университетах принято результаты научной работы распространять в виде препринтов. Чтобы это было характерно для украинских ВУЗов, утверждать не готов.

Удивила одна диссертация 2008 года, написанная в математическом институте им. Стеклова, а именно: список из трех статей, опубликованных по теме диссертации. Две из которых депонированы в ВИНИТИ. Вероятно, результаты работы этого молодого человека достаточно серьёзны, что и с одной публикацией он смог защититься.

Так вот о препринтах. Что-то похожее на препринт собирается разместить здесь и ваш покорный слуга. При этом не ожидая, что ему хватит для защиты одной опубликованной статьи и списка препринтов, депонированных куда-либо.

Как это следует из оформления статьи, ее планируется отправить в Вестник Киевского университета.

Бондаренко О.С. Розбиття пермутоедра.

Wednesday, January 6, 2010

Теория частичных порядков 2

В статье [1] упоминается о том, что граф линейных расширений $G(P)$ не является инвариантом сравнимости, при этом дается ссылка на [2].

Удалось найти работу [3], в которой отыскивается число линейных расширений с минимильным числом скачков.

В работе [1] приводится интересная теорема о том, что диаметр $G(P)$ равен числу несравнимых пар в минимальном двухмерном расширении $P$.
  1. Felsner S. The Linear-Extension-Diameter of a Poset / S. Felsner, K. Reuter // SIAM Journal on Discrete Mathematics, 1999.
  2. K. Reuter Linear Extensions of a Poset as Abstract Convex Sets, Preprint, Universitaet Hamburg, 1996.
  3. H.C. Jung Counting jump optimal linear extensions of some posets // Recent progress in algebra, AMS, 1999.

Monday, January 4, 2010

Теория частичных порядков

Изучаю последние несколько дней теорию частичных порядков [1] с ударением на следующие вопросы:
  1. Линейные расширения частичных порядков и их число для различных классов порядков.
  2. Инварианты графов сравнимости для соответствующих порядков.
Число линейных расширений данного линейного порядка является инвариантом графа сравнимости, также как и размерность Душника-Миллера.
Искал, но пока не нашел какие-либо описания такого параметра множества линейных расширений, как число линейных расширений с числом скачков (jump (setup) number) [2] или числом cтупенек (bump (stair) number) в заданном интервале. Известны задачи о нахождении перестановки с минимальным числом скачков (ступенек). Меня интересует число линейных расширений данного порядка с нулевым числом ступенек.

Кроме того, не нахожу ничего о выпуклых разбиениях симметрической группы.

1. Graham R.L. et al. Handbook of combinatorics Vol. 1.
2. Лозин В.В. E-свободные двудольные графы / Дискретный анализ и исследование операций, 2000.