Counting independent sets in graphs

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

תקציר

In this short survey article, we present an elementary, yet quite powerful, method of enumerating independent sets in graphs. This method was first employed more than three decades ago by Kleitman and Winston and has subsequently been used numerous times by many researchers in various contexts. Our presentation of the method is illustrated with several applications of it to 'real-life' combinatorial problems. In particular, we derive bounds on the number of independent sets in regular graphs, sum-free subsets of {1,..., n}, and C4-free graphs and give a short proof of an analogue of Roth's theorem on 3-term arithmetic progressions in sparse random sets of integers which was originally formulated and proved by Kohayakawa, Łuczak, and Rödl.

שפה מקוריתאנגלית
עמודים (מ-עד)5-18
מספר עמודים14
כתב עתEuropean Journal of Combinatorics
כרך48
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 אוג׳ 2015

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2607???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Counting independent sets in graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

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