September 8 - 12, 2014
Keywords of the presentation: Bipartite decomposition, Random graphs, Stein-Chen method
For a graph G, let bc(G) denote the minimum possible number of pairwise
edge disjoint complete bipartite subgraphs of G so that each edge of G
belongs to (exactly) one of them. The study of this quantity and its
variants received a considerable amount of attention and is related
to problems in communication complexity and geometry. After a brief
discussion of the background and earlier results on the subject I will
focus on the problem of determining the typical value of bc(G) for the
binomial random graph G=G(n,p), showing that a conjecture of Erdos about
it is (slightly) false, and suggesting an alternative one.
Keywords of the presentation: extremal combinatorics, counting discrete structures
Recently, Balogh-Morris-Samotij and Saxton-Thomason developed a method of counting independent sets in hypergraphs.
During the talk, I show a recent application of the method; solving the following Erdos problem:
What is the number of maximal triangle-free graphs?
If there is some extra time in the talk, I will survey some other recent applications.
These applications are partly joint with Das, Delcourt, Liu, Mycroft, Petrickova, Sharifzadeh and Treglown.
Endow S_n with the uniform probability measure. Given a permutation s of [n], let N(s) denote the number of ways that s can be written as a product of two involutions of [n]. We will identify several properties of the random variable N, including:
(1) An elementary derivation of the exact formula for N(s) in terms of the cycle lengths of s.
(2) The minimum, maximum, and expected values of N over S_n.
(3) The asymptotic distribution of log N, which resolves a conjecture of M. Lugo.
In particular, N is asymptotically lognormal. The proof of this draws on connections between N(s) and B(s), the product of the cycle lengths of s, along with the Erdős-Turán law, which states that B itself is asymptotically lognormal.
Keywords of the presentation: graph coloring, induced subgraphs, graph structure
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, and related problems.
This is joint work with Peter Maceli, Juraj Stacho and Mingxian Zhong.
Keywords of the presentation: Ramsey theory
Ramsey's theorem states that for any graph H there exists an n such that any 2-colouring of the complete graph on n vertices contains a monochromatic copy of H. Moreover, for large n, one can guarantee that there are at least c_H n^v copies of H, where v is the number of vertices in H. In this talk, we investigate the problem of optimising the constant c_H, focusing in particular on the case of complete graphs.
Keywords of the presentation: Extremal combinatorics, geometric graph theory, semi-algebraic relations
Famous Ramsey, Turan, and Szemeredi-type results prove the existence of certain patterns in graphs and hypergraphs under mild assumptions. We survey recent results which show much stronger/larger patterns for graphs and hypergraphs that arise from geometry or algebra.
Keywords of the presentation: Extremal hypergraphs, forests, Erdos-Sos conjecture, Erdos-Ko-Rado theorem
The Turan number ex(n,H) of an r-graph H is the largest size of an n-vertex
r-graph that does not contain H. The famous Erdos-Sos conjectrure concerns the
Turan number of a tree T of k vertices. The difficulty lies in the fact that
there could be very different extremal families, disjoint cliques of sizes k-1
or in some cases a graph with (k-2)/2 vertices of degree n-1.
A hypergraph H is a hypergraph forest if its edges can be ordered as
{E_1,..., E_m} such that for all i>1 there exits an alpha(i) < i such that the
intersection of E_i with earlier members contained entirely in E_{alpha(i)}.
Many extremal set theoretic results, such as the Erdos-Ko-Rado theorem, can
be described in terms of Turan numbers of very specific r-forests, or partial
r-forests. In this work we are looking for the possible widest class of
hypergraph forests where the extremal family is kind of concentrated, it
consists of a few high degree vertices. For all rgeq 4, we show that if H is
a partial r-forest such that each edge has at least two degre 1 vertices then
ex(n,H)=(s(H)-1) {n choose r-1} + O(n^{r-2})
where s(H) is the minimum size of a 1-cross-cut of H. Using structural
stability we also obtain exact results implying many recent asymptotic bounds.
Most of the new results presented are joint with Tao Jiang (Miami University,
Ohio).
For any r>0, Keevash, Knox, and Mycroft constructed a polynomial-time algorithm to determine the existence of perfect matchings in any n-vertex k-uniform hypergraph whose minimum codegree is at least n/k+rn.
We construct a polynomial-time algorithm to determine the existence of a perfect matching for any k-uniform hypergraph with minimum codegree at least n/k. This solves a problem of Karpiński, Ruciński and Szymańska completely.
Our proof is short and uses a lattice-based absorbing method.
In his 1989 paper (Linear Algebra and Its Applications,
113:173--182), Duarte solves an structured inverse eigenvalue problem, and
Hassani Monfared in his PhD dissertation (2014) solves similar problems
using the Jacobian method. In particular, it was shown that for any set of
n distinct real numbers, and a given graph G, there is a real symmetric
matrix A whose graph is G and its eigenvalues are the given numbers. It is
also shown that if the graph G is connected, then the matrix A with above
properties can be chosen such that all the eigenvectors of A are
nowhere-zero (that is, none of eigenvectors has a zero entry). There is a
belief that the later result could be proved using probabilistic methods.
Keywords of the presentation: Erdos-Ko-Rado, random hypergraph
One of the more interesting of recent combinatorial directions
has been the attempt to understand the extent to which
various classical facts remain true in a random setting.
The present talk will mostly discuss what we know about this question
when the ``classical fact" is the Erdos-Ko-Rado Theorem.
(Joint with Arran Hamm.)
Keywords of the presentation: giant component, hypergraphs, Galton-Watson branching process
The study of phase transitions in random graphs was initiated by Erdos and Renyi in 1960. They proved among other things that a uniform random graph undergoes a drastic change in the size and structure of the largest component, caused by altering a critical edge density. Since the seminal work of Erdos and Renyi, various random graph models have been introduced and studied over the last five decades. In this talk I will discuss some recent results in phase transitions in random hypergraphs. (Joint work with Oliver Cooley and Christoph Koch.)
Keywords of the presentation: Triangle-free, chromatic number, cycle lengths
Erdos conjectured that a triangle-free graph with chromatic number
k contains cycles of almost quadratically many
different lengths, as k tends to infinity.
We prove a somewhat
stronger inequality for the number of consecutive lengths of cycles in
k-chromatic graphs.
The bound has the best possible order of magnitude because of Kim's
construction of ``small'' triangle-free
graphs with chromatic number k.
We also give new lower bounds on the circumference and the number of
different cycle lengths for k-chromatic graphs in other monotone
classes, in particular, for graphs with bounded clique number and
for graphs without
odd cycles of a given length.
This is joint work with Benny Sudakov and Jacques Verstraete.
Keywords of the presentation: site percolation, pseudo-random graphs, giant component
We establish the existence of the phase transition in site percolation on pseudo-random d-regular graphs. Let G=(V,E) be an (n,d,lambda)-graph, that is, a d-regular graph on n vertices in which all eigenvalues of the adjacency matrix, but the first one, are at most lambda in their absolute values. Form a random subset R of V by putting every vertex v in V into R independently with probability p. Then for any small enough constant epsilon>0, if p=(1-epsilon)/d, then with high probability all connected components of the subgraph of G induced by R are of size at most logarithmic in n, while for p=(1+epsilon)/d, if the eigenvalue ratio lambda/d is small enough as a function of epsilon, then typically R contains a connected component of size at least epsilon n/d and a path of length proportional to epsilon^2n/d.
Unfortunately, because of the format of the talk, most probably we will not be able to address the fascinating question stated in the title in its full depth and generality. Thus, instead, we concentrate on the specific problem of finding
the threshold function for the `freeness' for Zuk's model of triangular random group which was recently settled in the affirmative by Sylwia Antoniuk, Tomasz Prytuła, Piotr Przytycki, Bartosz Zaleski and the speaker.
Keywords of the presentation: multiple covering, decomposition, hypergraph coloring
A set system is a k-fold covering of space if every point is contained in at least k sets. A 1-fold covering is called simply a covering. In 1980, motivated by a question of Laszlo Fejes Toth, I raised the following question. Given a plane convex set C, does there exist an integer k=k(C) such that every k-fold covering of the plane splits into 2 coverings? The same question makes sense in higher dimension. This problem has turned out to be relevant in sensor network scheduling and has generated a lot of research during the past 3 and a half decades.
In this talk, I will summarize the curious history of the problem, and give a survey of the most important results and related open problems.
An edge colouring of a graph G is called acyclic if it is proper and every
cycle contains at least three colours. We show that for every eps>0, there
exists a g=g(eps) such that if G has maximum degree D and girth at least g
then it admits an acyclic edge colouring with at most (1+eps)D colours.
This is a joint work with X. S. Cai, B. Reed and A. B. Watts.
A (possibly directed) graph is k-linked if for any two disjoint sets of
vertices {x1,...,xk} and {y1,...,yk} there are vertex disjoint paths
P1,...,Pk such that Pi goes from xi to yi. A theorem of Bollobás and
Thomason says that every 22k-connected (undirected) graph is k-linked. It
is desirable to obtain analogues for directed graphs as well. Although
Thomassen showed that the Bollobás-Thomason Theorem does not hold for
general directed graphs, he proved an analogue of the theorem for
tournaments - there is a function f(k) such that every strongly
f(k)-connected tournament is k-linked. The bound on f(k) was reduced to
O(k log k) by Kühn, Lapinskas, Osthus, and Patel, who also conjectured
that a linear bound should hold. We'll present the ideas behind a proof of
this conjecture, that every strongly 452k-connected tournament is
k-linked.
Keywords of the presentation: Extremal problems, Turan densities, flag algebras
Flag Algebras is a general method for proving results in asymptotic
extremal combinatorics that can be loosely described as ``systematic counting based on semi-definite programming''.
The concrete results proven via this method can be (again, loosely) classified into two groups of unequal size. Brute-force
applications use counting only; the role of a human being reduced to finding a tractable problem and doing a bit of programming.
In other applications of the method, more advanced concepts and tools from the general theory are used to help in finding
a ``flag algebra-assisted'' proof.
This talk will mostly be a survey of concrete results in extremal combinatorics obtained with the help of flag algebras provided
in either of these two modes. But instead of giving a plain and unannotated list of results, we will try to divide our account into several
connected stories that often include historical background, motivations and results obtained via other methods.
Keywords of the presentation: Minors, Rooted Minors
We discuss the edge-density required to force H as a minor,
especially when H is sparse.
We also discuss analogous results for rooted minors. This includes joint
work with Gwenael Joret, Dieter Rautenbach, Alex Scott, David Wood, and
Hehui Wu.
We present a restricted variable generalization of Warning's Second Theorem (a result giving a lower bound on the number of solutions of a low degree polynomial system over a finite field, assuming one solution exists). This is analogous to Schauz’s (and later Brink’s) restricted variable generalization of Chevalley's Theorem (a result giving conditions for a low degree polynomial system emph{not} to have exactly one solution). Just as Warning's Second Theorem implies Chevalley's Theorem, our result implies Schauz's Theorem. We include several combinatorial applications, enough to show that we have a general tool for obtaining quantitative refinements of combinatorial existence theorems.
This is joint work with Pete L. Clark (U. Georgia) and Aden Forrow (M.I.T.).
Keywords of the presentation: Erdos Magic, Lovasz Local Lemma, Brownian Motion
We discuss two recent methods in which an object
with a certain property is sought. In both, using of
a straightforward random object would succeed with
only exponentially small probability. The new
randomized algorithms run efficiently and also
give new proofs of the existence of the desired
object. In both cases there is a potentially broad
use of the methodology.
(i) Consider an instance of k-SAT in which each clause
overlaps (has a variable in common, regardless of the negation
symbol) with at most d others. Lovasz showed for certain
d,k (regardless of the number of variables) the
conjunction of the clauses was satisfiable. The new approach
due to Moser is to start with a random true-false assignment.
In a WHILE loop, if any clause is not satisfied we "fix it"
by a random reassignment. The analysis (due, basically, to
Don Knuth) of the algorithm is
unusual, connecting the running of the algorithm with certain
Tetris patterns, and leading to some algebraic combinatorics.
[These results apply in a quite general setting
with underlying independent "coin flips" and bad events (the
clause not being satisfied) that depend on only a few of the
coin flips.]
(ii) No Outliers. Given n vectors n-space
with all coefficients between -1 and +1 one wants a
vector x with all coordinates -1 or +1 so
that its dot products with all the n vectors are at
most K times the square root of n
in absolute value, K an absolute constant. A random
x would make the dot product Gaussian but there would
be outliers. The existence of such an x was first shown
by the speaker. The first algorithm was found by Nikhil
Bansal. The approach here, due to Lovett and Meka, is to
begin with x the all zero vector and let it float in a kind
of restricted Brownian Motion until all the coordinates hit
the boundary.
Keywords of the presentation: Random Graph Processes, Achlioptas Process, Connectivity Threshold
In an Achlioptas processes, starting with a graph that has n vertices
and no edge, in each round d edges are drawn uniformly
at random, and using some rule exactly one of them is chosen and
added to the evolving graph. For the class of Achlioptas processes
we investigate how much impact the rule has on one of the most basic
properties of a graph: connectivity. Our main results are twofold.
First, we study the prominent class of bounded size rules, which select
the edge to add according to the component sizes of its vertices,
treating all sizes larger than some constant equally. For such rules
we provide a ne analysis that exposes the limiting distribution of
the number of rounds until the graph gets connected, and we give a
detailed picture of the dynamics of the formation of the single component
from smaller components. Second, our results allow us to study
the connectivity transition of all Achlioptas processes, in the sense
that we identify a process that accelerates it as much as possible.
Joint work with Hafsteinn Einarsson, Johannes Lengler, Frank Mousset, and
Konstantinos Panagiotou
Keywords of the presentation: Ramsey graph, extremal problems, Ramsey equivalence
A graph G is a minimal Ramsey-graph for H if every two-colouring of the edges of G contains a monochromatic copy of H, but no proper subgraph of G has this property. Burr, Erdos and Lovasz investigated the extremal values of various graph parameters among minimal Ramsey-graphs for the clique. In particular they determined the smallest minimum degree of minimal Ramsey-graphs for the k-clique. Recently there has been much activity in extending their investigations in various directions, in the talk I survey some of these.
This represents joint work with Jacob Fox, Andrey Grinshpun, Anita Liebenau, and Yury Person.
Keywords of the presentation: list colourings, hypergraphs
Unlike the ordinary chromatic number, the list chromatic number necessarily
grows with the average degree. Indeed, Alon (2000) proved it grows with the
logarithm of the average degree. Recently, the same has been shown to be
true for uniform hypergraphs, by means of the "container method": we sketch
how this works. The question then arises as to the precise value of the
minimum list chromatic number. Here the answer turns out to be not what was
expected. We attempt to sketch the latest progress, and its implications
for containers. (Joint work with David Saxton and Ares Meroueh.)
The k-means method is an iterative clustering algorithm which associates each observation with one of k clusters. It traditionally employs cluster centers in the same space as the observed data. By relaxing this requirement, it is possible to apply the k-means method to infinite dimensional problems, for example smoothing problems in the presence of unknown data association. Via a Gamma-convergence argument, the associated optimization problem is shown to converge in the sense that both the k-means minimum and minimizers converge in the large data limit to quantities which depend upon the observed data only through its distribution.
Stochastic tropical geometry is the study of linear functionals of random
tropical varieties. It is an exciting new field at the interface of
algebraic geometry, probability and combinatorics, with connections to many
others. In this work, we study the simplest possible case: the number of
zeroes of a randomtropical polynomial.
Specifically, if a tropical polynomial has coefficients independent and
identically distributed according to some distribution $F$, then its number
of zeroes satisfies a central limit theorem. The scaling is governed by how
fast $F$ decays near $. This can be seen as a local universality result
for zeros ofrandom tropical polynomials.
Our proof draws on connections between random partitions, renewal theory
and random polytopes. In this talk, I sketch the main proof ideas and
discuss open questions in the field of stochastic tropical geometry.
Joint work with Francois Baccelli
Let G be a graph of density p on n vertices. Erdös, Luczak and Spencer defined a subgraph H of G to be full if H has m vertices and every vertex of H has degree at least p(m - 1) in H. Let f(G) denote the largest number of vertices in a full subgraph of G and let fp(n) denote the smallest value of f(G) over all graphs G of density p with n vertices. Erdös, Luczak and Spencer proved √2n ≤ f0:5(n) ≤ 2n2/3 (log n)1/3 and also showed f(G) = (n) when G is the random graph Gn,p.
In this talk, I will show that fp(n) ≥ min {p1/2n + 1; 0:1n2/3} for all p ∈ (0; 1), and for p close to the elements of {1/2, 2/3, 3/4; ::::} we show that fp(n) = O(n2/3), which determines the order of magnitude of fp(n) for infinitely many p. We also discuss the value of f(G) when G is a random or pseudorandom graph, as well as full subgraphs of regular graphs.
The methods include spectral techniques and discrepancy, together with some com-
binatorial algorithms to find full subgraphs. Our study was in part originally motivated by questions on bootstrap percolation in graphs. In conclusion, a number of interesting open questions will be presented.
Joint work with Victor Falgas-Ravry and Klas Markstrom during the program on
graphs, hypergraphs and computing at Institut Mittag-Leffler in winter 2014.
Keywords of the presentation: concentration, anti-concentration, small ball probability, inverse theorems, random graphs
In probabilistic combinatorics, one often needs to have some rough estimate for the distribution of a complicated random variable. There are two main kinds of estimates:
(1) Concentration: If one take an interval I far from the mean, then the probability that X in I is very small.
(2) Anti-concentration: If one take a "short" interval I, then the probability that X in I is also very small.
I am going to discuss a few recent results in these areas, together with applications. Most of the talk will be based on my papers "Small Ball Probability" with H. Nguyen, and "Random Weighted projections" with K. Wang, available on the arxiv.
Keywords of the presentation: asymptotic enumeration, degree sequence, power law
The number of graphs with a given degree sequence is still not known in any convenient form, even asymptotically, for moderately dense graphs. We obtain a formula that includes some heavy-tailed sequences in the sparse case (i.e. where the average degree is rather small).
Our general result requires upper bounds on the k-th moment of the degree sequence, for a few small integers k. Special cases include the first asymptotic enumeration results applicable to degree sequences following a power law with parameter between 2 and 3, which is the realm of empirically observed real-world networks. Another special case extends a recent result of Janson. A previous result on sparse graphs applies to a wide range of degree sequences but requires maximum degree M to the power 1/3, where M is the number of edges. Our new result applies in some cases when the maximum degree is almost the 3/5 power of M. The basic method is, as usual, that of estimating a very small probability, of the event that the random configuration model gives a simple graph.
This is joint work with Jane Gao.
We consider decompositions of digraphs into edge-disjoint paths.
Together with several enumerative and structural results, one of the
main interests lies in increasing walks. As we will see there is a
connection of decompositions with the n-th Weyl algebra (or
differential operators). Like Eulerian tours applicable for the
Amitsur-Levitski theorem, this approach helps to study skew-symmetric
polynomials on certain subspaces of Weyl algebra. We also discuss some
new types of restricted set partitions and generalized Stirling
numbers. For instance, G-Stirling functions which enumerate
decompositions by sources and sinks of paths.