Abstract: Consider a set of n random axis parallel boxes in the unit hyper-cube in R^d, where d is fixed
and n tends to infinity. We show that the minimum number of points one needs to pierce all these boxes is, with high probability, at least Omega_d(sqrt{n}(log n)^{d/2-1}) and at most O_d(sqrt{n}(log n)^{d/2-1} loglog n).
Thursday, November 12th
Hoi Nguyen , Rutgers University
"An optimal version of the inverse Littlewood-Offord theorem"
Time: 2:00 PM
Location: Hill 525
Abstract: Let V={v_1,..,v_n} be a multiset of n real numbers. Let eta_i be i.i.d. Bernoulli random variables.
The concentration probability P(V) of V is defined as P(V):=sup_v P(eta_1 v_1+..+eta_n v_n = v). A classical result of Littlewood-Offord and Erdos from the 1940s asserts that if the v_i are non-zero, then the concentration probability of V is O(n^{-1/2}).
In the reverse direction, Tao and Vu proved that any set of large concentration probability must have structure. In this talk, we will provide a general approach that gives an almost best possible characterization for all such V. This allows us to recover several previous forward Littlewood-Offord results, including a significant result of Stanley from the 1980s on the optimal value of P(V) when v_i are distinct.
(Joint with Van Vu, Rutgers University)
Time: 2pm
Venue: Hill 525
Thursday, November 5th
Zeev Dvir, Institute for Advanced Study
"New bounds on the size of Kakeya sets in finite fields and applications"
Time: 2:00 PM
Location: Hill 525
Abstract: A Kakeya set is a set in (F_q)^n (the n dimensional vector space over a field of q elements) which
contains a line in every direction. In this talk I will present a recent result which gives a lower bound of (q/2)^n on the size of such sets. This bound is tight to within a multiplicative factor of two from the known upper bounds. The proof extends the polyomial methods used in [Dvir 08, Saraf Sudan 08] and uses polynomials of unbounded degree. This new bound can be used to derive new results on randomness mergers and extractors which are of interest in computational complexity.
In the talk I will show the proof of the improved Kakeya bound and discuss the applications/connections to computer science.
Based on Joint work with S. Kopparty, S. Saraf and M. Sudan.
Thursday, October 15th
Liviu Ilinca, Rutgers University
"The number of 3-SAT functions "
Time: 2:00 PM
Location: Hill 525
Abstract: A k-SAT function is a Boolean function representable by a k-SAT formula in, say, disjunctive normal form. Let G(k,n) be the number of k-SAT functions of n variables. We show that G(3,n) is asymptotic to 2^{n + {n choose 3}}, a strong form of a conjecture of Bollobas, Brightwell and Leader. (Joint with Jeff Kahn)
Thursday, October 1st
Hamed Hatami, IAS and Princeton University
"Graph norms and Sidorenko's conjecture"
Time: 2:00 PM
Location: Hill 525
Abstract: I will prove some results in the direction of answering a question of
Lovasz about the norms defined by certain combinatorial structures.
Inspired by the similarity of the definitions of $L_p$ norms, trace norms, and
Gowers norms, we introduce and study a wide class of norms containing
these, as well as many other norms. It will be proven that every norm
in this class must satisfy a Cauchy-Schwarz-Gowers type inequality. I
will show an application of this inequality to a conjecture of
Sidorenko about subgraph densities.
Thursday, September 24th
Maria Chudnovsky , Columbia University (NOTE: SPECIAL TIME)
"Large cliques and stable sets in graphs with no 4-edge paths or 5-edge antipaths"
Time: 2:20 PM
Location: Hill 525
Abstract: For every fixed graph H, if a graph G does not contain H as a minor, then one can say a lot
about the structure and properties of H. Unfortunately, results of that kind do not seem to be true if we replace the minor
containment by induced subgraph containment. One of the few conjectures about general behavior of graphs with certain
induced subgraphs forbidden is the Erdos Hajnal Conjecture. It states that for every fixed graph H there exists a
constant δ(H), such that if a graph G has no iduced subgraph isomorphic to H, then G contains a big clique or a
big stable set of size |V(G)|^δ(H).
The Erdos Hajal Conjecture is known to be true for graphs H on at most four vertices, but there are some five-vertex graphs
for which the conjecture is still open. One of such graphs is a path of length four (edges). We prove that if a graph G does
not contain as induced subgraphs a path of length four or the complement of a path of length five, then G contains a clique
or a stable set of size |V(G)|^(1/6).
This is joint work with Yori Zwols.
Time: 2:20pm
Venue: Hill 525
NOTE: *SPECIAL TIME!*
Thursday, September 17th
Van Vu, Rutgers University
"Some problems with random Bernoulli matrices"
Time: 2:00 PM
Location: Hill 525
Abstract: I will discuss the state of the art of several well-known problems concerning random Bernoulli
matrices (both symmetric and non-symmetric models). There will be many open questions. The topics include:
(1) The singularity problem: How often is a random matrix singular?
(2) The determinant problem: How large is the typical determinant of a random matrix? How is it distributed?
(3) The permanent problem: How large is the typical permanent of a random matrix and how often is it equal zero?
(4) The eigenvector problems: How does a typical eigenvector look like?
(5) The permanent estimating problem: One can use a random determinant to estimate the permanent of a deterministic matrix. How accurate is this estimator?
This page was last updated on September 16, 2009 at 12:37 pm and is maintained by webmaster@math.rutgers.edu.
