The step Sidorenko property and non-norming edge-transitive
graphs

J 2019

The step Sidorenko property and non-norming edge-transitive graphs

KRÁĽ, Daniel; Taísa MARTINS; Péter Pál PACH a Marcin WROCHNA

Základní údaje

Originální název

The step Sidorenko property and non-norming edge-transitive graphs

Autoři

KRÁĽ, Daniel; Taísa MARTINS; Péter Pál PACH a Marcin WROCHNA

Vydání

Journal of Combinatorial Theory, Series A, San Diego, Academic Press, Elsevier, 2019, 0097-3165

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 1.133

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/19:00113648

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

Sidorenko's conjecture; Weakly forming graphs; Graph limits

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 19. 4. 2020 23:09, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Sidorenko's Conjecture asserts that every bipartite graph H has the Sidorenko property, i.e., a quasirandom graph minimizes the density of H among all graphs with the same edge density. We study a stronger property, which requires that a quasirandom multipartite graph minimizes the density of H among all graphs with the same edge densities between its parts; this property is called the step Sidorenko property. We show that many bipartite graphs fail to have the step Sidorenko property and use our results to show the existence of a bipartite edge-transitive graph that is not weakly norming; this answers a question of Hatami (2010) [13].

Citovat

KRÁĽ, Daniel; Taísa MARTINS; Péter Pál PACH a Marcin WROCHNA. The step Sidorenko property and non-norming edge-transitive graphs. Journal of Combinatorial Theory, Series A. San Diego: Academic Press, Elsevier, 2019, roč. 162, č. 1, s. 34-54. ISSN 0097-3165. Dostupné z: https://doi.org/10.1016/j.jcta.2018.09.012.

@article{1646441,
   author = {Kráľ, Daniel and Martins, Taísa and Pach, Péter Pál and Wrochna, Marcin},
   article_location = {San Diego},
   article_number = {1},
   doi = {https://doi.org/10.1016/j.jcta.2018.09.012},
   keywords = {Sidorenko's conjecture; Weakly forming graphs; Graph limits},
   language = {eng},
   issn = {0097-3165},
   journal = {Journal of Combinatorial Theory, Series A},
   title = {The step Sidorenko property and non-norming edge-transitive graphs},
   url = {http://dx.doi.org/10.1016/j.jcta.2018.09.012},
   volume = {162},
   year = {2019}
}

TY  - JOUR
ID  - 1646441
AU  - Kráľ, Daniel - Martins, Taísa - Pach, Péter Pál - Wrochna, Marcin
PY  - 2019
TI  - The step Sidorenko property and non-norming edge-transitive graphs
JF  - Journal of Combinatorial Theory, Series A
VL  - 162
IS  - 1
SP  - 34-54
EP  - 34-54
PB  - Academic Press, Elsevier
SN  - 00973165
KW  - Sidorenko's conjecture
KW  - Weakly forming graphs
KW  - Graph limits
UR  - http://dx.doi.org/10.1016/j.jcta.2018.09.012
L2  - http://dx.doi.org/10.1016/j.jcta.2018.09.012
N2  - Sidorenko's Conjecture asserts that every bipartite graph H has the Sidorenko property, i.e., a quasirandom graph minimizes the density of H among all graphs with the same edge density. We study a stronger property, which requires that a quasirandom multipartite graph minimizes the density of H among all graphs with the same edge densities between its parts; this property is called the step Sidorenko property. We show that many bipartite graphs fail to have the step Sidorenko property and use our results to show the existence of a bipartite edge-transitive graph that is not weakly norming; this answers a question of Hatami (2010) [13].
ER  -

KRÁĽ, Daniel; Taísa MARTINS; Péter Pál PACH a Marcin WROCHNA. The step Sidorenko property and non-norming edge-transitive graphs. \textit{Journal of Combinatorial Theory, Series A}. San Diego: Academic Press, Elsevier, 2019, roč.~162, č.~1, s.~34-54. ISSN~0097-3165. Dostupné z: https://doi.org/10.1016/j.jcta.2018.09.012.

Přehled o publikaci