Задачи для исследования аспирантам, студентам и школьникам / Introductory research problems

If you solve some introductory exercises on some topic, then we can meet and discuss future work. Write to my address sk*penk*@mccme.ru, *=o.
Если Вы решите несколько вводных задач по какой-либо теме, то я буду рад встретиться с Вами или выступить на семинаре с Вашим участием. Напишите мне по sk*penk*@mccme.ru, где *=o.
Студенты ФИВТ МФТИ могут работать над задачами для исследования в рамках мат. практикума, полугодовой курсовой работы по научному треку инновационного практикума, дипломной работы. Приглашаю к сотрудничеству также студентов НМУ и (в исключительных случаях) других ВУЗов.
Некоторые задачи доступны школьникам. Ученики `Интеллектуала' могут подойти ко мне на уроки или в перемену между ними (в кабинет или учительскую).
Q: Какие темы курсовых у Вас ещё свободны? A: В первом приближении все свободны. Подробнее обсудим при встрече после решения Вами вводных задач. Нижеприведенный список тем и уже подготовленных курсовых регулярно обновляется. Even if some papers below are listed, there still remain interesting research problems on the corresponding subject.

Последнее обновление 27.10.2023.

Netflix problem and realization of (hyper)graphs

Low rank matrix completion / Минимизация ранга восполнением матриц.
Netflix problem and realization of (hyper)graphs.
Примеры курсовых и дипломных работ, глав в диссертациях (здесь и далее пропускается `и не студенческих работ соответствующего уровня'):
* A. Bikeev, Realizability of discs with ribbons on a Moebius strip, arXiv:2010.15833. Мат. Просвещение (2022).
* A. Bikeev, Towards a short proof of the Fulek-Kyncl criterion for modulo 2 embeddability of graphs to surfaces, arXiv:2012.12070 (дипломная работа).
* E. Kogan, On the rank of Z_2-matrices with free entries on the diagonal, arXiv:2104.10668.
* E. Kogan and A. Skopenkov, A short exposition of the Patak-Tancer theorem on non-embeddability of k-complexes in 2k-manifolds, arXiv:2106.14010.
* E. Kogan and A. Skopenkov, Embedding of k-complexes in 2k-manifolds and minimum rank of partial symmetric matrices, arXiv:2112.06636.
* S. Dzhenzher and A. Skopenkov, To the Kühnel conjecture on embeddability of k-complexes in 2k-manifolds, arXiv:2208.04188. A quadratic estimation for the Kühnel conjecture on embeddings (presentation).

Combinatorial topology of configuration spaces
С. Дженжер, А. Мирошников, О. Никитенко, А. Скопенков, Циклы в графах и в гиперграфах. (Вклад А. Мирошникова составляет его липломную работу.)
E. Alkin, S. Dzhenzher, O. Nikitenko, A. Skopenkov, A. Voropaev, Cycles in graphs and in hypergraphs.
Примеры курсовых работ и глав в диссертациях:
* В. Ретинский и Д. Захаров, Фишки в вершинах дерева, draft.
* A. Skopenkov, O. Styrt, Embeddability of join powers and minimal rank of partial matrices, arXiv:2305.06339.
* Е. Бордачева, Симметричные 1-циклы во взрезанном квадрате графа.

Графы на плоскости и на поверхностях / Graphs in the plane and on surfaces

Realization of graphs with rotations
Вводные задачи в п. 1.4, 1.5, 2.2-2.5, основные в п. 2.9 `Реализуемость утолщений'.
Пример одного из основных результатов докторской диссертации (МГУ, 2008, В.О. Мантуров, теорема 10): A. Skopenkov, Embeddings into the plane of graphs with vertices of degree 4, Мат. Просвещение, 21 (2017), 197-204, arXiv:1008.4940.

Realization of winding numbers
Пример курсовой работы:
* T. Garaev, On drawing K_5 minus an edge in the plane, arXiv:2303.14503.

Разводимость путей на плоскости / Stability of intersections of paths in the plane
Параграф 3 `Устойчивость самопересечений графов на плоскости'.
Устойчивость пересечений путей на плоскости / Stability of intersections of paths in the plane. Вводные задачи в первом пункте, основные в его конце.
A. Skopenkov, Stability of intersections of graphs in the plane and the van Kampen obstruction, Topol. Appl. 240 (2018) 259-269, arXiv:1609.03727.

Гиперграфы в трехмерных (и многомерных) многообразиях

Реализуемость косых произведений графов: Пункт 5.15.
Пример возможной дипломной работы: D. Tonkonog, Embedding 3-manifolds with boundary into closed 3-manifolds, Topol. Appl., 158 (2011) 1157-1162. arXiv:1003.3029.

Дружественность деревьев / Friendliness between trees: Стр. 1-3.
Примеры курсовых работ:
* A. Rukhovich, On intersection of two embedded spheres in 3-space, Topol. Appl. 170 (2014) 96-103, arXiv:1012.0925.
* S. Avvakumov, How do curved spheres intersect in 3-space? Topol. Appl. 172 (2014) 87-94, arXiv:1210.7361.
* V. Belousov, A smaller counterexample to the Lando conjecture, arXiv:1311.3086.
* D. Kolodzey, On friendliness between trees, arXiv:1509.00370.

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

Параграфы 2 и 6.
A. Skopenkov, A user's guide to the topological Tverberg conjecture, Russian Math. Surveys, 73:2 (2018) 323-353.
A. Skopenkov, Whitney trick for eliminating multiple intersections.
Примеры курсовых работ:
* D. Yang, An elementary proof of Borsuk theorem, arXiv:1010.1990 (немного по другой теме).
* N. Khoroshavkina, A simple characterization of graphs of cutwidth 2, arXiv:1811.06716.
* E. Kolpakov, A `converse' to the Constraint Lemma, arXiv:1903.08910 (дипломная работа).
* Е. Колпаков, Доказательство теоремы Радона при помощи понижения размерности, Мат. Просвещение, 23 (2018). arXiv:1903.11055.
* В.И.Ретинский, А.Д.Рябичев, А.Б.Скопенков. Мотивированное изложение доказательства теоремы Тверберга, Мат. Просвещение, 27 (2021), 166-169. arXiv:2008.08361.
* A. Asanau, On the \lowercase{TRIPLE SELF-INTERSECTION NUMBER FOR GRAPHS IN THE PLANE,} draft.

Зацепления и вложения

Linking in 3-space and in higher dimensions
\S4.4 `Combinatorial isotopy of linkings of triangles', \S4.11 `Зацепленность симплексов в многомерном пространстве'.
A simple direct proof of the Milnor Theorem 4.7.2.
Примеры курсовых работ:
* E. Kogan, Linking of three triangles in 3-space, arXiv:1908.03865.
* Т. Гараев, Элементарное доказательство существования полинома Конвея, Мат. Просвещение, 29 (2022) 184-199. arXiv:2012.03086.
* A. Asanau, \lowercase{A SIMPLE PROOF THAT CONNECTED SUM OF ORDERED ORIENTED LINKS IS NOT WELL-DEFINED,} Math. Notes, accepted.

Realizability of hypergraphs and intrinsic linking theory
Realizability of hypergraphs and intrinsic linking theory (see problems in \S2.6). Подробнее: Параграфы 1 и 6. Introductory problems.
A. Skopenkov, Extendability of simplicial maps is undecidable, Discr. Comp. Geom., 69:1 (2022), 1--10, arXiv:2008.00492.
Примеры курсовых работ:
*A. Zimin, Alternative proofs of the Conway-Gordon-Sachs Theorems, arXiv:1311.2882.
* S. Parsa and A. Skopenkov, On embeddability of joins and their `factors', Topol. Appl., 326 (2023), arXiv:2003.12285 (жаль, что это написали мы с SP, а не студент).
* M. Starkov, An example of an `unlinked' set of $2k+3$ points in $2k$-space, arXiv:2402.09002.
Примеры дипломных работ:
* R. Karasev and A. Skopenkov, Some `converses' to intrinsic linking theorems, Discr. Comp. Geom., to appear, arXiv:2008.02523 (жаль, что это написали мы с РН, а не студент).
* E. Alkin, Hardness of almost embedding simplicial complexes in R^d, II, arXiv:2206.13486.
Пример PhD thesis (IST Austria, 2017, S. Parsa): A. Skopenkov, A short exposition of S. Parsa's theorems on intrinsic linking and non-realizability, arXiv:1808.08363.

Заузливание многомерных многообразий
Зацепления: параграф 4.
A. Skopenkov, Embeddings in Euclidean space: an introduction to their classification, to appear in Bull. Man. Atl.
Примеры дипломных работ
* (НМУ, 2014) S. Avvakumov, The classification of certain linked 3-manifolds in 6-space, Moscow Math. J., 16:1 (2016), 1-25. arXiv:1408.3918.
* (матфак ВШЭ, 2021) М. Fedorov, A description of values of Seifert form for punctured n-manifolds in (2n-1)-space, arXiv:2107.02541
Примеры возможных кандидатских диссертаций (или глав в них):
* D. Tonkonog, Embedding punctured n-manifolds in Euclidean (2n-1)-space, arXiv:1010.4271.
* S. Avvakumov, The classification of linked 3-manifolds in 6-space, Algebr. Geom. Topol. 22 (2022) 2587-2630, arXiv:1704.06501.
Пример введения в дипломную работу или кандидатскую диссертацию: M. Fedorov, Embeddings of manifolds with boundary: classification (версия от июня 2020 - курсовая работа); Some calculations involving configuration spaces of distinct points.
Пример кандидатской диссертации (МГУ, 2008): М.Б. Скопенков, Классификация зацеплений и ее применения.

Теорема Колмогорова-Арнольда о суперпозициях / On Hilbert's 13th problem on superpositions

Базисность плоских множеств / Basic planar sets.
13я Проблема Гильберта о суперпозициях функций / 13th Hilbert Problem on superpositions of functions.
Вводные задачи: стр. 13-14. Basic embeddings and Hilbert's 13th problem on superpositions (in Russian). Basic embeddings and Hilbert's 13th problem on superpositions.
Примеры курсовых работ:
* S. Dzhenzher and A. Skopenkov, A structured proof of the Kolmogorov superposition theorem, arXiv:2105.00408.
* I. Reshetnikov, Decomposition of number arrangements in the cube, arXiv:1412.8078. См. также: Kh. Nurligareev, I. Reshetnikov, Decompositions of functions defined on finite sets in R^d, Journal of Knot Theory and Its Ramifications. 31:2 (2022), arXiv:2204.11084.
Пример дипломной работы
* S. Dzhenzher, A simpler proof of the Sternfeld theorem, arXiv:2110.15565.
Пример главы в кандидатской диссертации (МГУ, 2003): V. Kurlin, Basic embeddings into a product of graphs, Topology and Its Applications, 102:2 (2000), 113-137.

Алгоритмы решения алгебраических уравнений

Сложность решения уравнений / Complexity of solving equations.
К алгоритмам решения алгебраических уравнений / Toward algorithms of solving of algebraic equations.
Some more proofs from the Book: solvability and insolvability of equations in radicals. Еще несколько доказательств из Книги: разрешимость и неразрешимость уравнений в радикалах.
Примеры курсовых работ:
* А. Сафин, Программа для построения правильных многоугольников циркулем и линейкой draft, 2008.
* D. Akhtyamov and I. Bogdanov, Solvability of cubic and quartic equations using one radical, arXiv:1411.4990.
* E. Kogan, Set complexity of construction of a regular polygon, arXiv:1711.05807, Мат. Просвещение, 23 (2019).

Разное

  • Примеры курсовых работ:
    * I. Vasenov, Tiling of regular polygon with similar right triangles, I, arXiv:2010.05052.
    * M. Laczkovich, I. Vasenov, Tiling of regular polygons with similar right triangles arXiv:2109.07817.
    * L. Vigdorchik, Tiling of regular polygon with similar right triangles, II, preprint.
  • Степенные последовательности (п. 2.11) и тета-гамильтоновость (п. 2.12).
  • Поверхности из квадратиков / Surfaces made by squares.
    Приведите четкие формулировки, полные доказательства и обобщения гипотез работы (по ошибке названных теоремами).
    Give rigorous statements, complete proofs and generalizations of conjectures of the paper (which were called theorems by mistake).
  • Другие задачи для исследования (в т.ч. учебные) можно найти в заметках и в материалах Московской математической конференции школьников. Среди них много задач, доступных и интересных студентам и школьникам, занимающимся программированием и компьютерной наукой.