Zarankiewicz problem (original) (raw)
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.
| Property | Value |
|---|---|
| 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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Zarankiewicz-4-3.svg?width=300 |
| dbo:wikiPageID | 3480707 (xsd:integer) |
| dbo:wikiPageLength | 26568 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116384053 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Projective_plane dbr:Pál_Turán dbr:Bipartite_double_cover dbc:Mathematical_problems dbr:Cube dbr:Upper_bound dbr:Vera_T._Sós dbr:Degree_(graph_theory) dbr:Induced_subgraph dbr:Integer_lattice dbr:Levi_graph dbr:Complete_bipartite_graph dbr:Matrix_of_ones dbr:Girth_(graph_theory) dbr:Clique_cover dbr:Combinatorics dbr:Wacław_Sierpiński dbr:Edge_(graph_theory) dbr:Forbidden_graph_characterization dbr:Digital_geometry dbr:Discrete_geometry dbr:Forbidden_subgraph_problem dbr:Hexagon dbr:Asymptotic_analysis dbc:Unsolved_problems_in_graph_theory dbr:Kazimierz_Zarankiewicz dbr:Biclique-free_graph dbr:Big_O_notation dbc:Extremal_graph_theory dbr:Bipartite_graph dbc:Bipartite_graphs dbr:Szemerédi–Trotter_theorem dbr:Field_norm dbr:Vertex_(graph_theory) dbr:Štefan_Znám dbr:Euclidean_plane dbr:Extremal_graph_theory dbr:Turán's_theorem dbr:Finite_geometry dbr:Submatrix dbr:Cage_graph dbr:(0,1)-matrix dbr:File:Heawood_Graph.svg dbr:File:Zarankiewicz-4-3.svg |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Reflist |
| dct:subject | dbc:Mathematical_problems dbc:Unsolved_problems_in_graph_theory dbc:Extremal_graph_theory dbc:Bipartite_graphs |
| rdf:type | yago:WikicatMathematicalProblems yago:WikicatUnsolvedProblemsInMathematics yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 yago:State100024720 |
| 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) |
| rdfs:label | Задача Заранкиевича (ru) Zarankiewicz problem (en) Задача Заранкевича (uk) |
| owl:sameAs | freebase:Zarankiewicz problem yago-res:Zarankiewicz problem wikidata:Zarankiewicz problem dbpedia-ru:Zarankiewicz problem dbpedia-uk:Zarankiewicz problem https://global.dbpedia.org/id/4xEgc |
| prov:wasDerivedFrom | wikipedia-en:Zarankiewicz_problem?oldid=1116384053&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Heawood_Graph.svg wiki-commons:Special:FilePath/Zarankiewicz-4-3.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Zarankiewicz_problem |
| is dbo:knownFor of | dbr:Kazimierz_Zarankiewicz |
| is dbo:wikiPageRedirects of | dbr:Kövari–Sós–Turán_theorem dbr:Kővári–Sós–Turán_theorem dbr:Kővári-Sós-Turán_theorem dbr:Kövari-Sós-Turán_theorem dbr:Kővari-Sós-Turán_theorem |
| is dbo:wikiPageWikiLink of | dbr:Vera_T._Sós dbr:Kövari–Sós–Turán_theorem dbr:Kővári–Sós–Turán_theorem dbr:Timeline_of_Polish_science_and_technology dbr:Erdős–Stone_theorem dbr:W._G._Brown dbr:Forbidden_graph_characterization dbr:Forbidden_subgraph_problem dbr:Kazimierz_Zarankiewicz dbr:Kővári-Sós-Turán_theorem dbr:Bipartite_graph dbr:Extremal_graph_theory dbr:List_of_unsolved_problems_in_mathematics dbr:Even_circuit_theorem dbr:Kövari-Sós-Turán_theorem dbr:Kővari-Sós-Turán_theorem |
| is dbp:knownFor of | dbr:Kazimierz_Zarankiewicz |
| is foaf:primaryTopic of | wikipedia-en:Zarankiewicz_problem |
