- UNSW
- ...
- Our schools
- Mathematics & Statistics
- Engage with us
- Seminars
- 2021
- The Erdős-Hajnal conjecture for the five-cycle
Science
Mathematics and Statistics
- Home
- Our school
- Study with us
- Our research
-
Student life & resources
- Undergraduate
- Honours year
- Postgraduate coursework
-
Postgraduate research
- Info for new students
- Current research students
- Postgraduate conference
- Postgraduate events
- Postgraduate student awards
- Michael Tallis PhD Research Travel Award
- Information about research theses
- Past research students
- Resources
- Entry requirements
- PhD projects
- Obtaining funding
- Application & fee information
-
Student services
- Help for postgraduate students
- Thesis guidelines
- School assessment policies
- Computing information
- Mathematics Drop-in Centre
- Consultation
- Statistics Consultation Service
- Academic advice
- Enrolment variation
- Changing tutorials
- Illness or misadventure
- Application form for existing casual tutors
- ARC grants Head of School sign off
- Computing facilities
- Choosing your major
- Student societies
- Student noticeboard
- Casual tutors
- Engage with us
- News & events
- Contact
- Home
- Our school
- Study with us
- Our research
-
Student life & resources
Postgraduate research
- Info for new students
- Current research students
- Postgraduate conference
- Postgraduate events
- Postgraduate student awards
- Michael Tallis PhD Research Travel Award
- Information about research theses
- Past research students
- Resources
- Entry requirements
- PhD projects
- Obtaining funding
- Application & fee information
Student services
- Help for postgraduate students
- Thesis guidelines
- School assessment policies
- Computing information
- Mathematics Drop-in Centre
- Consultation
- Statistics Consultation Service
- Academic advice
- Enrolment variation
- Changing tutorials
- Illness or misadventure
- Application form for existing casual tutors
- ARC grants Head of School sign off
- Computing facilities
- Choosing your major
- Engage with us
- News & events
- Contact
Abstract:
The Erdős-Hajnal conjecture states that for every graph HH there exists c>0c>0 such that every nn-vertex graph GG either contains HH as an induced subgraph, or has a clique or stable set of size at least nc.nc. I will talk about a proof of this conjecture for the case H=C5H=C5 (a five-cycle), and related results. The proof is based on an extension of a lemma about bipartite graphs due to Pach and Tomon.
This is joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour.
Speaker
Sophie Spirkl
Research Area
Pure Maths Seminar
Affiliation
University of Waterloo
Date
Wed, 03/03/2021 - 11:30am
Venue
Zoom meeting (see below)