Личный кабинет
Адрес e-mail:
Регистрация Забыли пароль?

Кафедра дискретной математики

Кафедра дискретной математики относится к факультету инноваций и высоких технологий. Заведует кафедрой Андрей Михайлович Райгородский, руководитель совместных исследовательских программ Яндекса и МФТИ, главный редактор журнала Moscow Journal of Combinatorics and Number Theory, доктор физико-математических наук.


Контакты

dm@phystech.edu


Константин Юрьевич Войтиков,
зам. зав. кафедрой:
voitikov.ku@mipt.ru


Виктория Юрьевна Головлёва,
секретарь кафедры:
golovleva.vu@mipt.ru


Дмитрий Вячеславович Самиров,
редактор кафедрального сайта:
samirov.dv@mipt.ru



Лекции о графах пересечений геометрических объектов от Иштвана Томона, 2019
24.11.2019

29 ноября и 2 декабря пройдут лекции венгерского математика Иштвана Томона. Он расскажет о графах пересечений геометрических объектов. Мероприятие организовано лабораторией комбинаторных и геометрических структур ФПМИ.


Лектор — Иштван Томон, молодой и яркий специалист в комбинаторике, младший научный сотрудник (постдок) Швейцарской высшей технической школы Цюриха. Известен своими результатами в экстремальной комбинаторике и исследованиями частично упорядоченных множеств. Трижды участвовал в Международной олимпиаде школьников: в 2006 году получил серебряную медаль, в 2008 и 2009 годах стал золотым медалистом.


Название цикла лекций: Intersection graphs of geometric objects


Аннотация: The intersection graph of some family of geometric objects (e.g. line segments, axis parallel rectangles, convex sets) is the graph, whose vertices correspond to the elements of this family, and two vertices are joined by an edge if the corresponding objects have a nonempty intersection. In the past 60 years, graph theoretic properties of such intersection graphs are extensively studied both from a theoretical and a practical point of view. In this mini-course, I will survey some classical and recent results about Ramsey and coloring properties of geometric intersection graphs, along with numerous open problems.


Лекции Иштвана Томона на английском языке пройдут:


29 ноября (пятница) 17:00 - 18:30 в поточной аудитории корпуса Физтех.Арктика;

2 декабря (понедельник) 17:00 - 18:30 в аудитории № 414 ГК.


Приглашаются все желающие. Участникам не из МФТИ необходимо написать организаторам лекции на почту kupavskaia.io@mipt.ru и в день лекции взять с собой паспорт.

Лекции венгерского математика Габора Тардоша, 2019
24.11.2019

С 26 по 28 ноября в поточной аудитории Физтех.Арктика пройдет цикл лекций об экстремальной теории вершинно- и рёберноупорядоченных графов от венгерского математика Габора Тардоша. Мероприятие организовано лабораторией комбинаторных и геометрических структур ФПМИ.


Габор Тардош – крупнейший специалист в комбинаторике, дискретной геометрии и теоретических вычислительных науках, научный сотрудник Института математики имени Реньи Венгерской академии наук в Будапеште. Один из его самых известных результатов – алгоритмическая версия локальной леммы Ловаса (совместно с Мозером). В 1992 году Габор Тардош получил премию Европейского математического общества для молодых исследователей. В 2018 году был приглашенным докладчиком на Международном математическом конгрессе.


Название цикла лекций: Extremal theory of vertex- and edge-ordered graphs


Аннотация: The basic question of Turan type extremal graph theory is the maximum number of edges in a simple graph on n vertices that does not contain a specified "forbidden" subgraph (or any one of several forbidden subgraphs). This is a classical topic of combinatorics with many deep results and lot of questions that are still open.


In my survey talk I will focus on extensions of this theory to simple graphs with an additional structure, namely a linear order on the set of vertices or edges. A single simple graph has several vertex order and by forbidding just one of them we obtain different extremal questions. Introducing either a vertex- or an edge-order makes the theory richer and more suitable to (mostly geometric) applications.


I will highlight several specific open problems about both vertex- and edge-ordered graphs. I will mention results from numerous researchers, among them Balazs Keszegh, Daniel Korandi, Jesse Geneson, Daniel Gerbner, Adam Marcus, Abhishek Methuku, Daniel Nagy, Janos Pach, Seth Pettie, Domotor Palvolgyi, Istvan Tomon, Mate Vizer, Creig Weidert, etc.


Расписание лекций (на английском языке):


26 ноября (вторник) 16:00 - 17:00;

27 ноября (среда) 16:00 - 17:00;

28 ноября (четверг) 17:00 - 18:00.


Приглашаются все желающие. Участникам не из МФТИ необходимо написать организаторам на почту kupavskaia.io@mipt.ru и в день лекции взять с собой паспорт.

Combinatorics and Geometry Days - I, 26.11.2019 - 27.11.2019
22.11.2019

26 и 27 ноября в МФТИ пройдет конференция Combinatorics and Geometry Days - I. 


Мероприятие организовано лабораторией комбинаторных и геометрических структур Физтех-школы прикладной математики и информатики (ФПМИ). 


Конференция послужит местом встречи для комбинаторов и геометров, где они обсудят и представят их последние научные результаты, а также прочитают обзорные лекции, которые будут понятны заинтересованным магистрантам и аспирантам. В частности именно в рамках данной конференции начнутся циклы лекции по комбинаторике Иштвана Томона и Габора Тардоша.


Конференция будет проходить 


26 ноября:

10:00 до 12:00 - аудитория 424 Корпуса Артика,

13:10 до 17:00 - поточной аудитория Корпуса Артика (4 этаж).


27 ноября:

10:00 до 13:00 - аудитория 119 Главного Корпуса,

14:00 до 19:00 - поточная аудитория Корпуса Артика (4 этаж).


Язык конференции - английский. Приглашаются все желающие. Участникам не из МФТИ необходимо написать организаторам лекции на почту kupavskaia.io@mipt.ru и в день конференции взять с собой паспорт.



Подробности на сайте конференции: http://combgeo.org/en/events/combinatorics-and-geometry-days-at-mipt-i/

Мини-курс Stefano Boccaletti "Complex Networks: Introduction and Applications"
11.11.2019
18 ноября 13:55-16:55
Главный Корпус, 123

19 ноября 10:45-13:45
Физтех.Арктика, поточная аудитория 4 этажа

1. Complex Networks: Introduction and mathematical description (I)
In this first lecture, I will introduce the formalism of complex networks, and describe some fundamental quantity related to network's structure, as the degree distribution, the clustering coefficient, the degree-degree correlations.
I will also introduce the main terminology used for the description of networks.

2. Complex networks: Introduction and mathematical description (II)
In this second lecture, I will describe several quantities which are generally used to characterize the structure of a network, as node centrality, node betweenness, network efficiency, and network's vulnerability.

3. Synchronization in complex networks: the Master Stability Function
In this third lecture I will consider a network of dynamical units and will describe the most important technique used for assessing synchronization: the Master Stability Function. I will discuss then several phenomena of synchronization
which can occur in dynamical networks.

4. Complex Network for Data Analysis
In this fourth lecture, I will describe how networks can be used for data analysis, and will in particular introduce two classes of networks (functional networks and parenclitic networks) which have recently found application in various fields of science.
Workshop on Complex Networks, 15 ноября, 10:00, Биофармацевтический Корпус, 107
10.11.2019
Дата и место: 15 ноября, 10:00, МФТИ, Биофармацевтический Корпус, 107

Ключевые докладчики: Stefano Boccaletti (CNR-ISC, Florence, Italy) и Nelly Litvak (University of Twente, the Netherlands).

Stefano Boccaletti "Parenclitic networks: how to uncover new functions and structural information from data"

Abstract: In this talk I will describe a novel method to represent time independent, scalar data sets as complex networks, and show (as an illustrative example) how it applies to biological data (gene expression in the response to osmotic stress of Arabidopsis thaliana). The proposed network representation allow to identify the most important features distinguishing an individual from a class: for the case of the plant response it turns out to be the nodes with highest centrality in appropriately reconstructed networks, called parenclitic networks. We also performed a target experiment, in which the predicted genes were artificially induced one by one, and the growth of the corresponding phenotypes compared to that of the wild-type. This novel representation extends the use of graph theory to data sets hitherto considered outside of the realm of its application, vastly simplifying the characterization of their underlying structure.


Stefano Boccaletti is a senior researcher in the Institute of Complex Systems in Florence. He is a specialist in statistical and nonlinear physics, nonlinear optics and complex systems sciences with applications to biology, medicine, social sciences and other areas. He contributed several influential papers studying the synchronization effect in complex networks, including the now standard way of their classification. His monograph "Complex Networks: Structure and Dynamics" is among the highest ever cited publications in the field of complex networks and applications.


Nelly Litvak "Current research directions in complex networks: an informal survey"

 
Nelly Litvak is a professor in Algorithms for Complex Networks with background in Applied Probability and Stochastic Operations Research. Her main research interests are in large networks such as on-line social networks and the World Wide Web, randomized algorithms, and random graphs, and since recently prediction for networks using machine learning. She is also known as an excellent lecturer and mathematics popularizer.

Видеозаписи рассказов о некоторых темах НИР, 2019
23.10.2019
Видео доступно по ссылке
Доклад израильского математика Рома Пинхаси по дискретной геометрии, 21.10.2019
15.10.2019

21 октября в 18:30 в аудитории 2.35 Физтех.Цифры в рамках Межкафедрального семинара по дискретной математике будет прочитан доклад «Point sets in general position that determine lines with a small piercing set» израильского математика Рома Пинхаси. Мероприятие организовано лабораторией комбинаторных и геометрических структур Физтех-школы прикладной математики и информатики (ФПМИ).


Лектор — Ром Пинхаси (Rom Pinchasi), специалист в дискретной геометрии, профессор института Технион (Technion) в городе Хайфе в Израиле. Известен исследованиями задач типа Сильвестра — Галлаи, а также топологических графов. Участник Международной математической олимпиады 1992 года в Москве.


Let P be a set of n points in general position (no three on a line) in the plane. Assume R is another set of n points disjoint from P such that every line through two points in P passes through a point in R. It is conjectured that in such a case P is contained in a cubic curve in the plane. In a joint work with Chaya Keller we prove this conjecture under additional assumption that the point in R collinear with two points a and b in P is not contained in the straight line segment delimited by a and b. This already generalizes a result of Jamison from 1978 about point sets that determine minimum number of distinct directions. Related results and open problems will be discussed on the seminar.


Доклад на английском языке. Приглашаются все желающие.


Для заказа пропуска нужно написать на почту: kupavskaia.io@mipt.ru

Московская математическая конференция школьников, 2019
08.10.2019
15 октября - рекомендуемый срок присылки работ на ММКШ
Лекции по топологической комбинаторике от израильского математика Рона Аарони
Лекции по топологической комбинаторике от израильского математика Рона Аарони
12.09.2019

С 16 по 18 сентября в 14:00 в поточной аудитории Физтех.Арктики пройдут лекции по топологической комбинаторике от израильского математика Рона Аарони. Лекция организована лабораторией комбинаторных и геометрических структур МФТИ и Физтех-школы прикладной математики и информатики (ФПМИ).


Лектор — Рон Аарони (Ron Aharoni), специалист в области топологической комбинаторики, профессор Израильского технологического института (Technion) в городе Хайфе. Известен своими работами о паросочетаниях в бесконечных графах, а также обобщением теоремы Холла на случай гиперграфов. Является популяризатором науки и автором нескольких несколько книг.


Abstract: 
The lecture series is devoted to colorful analogues of famous combinatorial theorems and interesting open questions in topological combinatorics. In particular, a connection between Hall-type theorems and generalizations of Colorful Caratheodory`s Theorem will be discussed. All topological and combinatorial facts needed for obtaining these results will be introduced.


Курс рассчитан на студентов старших курсов, аспирантов и исследователей в области комбинаторики. Язык лекций — английский. 
Курсы по выбору в осеннем семестре 2019
08.09.2019

МФТИ в социальных сетях