# Discrete Math Seminar (DMS)

The **Discrete Math Seminar (DMS)** is a research seminar intended for Kennesaw State faculty working in the various
fields of algebra, number theory, and discrete math. A main goal of the seminar is
to encourage collaborative work between KSU and neighboring institutions. Seminars
often involved advanced mathematical knowledge. However, the seminars are open to
anyone who is interested in attending.

**Unless specified otherwise, seminars are held every other Monday from 2:00-3:00pm in D-249 on the Marietta Campus.*

**Upcoming Events**

**Monday, April 23, 2018**

- Jan Strydom, KSU student
*"DAGs"*- ABSTRACT: We will discuss what Directed Acyclic Graphs (DAGs) are, and some of the applications and software which make use of DAGs.

**Past Events**

***Friday, September 22, 2017* — SPECIAL TIME/LOCATION — 1:00-2:00pm in MS 006 on the Kennesaw campus**

**Axel Brandt**, Davidson College*"Optimization, Probability, and Modeling as a tool in Extremal Graph Theory"*- ABSTRACT: Similar to optimization, questions in extremal graph theory ask for a maximum or minimum of a parameter under certain constraints. Although convex programming provides a powerful tool to solve numerical optimization questions, questions in extremal graph theory have historically been approached by ingenuity and trial-and-error. Recently, Razborov developed the theory of flag algebras, which provides a method of translating an extremal graph theory problem to a semidefinite programming problem. In this talk, we will explore the process of this translation.

**Friday, October 20, 2017 - SPECIAL TIME- 1:30-2:30pm**

**Babak Moazzez**, Kennesaw State University*"Spread of Influence in Graphs via Integer Programming: A polyhedral Study"*- ABSTRACT: Spread of influence in a network can be modeled and studied within the concept of dynamic monopolies in graphs. We give an integer programming formulation for finding a minimum dynamic monopoly in an undirected graph. The corresponding 0-1 polytope and its facets are studied and several families of facet defining inequalities are introduced. Computational experiments have been performed to show the strength of the IP formulation and its facet defining inequalities.

**Monday, February 19, 2018**

**Ahmad Peivandi**, Georgia State University*"Assignment Problems with Complementarities"*- ABSTRACT: The problem of allocating bundles of indivisible objects without transfers
arises in the assignment of courses to students, of computing resources like CPU time,
memory and disk space to computing tasks and the truck loads of food to food banks.
In these settings the complementarities in preferences are small compared with the
size of the market. We exploit this to design mechanisms satisfying efficiency, envy-freeness
and asymptotic strategy-proofness.

Informally, we assume that agents do not want bundles that are too large. There will be a parameter k such that the marginal utility of any item relative to a bundle of size k or larger is zero. We call such preferences k-demand preferences. Given this parameter we show how to represent probability shares over bundles as lotteries over approximately (deterministic) feasible integer allocations. The degree of infeasibility in these integer allocations will be controlled by the parameter k. In particular, ex-post, no good is over allocated by at most k-1 units.

**Monday, March 5, 2018**

**David Clark**, Grand Valley State University*"Anti-games on Steiner Triple Systems"*- ABSTRACT: In this talk, we turn tic-tac-toe upside down and discover an interesting game hiding behind it. More specifically, we explore a combinatorial game that is inspired by a cross of tic-tac-toe, SET, and the concept of "caps" in finite geometry. In Anti-Tic-Tac-Toe, the objective of tic-tac-toe is reversed: Two players take turns selecting points and the first player to get 3 in a row loses the game. Steiner Triple Systems turn out to be a perfect place to play Anti-Tic-Tac-Toe: These are structures consisting of a set of points together with some "lines" of 3 points each, such that every pair of points appears in exactly one line — features which match traditional tic-tac-toe well. We will demonstrate winning strategies on two types of Steiner Triple Systems which have strong geometric connections. We will also see how the losing player can take advantage of substructures within these systems in order to put off their inevitable loss for as long as possible (thus removing the one endearing feature of tic-tac-toe: its brevity). These games originate from, and provide excellent opportunities for, undergraduate research.

***Monday, March 19, 2018* — SPECIAL TIME/LOCATION — 4:00-5:00pm in Wilson Student Center, Ballroom B (Marietta Campus)**

**Infinite Horizons Lecture****Kim Ruane**, Tufts University*"Linear Algebra in the Real World"*- ABSTRACT: After telling you a bit about my days at KSU and how I ended up where I
am today, I will discuss some applications of Linear Algebra that I like to cover
when I teach this class for undergraduates. The main one I will focus on is the connection
between Linear Algebra and the Page Rank Algorithm used by search engines such as
Google. There is a very simple idea behind page rank and it uses elementary ideas
from Linear Algebra and Graph Theory. Of course, the implementation of this simple
idea is much more difficult but the linear algebra behind the basic principle is something
we teach in a first year Linear Algebra course. I tend to present applications of
linear algebra as soon as I start to see the students freaking out over the abstraction
they are faced with in the course!