Bookmark and Share

Discrete Mathematics Seminar

Spring 2017 - In Lytle 203, unless otherwise noted

Thursday, May 4, at 3pm - Dr. Janet Fierson and Mr. Eric Frazier, La Salle University

"An interdisciplinary investigation of coloring graphs"

Working in the area of chromatic graph theory, we introduce the concept of the coloring graph and share discoveries about its properties. Originally applied to vertex coloring and edge coloring only, this idea has recently been applied to rainbow connection, another relatively new topic. We provide details of our findings, with a particular emphasis on the usefulness of incorporating computer programming into the research process.  

Friday, April 28, at 11am - Ms. Amanda Lohss, Drexel University Ph.D. Candidate

"Tableaux and the Asymmetric Simple Exclusion Process (ASEP)"

Combinatorics is an amazing area of mathematics in which seemly simple objects are surprisingly rich in applications. Tableaux are such combinatorical objects which are as simple to define as the rules for Sudoku (and actually quite similar). Several variations of tableaux have recently been introduced due to connections with an important particle model, the Asymmetric Simple Exclusion Process (ASEP), which has been said to be the default model for transport phenomenon and is used extensively in physics, biology, and biochemistry. This connection allows various questions about the ASEP to be translated in terms of tableaux and proven in a mathematically elegant way. This talk will discuss the surprising relationship between tableaux and the ASEP as well as some results on tableaux which solve previous conjectures significant in terms of the ASEP.  

Thursday, April 6, at 3pm - Dr. Brittany Shelton, Albright College

"On God's Number(s) for Rubik's Slide"

Rubik's Slide is a puzzle which consists of a 3 x 3 grid of squares that is reminiscent of a face of the well-known cube. Each square may be lit one of two colors or remain unlit. The goal is to use a series of moves, which we view as permutations, to change a given initial arrangement to a given final arrangement. Each play of the game has different initial and final arrangements. To examine the puzzle, we use a simpler 2 x 2 version of the puzzle to introduce a graph-theoretic approach, which views the set of all possible puzzle positions as the vertices of a (Cayley) graph. For the easy setting of the puzzle, the size of the graph depends on the initial coloring of the grid. We determine the size of the graph for all possible arrangements of play and determine the associated god's number (the most moves needed to solve the puzzle from any arrangement in the graph).

We provide a Hamiltonian path through the graph of all puzzle arrangements that describes a sequence of moves that will solve the easy puzzle for any initial and final arrangements. Further, we use a computer program to determine an upper bound for god's number associated to the graph representing the medium and hard versions of the puzzle. This is joint work with Michael A. Jones, Mathematical Reviews, Ann Arbor MI and Miriam Weaverdyck, Bethel College, North Newton KS.  

Friday, March 31 at 3pm - Dr. James Hammer, Cedar Crest College

"Embedding Complete Multipartite Graphs into Smallest Dimension"

For a finite, simple graph G, define G to be of dimension d if d is the minimum value such that G can be drawn with vertices being points of R_d, where adjacent vertices are necessarily placed a unit distance apart. We determine the dimension of all complete multipartite graphs. Letting G be a complete multipartite graph with n parts, m of which have size one or two, our main result is that G is of dimension 2n - m - 1 when all parts or all but one part of G has size one, and G is of dimension 2n - m otherwise.  

Thursday, March 23 at 11am (Lytle 136) - Ms. Shannon Golden, KU Math Major

"Coloring the Integers"

We will assign each natural number to be one of two colors (RED or BLUE). The condition is that when the equation x+y=z is monochromatic, meaning that x, y and z are all the same color, we stop. By generalizing the equation with a coefficient w to (w)x+y=z, we will explore a theorem for the color assignments that allow us to color the most numbers. In the second part of the talk, we will turn this coloring into a two person game. Starting at 1, players alternate assigning colors. In order to win, the opponent must not be able to assign their number to be either color.  

Tuesday, March 7 at 4:30pm - Dr. Ferdinand Ihringer, University of Regina

"Intriguing Sets in Quadrangles, Hexagons and Octagons"

A generalized quadrangle (GQ) of order (s;t) consists of a set of points P and a set of lines L such that each line contains exactly s+1 points and each point lies in exactly t+1 lines. The point graph of a GQ is strongly regular. We limit ourselves to classical GQs, which are closely related to orthogonal, symplectic and unitary groups.

In the first part of the talk, we will discuss bounds for the independence number of the point graphs of GQs. In the second part, we will present some results on the existence of intriguing sets, a natural generalization of Delsartes cliques and Delsartes cocliques, in GQs. In the third part, we will present similar results for generalized hexagons and generalized octagons.  

Thursday, March 2 at 3pm - Dr. Barry Smith, Lebanon Valley College

"Necklace invariants: tools for analyzing class groups "

Gauss created a binary operation on classes of binary quadratic forms, and through a computational ๐‘ก๐‘œ๐‘ข๐‘Ÿ ๐‘‘๐‘’ ๐‘“๐‘œ๐‘Ÿ๐‘๐‘’, he showed that the classes form an abelian group. Class groups have dominated the field of algebraic number theory ever since. I will describe how to attach combinatorial necklaces to classes of indefinite binary quadratic forms and how to use these necklace invariants to obtain results about class groups. 

Friday, February 17 at 11am - Dr. Joshua Harrington, Cedar Crest College

"Fields Containing Consecutive Elements of Order n"

Given a positive integer n, we study conditions under which a finite field of prime order will contain consecutive elements of order n. A curious connection to the Lucas Numbers and Mersenne numbers will be discussed.  

Friday, February 5 at 11am - Dr. Brian Kronenthal

"REUs and ADGs"

Undergraduates can do research in math, and you don’t even have to be a junior or senior. In fact, some research programs specifically target students who are just finishing their freshman or sophomore years. In this talk, I will briefly describe the National Science Foundation’s Research Experiences for Undergraduates (REU) program, as well as explain an REU project that I will be supervising this summer at Lafayette College on Algebraically Defined Graphs (ADGs). I encourage any interested Kutztown students to apply for this project (especially students who have taken Abstract Algebra or Number Theory), as well as other REU programs of interest.  

Friday, January 27 at 11am - organizational meeting

Fall 2016 - Fridays at 11:00 a.m. in Lytle 136, unless otherwise noted

Friday, November 11 at 3pm - Mr. Zach Kern, KU Math Major

"An empirical analysis of three population-based metaheuristics for solving the multidimensional knapsack problem"

The Multidimensional Knapsack Problem (MKP) is a computationally complex (NP-hard) combinatorial optimization problem with many real-world applications. In this study, we adapt two relatively new metaheuristics designed originally to solve continuous nonlinear problems to solve the binary Multidimensional Knapsack Problem. Specifically, we adapt the two-phase Teaching-Learning Based Optimization (TLBO) approach developed by Rao, Savsani and Vakharia (2011) and the recently introduced metaheuristic JAYA by Rao (2016) both designed for continuous nonlinear optimization problems to solve the binary MKP. Where other metaheuristics require parameter fine-tuning, TLBO and JAYA both only require determining population size and termination criteria—same as all other population-based metaheuristics. Using 270 test problems available in Beasley’s OR-Library, empirical results for TLBO and JAYA are compared to a well-known genetic algorithm (GA) approach to demonstrate the competitiveness of TLBO and JAYA for solving the MKP. The advantage of the TLBO and JAYA approaches are their relative simplicity.  

Friday, November 4 - Mr. Diego Manzano-Ruiz, KU Math Major

"Vertex Coloring Game on Graphs"

This project focuses on a game related to combinatorics and graph theory. In this game, two players, Alice and Bob, color a vertex of a given graph by alternating turns: Alice uses color A and Bob uses color B. The only rule is that once a vertex is colored, no neighbors of that vertex can receive the same color. The first player who is unable to color a vertex loses the game. We determine which player has a winning strategy on several particular types of graphs, such as paths, cycles, and certain grids. We are also able to answer some questions for general graphs.  

Friday, October 14 at 3pm - Dr. Oskars Rieksts and Mr. Andrew Wernicki, KU Department of Computer Science and Information Technology

"Generic Prime Collatz – an extension and a restriction of Collatz "

The Collatz "3n+1" Conjecture states that if you pick any positive integer n, divide it by 2 if n is even, replace it with 3n+1 if it is odd, and repeat that process over and over, that eventually you will end up in the cycle 4, 2, 1, 4, 2, 1, .... Try it! The goal of this talk will be to explore ways to generalize the familiar Collatz function by looking at integers other than 3 to serve in the role of “multiplier”. Observing that 2 and 3, the two operative values in traditional Collatz, are the first two primes, one approach would be to extend Collatz by allowing any prime to serve as multiplier. The question, then, is – can generalizing be done in such a way as to create the peculiar behavior of Collatz?  

Friday, October 7

"Graph Theoretic Games"

Let's have fun understanding some graph-theoretic games connected to NP-hard problems. You do not have to know what NP-hard means to enjoy this meeting; the games will be fun and interesting!  

Friday, September 30 in Lytle 215 - Dr. Brian Kronenthal

"An Introduction to Magma"

Magma is a useful (and powerful!) computer algebra software package that is especially designed to perform tasks related to algebra, number theory, and related mathematical fields. Magma is available to all Kutztown students and faculty to use for free! In this talk, I will demonstrate (and give participants the opportunity to try) a few of Magma's many interesting features.  

Friday, September 23

"Problem Session II"

Friday, September 16 in Lytle 120

"Problem Session"

This week, we are going to have our traditional "problem session" meeting to kick off the seminar. Anyone is welcome to spend a fraction of the meeting describing an interesting problem that they are working on or would like to work on, possibly in collaboration with others. We will also have an "organizational" time in which we get ideas for topics for discussion in subsequent meetings, solicit volunteers to give a talk, and get ideas for people to invite to give a talk.  

Spring 2016 - Fridays at 11:00 a.m. in Lytle 203, unless otherwise noted

Friday, April 29 - Dr. Eric Landquist

"The Mathematics of Voting Theory"

Voting theory sounds simple enough, but there is quite a lot of deep mathematics there and some rather surprising results. I'll give an example to show that depending on the voting method used in the 2008 Presidential election, either Obama (D), McCain (R), or Barr (L) could have ended up with the electoral votes for Indiana. We'll discuss various voting methods and the philosophies and psychology behind them. The intent is not to debate politics, but to show how mathematics impacts and explains society.  

Friday, April 8 - Professor John Botzum

"It Does Matter How You Slice It: The Combinatorics of Pizza-Slicing"

Mathematics students are urged to recognize patterns and form general conclusions. However, Students of elementary mathematics are cautioned against assuming that conjectures formed inductively are necessarily true in the general case. A classic example of a reasonable conjecture that is false arises in the solution of the following problem : What is the maximum number of regions formed by pairwise connections of n points on the circle? We will employ elementary counting methods to solve this problem and more general problems.  

Friday, April 1 - Dr. Reinier Bröker, Brown University

"Constructing elliptic curves of prescribed order"

Elliptic curves have become increasingly important during the last 30 years, and made the front page of The New York Times for playing a key role in Wiles’ proof of Fermat’s last theorem. In this talk I will give an introduction to elliptic curves, and consider the problem of constructing an elliptic curve with a given number of points. Many examples will be given.  

Friday, March 25 at 3:00 p.m. - Dr. Gene Fiorini, Muhlenberg College

"Measuring Robustness of the Hudson River Food Web and Symmetric Class-0 Subgraphs"

Competition graphs and graph pebbling are two examples of graph theoretical-type games played on a graph under well-defined conditions. In the case of graph pebbling, the pebbling number pi(G) of a graph G is the minimum number of pebbles necessary to guarantee that, regardless of distribution of pebbles and regardless of the target vertex, there exists a sequence of pebbling moves that results in placing a pebble on the target vertex. A class-0 graph is one in which the pebbling number is the order of the graph, pi(G)=|V(G)|. This talk will consider under what conditions the edge set of a graph G can be partitioned into k class-0 subgraphs, k a positive integer. Furthermore, suppose D is a simple digraph with vertex set V(D) and edge set E(D). The competition graph G(V(G),E(G)) of D is defined as a graph with vertex set V(G)=V(D) and edge vw in E(G) if and only if for some vertex u in V, there exist directed edges (u,v) and (u,w) in E(D). This talk will present some recent results applying the competition graph concept of connectance to measure food web robustness.  

Friday, March 18 - Dr. Ju Zhou

"Integer Flows of Graphs and Graph Coloring - Part 2"

Friday, February 26 - Problem Session

Potential research problems for undergraduates!

Thursday, February 18 - Problem Session

Potential research problems for undergraduates!

Friday, February 5 - Dr. Ju Zhou

"Integer Flows of Graphs and Graph Coloring - Part 1"

In mathematics, the goals of researchers are to obtain new results and prove their correctness, create simple proofs for already established results, discover or create connections between different fields, construct and solve mathematical models for real world problems, and so on. In this talk, Dr. Zhou will talk about map coloring, integer flows, and group connectivity and their relationships. Also she will talk about some of the well-known conjectures and recent progress in each field. 

Friday, January 29 - Organizational meeting

Anyone who would like to speak is welcome to give a talk, students and faculty alike. Feel free to suggest topics to discuss or learn about, articles to read and discuss, etc.


Fall 2015 - Thursday or Friday at 11:00 a.m. in Lytle 136

Friday, November 20 - Dr. Fran Vasko

"Gurobi optimization software"

Dr. Vasko will tell us about an interesting talk he attended at Lehigh University about Gurobi optimization software.

Friday, October 30 - Math Movie!

"N is a number"

We will watch this film about legendary mathematician Paul Erdös!

Thursday, October 22 - Ms. Jiao Xu, Kutztown Mathematics Major

"Coinbinatorics"

We will discuss an interesting coin-flipping game with a combinatorial flavor and a surprising result!

Friday, October 16 - Dr. Amy Lu

"The Teaching-Learning-Based Optimization Metaheuristic for Discrete Combinatorial Optimization Problems"

The Teaching-Learning-Based Optimization (TLBO) metaheuristic requires no parameter fine-tuning other than determining the population size and convergence criteria. In this paper, we enhance the performance of the TLBO method by introducing "a local neighborhood search on the best solution" before the teaching phase of TLBO. We use it to solve the problems from the literature for multiple-choice multidimensional knapsack problem (MMKP), and demonstrate that TLBO outperforms the best published solution approaches for the MMKP.

Thursday, September 24 - Dr. Brian Kronenthal

"An Immensely Interesting Integer Sequence"

Can you fill in the blanks in the following sequence of integers? No internet please!  

2, 6, 8, 10, 32, 84, 128, 186, _____, _____, 2048, 3172, 8192, 19816, ...  

In this talk, we will explain where this sequence comes from, along the way discussing some special polynomials and introducing you to incidence geometry (generalized quadrangles in particular) and algebraically defined graphs.  Don't worry, we will also fill in the blanks and give a formula to calculate every term of the sequence!

Friday, September 4 and Friday, September 11 - Faculty presentations

Ideas for student research, projects, and independent studies.

Friday, August 28 - Organizational meeting


Spring 2015 - Alternating Thursdays and Fridays at 11:00 a.m. in Lytle 203

May 1 - Wrap-up and plans for next semester

April 23 - Dr. Rajeev Kumar, College of Business

"A Smart Market of Personal Information."   

April 17 - Still more discussion on the graceful labeling problem!

April 10 (Lytle 226) - Kenneth Zyma (Masters Thesis Defense)

"Solving Medium-Scale Instances of the Cable-Trench Problem Applied to the Proposed LOFAR Super Station in Nancay France."

April 2 - Even more discussion on the graceful labeling problem.

March 27 - More discussion on the graceful labeling problem.

March 19 - The second half of the movie, "Counting from Infinity: Yitang Zhang and the Twin Primes Conjecture." 

March 6 - The first half of the movie, "Counting from Infinity: Yitang Zhang and the Twin Primes Conjecture." 

March 5 - Review of a proof that all binary trees can be labeled gracefully.

February 26 - Dr. Amy Lu

"Adapting the Teaching-Learning-Based Optimization Metaheuristic to the Weighted Set Covering Problem."

February 20 - The Graceful Labeling Problem (continued!)

February 12 - The Graceful Labeling Problem

February 6 - The Graceful Labeling Problem and the k-Equitable Labeling Problem

January 29 - k-equitable tree labelings and graceful labeling of trees

January 23 - Organizational meeting


Fall 2014 - Friday at 11:00 a.m. in Lytle 203

November 20 - Dr. Greg Schaper, Computer Science

"A Model of Computation for Teaching and Learning C++."

November 14 - Dr. Ge Xia, Department of Computer Science at Lafayette College

"The Stretch Factor of the Delaunay Triangulation is less than 1.998 ."

November 7 - Fixed-Parameter Tractable algorithms

October 31 - Dr. Yong Zhang, Computer Science

"Introduction to parametrized algorithms and complexity."

October 24 (Lytle 108) - Fun problem session

October 17 - Adib Farah, Computer Science

"Introduction to Big Data"

October 10 - Open Mic

October 3 - Problem-Solving Session

September 26 - Problem-Solving Session

September 19 - Dr. Eric Landquist

"Making Cryptanalysis Less Cryptic and Fried Eggs on Friday: Cracking early versions of the UberCrypt stream cipher"

In this talk, I'll give a quick overview of last week's talk and then poke around with pseudorandom number generators as a way of practically implementing a one-time pad, the only cryptosystem with perfect security. This provides the motivation for the stream cipher UberCrypt, developed by Mr. Joe Chiarella of Colloid, LLC, based in the Harrisburg area. UberCrypt aims to create a cryptographically secure pseudorandom number generator in order to provide perfect security. I'll describe the essential components of UberCrypt and show how one can crack earlier versions of the cipher via a chosen plaintext attack. The approach uses linear algebra with slightly more sophistication than you would see in a high school algebra course (the only difference is that all arithmetic is performed modulo 2, that is, over the binary field {0, 1}). The current version of UberCrypt has not been cracked as of the writing of this abstract, and so remains an open problem.

September 12 - Dr. Eric Landquist

"Making Cryptography Less Cryptic"

In this talk, I will give an overview of cryptography and go over enough mathematical background to help everyone follow next week's talk on how to crack a stream cipher. We'll talk about private key versus public key cryptography, but will focus on different kinds of private key cryptosystems. We'll then get into different kinds of attacks on a cryptosystem and the attributes of a secure cipher.


Spring 2014 - Friday at 11:00 a.m. in Lytle 136

April 25 - Professor John Botzum

"Don't Stand So Close to Me or: How I Learned to Stop Worrying and Love the Twin Prime Conjecture"

Number theory -- the most easily accessible, but possibly the least penetrable of branches of mathematics has intrigued professional and amateur mathematicians for centuries. In honor of the monumental paper published by Yiteng Zhang last April 17th, I will present an introduction to the Twin Prime Conjecture and discuss Zhang's work and the work of Polymath 8a, an international group of renowned mathematicians led by Terrence Tao.

April 14 - Combinatorical Problems (continued)

April 11 - Combinatorical Problems

  1. The Cable-Trench Problem
  2. Analyze the game Flow Free - For a board of a given size and a given number of dots, how many different games are there? How many give you a unique solution or no solution?

April 4 - Dr. Greg Schaper

Problem-Solving Processes

The key to success isn't knowing what to think, but knowing how to think.  Dr. Schaper will give an overview of the process that he uses to solve problems and how different brances of Math, Computer Science, and other disciplines factor into this problem-solving process.

March 28 - Dr. Fran Vasko

Dr. Vasko will explain how he has applied the matching problem in graph theory to the problem of determining optimal cuts of rectangular pieces of stock.  This work was successfully implemented for Bethlehem Steel and published the Journal of the Operational Research Society in 2000.

March 14 - Bitcoin Part 4

Computer Science undergraduates discuss cryptocurrency.

March 7 - Bitcoin Part 3

Hacks of the Online Cryptocurrency Exchange Mt. Gox

February 28 - Bitcoin Part 2

February 19 (Wednesday) - Dr. Brian Kronenthal

"Two Perspectives on Generalized Quadrangles"

February 7 - Bitcoin

Bitcoin is a decentralized digital currency whose security relies on various cryptographic protocols and mathematically and computationally hard problems.  It is a fascinating protocol in many regards.


Fall 2013 - Alternating Thursdays and Fridays at 11:00 a.m. in Lytle 109

December 6- Dr. Amy Lu

"Homogeneous structures and their reducts."

November 22- Dr. Tony Wong

"A problem on matroid theory by Dominic Welsh."

November 14- Dr. Joshua Goodson

"Orbits of an Action Involving Extra-special Groups."

November 8- Dr. Eric Landquist

"The Hunt for Primes and Perfection and How You Can Win $3000."

October 31 - Dr. Greg Schaper, Computer Science

"Conjecture: (P = NP) and (P ≠ NP)."

October 24 - Dr. Ju Zhou

"Pancyclicity of Claw-free Graphs."

October 11 - More interesting problems in discrete mathematics

October 3 - Dr. Tony Wong

"Some interesting problems in combinatorics."

September 26 - Dr. Brian Kronenthal

"Generalized quadrangles, algebraically defined graphs, and permutation polynomials: an introduction."

September 19- Faculty presentations of interesting discrete mathematics (research?) problems

September 12- Dr. Eric Landquist

"What is Discrete Math? Making Discrete Math Less Discreet!"