Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-02-11T21:41:48.194Z Has data issue: false hasContentIssue false
  • English
  • Français

Maximizing the Number of Independent Sets of a Fixed Size

Published online by Cambridge University Press:  14 October 2014

WENYING GAN ,
PO-SHEN LOH  and
BENNY SUDAKOV
WENYING GAN
Affiliation:
Department of Mathematics, ETH, 8092 Zurich, Switzerland (e-mail: ganw@math.ethz.ch, benjamin.sudakov@math.ethz.ch)
PO-SHEN LOH
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA (e-mail: ploh@cmu.edu)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, ETH, 8092 Zurich, Switzerland (e-mail: ganw@math.ethz.ch, benjamin.sudakov@math.ethz.ch)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let it(G) be the number of independent sets of size t in a graph G. Engbers and Galvin asked how large it(G) could be in graphs with minimum degree at least δ. They further conjectured that when n ⩾ 2δ and t ⩾ 3, it(G) is maximized by the complete bipartite graph Kδ,n−δ. This conjecture has recently drawn the attention of many researchers. In this short note, we prove this conjecture.

Keywords

Primary 05C69Secondary 05D99
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Issue 3 , May 2015 , pp. 521 - 527
Copyright
Copyright © Cambridge University Press 2014 

References

[1]Alexander, J., Cutler, J. and Mink, T. (2012) Independent sets in graphs with given minimum degree. Electron. J. Combin. 19 P37.CrossRefGoogle Scholar
[2]Alexander, J. and Mink, T. (2013) A new method for enumerating independent sets of a fixed size in general graphs. arXiv:1308.3242Google Scholar
[3]Cutler, J. and Radcliffe, A. J. (2013) The maximum number of complete subgraphs in a graph with given maximum degree. J. Combin. Theory Ser. B 104 60–71.Google Scholar
[4]Engbers, J. and Galvin, D. (2014) Counting independent sets of a fixed size in graphs with a given minimum degree. J. Graph Theory 76 149–168.CrossRefGoogle Scholar
[5]Galvin, D. (2011) Two problems on independent sets in graphs. Discrete Math. 311 2105–2112.CrossRefGoogle Scholar
[6]Kahn, J. (2001) An entropy approach to the hard-core model on bipartite graphs. Combin. Probab. Comput. 10 219–237.CrossRefGoogle Scholar
[7]Katona, G. (1968) A theorem of finite sets. In Theory of Graphs: Proc. Colloq., Tihhany, 1966, Academic Press, pp. 187–207.Google Scholar
[8]Kruskal, J. B. (1964) The number of simplices in a complex. In Mathematical Optimization Techniques (Bellman, R., ed.), University of California Press, pp. 251–278.Google Scholar
[9]Law, H. and McDiarmid, C. (2013) On independent sets in graphs with given minimum degree. Combin. Probab. Comput. 22 874–884.Google Scholar
[10]Lovász, L. (2007) Combinatorial Problems and Exercises, AMS.Google Scholar
[11]Sauvé, I. L. (1961) On chromatic graphs. Amer. Math. Monthly 68 107–111.Google Scholar
[12]Zhao, Y. (2010) The number of independent sets in a regular graph. Combin. Probab. Comput. 19 109–112.CrossRefGoogle Scholar