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

Series: Combinatorics Seminar

We consider higher order Markov random fields to study independent sets in
regular graphs of large girth (i.e. Bethe lattice, Cayley tree). We give
sufficient conditions for a second-order homogenous isotropic Markov
random field to exhibit long-range boundary independence (i.e. decay of
correlations, unique infinite-volume Gibbs measure), and give both
necessary and sufficient conditions when the relevant clique potentials of
the corresponding Gibbs measure satisfy a log-convexity assumption. We
gain further insight into this characterization by interpreting our model
as a multi-dimensional perturbation of the hardcore model, and (under a
convexity assumption) give a simple polyhedral characterization for those
perturbations (around the well-studied critical activity of the hardcore
model) which maintain long-range boundary independence. After identifying
several features of this polyhedron, we also characterize (again as a
polyhedral set) how one can change the occupancy probabilities through
such a perturbation. We then use linear programming to analyze the
properties of this set of attainable probabilities, showing that although
one cannot acheive denser independent sets, it is possible to optimize the
number of excluded nodes which are adjacent to no included nodes.

Series: Combinatorics Seminar

A permutation of the set {1,2,...,n} is connected if there is no k < n such
that the set of the first k numbers is invariant as a set under the
permutation. For each permutation, there is a corresponding graph whose
vertices are the letters of the permutation and whose edges correspond to
the inversions in the permutation. In this way, connected permutations
correspond to connected permutation graphs.
We find a growth process of a random permutation in which we start with the
identity permutation on a fixed set of letters and increase the number of
inversions one at a time. After the m-th step of the process, we obtain a
random permutation s(n,m) that is uniformly distributed over all
permutations of {1,2,...,n} with m inversions. We will discuss the evolution
process, the connectedness threshold for the number of inversions of s(n,m),
and the sizes of the components when m is near the threshold value. This
study fits into the wider framework of random graphs since it is analogous
to studying phase transitions in random graphs. It is a joint work with my
adviser Boris Pittel.

Series: Combinatorics Seminar

This talk will be on an algebraic proof of theSzemeredi-Trotter theorem, as given by Kaplan, Matousek and Sharir.The lecture assumes no prior knowledge of advanced algebra.

Series: Combinatorics Seminar

The additive energy of a set of integers gives key
information on the additive structure of the set. In this talk, we
discuss a new, closely related statistic called the indexed additive
energy. We will investigate the relationship between the indexed
additive energy, the regular additive energy, and the size of the
sumset.

Series: Combinatorics Seminar

The Green-Tao theorem says that the primes contain arithmetic progressions
of arbitrary length. Tao and Ziegler extended it to polynomial
progressions, showing that congurations {a+P_1(d), ..., a+P_k(d)}
exist in the primes, where P_1, ..., P_k are polynomials in
\mathbf{Z}[x] without constant terms (thus the Green-Tao theorem
corresponds to the case where all the P_i are linear). We extend this
result further, showing that we can add the extra requirement that d be
of the form p-1 (or p + 1) where p is prime. This is joint work with
Julia Wolf.

Series: Combinatorics Seminar

The k-core of a (hyper)graph is the unique subgraph where all vertices have degree at least k and which is the maximal induced subgraph with this property. It provides one measure of how dense a graph is; a sparse graph will tend to have a k-core which is smaller in size compared to a dense graph. Likewise a sparse graph will have an empty k-core for more values of k. I will survey the results on the random k-core of various random graph models. A common feature is how the size of the k-core undergoes a phase transition as the density parameter passes a critical threshold. I will also describe how these results are related to a class of related problems that initially don't appear to involve random graphs. Among these is an interesting problem arising from probabilistic number theory where the random hypergraph model has vertex degrees that are "non-homogeneous"---some vertices have larger expected degree than others.

Series: Combinatorics Seminar

Given integers k\ge 3 and d with k/2 \leq d \leq k-1,
we give a minimum d-degree condition that ensures a perfect matching in
a k-uniform hypergraph. This condition is best possible and extends the
results of Pikhurko, R\"odl, Ruci\'{n}ski and Szemer\'edi. Our
approach makes use of the absorbing method. This is a joint work
with Andrew Treglown.

Series: Combinatorics Seminar

The talk is devoted to the classical problem of estimating the Van der Waerden number W(n,k). The famous Van der Waerden theorem states that, for any integers n\ge 3, k\ge 2, there exists the smallest integer W(n,k) such that in any k-coloring of the set {1,2,...,W(n,k)}, there exists a monochromatic arithmetic progression of length n. Our talk is focused on the lower bounds for the van der Waerden number. We shall show that estimating W(n,k) from below is closely connected with extremal problems concerning colorings of uniform hypergraphs with large girth. We present a new lower bound for W(n,k), whose proof is based on a continuous-time random recoloring process.

Series: Combinatorics Seminar

A variety of problems in extremal combinatorics can be stated as: For
two given graphs $H_1$ and $H_2$, if the number of induced copies of
$H_1$ in a $n$-vertex graph $G$ is known, what is the maximum or
minimum number of induced copies of $H_2$ in $G$? Numerous cases of
this question were studied by Tur\'an, Erd\H{o}s, Kruskal and Katona,
and several others. Tur\'an proved that the maximal edge density in
any graph with no cliques of size $r$ is attained by an $r-1$ partite
graph. Kruskal and Katona found that cliques, among all graphs,
maximize the number of induced copies of $K_s$ when $r

Series: Combinatorics Seminar

Given a set of tiles on a square grid (think polyominoes) and a region, can we tile the region by copies of the tiles? In general this decision problem is undecidable for infinite regions and NP-complete for finite regions. In the case of simply connected finite regions, the problem can be solved in polynomial time for some simple sets of tiles using combinatorial group theory; whereas the NP-completeness proofs rely heavily on the regions having lots of holes. We construct a fixed set of rectangular tiles whose tileability problem is NP-complete even for simply connected regions.This is joint work with Igor Pak.