Discrete Applied Math Seminar, Fall 2013
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 input-output 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 most-frequently 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,
SB 106 Gergely (Greg) Balint, IIT Applied Math
Non-Adaptive 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,
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 k-tuple 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 (distance-based) 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 "strategy-proof" location functions, which are those for which it is impossible for any customer "j" to favorably manipulate the results by reporting vertices that are sub-optimal from "j's" point-of-view.
Wednesday, Oct 23,
1:50 pm
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 well-known 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 Hanani-Tutte

The beautiful (and old) Hanani-Tutte 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 well-understood. However, many variants of planarity have been defined for applications: there are c-planarity, simultaneous planarity, strip-planarity, level-planarity, 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 Hanani-Tutte characterization of planarity can shed new light on planarity variants. Hanani-Tutte 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 two-connectivity

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 two-dimensional plane. We must place a minimum-size (multi)set Q of wireless relay nodes in the two dimensional plane such that the unit-disk graph induced by the union of S and Q is two-connected. The unit-disk 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: two-edge-connectivity and biconnectivity. We use variants of the same algorithms, with improved analysis, to obtain approximation ratios of 9 for two-edge-connectivity, and 5 for biconnectivity respectively.
Spring 2014 plans
Thursday, February 6 Ameera Chowdhury, Carnegie Mellon University
A Proof of the Manickam-Miklós-Singhi Conjecture for Vector Spaces
Date TBA F.R. McMorris, IIT and University of Louisville
(1) Sphere-of-attraction 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
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 goodness-of-fit 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 real-world 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 basis-exchange graph of a Matroid have algorithmic importance. First, we will present some background knowledge such as matroids, basis-exchange graph, and eigenvalue of the Laplacian. In the second part, several new and old lower bounds for the spectral gap for the basis-exchange graphs will presented and applied to algorithmic questions. We will conclude with problems for future work.
Friday, March 1st,
12:40 pm
E1 122 Jeong-Hyun 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 Kabanjanskii--Levenstein and Jung's theorem in Combinatorial Geometry. We show applications of these coding theoretic results to the lower bound on chromatic number of the n-dimensional integer grid. This is motivated by Hadwiger--Nelson 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 (two-player) 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 pay-off 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 non-cooperative 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
Non-Adaptive Group Testing and the Group Sum Design
The area of non-adaptive group testing is a well-sought 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 non-adaptive 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 4-edge 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
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 black-box 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 - k-cop win number
Wednesday, Oct 17th,
3:30 pm
E1 242 Chris Mitillos
Open Problems: Ore's Conjecture - edge bounds on k-critical 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 basis-exchange graph of a Matroid have algorithmic importance. In the first part of this presentation, we will present some background knowledge such as matroids, basis-exchange graph, and eigenvalue of the Laplacian. In the second part, several new and old lower bounds of the spectral gap for the basis-exchange 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 basis-exchange graph of a Matroid have algorithmic importance. In the first part of this presentation, we will present some background knowledge such as matroids, basis-exchange graph, and eigenvalue of the Laplacian. In the second part, several new and old lower bounds of the spectral gap for the basis-exchange graphs will presented and applied to algorithmic questions.
Wednesday, Nov 28th,
3:30 pm
E1 242 Gergely (Greg) Balint
Non-Adaptive Group Testing
Introduction to non-adaptive group testing. Basic probabilistic methods, some improvements (given time explanations as to why they work), non-probabilistic method(s) (group theory/number theory based, hypergraph-based), examples through small matrices.
For More Information Contact: Prof. Hemanshu Kaul