Mathematics Department - Discrete Math - Spring 2014

Discrete Math - Spring 2014



Organizer(s)

Jeffry Kahn, Hao Huang

Archive



Upcoming Talks


Tuesday, April 29th

Siddhartha Sahi, Rutgers University

"Minimally complex exchange mechanisms: Emergence of prices, markets, and money"

Time: 2:00 PM
Location: Hill 525
Abstract: We consider abstract exchange mechanisms wherein individuals submit "diversified" offers in m commodities, which are then redistributed to them. Our first result is that if the mechanism satisfies certain natural conditions embodying "fairness" and "convenience" then it admits unique prices, in the sense of consistent exchange-rates across commodity pairs ij that equalize the valuation of offers and returns for each individual. We next define certain integers τ_{ij},π_{ij} and k_{i} which represent the "time" required to exchange i for j, the "difficulty" in determining the exchange ratio, and the "dimension" of the offer space in i; we refer to these as time- , price- and message- complexity of the mechanism. Our second result is that there are only a finite number of minimally complex mechanisms, and these moreover correspond to certain directed graphs G in a precise sense. The edges of G can be regarded as markets for commodity pairs, and prices play a stronger role in that the return to a trader depends only on his own offer and the prices. Finally we consider "strongly" minimal mechanisms, with smallest "worst case" complexities τ = max τ_{ij} and π = max π_{ij}. Our third main result is that for m >3 commodities that there are precisely three such mechanisms, which correspond to the star, cycle, and complete graphs, and which have complexities (π,τ) = (4,2), (2,m-1), (m˛-m,1) respectively. The star mechanism, unlike the other two, has a distinguished commodity -- the money -- that serves as the sole medium of exchange. As m→∞ it is the only one with bounded (π,τ).





Past Talks


Tuesday, April 22nd

Katherine Edwards, Princeton University

"Bounding the fractional chromatic number of K_Delta -free graphs"

Time: 2:00 PM
Location: Hill 525
Abstract: Fractional colouring is a generalization of graph colouring in which vertices are assigned sets of colours so that every pair of adjacent vertices receive disjoint sets. The fractional chromatic number is bounded above by the maximum degree Delta, but in graphs which do not contain a clique of size Delta we can generally find stronger upper bounds. I will discuss some recent progress in bounding the fractional chromatic number of K_Delta -free graphs away from Delta. Our method relies on a local strengthening of the fractional relaxation of Reed's omega, Delta, chi conjecture which roughly stipulates that if a graph has high fractional chromatic number then it must contain a vertex of high degree and a large clique in the same local area of the graph. I will also discuss new, stronger local bounds on the fractional chromatic number. Joint work with Andrew King.


Tuesday, April 15th

Emmanuel Abbe, Princeton University

"Thresholds for inverse problems on random graphs"

Time: 2:00 PM
Location: Hill 525
Abstract: We consider inverse problems on random graphs, where vertex-variables are to be recovered from dependent edge-variables. In particular, we consider the linear inverse problem Y=I(G)X+Z, where I(G) is the incidence matrix of an Erdős-Rényi random graph, X is the vector of vertex-variables assumed to be Boolean, and Z is an iid noise vector. In the absence of noise, X can be fully recovered if and only if G is connected, with a sharp threshold at log(n)/n, and X can be partially recovered (more than 50%) if and only if G has a giant component, with a sharp threshold at 1/n. We will show how these thresholds are rescaled in order to cope with the noise. Concentration results and recovery algorithms will be discussed. Based on joint works with A. Bandeira, A. Bracher, A. Singer, and A. Montanari.


Tuesday, April 8th

Swastik Kopparty, Rutgers University

"Nikodym sets in finite fields"

Time: 2:00 PM
Location: Hill 525
Abstract: A Nikodym set in F^n (where F is a finite field), is a subset N of F^n such that for every point x in F^n, there is some line L through x such that all of L (except possibly x) is contained in N. The basic problem is to determine how small a Nikodym set can be. Nikodym sets are closely related to Kakeya sets, but there are some curious differences. I will survey what theorems are known about Nikodym sets, and prove some of them.


Tuesday, April 1st

Mrinal Kumar, Rutgers University

"Lower bounds for homogeneous depth 4 arithmetic circuits"

Time: 2:00 PM
Location: Hill 525
Abstract: In this talk, we will prove super-polynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. This result builds upon and extends a long line of recent works which prove super-polynomial (and in some cases exponential) lower bounds for various restricted classes of homogeneous depth 4 circuits. The interest in homogeneous depth 4 circuits is motivated by the 'depth reduction' results of Agrawal-Vinay, Koiran and Tavenas which show that strong enough lower bounds for homogeneous depth four circuits would suffice to answer the VP vs VNP question in algebraic complexity theory, which is an algebraic analogue of the more well known P vs NP question. Joint work with Shubhangi Saraf.


Tuesday, March 25th

Esther Ezra, Courant Institute, NYU

"Geometric Discrepancy Via the Entropy Method"

Time: 2:00 PM
Location: Hill 525
Abstract: In this talk I will present new discrepancy bounds for set systems of bounded primal shatter dimension, with the property that these bounds are sensitive to the actual set sizes. These bounds are nearly-optimal. Such set systems are abstract, but they can be realized by simply-shaped regions, as halfspaces, balls, and octants in d dimensions, to name a few. Our analysis exploits the so-called Entropy method and the technique of partial coloring, combined with the existence of small delta-packings.


Tuesday, March 11th

Ori Parzanchevski, Institute for Advanced Study

"High-dimensional expanders"

Time: 2:00 PM
Location: Hill 525
Abstract: Expanders are highly connected sparse graphs, which have many interesting properties and applications. In the last decade several generalizations of expanders to simplicial complexes (or hypergraphs) were suggested, based on ideas in combinatorics, geometry, spectral theory and dynamics. I will present some of these notions of high dimensional expansion, and some relations between them. No prior knowledge is assumed.


Tuesday, March 4th

Nicolas Fraiman, University of Pennsylvania

"Connectivity of geometric k-out graphs"

Time: 2:00 PM
Location: Hill 525
Abstract: Consider n uniform random points in the unit square. One may form a random geometric graph by connecting two points by an edge if their distance is at most r. For a positive integer k, we form a subgraph of the random geometric graph by selecting, at random, k vertices among the neighbors of any given vertex, and keeping only the edges joining the vertex to the selected neighbors. We present results about connectivity properties of such graphs. This is joint work with Nicolas Broutin, Luc Devroye and Gabor Lugosi.


Tuesday, February 25th

Edinah Gnang, Institute for Advanced Study

"Representing Integers ONLY using ONE"

Time: 2:00 PM
Location: Hill 525
Abstract: Suppose that you have a Reverse Polish Calculator where the only functioning keys are the "plus", "times", and "power", "1", and, of course the "Enter" key. In how many ways can you express 40? (Ans.: 2601671905509333123020 ways). Also, how to generate, uniformly at random, one such expression? Also, what is the shortest way of doing it? In our talk we present an answer to these questions and discuss their connections with complexity theory.


Tuesday, February 18th

Avi Wigderson, Institute for Advanced Study

"Can every sequential computation be efficiently parallelized?"

Time: 2:00 PM
Location: Hill 525
Abstract: One of the major open problems in complexity theory is proving explicit super-polynomial lower bounds for Boolean formulas (sometimes called the "P vs. NC1" problem). This problem essentially captures the power of parallel computation and of small-space computation. 20 years ago Karchmer, Raz, and Wigderson showed that such lower bounds will follow from the following conjecture: for any two Boolean functions f and g, the depth complexity of their composition is roughly the sum of the individual depth of each. Moreover, using the equivalence of circuit depth and communication complexity of Karchmer-Wigderson games, they suggested a path towards proving this conjecture through a series of communication complexity lower bounds.


Wednesday, February 12th

Maria Chudnovsky, Columbia University

"Coloring graphs with forbidden induced subgraphs"

Time: 2:00 PM
Location: Hill 705
Abstract: Since graph-coloring is an NP-complete problem in general, it is natural to ask how the complexity changes if the input graph is known not to contain a certain induced subgraph H. Due to results of Kaminski and Lozin, and Hoyler, the problem remains NP-complete, unless H is the disjoint union of paths. Recently the question of coloring graphs with a fixed-length induced path forbidden has received considerable attention. Only one case of that problem remains open for k-coloring when k>=4, and that is the case of 4-coloring graphs with no induced 6-vertex path. However, little is known for 3-coloring. Recently we settled the first open case for 3-coloring; namely we showed that 3-coloring graphs with no induced 7-vertex paths can be done in polynomial time. We also made progress on the 4-coloring question. In this talk we will discuss some of the ideas of the algorithms. This is joint work with Peter Maceli, Juraj Stacho and Mingxian Zhong.


Tuesday, February 4th

Yuval Filmus, Institute for Advanced Study

"Triangle-intersecting families of graphs"

Time: 2:00 PM
Location: Hill 525
Abstract: In 1938, Erdős, Ko and Rado proved their seminal result on intersecting families of sets. They only published their result in 1961, and their paper gave birth to an entire area in extremal combinatorics. One of the questions in this are was asked in 1976 by Simonovits and Sós: How big can a collection of subgraphs of K_n be, if the intersection of any two of them contains a triangle? They conjectured that such a collection can contain at most 1/8 of the graphs. The first non-trivial bound for this question, obtained by Chung, Frankl, Graham and Shearer in 1986, was an upper bound of 1/4. We prove the conjecture of Simonovits and Sós, furthermore determining the optimal collections, and obtaining a stability result. The methods we use are spectral – we use a bound due to Hoffman which is a special case of the Lovász theta function. Joint work with David Ellis (Queen Mary's University of London) and Ehud Friedgut (Weizmann institute).


Tuesday, January 28th

Ameerah Chowdhury, Carnegie Mellon University

"A Proof of the Manickam-Miklos-Singhi Conjecture for Vector Spaces"

Time: 2:00 PM
Location: Hill 525
Abstract: Let V be an n-dimensional vector space over a finite field. Assign a real-valued weight to each 1-dimensional subspace in V so that the sum of all weights is zero. Define the weight of a subspace S of V to be the sum of the weights of all the 1-dimensional subspaces it contains. We prove that if n >= 3k, then the number of k-dimensional subspaces in V with nonnegative weight is at least the number of k-dimensional subspaces in V that contain a fixed 1-dimensional subspace. This result verifies a conjecture of Manickam and Singhi from 1988. Joint work with Ghassan Sarkis (Pomona College) and Shahriar Shahriari (Pomona College).


This page was last updated on April 09, 2014 at 08:32 am and is maintained by webmaster@math.rutgers.edu.
For questions regarding courses and/or special permission, please contact mclausen@math.rutgers.edu.
For questions or comments about this site, please contact help@math.rutgers.edu.
© 2014 Rutgers, The State University of New Jersey. All rights reserved.