Universality of Graphs with Few Triangles and Anti-Triangles

Dan Hefetz, Mykhaylo Tyomkyn

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

We study 3-random-like graphs, that is, sequences of graphs in which the densities of triangles and anti-Triangles converge to 1/8. Since the random graph n,1/2 is, in particular, 3-random-like, this can be viewed as a weak version of quasi-randomness. We first show that 3-random-like graphs are 4-universal, that is, they contain induced copies of all 4-vertex graphs. This settles a question of Linial and Morgenstern [10]. We then show that for larger subgraphs, 3-random-like sequences demonstrate completely different behaviour. We prove that for every graph H on n ≥ 13 vertices there exist 3-random-like graphs without an induced copy of H. Moreover, we prove that for every â"" there are 3-random-like graphs which are â""-universal but not m-universal when m is sufficiently large compared to â"".

שפה מקוריתאנגלית
עמודים (מ-עד)560-576
מספר עמודים17
כתב עתCombinatorics Probability and Computing
כרך25
מספר גיליון4
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 יולי 2016
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Universality of Graphs with Few Triangles and Anti-Triangles'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי