| dbo:abstract
|
- The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices and has no complete bipartite subgraphs of a given size. It belongs to the field of extremal graph theory, a branch of combinatorics, and is named after the Polish mathematician Kazimierz Zarankiewicz, who proposed several special cases of the problem in 1951. (en)
- Задача Заранкиевича, открытая проблема в математике, задаёт вопрос о наибольшем возможном числе рёбер в двудольном графе, имеющем заданное число вершин, но не содержащего полных двудольных подграфов заданного размера. Задача принадлежит области экстремальной теории графов, ветви комбинаторики, и названа именем польского математика , описавшего некоторые специальные случаи данной задачи в 1951. Теорема Ковари–Сос–Турана, названная именами Тамаса Ковари, и Пала Турана, даёт верхнюю границу для задачи Заранкиевича. Доказано, что если на одной из долей запрещённого двудольного графа имеется не более трёх вершин, эта граница отличается не более чем на постоянный множитель от истинного значения. Для бо́льших запрещённых подграфов известны лучшие значения границы, и есть гипотеза, что они тесны. Приложения теоремы Ковари–Сос–Турана включают оценку числа инциденций различных типов геометрических объектов в комбинаторной геометрии. (ru)
- Зада́ча Заранке́вича — відкрита проблема в математиці, ставить питання про найбільшу можливу кількість ребер у двочастковому графі, який має задану кількість вершин, але не містить повних двочасткових підграфів заданого розміру. Задача належить до галузі екстремальної теорії графів, гілки комбінаторики, і названа ім'ям польського математика , який описав деякі часткові випадки цієї задачі 1951 року. Теорема Коварі — Шош — Турана, названа іменами Тамаса Коварі, Віри Шош і Пала Турана, дає верхню межу для задачі Заранкевича. Доведено, що якщо на одній із часток забороненого двочасткового графа є не більше трьох вершин, ця межа відрізняється не більше ніж на сталий множник від істинного значення. Для великих заборонених підграфів відомі найкращі значення межі, і є гіпотеза, що вони тісні. Застосування теореми Коварі — Шош — Турана включають оцінення числа інциденцій різних типів геометричних об'єктів у комбінаторній геометрії. (uk)
|
| rdfs:comment
|
- The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices and has no complete bipartite subgraphs of a given size. It belongs to the field of extremal graph theory, a branch of combinatorics, and is named after the Polish mathematician Kazimierz Zarankiewicz, who proposed several special cases of the problem in 1951. (en)
- Задача Заранкиевича, открытая проблема в математике, задаёт вопрос о наибольшем возможном числе рёбер в двудольном графе, имеющем заданное число вершин, но не содержащего полных двудольных подграфов заданного размера. Задача принадлежит области экстремальной теории графов, ветви комбинаторики, и названа именем польского математика , описавшего некоторые специальные случаи данной задачи в 1951. (ru)
- Зада́ча Заранке́вича — відкрита проблема в математиці, ставить питання про найбільшу можливу кількість ребер у двочастковому графі, який має задану кількість вершин, але не містить повних двочасткових підграфів заданого розміру. Задача належить до галузі екстремальної теорії графів, гілки комбінаторики, і названа ім'ям польського математика , який описав деякі часткові випадки цієї задачі 1951 року. (uk)
|
