Combinatorial Theory Seminar

Tue, 24/04/2012 14:30	Choongbum Lee (UCLA)	Combinatorial Theory Seminar	L3
	Large and judicious bisections of graphs
	It is very well known that every graph on $n$ vertices and $m$ edges admits a bipartition of size at least $m/2$ . This bound can be improved to $m/2 + (n-1)/4$ for connected graphs, and $m/2 + n/6$ for graphs without isolated vertices, as proved by Edwards, and Erdös, Gyárfás, and Kohayakawa, respectively. A bisection of a graph is a bipartition in which the size of the two parts differ by at most 1. We prove that graphs with maximum degree $o(n)$ in fact admit a bisection which asymptotically achieves the above bounds.These results follow from a more general theorem, which can also be used to answer several questions and conjectures of Bollobás and Scott on judicious bisections of graphs.Joint work with Po-Shen Loh and Benny Sudakov

Tue, 08/05/2012 14:30	Hao Huang (UCLA)	Combinatorial Theory Seminar	L3
	Extremal Problems in Eulerian Digraphs
	Graphs and digraphs behave quite differently, and many classical results for graphs are often trivially false when extended to general digraphs. Therefore it is usually necessary to restrict to a smaller family of digraphs to obtain meaningful results. One such very natural family is Eulerian digraphs, in which the in-degree equals out-degree at every vertex. In this talk, we discuss several natural parameters for Eulerian digraphs and study their connections. In particular, we show that for any Eulerian digraph G with n vertices and m arcs, the minimum feedback arc set (the smallest set of arcs whose removal makes G acyclic) has size at least $m^2/2n^2+m/2n$ , and this bound is tight. Using this result, we show how to find subgraphs of high minimum degrees, and also long cycles in Eulerian digraphs. These results were motivated by a conjecture of Bollobás and Scott. Joint work with Ma, Shapira, Sudakov and Yuster

Tue, 22/05/2012 14:30	Jozef Skokan (LSE)	Combinatorial Theory Seminar	L3
	Strong Ramsey saturation for cycles
	We call a graph $H$ Ramsey-unsaturated if there is an edge in the complement of $H$ such that the Ramsey number $r(H)$ of $H$ does not change upon adding it to $H$ . This notion was introduced by Balister, Lehel and Schelp who also showed that cycles (except for $C_4$ ) are Ramsey-unsaturated, and conjectured that, moreover, one may add any chord without changing the Ramsey number of the cycle $C_n$ , unless $n$ is even and adding the chord creates an odd cycle. We prove this conjecture for large cycles by showing a stronger statement: If a graph $H$ is obtained by adding a linear number of chords to a cycle $C_n$ , then $r(H)=r(C_n)$ , as long as the maximum degree of $H$ is bounded, $H$ is either bipartite (for even $n$ ) or almost bipartite (for odd $n$ ), and $n$ is large. This motivates us to call cycles strongly Ramsey-unsaturated. Our proof uses the regularity method.

Forthcoming Seminars