- You are here:
- GT Home
- Home
- News & Events

Series: Combinatorics Seminar

An old question in additive number theory is determining the length of the longest progression in a sumset A+B = {a + b : a in A, b in B}, given that A and B are "large" subsets of {1,2,...,n}. I will survey some of the results on this problem, including a discussion of the methods, and also will discuss some open questions and conjectures.

Series: Combinatorics Seminar

We give a complete description of the coefficients of the characteristic polynomial $\chi_H(\lambda)$ of a ($k$-uniform) hypergraph $H$, defined by the hyperdeterminant $\det(\mathcal{A} - \lambda \mathcal{I})$, where $\mathcal{A}$ is of the adjacency tensor/hypermatrix of $H$, and the hyperdeterminant is defined in terms of resultants of homogeneous systems associated to its argument. The co-degree $k$ coefficients can be obtained by an explicit formula yielding a linear combination of subgraph counts in $H$ of certain ``Veblen hypergraphs''. This generalizes the Harary-Sachs Theorem for graphs, provides hints of a Leibniz-type formula for symmetric hyperdeterminants, and can be used in concert with computational algebraic methods to obtain the full characteristic polynomial of many new hypergraphs, even when the degrees of these polynomials is enormous. Joint work with Greg Clark of USC.

Series: Combinatorics Seminar

Series: Combinatorics Seminar

A recent extension by Guth (2015) of the basic polynomial partitioning technique of Guth and Katz (2015) shows the existence of a partitioning polynomial for a given set of k-dimensional varieties in R^d, such that its zero set subdivides space into open cells, each meeting only a small fraction of the given varieties. For k > 0, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. This, in particular, applies to the setting of n algebraic curves, or, in fact, just lines, in 3-space. In this work we present an efficient algorithmic construction for this setting almost matching the bounds of Guth (2015); For any D > 0, we efficiently construct a decomposition of space into O(D^3\log^3{D}) open cells, each of which meets at most O(n/D^2) curves from the input. The construction time is O(n^2), where the constant of proportionality depends on the maximum degree of the polynomials defining the input curves. For the case of lines in 3-space we present an improved implementation using a range search machinery. As a main application, we revisit the problem of eliminating depth cycles among non-vertical pairwise disjoint triangles in 3-space, recently been studied by Aronov et al. Joint work with Boris Aronov and Josh Zahl.

Series: Combinatorics Seminar

Given a collection of finite sets, Kneser-type problems aim to partition this collection into parts with well-understood intersection pattern, such as in each part any two sets intersect. Since Lovász' solution of Kneser's conjecture, concerning intersections of all k-subsets of an n-set, topological methods have been a central tool in understanding intersection patterns of finite sets. We will develop a method that in addition to using topological machinery takes the topology of the collection of finite sets into account via a translation to a problem in Euclidean geometry. This leads to simple proofs of old and new results.

Series: Combinatorics Seminar

A long-standing conjecture of Erdős states that any n-vertex triangle-free
graph can be made bipartite by deleting at most n^2/25 edges. In this talk, we
study how many edges need to be removed from an H-free graph for a general
graph H. By generalizing a result of Sudakov for 4-colorable graphs H, we show
that if H is 6-colorable then G can be made bipartite by deleting at most
4n^2/25+O(n) edges. In the case of H=K_6, we actually prove the exact bound
4n^2/25 and show that this amount is needed only in the case G is a complete
5-partite graph with balanced parts. As one of the steps in the proof, we use a
strengthening of a result of Füredi on stable version of Turán's theorem.
This is a joint work with P. Hu, B. Lidický, T. Martins-Lopez and S. Norin.

Series: Combinatorics Seminar

The (type A) Hecke algebra H_n(q) is an n!-dimensional q-analog of the symmetric group. A related trace space of certain functions on H_n(q) has dimension equal to the number of integer partitions of n. If we could evaluate all functions belonging to some basis of the trace space on all elements of some basis of H_n(q), then by linearity we could evaluate em all traces on all elements of H_n(q). Unfortunately there is no simple published formula which accomplishes this. We will consider a basis of H_n(q) which is related to structures called wiring diagrams, and a combinatorial rule for evaluating one trace basis on all elements of this wiring diagram basis. This result, the first of its kind, is joint work with Justin Lambright and Ryan Kaliszewski.

Series: Combinatorics Seminar

How many triangles are needed to make the new graphs not look like random graphs?
I am trying to answer this question.
(The talk will be during 12:05-1:15pm; please note the room is *Skiles 256*)

Series: Combinatorics Seminar

This is Lecture 3 of a series of 3 lectures. See the abstract on Tuesday's ACO colloquium of this week.(Please note that this lecture will be 80 minutes' long.)

Series: Combinatorics Seminar

I will describe two new local limit theorems on the
Heisenberg group, and on an arbitrary connected, simply connected
nilpotent Lie group. The limit theorems admit general driving measures
and permit testing against test functions with an arbitrary
translation on the left and the right. The techniques introduced include
a rearrangement group action, the Gowers-Cauchy-Schwarz inequality, and
a Lindeberg replacement scheme which approximates the driving measure
with the corresponding heat kernel. These
results generalize earlier local limit theorems of Alexopoulos and
Breuillard, answering several open questions. The work on the
Heisenberg group is joint with Persi Diaconis.