Loading Events

« All Events

  • This event has passed.

Stijn Cambie, The 69-conjecture and more surprises on the number of independent sets

Wednesday, December 28, 2022 @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)


Stijn Cambie
IBS Extremal Combinatorics and Probability Group

Various types of independent sets have been studied for decades. As an example, the minimum number of maximal independent sets in a connected graph of given order is easy to determine (hint; the answer is written in the stars). When considering this question for twin-free graphs, it becomes less trivial and one discovers some surprising behaviour. The minimum number of maximal independent sets turns out to be;

  • logarithmic in the number of vertices for arbitrary graphs,
  • linear for bipartite graphs
  • and exponential for trees.

Finally, we also have a sneak peek on the 69-conjecture, part of an unpublished work on an inverse problem on the number of independent sets.

In this talk, we will focus on the basic concepts, the intuition behind the statements and sketch some proof ideas.

The talk is based on joint work with Stephan Wagner, with the main chunk being available at arXiv:2211.04357.


Wednesday, December 28, 2022
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B332
IBS (기초과학연구원) + Google Map


Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.