BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240409T163000
DTEND;TZID=Asia/Seoul:20240409T173000
DTSTAMP:20260418T041523
CREATED:20240326T004410Z
LAST-MODIFIED:20240707T072218Z
UID:8416-1712680200-1712683800@dimag.ibs.re.kr
SUMMARY:Eero Räty\, Positive discrepancy\, MaxCut and eigenvalues of graphs
DESCRIPTION:The positive discrepancy of a graph $G$ of edge density $p$ is defined as the maximum of $e(U) – p|U|(|U|-1)/2$\, where the maximum is taken over subsets of vertices in G. In 1993 Alon proved that if G is a $d$-regular graph on $n$ vertices and $d = O(n^{1/9})$\, then the positive discrepancy of $G$ is at least $c d^{1/2}n$ for some constant $c$. \nWe extend this result by proving lower bounds for the positive discrepancy with average degree d when $d < (1/2 – \epsilon)n$. We prove that the same lower bound remains true when $d < n^(2/3)$\, while in the ranges $n^{2/3} < d < n^{4/5}$ and $n^{4/5} < d < (1/2 – \epsilon)n$ we prove that the positive discrepancy is at least $n^2/d$ and $d^{1/4}n/log(n)$ respectively. \nOur proofs are based on semidefinite programming and linear algebraic techniques. Our results are tight when $d < n^{3/4}$\, thus demonstrating a change in the behaviour around $d = n^{2/3}$ when a random graph no longer minimises the positive discrepancy. As a by-product\, we also present lower bounds for the second largest eigenvalue of a $d$-regular graph when $d < (1/2 – \epsilon)n$\, thus extending the celebrated Alon-Boppana theorem. \nThis is joint work with Benjamin Sudakov and István Tomon.
URL:https://dimag.ibs.re.kr/event/2024-04-09/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR