Discrete Applied Math Seminar, Fall 2013
DEPARTMENT OF APPLIED MATHEMATICS 
Date & Time  Location  Speaker/Title 
Wednesday, Sept 4, 1:50 pm 
E1 102 
Robert Ellis, IIT Applied Math
Introduction to group testing design matrices The point of group testing is to reduce the cost of finding defective items in a population by testing pools if items rather than testing each item one at a time. In the basic group testing model, we have a population of items of which a small number is defective. We wish to identify the subset of defective items, and are allowed to test pools (subsets) from the population, with a positive test outcome if and only if the pool tested contains a defective item. We define separable and disjunct matrices, give various examples and tables of good matrices for small parameters, and describe two recent constructions of the speaker and G. Balint for producing new matrices from old. 
Monday, Sept 9, 4:40 pm 
LS 152 
Mustafa Bilgic, IIT Computer Science
Active Learning: Past, Present, and Future Applied Mathematics Colloquium A fundamental task of machine learning is prediction, where a model is built using existing inputoutput pairs, and then it is applied to future instances where the input is known but output is not. Examples include spam detection, sentiment analysis, and movie recommendation. Constructing enough training data for predictive models is a tedious and costly process where expert and user feedback is needed: emails need to be classified as spam/ham, phrases in reviews need to be tagged as positive/negative, and movies need to be rated. Active learning is the subfield of machine learning that aims to train an accurate model with minimal expert and user feedback. Active learning has been studied in the past two decades and many methods have been developed. In this talk, I will provide a survey of the mostfrequently utilized active learning strategies. In addition to providing theoretical background, I will discuss results of an extensive empirical study highlighting strengths and weaknesses of these strategies. I will conclude with current and future research trends with an example applied to homophilic networks. 
Friday, Sept 13, 1:50 pm 
E1 119 
Dan Cranston, Virginia Commonwealth University
Graphs with χ = Δ have Big Cliques Let G be a graph with maximum degree Δ≥3. Brooks' Theorem says that if G has chromatic number Δ+1, then G has a clique on Δ+1 vertices; otherwise G has chromatic number at most Δ. In 1977 Borodin and Kostochka conjectured that if G is a graph with maximum degree Δ≥9 and chromatic number Δ, then G has a clique on Δ vertices. For maximum degree Δ≥13, we prove that if G has chromatic number Δ, then G has a clique on at least Δ3 vertices. This is joint work with Landon Rabern. 
Wednesday, Sept 18, 1:50 pm 
E1 102 
Despina Stasi, IIT Applied Math
Hydra Number of Graphs In this talk we define and discuss the hydra number, a graph parameter arising from an optimization problem for Horn formulas in propositional logic. The hydra number of a graph G=(V,E) is the minimal number of hyperarcs of the form u,v→w required in a directed hypergraph H=(V,F), such that, for every pair (u,v), the set of vertices reachable in H from {u,v} is the entire vertex set V if (u,v) is an edge in E, and it is only the vertices themselves otherwise. Here reachability is defined by the standard forward chaining or marking algorithm. We give various bounds for the hydra number and discuss its connection to the path cover number of the line graph L(G), and to the total interval number of a graph. We will define the relevant notions of Horn formulas, directed hypergraphs, and graph theoretical notions that we use. This talk is based on joint work with Gyorgy Turan and Robert H. Sloan. 
Wednesday, Sept 25, 1:15pm2:05pm 
SB 106 
Gergely (Greg) Balint, IIT Applied Math
NonAdaptive Group Testing Group testing is a well researched and practically important topic (e.g. in biological research). The basic idea of group testing is to perfectly identify a small portion of 'special' elements in a large(r) population (e.g. defective genes). The beauty of the topic is partially due to the many different constraints that can come up from actual (practical) constraints. In our exam representation we will talk about both asymptotical and practical important results in the area, touching known construction methods. These results spin through a wide variety of techniqies and fields, from entropy based arguments through combinatorics and number theory. Finally we will talk about our results with Professor Robert Ellis and planned future work. (This talk is part of Gergely's comprehensive exam for a Ph.D. The first 50 minutes are open to the IIT community.) 
Tuesday, October 1, 3:15pm4:05pm 
TBA 
Jonathan Beagley, Valparaiso University
Convex Geometries and The Copoint Graph We introduce abstract convex geometries. Much as matroids can be thought of as "discrete vector spaces", convex geometries are "discrete convex hulls". There are specific convex sets of particular importance, called copoints. In 2006, Morris introduced a graph on the copoints where the cliques in this graph correspond to convexly independent sets in the convex geometry. We discuss results related to the chromatic number of this graph, both generally, and for planar point sets in general position. 
Wednesday, Oct 16, 1:50 pm 
E1 102 
F.R. McMorris, IIT and University of Louisville
Location Functions on Trees and Beyond: A Short Survey and Some Recent Results Let G =(V,E) be a finite connected graph and π a ktuple in V. Think of k customers, each one reporting a most preferred vertex. Location and consensus theory often involves finding the set of vertices x, for which D(x,π) is minimum, where D(x,π) is some measure of the "remoteness" of x to π. Finding these vertices is thus an optimization problem, and the OR folks have produced many nice algorithmic approaches. But what properties does an exact algorithm have when considered abstractly as a function? Perhaps some counterintuitive things are going on—or perhaps not, and the function can be shown to satisfy a list of desired axioms. A function that returns, for any π, the set of vertices minimizing D is called a (distancebased) location function and the problem of characterizing various functions of this type has been a challenge for more than 25 years. In this talk a survey of some old and new results is presented, while focusing on the case where G is a tree or, more generally, a median graph. I will discuss functions based on three examples of D that are popular in the location theory literature. If time and interest permits, I will also discuss some recent results on the notion of "strategyproof" location functions, which are those for which it is impossible for any customer "j" to favorably manipulate the results by reporting vertices that are suboptimal from "j's" pointofview. 
Wednesday, Oct 23, 1:50 pm 
(CANCELLED)
TBA 

Wednesday, Oct 24, 4:40 pm 
LS 152 
Jesus De Loera,
Department of Mathematics
University of California Davis
Algebraic and Geometric Ideas in Linear Optimization Applied Mathematics Colloquium Linear programming is undeniably a central software tool of applied mathematics and a source of many fascinating mathematical problems. In this talk I will present several advances from the past 5 years in the theory of algorithms in linear optimization. These results include new results on the complexity of the simplex method, the structure of central paths of interior point methods, and about the geometry of some less wellknown iterative techniques. One interesting feature of these advances is that they connect this very applied algorithmic field with topics that are often not thought as applied such as algebraic geometry and combinatorial topology. 
Wednesday, Oct 30, 1:50 pm 
E1 102 
Marcus Schaefer, DePaul University
Planarities and HananiTutte The beautiful (and old) HananiTutte theorem states that a graph is planar if and only if it can be drawn so that any pair of independent edges crosses an even number of times. One of the many results which witness that planarity of a graph is wellunderstood. However, many variants of planarity have been defined for applications: there are cplanarity, simultaneous planarity, stripplanarity, levelplanarity, radial planarity, and the list doesn't end here. Most of these planarity variants we do not yet understand very well, theoretically or practically (algorithmically). In this talk we review if and how the HananiTutte characterization of planarity can shed new light on planarity variants. HananiTutte style characterizations are very algebraic and lend themselves to implementations. This leads to an algorithm that can solve many (if not all) of the planarity problems mentioned above. 
Wednesday, Date:TBA, 1:50 pm 
E1 102 
Gruia Calinescu, IIT Computer Science
Relay placement for twoconnectivity Motivated by applications to wireless sensor networks, we study the following problem. We are given a set S of wireless sensor nodes, given as a multiset of points in the twodimensional plane. We must place a minimumsize (multi)set Q of wireless relay nodes in the two dimensional plane such that the unitdisk graph induced by the union of S and Q is twoconnected. The unitdisk graph of a set of points has an edge between two points if their Euclidean distance is at most 1. In Infocom 2006, Kashyap, Khuller, and Shayman present two algorithms, both with approximation ratio of 10 for the two variants of the problem: twoedgeconnectivity and biconnectivity. We use variants of the same algorithms, with improved analysis, to obtain approximation ratios of 9 for twoedgeconnectivity, and 5 for biconnectivity respectively. 
Spring 2014 plans 


Thursday, February 6 
Ameera Chowdhury, Carnegie Mellon University
A Proof of the ManickamMiklósSinghi Conjecture for Vector Spaces 

Date TBA 
F.R. McMorris, IIT and University of Louisville
(1) Sphereofattraction graphs: what we know and what we would like to know. (2) New Methods in Supertrees (phylogenetic trees, a very active area in computational biology), a colloquium talk 
For More Information Contact: Prof. Michael Pelsmajer 
Discrete Applied Math Seminar, Spring 2013
DEPARTMENT OF APPLIED MATHEMATICS 
Date & Time  Location  Speaker/Title 
Wednesday, Jan 23rd, 4:40 pm 
LS 152 
Sonja Petrovic, Penn State University
Algebra, geometry and combinatorics for network models Given a large sparse data set, two of the fundamental questions relevant for statistical analysis are: (1) what are model parameters that "best explain the data", in the sense that they make the given data most likely to have been observed under the proposed model?, and (2) can the proposed model even be considered appropriate for the given data? In traditional statistics, these questions do have an answer: the first is done by computing the maximum likelihood estimators (MLEs), and the second by computing goodnessoffit statistics. In recent years, data sets coming from social networks, for example, are not amenable to traditional analysis and pose several challenges. In this talk I will describe some of the challenges we face today, and offer examples of techniques from an emerging field of algebraic statistics that can be used to study these problems. 
Monday, Feb 11th, 4:40 pm 
LS 152 
Alexander Gutfraind, UIC
A multiscale method for graph generation Graphs (networks) are widely used in science and technology to represent relationships between entities, such as social or ecological links between organisms, enzymatic interactions in metabolic systems, or computer infrastructure. Statistical analyses of networks can provide critical insights into the structure, function, dynamics, and evolution of those systems. However, the structures of realworld networks are often not known completely, and they may exhibit considerable variation so that no single network is sufficiently representative of a system. In such situations, researchers may turn to proxy data from related systems, sophisticated methods for network inference, or synthetic networks. Here, we introduce a flexible method for synthesizing realistic ensembles of networks starting from a known network, through a series of mappings that coarsen and later refine the network structure by randomized editing. The method, MUSKETEER, preserves structural properties with minimal bias, including unknown or unspecified features, while introducing realistic variability at multiple scales. Using examples from several domains, we show that MUSKETEER produces the intended stochasticity while achieving greater fidelity across a suite of network properties than do other commonly used network generation algorithms. 
Friday, Feb 22nd, 12:40 pm 
E1 122 
Jinyu Huang
Matroid Expansion Conjecture: An Eigenvalue Approach The nontrivial lower bounds of the spectral gap for discrete Laplacian of the basisexchange graph of a Matroid have algorithmic importance. First, we will present some background knowledge such as matroids, basisexchange graph, and eigenvalue of the Laplacian. In the second part, several new and old lower bounds for the spectral gap for the basisexchange graphs will presented and applied to algorithmic questions. We will conclude with problems for future work. 
Friday, March 1st, 12:40 pm 
E1 122 
JeongHyun Kang, U. of West Georgia and IIT
Codes with bounded distances, and their applications to distance graphs In Coding Theory, the maximum size of binary codes of length n with minimum distance d is a well studied problem. In this talk, we study binary codes when there is a restriction on maximum distance as well. Various upper bounds including an exponential upper bound have been established using a result of KabanjanskiiLevenstein and Jung's theorem in Combinatorial Geometry. We show applications of these coding theoretic results to the lower bound on chromatic number of the ndimensional integer grid. This is motivated by HadwigerNelson problem that asks for the minimum number of colors needed to color the real plane such that any two points at distance 1 are forbidden to receive the same color. The best known lower and upper bounds are 4 and 7, with no improvement in the last 50 years. This is a joint work with S. Anderson and H. Maharaj. 
Friday, March 8th, 12:40 pm 
E1 122 
Gergely Balint
Attacker Defender Games Attacker defender games are (twoplayer) games played on graphs. The player strategies are subsets of the edges or vertices of the graph (for example the defender sends message(s) through paths and the attacker tries to intercept them by 'hitting' edges). This time I will discuss a variant to this game and some of the basic results on this particular kind of games in hopes of interest and discussion on which direction could be followed to further the existing research. 
Monday, March11th, 4:40 pm 
LS 152 
Vijay Subramanian, Northwestern University
Network Games: Spotting Trendsetters and Bargaining With Middlemen Network games provide a basic framework for studying the diffusion of new ideas or behaviors through a population. In these models, agents decide to adopt a new idea based on optimizing payoff that depends on the adoption decisions of their neighbors in an underlying network. After introducing the model, we present results for two problems. The first considers the problem of inferring early adopters or first movers given a snap shot of the adoption state at a given time. We present some results on solving this problem in what is known as the low temperature regime. We conclude the first part with a discussion on reducing the complexity of such inference problems for large networks. The second considers a dynamic and decentralized market modeled by a noncooperative networked bargaining game. Our goal is to study how the network structure of the market and the role of middlemen influence the market's efficiency and fairness. We introduce the concept of limit stationary equilibrium in a general trading network and use it to analyze how endogenous delay emerges in trade and how surplus is shared between sellers and buyers. 
Friday, April 19th, 12:40 pm 
E1 122 
Gergely Balint
NonAdaptive Group Testing and the Group Sum Design The area of nonadaptive group testing is a wellsought topic in recent years. The general problem is  we have a large set of elements, N which contains some 'special items'. The (sub)set of special items is D. Our job is to precisely identify D. For this we can take tests on groups of elements of N (hence group testing), and for each test we get the answer whether there was at least one special element in the group. Our goal is to identify all the special elements in as few tests as possible. In the nonadaptive case we have to lay down the details of each test in advance and cannot change it on the fly as new data flows in. In our talk we will present (graphs of) existing best bounds for smaller parameters, and talk about possible improvements. After this intro part of the talk we will present our new design, the Group Sum  which improves already existing bounds for certain parameter range(s), discuss its potential and ways of possible future enhancements. 
Thursday, April 18th, 3:15pm  4:30pm Tuesday, April 23rd, 3:15pm  4:30pm Thursday, April 25th, 3:15pm  4:30pm Tuesday, April 30th, 3:15pm  4:30pm Thursday, May 2nd, 3:15pm  4:30pm 
E1 102 
See Math 554: Student Talks for the list of speakers and abstracts. 
Friday, May 3rd, 12:40 pm 
E1 122 
Lujia Wang
Crossing Number vs. Pairwise Crossing number of graphs The crossing number of a graph $G$, $\crs(G)$ is the minimum number of intersections among edges over all possible drawings on a plane. The pairwise crossing number $\pcr(G)$ is the the minimum number of pairs of edges that cross at least once over drawings. In the first part of this survey, we deal with the conjecture that $\pcr(G)=\crs(G)$, and prove that this is true for 4edge weighted maps on annulus. Moreover, we develop methods for solving analogous $n$edge problems including the classification of permutations on a circle. In the second part, we define the generalized crossing number $\crs_i(G)$ as the crossing number of a graph on the orientable surface of genus $i$. The crossing sequence is defined as $(\crs_i(G))_{i=0}^{g(G)}$, where $g(G)$ is the genus of the graph. This part aims at the conjecture that for each sequence of 4 numbers decreasing to 0, there is some graph with such numbers as its crossing sequence. We come up with a particular family of graphs which have concave crossing sequences of length 4, but partially prove it. 
For More Information Contact: Prof. Hemanshu Kaul 
Discrete Applied Math Seminar, Fall 2012
DEPARTMENT OF APPLIED MATHEMATICS 
Date & Time  Location  Speaker/Title 
Wednesday, Sept 5th, 3:30 pm 
E1 242 
Jinyu Huang
Progress in Polynomial Identity Testing Jinyu will present an algebraic problem in algorithm design and complexity theory: the Polynomial Identity Testing (PIT) problem: given a multivariate polynomial over a field, determine whether the polynomial is identically zero. He will describe a polynomial time blackbox algorithm of identity testing for certain kind of the low degree polynomials. 
Wednesday, Sept 19th, 3:30 pm 
E1 242 
Chris Mitillos
Progress in Fall Coloring of Graph Chris will present a compendium of his results on Fall coloring in preparation for his talk at MIGHTY conference. 
Wednesday, Oct 3rd, 3:30 pm 
E1 242 
Michael Pelsmajer
Crossing Numbers Introduction to topological graph theory  how to distinguish between the 'independent odd crossing number' and the 'odd crossing number'. Lujia Wang Open Problems: Cop and robber games  kcop win number 
Wednesday, Oct 17th, 3:30 pm 
E1 242 
Chris Mitillos
Open Problems: Ore's Conjecture  edge bounds on kcritical graphs Gergely Balint Open Problems: Extremal problems on Graph Homomorphisms  fix a graph H, what graphs G maximize the number of homomorphisms from G to H. 
Wednesday, Oct 24th, 3:30 pm 
E1 242 
Arturo Jurado
Open Problems: Zero Forcing Sets and Propagation Time Yunjiao Liu Open Problems: Saturation number and induced Saturation number 
Wednesday, Oct 31st, 3:30 pm 
E1 242 
Jinyu Huang
Eigenvalues, Matroids and Graphs: Part I The nontrivial lower bounds of the spectral gap for discrete Laplacian of the basisexchange graph of a Matroid have algorithmic importance. In the first part of this presentation, we will present some background knowledge such as matroids, basisexchange graph, and eigenvalue of the Laplacian. In the second part, several new and old lower bounds of the spectral gap for the basisexchange graphs will presented and applied to algorithmic questions. 
Wednesday, Nov 7th, 3:30 pm 
E1 242 
Jinyu Huang
Eigenvalues, Matroids and Graphs: Part II The nontrivial lower bounds of the spectral gap for discrete Laplacian of the basisexchange graph of a Matroid have algorithmic importance. In the first part of this presentation, we will present some background knowledge such as matroids, basisexchange graph, and eigenvalue of the Laplacian. In the second part, several new and old lower bounds of the spectral gap for the basisexchange graphs will presented and applied to algorithmic questions. 
Wednesday, Nov 28th, 3:30 pm 
E1 242 
Gergely (Greg) Balint
NonAdaptive Group Testing Introduction to nonadaptive group testing. Basic probabilistic methods, some improvements (given time explanations as to why they work), nonprobabilistic method(s) (group theory/number theory based, hypergraphbased), examples through small matrices. 
For More Information Contact: Prof. Hemanshu Kaul 