2022
Non-Bipartite K-Common Graphs
KRÁĽ, Daniel; Jonathan A NOEL; Sergey NORIN; Jan VOLEC; Fan WEI et. al.Basic information
Original name
Non-Bipartite K-Common Graphs
Authors
KRÁĽ, Daniel (203 Czech Republic, guarantor, belonging to the institution); Jonathan A NOEL; Sergey NORIN; Jan VOLEC and Fan WEI
Edition
COMBINATORICA, GERMANY, SPRINGER HEIDELBERG, 2022, 0209-9683
Other information
Language
English
Type of outcome
Article in a journal
Field of Study
10101 Pure mathematics
Country of publisher
Germany
Confidentiality degree
is not subject to a state or trade secret
References:
Impact factor
Impact factor: 1.100
RIV identification code
RIV/00216224:14330/22:00127840
Organization unit
Faculty of Informatics
UT WoS
000757755200002
EID Scopus
2-s2.0-85124762881
Keywords in English
common graphs; extremal combinatorics; Sidorenko's conjecture
Tags
International impact, Reviewed
Changed: 28/3/2023 12:08, RNDr. Pavel Šmerk, Ph.D.
Abstract
In the original language
A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of Kn is asymptotically minimized by a random coloring. For every k, we construct a connected non-bipartite k-common graph. This resolves a problem raised by Jagger, Štovíček and Thomason [20]. We also show that a graph H is k-common for every k if and only if H is Sidorenko and that H is locally k-common for every k if and only if H is locally Sidorenko.
Links
| MUNI/I/1677/2018, interní kód MU |
|