Discrete Math Seminar

Name: Stijn Cambie, The 69-conjecture and more surprises on the number of independent sets
Start: 2022-12-28T16:30:00+09:00
End: 2022-12-28T17:30:00+09:00
Location: Room B332

S	M	T	W	T	F	S
				0 events 1 0 events, 1	0 events 2 0 events, 2	0 events 3 0 events, 3
0 events 4 0 events, 4	0 events 5 0 events, 5	1 event 6 1 event, 6 4:30 PM - 5:30 PM Giannos Stamoulis, Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes Tuesday, December 6, 2022 @ 4:30 PM - 5:30 PM KST Giannos Stamoulis, Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes The disjoint paths logic, FOL+DP, is an extension of First Order Logic (FOL) with the extra atomic predicate $\mathsf{dp}_k(x_1,y_1,\ldots,x_k,y_k),$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i,$ for $i\in \{1,\ldots, k\}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every … Continue Reading	0 events 7 0 events, 7	0 events 8 0 events, 8	0 events 9 0 events, 9	0 events 10 0 events, 10
0 events 11 0 events, 11	0 events 12 0 events, 12	0 events 13 0 events, 13	0 events 14 0 events, 14	0 events 15 0 events, 15	0 events 16 0 events, 16	0 events 17 0 events, 17
0 events 18 0 events, 18	0 events 19 0 events, 19	0 events 20 0 events, 20	0 events 21 0 events, 21	0 events 22 0 events, 22	0 events 23 0 events, 23	0 events 24 0 events, 24
0 events 25 0 events, 25	0 events 26 0 events, 26	0 events 27 0 events, 27	1 event 28 1 event, 28 4:30 PM - 5:30 PM 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 Stijn Cambie, The 69-conjecture and more surprises on the number of independent sets 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 … Continue Reading	0 events 29 0 events, 29	0 events 30 0 events, 30	0 events 31 0 events, 31