is 190 year old!
A következő kombinatorika szemináriumok ideje
helye
és előadásai:
10:30-11:30
Let G and H be graphs or hypergraphs. A perfect H-packing in G is a collection of vertex-disjoint copies of H in G which together cover every vertex of G. In the simplest case, where H is the graph consisting of a single edge, a perfect H-packing in G is simply a perfect matching in G; Dirac's theorem tells us that such a packing must exist if G has minimum degree at least n/2 (where n is the number of vertices of G). The problem of what minimum degree is needed to ensure a perfect H-packing in G for general graphs H was then tackled by many researchers, before K\"uhn and Osthus finally established the correct threshold for all graphs H (up to an additive constant).
However, for k-uniform hypergraphs (or k-graphs) much less is known. The case of a perfect matching has been well-studied, but apart from this there were previously no known asymptotically correct results on the minimum degree needed to ensure a perfect H-packing in G for k > 4 (for any of the various common generalisations of the notion of degree to the k-graph setting).
In this talk I will demonstrate, for any complete k-partite k-graph H, the asymptotically best-possible minimum codegree condition for a k-graph G which ensures that G contains a perfect H-packing. This condition depends on the sizes of the vertex classes of H, and whether these sizes, or their differences, share any common factors greater than one.
11:30-12:00
Andrasfai, Erdos and Sos proved that all triangle-free graphs with minimum degree strictly greater than 2n/5 are bipartite. We consider an adaptation of this result to a random graph setting and discuss some other random graph versions of classical results.
12:00-12:30
The theory of hypergraph Lagrangians, developed by Frankl and F\"{u}redi [Bull. Inst. Math. Acad. Sin. \textbf{16} (1988), 305--313] and Sidorenko [Mat. Zametki \textbf{41} (1987), 433--455], is a valuable tool in the field of hypergraph Tur\'{a}n problems. Here we present a generalised notion of the hypergraph Lagrangian and use it to show that the maximum Lagrangian of an $r$-graph $H$ with the property that for all $e,f\in E(H), \ \abs{e\cap f}\neq r-2$ is attained by $K_{r+1}^{(r)}$, the complete $r$-graph on $r+1$ vertices in the cases $r=3,4,5,6,7$and 8. As a consequence we determine the Tur\'{a}n density of what we shall call the `$r$-uniform generalised $K_4$' for these values of $r$. More precisely, the $r$-uniform generalised $K_4$, denoted by $\mathcal{K}_{4}^{(r)}$, is the $r$-graph on the $5r-6$ vertices $\{x_i, y_j, z_{ijk}:i=1,\ldots,r, j=1,2, k=1,\ldots r-2\}$ and with the 6 edges $$ \{x_1,\ldots,x_r\}, \{y_1, y_2, x_3,\ldots, x_r\}\ \mbox{and}\ \{x_i, y_j,z_{ij1}, \ldots, z_{ij(r-2)} \}\ \mbox{for}\ i,j\in\{1,2\}. $$
We note that $\mathcal{K}_4^{(2)}=K_4$, the complete graph on 4 vertices, so that the above results may be viewed as hypergraph extensions of known Tur\'{a}n results on $K_4$. The generalised $K_4$ is naturally related to the generalised triangle, whose Tur\'{a}n density is considered (either implicitly or explicitly) in the works of Frankl and F\"{u}redi [J. Combin. Theory Ser. A \textbf{52} (1989), 129--147] and Pikhurko [Combinatorica \textbf{28} (2008) 187--208] amongst others.
14:00-14:30
Abstract: In 2008 the method of Johansson, Kahn and Vu for determining the threshold for the presence of a H-factor in a random graph, with H strictly balanced, was published. Later Krivelevich, Lee and Sudakov showed that Hamiltonicity is robust: after appropriate random edge deletion in a Dirac graph, whp a Hamilton cycle remains. We discuss robustness of triangle factors in suitable graphs and how the threshold methods might be adapted to this setting.
14:30-15:30
Abstract: Flag Algebras is a recently developed method by Razborov with many applications in extremal combinatorics, discrete geometry, and number theory. Flag Algebras seems to work very well if the extremal construction is a blow-up of a small structure. However, if the extremal construction is an iterated blow-up, Flag Algebras still provide a bound, but the bound is not exact.
Erd\H{o}s and S\'os proposed a problem of maximizing the number $F(n)$ of rainbow triangles in 3-edge-colored complete graphs on $n$ vertices. They conjectured that $F(n)=F(a)+F(b)+F(c)+F(d)+abc+abd+acd+bcd$, where $a+b+c+d=n$ and $a,b,c,d$ are as equal as possible and $F(0) = 0$. This is an example of a problem where the extremal construction is an iterated blow-up.
In this talk we give an introduction to Flag Algebras and show that they can be combined with a stability argument that proves the conjectured recurrence by Erd\H{o}s and S\'os for sufficiently large $n$.
This is joint work with J\'{o}zsef Balogh, Ping Hu, Florian Pfender, Jan Volec, and Michael Young
Mindenkit szeretettel várunk,
Péter
Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073, Telemedicine Oriented Research in the Fields of Mathematics, Informatics and Medical Sciences