RUS  ENG
Полная версия
СЕМИНАРЫ

Семинар Добрушинской лаборатории Высшей школы современной математики МФТИ
25 сентября 2012 г. 16:00, комн. 307 ИППИ РАН (Большой Каретный пер., 19), Москва


Максимальные паросочетания без пересечений

А. А. Владимиров

Институт проблем передачи информации им. А. А. Харкевича РАН, г. Москва

Аннотация: Решается задача определения максимального паросочетания без пересечений в случайном слове, записанном в алфавите {1,2,3,4}, с разрешенными парами 12 и 34. В упрощенном варианте для алфавита {1,...,M} разрешены пары 11, 22,...,MM. С прикладной точки зрения эта задача описывает модели вторичных структур молекул РНК (см. O.V. Valba, M.V. Tamm, S.K. Nechaev, "New alphabet-dependent morphological transition in a random RNA alignment"). Будет доказано, что в обеих постановках при M>2 ненулевая доля символов остается без пары. Если допустимые пары выбираются случайно с вероятностью 0<p<1, то имеет место фазовый переход: при значении параметра p порядка 0.38 доля не спаренных символов становится (асимптотически) равной нулю.


© МИАН, 2025