|
|
Семинар Добрушинской лаборатории Высшей школы современной математики МФТИ
25 сентября 2012 г. 16:00, комн. 307 ИППИ РАН (Большой Каретный пер., 19), Москва
|
|
|
|
|
|
Максимальные паросочетания без пересечений
А. А. Владимиров Институт проблем передачи информации им. А. А. Харкевича РАН, г. Москва
|
Количество просмотров: |
Эта страница: | 201 |
|
Аннотация:
Решается задача определения максимального паросочетания без пересечений в случайном слове, записанном в алфавите {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 доля не спаренных символов становится (асимптотически) равной нулю.
|
|