The Library
The step Sidorenko property and non-norming edge-transitive graphs
Tools
Králʼ, Daniel, Martins, Taísa L., Pach, Péter Pál and Wrochna, Marcin (2019) The step Sidorenko property and non-norming edge-transitive graphs. Journal of Combinatorial Theory Series A, 162 . pp. 34-54. doi:10.1016/j.jcta.2018.09.012 ISSN 0097-3165 .
|
PDF
WRAP-step-Sidorenko-property-non-norming-edge-graphs-Kral-2018.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (668Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.jcta.2018.09.012
Abstract
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 [Israel J. Math. 175 (2010), 125-150].
Item Type: | Journal Article | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Bipartite graphs, Random graphs | ||||||||||||||||||||||||
Journal or Publication Title: | Journal of Combinatorial Theory Series A | ||||||||||||||||||||||||
Publisher: | Elsevier | ||||||||||||||||||||||||
ISSN: | 0097-3165 | ||||||||||||||||||||||||
Official Date: | February 2019 | ||||||||||||||||||||||||
Dates: |
|
||||||||||||||||||||||||
Volume: | 162 | ||||||||||||||||||||||||
Page Range: | pp. 34-54 | ||||||||||||||||||||||||
DOI: | 10.1016/j.jcta.2018.09.012 | ||||||||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||||||||
Date of first compliant deposit: | 20 September 2018 | ||||||||||||||||||||||||
Date of first compliant Open Access: | 2 October 2019 | ||||||||||||||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||||||||||||||
Related URLs: | |||||||||||||||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year