Extremal graph theory (original) (raw)
Extremální teorie grafů je oblastí teorie grafů, která zkoumá vztah kvantitativních parametrů konečných grafů. Extremální teorie grafů též může být vnímána jako obor , která zkoumá podobné problémy pro další diskrétní struktury (zejména pro množinové systémy a hypergrafy).
| Property | Value |
|---|---|
| dbo:abstract | Extremální teorie grafů je oblastí teorie grafů, která zkoumá vztah kvantitativních parametrů konečných grafů. Extremální teorie grafů též může být vnímána jako obor , která zkoumá podobné problémy pro další diskrétní struktury (zejména pro množinové systémy a hypergrafy). (cs) Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure.Results in extremal graph theory deal with quantitative connections between various graph properties, both global (such as the number of vertices and edges) and local (such as the existence of specific subgraphs), and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy?A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory. Extremal graph theory is closely related to fields such as Ramsey theory, spectral graph theory, computational complexity theory, and additive combinatorics, and frequently employs the probabilistic method. (en) Die extremale Graphentheorie ist ein Teilgebiet der Mathematik. Sie untersucht, welche Graphen einer gegebenen Klasse (wie der Klasse der Graphen ohne Hamiltonkreis) einen bestimmten Graphenparameter (wie die maximale Anzahl von Kanten oder die Kantendichte) maximieren oder minimieren. Ein Ergebnis der extremalen Graphentheorie ist beispielsweise, dass Graphen mit Knoten, die keinen Kreis der Länge 3 enthalten, höchstens Kanten besitzen. Das ist ein Spezialfall des Satzes von Pál Turán (1941), der die extremale Graphentheorie begründete: Satz von Turán: Ein Graph mit n Knoten ohne p-Clique (vollständiger Untergraph mit p Knoten), , hat maximal Kanten. Definiert man zu einem Graphen die Zahl als die maximale Kantenzahl, die ein Graph mit Knoten und ohne einen zu isomorphen Untergraphen haben kann, so lässt sich diese Aussage zu umformulieren, wobei der vollständige Graph mit Knoten ist. Bezeichnet man mit den Kreisgraphen mit Knoten, so erhält man als weiteres Beispiel . Der Graph, der aus durch Hinzunahme eines weiteren Knotens und einer Kante entsteht, hat keinen zu isomorphen Untergraphen und Kanten (siehe nebenstehende Zeichnung für ). Die Hinzunahme einer weiteren Kante führt offenbar zu einem zu isomorphen Untergraphen. (de) La teoría de grafos extremales es una rama de las matemáticas que estudia cómo es que propiedades globales de un grafo pueden influir en su subestructura local. Esta rama abarca un vasto número de resultados que describen cómo ciertas propiedades de las gráficas - número de vértices, número de aristas, densidad de aristas, número cromático, o cintura, por ejemplo - garantizan la existencia de ciertas subestructuras locales. Uno de los principales objetos de estudio de esta área de teoría de grafos son los grafos extremales, que son o bien maximales o minimales con respecto a algún parámetro global, y tales que contienen (o no contienen) cierta subestructura local - ya sea un clique, o una coloración de sus aristas. (es) En théorie des graphes, un graphe extrémal (anglais : extremal graph) par rapport à une propriété est un graphe tel que l'ajout de n'importe quelle arête amène le graphe à vérifier la propriété . L'étude des graphes extrémaux se décompose en deux sujets : la recherche de bornes inférieures sur le nombre d'arêtes nécessaires à assurer la propriété (voire sur d'autres paramètres comme le degré minimum) et la caractérisation des graphes extrémaux proprement dits. L'étude des graphes extrémaux est une branche de l'étude combinatoire des graphes. (fr) Экстремальная теория графов — это ветвь теории графов. Экстремальная теория графов изучает экстремальные (максимальные или минимальные) свойства графов, удовлетворяющих определённым условиям. Экстремальность может относиться к различным инвариантам графов, таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа. (ru) Екстремальна теорія графів — це гілка теорії графів. Екстремальна теорія графів вивчає екстремальні (максимальні або мінімальні) властивості графів, які задовольняють певним умовам. Екстремальність може стосуватися різних інваріантів графів, таких як порядок, розмір або обхват. В абстрактнішому сенсі, теорія вивчає, як глобальні властивості графу впливають на локальні підструктури графу. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Turan_13-4.svg?width=300 |
| dbo:wikiPageID | 529568 (xsd:integer) |
| dbo:wikiPageLength | 9968 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1101691610 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probabilistic_method dbr:Dense_graph dbr:Vizing's_theorem dbr:Dependent_random_choice dbr:Independent_set_(graph_theory) dbr:Mathematics dbr:Graph_homomorphism dbr:Graph_removal_lemma dbr:NP-hard dbr:Container_method dbr:Erdős–Stone_theorem dbr:Clique_number dbr:Combinatorics dbr:Computational_complexity_theory dbr:Additive_combinatorics dbr:Spectral_graph_theory dbr:Edge_coloring dbr:Four-color_theorem dbr:Brooks'_theorem dbr:Graph_property dbr:Graph_theory dbr:Graphon dbr:Ramsey_theory dbr:Szemerédi_regularity_lemma dbr:Hypergraph_regularity_method dbc:Extremal_graph_theory dbr:Bipartite_graph dbr:Zarankiewicz_problem dbr:Planar_graph dbr:Greedy_coloring dbr:Hölder's_inequality dbr:Ore's_theorem dbr:Extremal_combinatorics dbr:Cauchy-Schwarz_inequality dbr:Turán's_theorem dbr:Ruzsa–Szemerédi_problem dbr:Sidorenko's_conjecture dbr:Ramsey-Turán_theory dbr:Turán_graph dbr:Random_graph dbr:Hypergraphs dbr:Probabilistic_combinatorics dbr:File:Petersen_graph_3-coloring.svg dbr:File:Turan_13-4.svg dbr:File:Epsilon_regular_partition.png |
| dbp:quote | Extremal graph theory, in its strictest sense, is a branch of graph theory developed and loved by Hungarians. (en) |
| dbp:source | Bollobás (en) |
| dbp:width | 300 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Main dbt:Quote_box |
| dcterms:subject | dbc:Extremal_graph_theory |
| gold:hypernym | dbr:Branch |
| rdf:type | dbo:Organisation |
| rdfs:comment | Extremální teorie grafů je oblastí teorie grafů, která zkoumá vztah kvantitativních parametrů konečných grafů. Extremální teorie grafů též může být vnímána jako obor , která zkoumá podobné problémy pro další diskrétní struktury (zejména pro množinové systémy a hypergrafy). (cs) En théorie des graphes, un graphe extrémal (anglais : extremal graph) par rapport à une propriété est un graphe tel que l'ajout de n'importe quelle arête amène le graphe à vérifier la propriété . L'étude des graphes extrémaux se décompose en deux sujets : la recherche de bornes inférieures sur le nombre d'arêtes nécessaires à assurer la propriété (voire sur d'autres paramètres comme le degré minimum) et la caractérisation des graphes extrémaux proprement dits. L'étude des graphes extrémaux est une branche de l'étude combinatoire des graphes. (fr) Экстремальная теория графов — это ветвь теории графов. Экстремальная теория графов изучает экстремальные (максимальные или минимальные) свойства графов, удовлетворяющих определённым условиям. Экстремальность может относиться к различным инвариантам графов, таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа. (ru) Екстремальна теорія графів — це гілка теорії графів. Екстремальна теорія графів вивчає екстремальні (максимальні або мінімальні) властивості графів, які задовольняють певним умовам. Екстремальність може стосуватися різних інваріантів графів, таких як порядок, розмір або обхват. В абстрактнішому сенсі, теорія вивчає, як глобальні властивості графу впливають на локальні підструктури графу. (uk) Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure.Results in extremal graph theory deal with quantitative connections between various graph properties, both global (such as the number of vertices and edges) and local (such as the existence of specific subgraphs), and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy?A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objec (en) Die extremale Graphentheorie ist ein Teilgebiet der Mathematik. Sie untersucht, welche Graphen einer gegebenen Klasse (wie der Klasse der Graphen ohne Hamiltonkreis) einen bestimmten Graphenparameter (wie die maximale Anzahl von Kanten oder die Kantendichte) maximieren oder minimieren. Ein Ergebnis der extremalen Graphentheorie ist beispielsweise, dass Graphen mit Knoten, die keinen Kreis der Länge 3 enthalten, höchstens Kanten besitzen. Das ist ein Spezialfall des Satzes von Pál Turán (1941), der die extremale Graphentheorie begründete: . (de) La teoría de grafos extremales es una rama de las matemáticas que estudia cómo es que propiedades globales de un grafo pueden influir en su subestructura local. Esta rama abarca un vasto número de resultados que describen cómo ciertas propiedades de las gráficas - número de vértices, número de aristas, densidad de aristas, número cromático, o cintura, por ejemplo - garantizan la existencia de ciertas subestructuras locales. (es) |
| rdfs:label | Extremal graph theory (en) Extremální teorie grafů (cs) Extremale Graphentheorie (de) Teoría de grafos extremales (es) Théorie des graphes extrémaux (fr) Экстремальная теория графов (ru) Екстремальна теорія графів (uk) |
| owl:sameAs | freebase:Extremal graph theory wikidata:Extremal graph theory dbpedia-cs:Extremal graph theory dbpedia-de:Extremal graph theory dbpedia-es:Extremal graph theory dbpedia-fa:Extremal graph theory dbpedia-fr:Extremal graph theory dbpedia-ru:Extremal graph theory dbpedia-uk:Extremal graph theory https://global.dbpedia.org/id/4uZ7F |
| prov:wasDerivedFrom | wikipedia-en:Extremal_graph_theory?oldid=1101691610&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Epsilon_regular_partition.png wiki-commons:Special:FilePath/Turan_13-4.svg wiki-commons:Special:FilePath/Petersen_graph_3-coloring.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Extremal_graph_theory |
| is dbo:academicDiscipline of | dbr:Béla_Bollobás |
| is dbo:knownFor of | dbr:Pál_Turán dbr:Béla_Bollobás dbr:Fan_Chung |
| is dbo:wikiPageRedirects of | dbr:Extremal_graph |
| is dbo:wikiPageWikiLink of | dbr:Pál_Turán dbr:List_of_University_of_California,_San_Diego_people dbr:David_Conlon dbr:Apollonian_network dbr:List_of_graph_theory_topics dbr:Unit_distance_graph dbr:David_Wood_(mathematician) dbr:Dependent_random_choice dbr:List_of_mathematical_theories dbr:Pearls_in_Graph_Theory dbr:Ernst_G._Straus dbr:Friendship_graph dbr:Glossary_of_areas_of_mathematics dbr:Container_method dbr:Erdős_on_Graphs dbr:Erdős–Stone_theorem dbr:Miklós_Simonovits dbr:Line_graph dbr:Common_graph dbr:Michael_Scott_Jacobson dbr:Béla_Bollobás dbr:W._G._Brown dbr:János_Körner dbr:Expander_graph dbr:Fan_Chung dbr:Forbidden_subgraph_problem dbr:Graph_theory dbr:Graphon dbr:Ramsey_theory dbr:Szemerédi_regularity_lemma dbr:Jacob_Fox dbr:Hypergraph_regularity_method dbr:Pankaj_K._Agarwal dbr:Kazimierz_Zarankiewicz dbr:Blow-up_lemma dbr:Homomorphism_density dbr:Zarankiewicz_problem dbr:Ramanujan_graph dbr:Ramsey's_theorem dbr:Extremal_combinatorics dbr:Turán's_theorem dbr:Ruzsa–Szemerédi_problem dbr:Even_circuit_theorem dbr:Topological_graph dbr:Ramsey-Turán_theory dbr:Turán_graph dbr:U._S._R._Murty dbr:Extremal_graph |
| is dbp:fields of | dbr:Béla_Bollobás |
| is dbp:knownFor of | dbr:Pál_Turán dbr:Béla_Bollobás dbr:Fan_Chung |
| is foaf:primaryTopic of | wikipedia-en:Extremal_graph_theory |
