University of Cambridge > Talks.cam > Combinatorics Seminar > Small subgraphs with large average degree

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Small subgraphs with large average degree

Download to your calendar using vCal

  • UserOliver Janzer (Cambridge)
  • ClockThursday 20 October 2022, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact .

We study the fundamental problem of finding small dense subgraphs in a given graph. For a real number s>2, we prove that every graph on n vertices with average degree at least d contains a subgraph of average degree at least s on at most nd(log d){O_s(1)} vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. In addition, we show that every graph with n vertices and average degree at least n^{1-2/s+eps} contains a subgraph of average degree at least s on O_{eps,s}(1) vertices, which is also optimal up to the constant hidden in the O(.) notation, and resolves a conjecture of Verstraete. Joint work with Benny Sudakov and Istvan Tomon.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Biological and Soft Systems Seminars Cambridge Area Sequencing Informatics Meeting VIII (2016) Fisher Hall, Guildhall Street, Cambridge

Other talks

Title to be confirmed Morning Tea and Coffee Title to be confirmed CPH IRC and PHI BSU Seminar: "Response Adaptivity Across Clinical Trials In Portfolios of Biomedical Innovations" Group Presentation 5
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity