Extremal results for odd cycles in sparse pseudorandom graphs

Elad Aigner-Horev; Hiêp Hàn; Mathias Schacht

doi:10.1016/j.endm.2013.10.060

Extremal results for odd cycles in sparse pseudorandom graphs

Elad Aigner-Horev
, Hiêp Hàn
, Mathias Schacht

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

תקציר

We consider extremal problems for subgraphs of pseudorandom graphs. Our results implies that for (n, d, λ)-graphs Γ satisfying. λ2k-1≪d2kn(logn)-2(k-1)(2k-1) any subgraph G⊂. Γ not containing a cycle of length 2. k+. 1 has relative density at most 12+o(1). Up to the polylog-factor the condition on λ is best possible and was conjectured by Krivelevich, Lee and Sudakov.

שפה מקורית	אנגלית
עמודים (מ-עד)	385-391
מספר עמודים	7
כתב עת	Electronic Notes in Discrete Mathematics
כרך	44
מזהי עצם דיגיטלי (DOIs)	https://doi.org/10.1016/j.endm.2013.10.060
סטטוס פרסום	פורסם - 5 נוב׳ 2013
פורסם באופן חיצוני	כן

גישה למסמך

10.1016/j.endm.2013.10.060

קבצים וקישורים אחרים

Link to publication in Scopus

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

@article{f018ade0d7054da8b469082912d3ac89,

title = "Extremal results for odd cycles in sparse pseudorandom graphs",

abstract = "We consider extremal problems for subgraphs of pseudorandom graphs. Our results implies that for (n, d, λ)-graphs Γ satisfying. λ2k-1≪d2kn(logn)-2(k-1)(2k-1) any subgraph G⊂. Γ not containing a cycle of length 2. k+. 1 has relative density at most 12+o(1). Up to the polylog-factor the condition on λ is best possible and was conjectured by Krivelevich, Lee and Sudakov.",

keywords = "Extremal graph theory, Odd cycles, Pseudorandom graphs",

author = "Elad Aigner-Horev and Hi{\^e}p H{\`a}n and Mathias Schacht",

note = "Funding Information: 1 Supported by FAPESP (Proc. 2010/16526-3) and by NUMEC/USP, lagem Estoc{\'a}stica e Complexidade of the University of S{\~a}o Paulo. 2Email: elad.horev|[email protected] 3Email: [email protected]",

year = "2013",

month = nov,

day = "5",

doi = "10.1016/j.endm.2013.10.060",

language = "אנגלית",

volume = "44",

pages = "385--391",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Extremal results for odd cycles in sparse pseudorandom graphs

AU - Aigner-Horev, Elad

AU - Hàn, Hiêp

AU - Schacht, Mathias

N1 - Funding Information: 1 Supported by FAPESP (Proc. 2010/16526-3) and by NUMEC/USP, lagem Estocástica e Complexidade of the University of São Paulo. 2Email: elad.horev|[email protected] 3Email: [email protected]

PY - 2013/11/5

Y1 - 2013/11/5

N2 - We consider extremal problems for subgraphs of pseudorandom graphs. Our results implies that for (n, d, λ)-graphs Γ satisfying. λ2k-1≪d2kn(logn)-2(k-1)(2k-1) any subgraph G⊂. Γ not containing a cycle of length 2. k+. 1 has relative density at most 12+o(1). Up to the polylog-factor the condition on λ is best possible and was conjectured by Krivelevich, Lee and Sudakov.

AB - We consider extremal problems for subgraphs of pseudorandom graphs. Our results implies that for (n, d, λ)-graphs Γ satisfying. λ2k-1≪d2kn(logn)-2(k-1)(2k-1) any subgraph G⊂. Γ not containing a cycle of length 2. k+. 1 has relative density at most 12+o(1). Up to the polylog-factor the condition on λ is best possible and was conjectured by Krivelevich, Lee and Sudakov.

KW - Extremal graph theory

KW - Odd cycles

KW - Pseudorandom graphs

UR - https://www.scopus.com/pages/publications/84887167768

U2 - 10.1016/j.endm.2013.10.060

DO - 10.1016/j.endm.2013.10.060

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84887167768

SN - 1571-0653

VL - 44

SP - 385

EP - 391

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Extremal results for odd cycles in sparse pseudorandom graphs

תקציר

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

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