Sidorenko's conjecture is a conjecture in the field of graph theory, posed by in 1986. Roughly speaking, the conjecture states that for any bipartite graph and graph on vertices with average degree , there are at least labeled copies of in , up to a small error term. Formally, it provides an intuitive inequality about graph homomorphism densities in graphons. The conjectured inequality can be interpreted as a statement that the density of copies of in a graph is asymptotically minimized by a random graph, as one would expect a fraction of possible subgraphs to be a copy of if each edge exists with probability .
| Attributes | Values |
|---|
| rdfs:label
| - Conjecture de Sidorenko (fr)
- Sidorenko's conjecture (en)
- Гипотеза Сидоренко (ru)
|
| rdfs:comment
| - La conjecture de Sidorenko est une conjecture de la théorie des graphes, formulée par Alexander Sidorenko en 1986. Elle affirme que pour tout graphe biparti et tout graphe à sommets de degré moyen , il y a au moins copies de dans , à un petit terme d'erreur près. Plus formellement, elle fournit une inégalité intuitive sur les densités d'homomorphismes de graphons. L'inégalité conjecturée peut être interprétée comme l'assertion selon laquelle la densité de copies de dans un graphe est asymptotiquement minimisée par un graphe aléatoire ; elle est égale à la fraction dee sous-graphes qui sont une copie de , dans le cas où chaque arête existe avec probabilité . (fr)
- Sidorenko's conjecture is a conjecture in the field of graph theory, posed by in 1986. Roughly speaking, the conjecture states that for any bipartite graph and graph on vertices with average degree , there are at least labeled copies of in , up to a small error term. Formally, it provides an intuitive inequality about graph homomorphism densities in graphons. The conjectured inequality can be interpreted as a statement that the density of copies of in a graph is asymptotically minimized by a random graph, as one would expect a fraction of possible subgraphs to be a copy of if each edge exists with probability . (en)
- Гипотеза Сидоренко из теории графов касается оценки числа гомоморфизмов некоторого (произвольного, но фиксируемого) графа в произвольный граф . Она утверждает, что при двудольном это число никогда не меньше, чем для случайного графа размера с той же ожидаемой плотностью рёбер, что и у . Гипотезу выдвинул Александр Сидоренко в 1986 году (частный случай был доказан ещё раньше). Она разными методами доказана для некоторых классов графов , но далека от общего решения. (ru)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - La conjecture de Sidorenko est une conjecture de la théorie des graphes, formulée par Alexander Sidorenko en 1986. Elle affirme que pour tout graphe biparti et tout graphe à sommets de degré moyen , il y a au moins copies de dans , à un petit terme d'erreur près. Plus formellement, elle fournit une inégalité intuitive sur les densités d'homomorphismes de graphons. L'inégalité conjecturée peut être interprétée comme l'assertion selon laquelle la densité de copies de dans un graphe est asymptotiquement minimisée par un graphe aléatoire ; elle est égale à la fraction dee sous-graphes qui sont une copie de , dans le cas où chaque arête existe avec probabilité . (fr)
- Sidorenko's conjecture is a conjecture in the field of graph theory, posed by in 1986. Roughly speaking, the conjecture states that for any bipartite graph and graph on vertices with average degree , there are at least labeled copies of in , up to a small error term. Formally, it provides an intuitive inequality about graph homomorphism densities in graphons. The conjectured inequality can be interpreted as a statement that the density of copies of in a graph is asymptotically minimized by a random graph, as one would expect a fraction of possible subgraphs to be a copy of if each edge exists with probability . (en)
- Гипотеза Сидоренко из теории графов касается оценки числа гомоморфизмов некоторого (произвольного, но фиксируемого) графа в произвольный граф . Она утверждает, что при двудольном это число никогда не меньше, чем для случайного графа размера с той же ожидаемой плотностью рёбер, что и у . Гипотезу выдвинул Александр Сидоренко в 1986 году (частный случай был доказан ещё раньше). Она разными методами доказана для некоторых классов графов , но далека от общего решения. (ru)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)