Maximizing the Number of Independent Sets of a Fixed Size

DOI10.1017/S0963548314000546zbMath1371.05213arXiv1311.4147OpenAlexW3105673126MaRDI QIDQ5364240

Po-Shen Loh, Wenying Gan, Benjamin 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)

Related Items (22)

Tree densities in sparse graph classes ⋮ Cliques in graphs excluding a complete graph minor ⋮ Complete subgraphs in connected graphs and its application to spectral moment ⋮ Maximizing the density of \(K_t\)'s in graphs of bounded degree and clique number ⋮ Homomorphisms into loop-threshold graphs ⋮ Generalized Turán problems for double stars ⋮ Maximizing the number of independent sets of fixed size in Kn‐covered graphs ⋮ Many triangles with few edges ⋮ Regular Turán numbers and some Gan–Loh–Sudakov‐type problems ⋮ The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree ⋮ Many Cliques in Bounded-Degree Hypergraphs ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Many cliques with few edges ⋮ Extremal Graphs with Local Covering Conditions ⋮ Independent sets in graphs ⋮ Many cliques with few edges and bounded maximum degree ⋮ Tight bounds on the coefficients of partition functions via stability ⋮ Independent sets in \(n\)-vertex \(k\)-chromatic \(\ell \)-connected graphs ⋮ Many H-Copies in Graphs with a Forbidden Tree ⋮ Many \(T\) copies in \(H\)-free graphs ⋮ A simple proof of the Gan-Loh-Sudakov conjecture ⋮ Supersaturation for subgraph counts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independent sets in graphs with given minimum degree
• Two problems on independent sets in graphs
• The maximum number of complete subgraphs in a graph with given maximum degree
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• On Chromatic Graphs
• A New Method for Enumerating Independent Sets of a Fixed Size in General Graphs
• On Independent Sets in Graphs with Given Minimum Degree
• Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree

This page was built for publication: Maximizing the Number of Independent Sets of a Fixed Size