|
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 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 |