Maximizing the number of independent sets of a fixed size

DOI10.1017/S0963548314000546MaRDI QIDQ5364240zbMATH OpenOpenAlexFDO

Authors Wenying Gan, Po-Shen Loh, Benny Sudakov

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.4147

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Let $i_t(G)$ be the number of independent sets of size $t$ in a graph $G$. Engbers and Galvin asked how large $i_t(G)$ could be in graphs with minimum degree at least $delta$. They further conjectured that when $ngeq2delta$ and $tgeq3$, $i_t(G)$ is maximized by the complete bipartite graph $K_{delta,n-delta}$. This conjecture has drawn the attention of many researchers recently. In this short note, we prove this conjecture.

Recommendations

• Counting independent sets of a fixed size in graphs with a given minimum degree
• On independent sets in graphs with given minimum degree
• Two problems on independent sets in graphs
• Independent sets in graphs with given minimum degree
• The maximum number of complete subgraphs of fixed size in a graph with given maximum degree

Cites work

• A new method for enumerating independent sets of a fixed size in general graphs
• An entropy approach to the hard-core model on bipartite graphs
• Counting independent sets of a fixed size in graphs with a given minimum degree
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• Independent sets in graphs with given minimum degree
• On Chromatic Graphs
• On independent sets in graphs with given minimum degree
• The maximum number of complete subgraphs in a graph with given maximum degree
• Two problems on independent sets in graphs

Cited in

(40)

• Random maximal independent sets and the unfriendly theater seating arrangement problem
• The maximum number of balancing sets
• On generating all maximal independent sets
• On the maximum number of maximum independent sets
• Many cliques with few edges and bounded maximum degree
• An extension of the Win theorem: counting the number of maximum independent sets
• Independent sets in \(n\)-vertex \(k\)-chromatic \(\ell \)-connected graphs
• A simple proof of the Gan-Loh-Sudakov conjecture
• Supersaturation for subgraph counts
• Maximizing the density of \(K_t\)'s in graphs of bounded degree and clique number
• Homomorphisms into loop-threshold graphs
• Many cliques with few edges
• Many triangles with few edges
• Complete subgraphs in connected graphs and its application to spectral moment
• The maximum number of complete subgraphs of fixed size in a graph with given maximum degree
• Cliques in graphs excluding a complete graph minor
• Maximizing the Number of Nonnegative Subsets
• Extremal graphs with local covering conditions
• The max quasi-independent set Problem
• scientific article; zbMATH DE number 1305522 (Why is no real title available?)
• scientific article; zbMATH DE number 1874435 (Why is no real title available?)
• Independent sets in graphs
• Tree densities in sparse graph classes
• Many H-copies in graphs with a forbidden tree
• On independent sets in graphs with given minimum degree
• Counting independent sets of a fixed size in graphs with a given minimum degree
• Tight bounds on the coefficients of partition functions via stability
• Many \(T\) copies in \(H\)-free graphs
• Generalized Turán problems for double stars
• Maximizing the number of independent sets of fixed size in Kn‐covered graphs
• Regular Turán numbers and some Gan–Loh–Sudakov‐type problems
• Many Cliques in Bounded-Degree Hypergraphs
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• Two problems on independent sets in graphs
• Exact results on generalized Erdős-Gallai problems
• A note on the generalized Turán number of star forests
• On a conjecture of regular graphs having the minimum number of induced paths of length two
• Generalized Turán problems for small graphs
• On the generalized Turán number of star forests
• The generalized Turán number of 4S_

This page was built for publication: Maximizing the number of independent sets of a fixed size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364240)