Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, April 10, 2014, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Dániel Korándi

K_s,t-saturated bipartite graphs

An n-by-n bipartite graph is H-saturated if the addition of any missing edge between its two parts creates a new copy of H. In 1964, Erdős, Hajnal and Moon made a conjecture on the minimum number of edges in a K_s,s-saturated bipartite graph. This conjecture was proved independently by Wessel and Bollobás in a more general, but ordered, setting: they showed that the minimum number of edges in a K_(s,t)-saturated bipartite graph is n²-(n-s+1)(n-t+1), where K_(s,t) is the "ordered" complete bipartite graph with s vertices in the first color class and t vertices in the second. However, the very natural question of determining the minimum number of edges in the unordered K_s,t-saturated case remained unsolved. This problem was considered recently by Moshkovitz and Shapira who also conjectured what its answer should be. We give a bound on the minimum number of edges in a K_s,t-saturated bipartite graph that is only smaller by an additive constant than the conjectured value. In this talk we sketch the ideas behind the proof.
Joint work with Wenying Gan and Benny Sudakov.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login