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:20240402T163000
DTEND;TZID=Asia/Seoul:20240402T173000
DTSTAMP:20260418T023652
CREATED:20240108T054534Z
LAST-MODIFIED:20240707T072458Z
UID:8109-1712075400-1712079000@dimag.ibs.re.kr
SUMMARY:Casey Tompkins\, On graphs without cycles of length 0 modulo 4
DESCRIPTION:Bollobás proved that for every $k$ and $\ell$ such that $k\mathbb{Z}+\ell$ contains an even number\, an $n$-vertex graph containing no cycle of length $\ell \bmod k$ can contain at most a linear number of edges. The precise (or asymptotic) value of the maximum number of edges in such a graph is known for very few pairs $\ell$ and $k$. We precisely determine the maximum number of edges in a graph containing no cycle of length $0 \bmod 4$.\nThis is joint work with Ervin Győri\, Binlong Li\, Nika Salia\, Kitti Varga and Manran Zhu.
URL:https://dimag.ibs.re.kr/event/2024-04-02/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240409T163000
DTEND;TZID=Asia/Seoul:20240409T173000
DTSTAMP:20260418T023652
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
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240416T163000
DTEND;TZID=Asia/Seoul:20240416T173000
DTSTAMP:20260418T023652
CREATED:20240108T120038Z
LAST-MODIFIED:20240707T072207Z
UID:8112-1713285000-1713288600@dimag.ibs.re.kr
SUMMARY:Magnus Wahlström\, Algorithmic aspects of linear delta-matroids
DESCRIPTION:Delta-matroids are a generalization of matroids with connections to many parts of graph theory and combinatorics (such as matching theory and the structure of topological graph embeddings). Formally\, a delta-matroid is a pair $D=(V\,\mathcal F)$ where $\mathcal F$ is a collection of subsets of V known as “feasible sets.” (They can be thought of as generalizing the set of bases of a matroid\, while relaxing the condition that all bases must have the same cardinality.) \nLike with matroids\, an important class of delta-matroids are linear delta-matroids\, where the feasible sets are represented via a skew-symmetric matrix. Prominent examples of linear delta-matroids include linear matroids and matching delta-matroids (where the latter are represented via the famous Tutte matrix). \nHowever\, the study of algorithms over delta-matroids seems to have been much less developed than over matroids. \nIn this talk\, we review recent results on representations of and algorithms over linear delta-matroids. We first focus on classical polynomial-time aspects. We present a new (equivalent) representation of linear delta-matroids that is more suitable for algorithmic purposes\, and we show that so-called delta-sums and unions of linear delta-matroids are linear. As a result\, we get faster (randomized) algorithms for Linear Delta-matroid Parity and Linear Delta-matroid Intersection\, improving results from Geelen et al. (2004). \nWe then move on to parameterized complexity aspects of linear delta-matroids. We find that many results regarding linear matroids which have had applications in FPT algorithms and kernelization directly generalize to linear delta-matroids of bounded rank. On the other hand\, unlike with matroids\, there is a significant difference between the “rank” and “cardinality” parameters – the structure of bounded-cardinality feasible sets in a delta-matroid of unbounded rank is significantly harder to deal with than feasible sets in a bounded-rank delta-matroid.
URL:https://dimag.ibs.re.kr/event/2024-04-16/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240423T163000
DTEND;TZID=Asia/Seoul:20240423T173000
DTSTAMP:20260418T023652
CREATED:20240325T144336Z
LAST-MODIFIED:20240705T153042Z
UID:8410-1713889800-1713893400@dimag.ibs.re.kr
SUMMARY:Víctor Dalmau\, Right-adjoints of Datalog Programs
DESCRIPTION:We say that two functors Λ and Γ between thin categories of relational structures are adjoint if for all structures A and B\, we have that Λ(A) maps homomorphically to B if and only if A maps homomorphically to Γ(B). If this is the case Λ is called the left adjoint to Γ and Γ the right adjoint to Λ. In 2015\, Foniok and Tardif described some functors on the category of digraphs that allow both left and right adjoints. The main contribution of Foniok and Tardif is a construction of right adjoints to some of the functors identified as right adjoints by Pultr in 1970. We shall present several recent advances in this direction including a new approach based on the notion of Datalog Program borrowed from logic.
URL:https://dimag.ibs.re.kr/event/2024-04-23/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240430T163000
DTEND;TZID=Asia/Seoul:20240430T173000
DTSTAMP:20260418T023652
CREATED:20240215T002334Z
LAST-MODIFIED:20240707T072159Z
UID:8252-1714494600-1714498200@dimag.ibs.re.kr
SUMMARY:Maximilian Gorsky\, Towards the half-integral Erdős-Pósa property for even dicycles
DESCRIPTION:A family $\mathcal F$ of (di)graphs is said to have the half- or quarter-integral Erdős-Pósa property if\, for any integer $k$ and any (di)graph $G$\, there either exist $k$ copies of graphs in $\mathcal F$ within $G$ such that any vertex of $G$ is contained in at most 2\, respectively at most 4\, of these copies\, or there exists a vertex set $A$ of size at most $f(k)$ such that $G – A$ contains no copies of graphs in $\mathcal F$. Very recently we showed that even dicycles have the quarter-integral Erdős-Pósa property [STOC’24] via the proof of a structure theorem for digraphs without large packings of even dicycles. \nIn this talk we discuss our current effort to improve this approach towards the half-integral Erdős-Pósa property\, which would be best possible\, as even dicycles do not have the integral Erdős-Pósa property. Complementing the talk given by Sebastian Wiederrecht in this seminar regarding our initial result\, we also shine a light on some of the particulars of the embedding we use in lieu of flatness and how this helps us to move even dicycles through the digraph. In the process of this\, we highlight the parts of the proof that initially caused the result to be quarter-integral. \n(This is joint work with Ken-ichi Kawarabayashi\, Stephan Kreutzer\, and Sebastian Wiederrecht.)
URL:https://dimag.ibs.re.kr/event/2024-04-30/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR