Department of

# Mathematics

Seminar Calendar
for events the day of Wednesday, February 20, 2019.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
     January 2019          February 2019            March 2019
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1  2  3  4  5                   1  2                   1  2
6  7  8  9 10 11 12    3  4  5  6  7  8  9    3  4  5  6  7  8  9
13 14 15 16 17 18 19   10 11 12 13 14 15 16   10 11 12 13 14 15 16
20 21 22 23 24 25 26   17 18 19 20 21 22 23   17 18 19 20 21 22 23
27 28 29 30 31         24 25 26 27 28         24 25 26 27 28 29 30
31


Wednesday, February 20, 2019

4:00 pm in 245 Altgeld Hall,Wednesday, February 20, 2019

#### Connecting Boolean (un)satisfiability to Graph Theory

###### Vaibhav Karve (Illinois Math)

Abstract: Given a Boolean formula can we find consistent assignments (True or False)for variables such that the formula is satisfied? This is the Boolean Satisfiability problem, a problem of great historic value in computer science. It is the first problem that was proven to be NP-complete. In this talk, I will introduce Satisfiability and explain what the terms P, NP, NP-complete... mean. I will then demonstrate a (surprising)connection between Boolean formulas and graph theory which will help us gain a more visual understanding of when a class of formulas is satisfiable or unsatisfiable. There will be lots of small graphs in this talk.