Combinatorics Seminar

When: Sunday, June 14, 10am Where: Schreiber 309 Speaker: Benny Sudakov, UCLA Title: Triangle packings and 1-factors in oriented graphs

Abstract:

An oriented graph is a directed graph which can be obtained from a simple undirected graph by orienting its edges. In this talk we show that any oriented graph G on n vertices with minimum indegree and outdegree at least (1/2-o(1))n contains a packing of cyclic triangles covering all but at most 3 vertices. This is best possible and almost answers an open question of Cuckler and Yuster. Under the same hypotheses, we also show that one can embed any prescribed almost 1-factor in G.

Joint work with P. Keevash