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

Series: Combinatorics Seminar

The secondary polytope of a point configuration A is a polytope
whose faces are in bijection with regular subdivions of A, e.g. the secondary
polytope of the vertices of polygon is an associahedron. The resultant of a
tuple of point configurations A_1, A_2, ..., A_k in Z^n is the set of
coefficients for which the polynomials with supports A_1, A_2, ..., A_k have a
common root with no zero coordinates over complex numbers, e.g. when each A_1
is a standard simplex and k = n+1, the resultant is defined by a determinant.
The Newton polytope of a polynomial is the convex hull of the exponents, e.g.
the Newton polytope of the determinant is the perfect matching polytope.
In this talk, I will explain the close connection between secondary polytopes
and Newton polytopes of resultants, using tropical geometry, based on joint
work with Anders Jensen.

Series: Combinatorics Seminar

Ramsey theory studies the internal homogenity of mathematical structures
(i.e.
graphs, number sets), parts of which (subgraphs, number subsets) are
arbitrarily coloured. Often, the sufficient object size implies the
existence
of a monochromatic sub-object. Combinatorial games are 2-player games of
skill
with perfect information. The theory of combinatorial games studies mostly
the
questions of existence of winning or drawing strategies.
Let us consider an object that is studied by a particular Ramsey-type
theorem.
Assume two players alternately colour parts of this object by two colours
and their goal is to create certain monochromatic sub-object.
Then this is a combinatorial game.
We focus on the minimum object size such that the appropriate
Ramsey-type theorem
holds, called "Ramsey number", and on the minimum object size such that the
first player has a winning strategy in the corresponding combinatorial game,
called "game number".
In this talk, we investigate the "restricted Ramsey-type theorems".
This means, we show the existence of first player's winning strategies,
and we show that game numbers are surprisingly small, compared to
Ramsey numbers. (This is joint work with Jarek Nesetril.)

Series: Combinatorics Seminar

How large can a subset of the first N natural numbers be before it is guaranteed to contain two distinct elements which differ by a perfect square? What if I replaced "perfect square" with the image of a more general polynomial, or perhaps "one less than a prime number"? We will discuss results of this flavor, including recent improvements and generalizations.

Series: Combinatorics Seminar

The generalized flow model is a classical and widely applicable extension of network flows, where on every arc, the flow leaving the arc is a linear function of the flow entering the arc. In the talk, I will investigate a nonlinear extension of this model, with the flow leaving an arc being a concave function of the entering flow. I exhibit the first combinatorial polynomial time algorithm for solving corresponding optimization problems. This model turns out to be a common framework for solving several market equilibrium problems, such as linear Fisher markets, and immediately enables to extend them to more general settings. I will also give a survey on generalized flow algorithms and previous nonlinear flow models.

Series: Combinatorics Seminar

Colloids are mixtures of molecules well-studied in material science that
are not well-understood mathematically. Physicists model colloids as a system of two types
of tiles (type A and type B) embedded on a region of the plane, where no two tiles can
overlap. It is conjectured that at high density, the type A tiles tend to separate out and
form large "clusters". To verify this conjecture, we need methods for counting these
configurations directly or efficient algorithms for sampling. Local sampling algorithms are
known to be inefficient. However, we provide the first rigorous analysis of a global "DK
Algorithm" introduced by Dress and Krauth. We also examine the clustering effect directly
via a combinatorial argument. We prove for a certain class of colloid models that at high
density the configurations are likely to exhibit clustering, whereas at low density the tiles
are all well-distributed. Joint work with Sarah Miracle and Dana Randall.

Series: Combinatorics Seminar

The Bohman-Frieze process is a simple modification of the Erdős-Rényi random
graph that adds dependence between the edges biased in favor of joining
isolated vertices. We present new results on the phase transition of the
Bohman-Frieze process and show that qualitatively it belongs to the same
class as the Erdős-Rényi process. The results include the size and structure
of small components in the barely sub- and supercritical time periods. We
will also mention a class of random graph processes that seems to exhibit
markedly different critical behavior.

Series: Combinatorics Seminar

In the Property Testing model an algorithm is required to distinguish between the
case that an object has a property or is far from having the property. Recently, there
has been a lot of interest in understanding which properties of Boolean functions
admit testers making only a constant number of queries, and a common theme
investigated in this context is linear invariance. A series of gradual results has
led to a conjectured characterization of all testable linear invariant properties.
Some of these results consider properties where the query upper bounds are towers of
exponentials of large height dependent on the distance parameter. A natural question
suggested by these bounds is whether there are non-trivial families with testers
making only a polynomial number of queries in the distance parameter.In this talk I
will focus on a particular linear-invariant property where this is indeed the
case: odd-cycle freeness.Informally, a Boolean function fon n variables is odd-cycle
free if there is no x_1, x_2, .., x_2k+1 satisfying f(x_i)=1 and sum_i x_i = 0.This
property is the Boolean function analogue of bipartiteness in the dense graph model.
I will discuss two testing algorithms for this property: the first relies on graph
eigenvalues considerations and the second on Fourier analytic techniques. I will
also mention several related open problems.
Based on joint work with Arnab Bhattacharyya, Prasad Raghavendra, Asaf Shapira

Series: Combinatorics Seminar

A rectangulation is a tiling of a rectangle by rectangles. The rectangulation is called generic if no four of its rectangles share a corner. We will consider the problem of counting generic rectangulations (with n rectangles) up to combinatorial equivalence. This talk will present and explain an initial step in the enumeration: the fact that generic rectangulations are in bijection with permutations that avoid a certain set of patterns. I'll give background information on rectangulations and pattern avoidance. Then I'll make the connection between generic rectangulations and pattern avoiding permutations, which draws on earlier work with Shirley Law on "diagonal" rectangulations. I'll also comment on two theories that led to this result and its proof: the lattice theory of the weak order on permutations and the theory of combinatorial Hopf algebras.

Series: Combinatorics Seminar

A set~$A$ of integers is a \textit{Sidon set} if all thesums~$a_1+a_2$, with~$a_1\leq a_2$ and~$a_1$,~$a_2\in A$, aredistinct. In the 1940s, Chowla, Erd\H{o}s and Tur\'an determinedasymptotically the maximum possible size of a Sidon set contained in$[n]=\{0,1,\dots,n-1\}$. We study Sidon sets contained in sparserandom sets of integers, replacing the `dense environment'~$[n]$ by asparse, random subset~$R$ of~$[n]$.Let~$R=[n]_m$ be a uniformly chosen, random $m$-element subsetof~$[n]$. Let~$F([n]_m)=\max\{|S|\colon S\subset[n]_m\hbox{ Sidon}\}$. An abridged version of our results states as follows.Fix a constant~$0\leq a\leq1$ and suppose~$m=m(n)=(1+o(1))n^a$. Thenthere is a constant $b=b(a)$ for which~$F([n]_m)=n^{b+o(1)}$ almostsurely. The function~$b=b(a)$ is a continuous, piecewise linearfunction of~$a$, not differentiable at two points:~$a=1/3$and~$a=2/3$; between those two points, the function~$b=b(a)$ isconstant.

Series: Combinatorics Seminar

The Ising problem on finite graphs is usually treated by a reduction to the dimer problem. Is this a wise thing to do? I will show two (if time allows) recent results indicating that the Ising problem allows better mathematical analysis than the dimer problem. Joint partly with Gregor Masbaum and partly with Petr Somberg.