BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Drupal iCal API//EN X-WR-CALNAME:Events items teaser X-WR-TIMEZONE:America/Toronto BEGIN:VTIMEZONE TZID:America/Toronto X-LIC-LOCATION:America/Toronto BEGIN:DAYLIGHT TZNAME:EDT TZOFFSETFROM:-0500 TZOFFSETTO:-0400 DTSTART:20260308T070000 END:DAYLIGHT BEGIN:STANDARD TZNAME:EST TZOFFSETFROM:-0400 TZOFFSETTO:-0500 DTSTART:20251102T060000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT UID:6adceee310a26 DTSTART;TZID=America/Toronto:20261030T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20261030T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-bertrand-guenin-integral-set-packing-versus SUMMARY:Tutte Colloquium | Bertrand Guenin\, Integral Set Packing versus\nI ntegral Set Covering CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Bertrand Guenin\n\nAFFILIATION:\n University of Wate rloo\n\nLOCATION:\n MC 5501\n\nABSTRACT: A 0-1 matrix M is _perfect_ if t he polyhedron {x ≥ 0 : Mx\n≤ 1} is integral. Perfect matrices are clos ely related to perfect\ngraphs and have several remarkable properties. In particular\,\nperfectness is equivalent to total dual integrality\, and pe rfect\nmatrices admit an excluded-minor characterization.\n\nA 0-1 matrix M is _ideal_ if the polyhedron {x ≥ 0 : Mx ≥ 1} is\nintegral. Unlike p erfect matrices\, ideal matrices do not correspond to\na single well-under stood class of combinatorial objects. In this talk\,\nwe will explore whic h of the remarkable properties of perfect matrices\nhave counterparts for ideal matrices. We will discuss what is known\,\nwhat fails\, and some of the intriguing open questions that arise from\nthis comparison. DTSTAMP:20261024T174611Z END:VEVENT BEGIN:VEVENT UID:6adceee314526 DTSTART;TZID=America/Toronto:20261026T110000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20261026T120000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combinatoric s-and-optimization-reading-group-arkaprava SUMMARY:Combinatorics and Optimization reading group | Arkaprava Choudhury\ ,\nProof of the Sunflower Conjecture CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Arkaprava Choudhury\n\nAFFILIATION:\n University of Waterloo\n\nROOM:\n MC 6029\n\nABSTRACT: A $k$-sunflower is a family of $ k$ distinct sets whose\npairwise intersections all coincide. The Erd\\H{o} s--Szemer\\'edi\nconjecture asserts that for every $k \\ge 3$ there is a c onstant $c_k <\n2$ such that any $k$-sunflower-free family $\\mathcal{F} \ \subseteq\n2^{[n]}$ satisfies $|\\mathcal{F}| \\le c_k^{\\\,n}$. Bucic\, H e\, and Lee\nrecently proved this with an explicit bound.\n\nIn this talk we survey the problem and its place among sunflower\nquestions\, then work through the proof\, centered on a vector-sunflower\nargument. We also dis cuss how the result relates to a related problem\,\nthe uniform Erd\\H{o}s --Rado conjecture\, which it does not settle. No\nprior background is assu med.  DTSTAMP:20261024T174611Z END:VEVENT BEGIN:VEVENT UID:6adceee315180 DTSTART;TZID=America/Toronto:20261026T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20261026T160000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/graphs-and-m atroids-hidde-koerts-faster-3-colouring SUMMARY:Graphs and Matroids | Hidde Koerts\, Faster 3-colouring algorithm f or\ngraphs of diameter 3 CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Hidde Koerts \n\nAFFILIATION:\n University of Water loo\n\nROOM:\n MC 6029\n\nABSTRACT: Determining whether a graph is k-colo urable is a famously\nhard computational problem. Even when placing signif icant restrictions\non the graph\, the resulting problem is often NP-hard.  In this talk\,\nwe focus on the case of restricting the diameter. Under the\nExponential Time Hypothesis\, there does not exist a sub-exponential\ nalgorithm for 3-colouring diameter-4 graphs or for 4-colouring\ndiameter- 2 graphs. Hence\, the interesting remaining cases are\n3-colouring graphs of diameter 2 or 3. We show that 3-colouring\ndiameter-3 graphs can be so lved in 2^O(n^{2/3−ε}) for any ε < 1/33\nby providing an algorithm bas ed on a structural result. This improves\non the previous best known algor ithm due to Dębski\, Piecyk and\nRzążewski.\n\nThis talk is based on jo int work with Carla Groenland and Sophie\nSpirkl. DTSTAMP:20261024T174611Z END:VEVENT BEGIN:VEVENT UID:6adceee315d2f DTSTART;TZID=America/Toronto:20261028T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20261028T110000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/crypto-readi ng-group-quantum-computing-douglas-stebila-qkd SUMMARY:Crypto Reading Group on quantum computing | Douglas Stebila\, QKD\n Security CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Douglas Stebila\n\nAFFILIATION:\n University of Wate rloo\n\nROOM:\n MC 5501\n\nABSTRACT: Having seen the BB84 quantum key dis tribution protocol last\nweek\, this week we’ll see what it means for QK D to be secure\,\nfollowing the basic principle that “information gain i mplies\ndisturbance”. We’ll talk about what authentication is needed f or\nQKD’s security guarantees to hold\, and other factors like device\ns ecurity and finite key effects. DTSTAMP:20261024T174611Z END:VEVENT BEGIN:VEVENT UID:6adceee3168a9 DTSTART;TZID=America/Toronto:20261029T143000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20261029T153000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/algebraic-an d-enumerative-combinatorics-seminar-shao-yuan SUMMARY:Algebraic and Enumerative Combinatorics Seminar | Shao Yuan Lin\,\n Distinguishability and linear independence for H-chromatic symmetric\nfunc tions CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Shao Yuan Lin\n\nAFFILIATION:\n University of Waterl oo\n\nLOCATION:\n MC 5417\n\nABSTRACT: We study the H-chromatic symmetric functions X_G^H\nintroduced by Eagles et al. (2022)\, which generalizes t he chromatic\nsymmetric function X_G to the context of H-colorings\, which tracks\ngraph homomorphisms G → H. We first show that self-chromatic\ns ymmetric functions X_G^G determine quantities like the connected\ncomponen ts of a forest and the degree sequence of a caterpillar. We\nthen show tha t the X_G^H's form a basis of the symmetric function ring\nfor certain col lections of (G\,H)\, such as the self-CSFs of complete\nmultipartite graph s. Lastly\, we define and discuss H-chromatic\npolynomials as specializati ons of H-CSFs. This is joint work with\nLaura Pierson.\n\nThere will be a pre-seminar presenting relevant background at\nbeginning graduate level st arting at 1:30pm in MC 5417. DTSTAMP:20261024T174611Z END:VEVENT BEGIN:VEVENT UID:6adceee31742c DTSTART;TZID=America/Toronto:20261019T150000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20261019T160000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/graphs-and-m atroids-emanuel-juliano-morais-silva-connection SUMMARY:Graphs and Matroids | Emanuel Juliano Morais Silva\, On the connect ion\nbetween max-cuts\, the vector chromatic number\, and random sphere\ng raphs CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Emanuel Juliano Morais Silva\n\nAFFILIATION:\n Unive rsity of Waterloo\n\nROOM:\n MC 6029\n\nABSTRACT: It is well known that t he maximum cut size of a graph is at\nleast half its number of edges. But how small can this difference be?\nUsing random hyperplane rounding\, a te chnique from semidefinite\noptimization\, Balla\, Janzer\, and Sudakov obt ained a lower bound on\nthis difference in terms of the vector chromatic n umber\, recovering\nknown extremal bounds for $C_r$-free graphs. I will pr esent their\nargument and show that the constant in their vector-chromatic bound is\noptimal by constructing a random sphere graph. DTSTAMP:20261024T174611Z END:VEVENT BEGIN:VEVENT UID:6adceee318061 DTSTART;TZID=America/Toronto:20261021T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20261021T110000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/crypto-readi ng-group-quantum-computing-masuda-fatima-maggie SUMMARY:Crypto Reading Group on quantum computing | Masuda Fatima & Maggie\ nSimmons\, Quantum Key Distribution CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Masuda Fatima & Maggie Simmons\n\nAFFILIATION:\n Uni versity of Waterloo\n\nROOM:\n MC 5501\n\nABSTRACT: Quantum Key Distribut ion (QKD) uses the laws of Quantum\nMechanics to allow two parties to prod uce a shared secret key only\nknown to them without it's security relying on the computational\nhardness. In this presentation\, we will introduce t he QKD protocol\nBB84\, and present how it is secure against various attac ks. We will\nalso discuss two major phases in BB84: the information reconc iliation\nphase between keys of sender and receiver via error correcting c odes\nand the privacy amplification phase where two communicating parties\ ndistill highly secret shared key from a larger body of a shared key\,\nwh ich is only partially secret. Finally\, we will give a brief overview\nof Muckle-based hybrid authenticated key exchange (AKE) protocols. DTSTAMP:20261024T174611Z END:VEVENT BEGIN:VEVENT UID:6adceee318c4a DTSTART;TZID=America/Toronto:20261022T143000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20261022T153000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/algebraic-an d-enumerative-combinatorics-seminar-patty SUMMARY:Algebraic and Enumerative Combinatorics Seminar | Patty Commins\,\n Signed combinatorics and the Mantaci–Reutenauer algebra CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Patty Commins\n\nAFFILIATION:\n Laboratoire d'Algèb re\, de Combinatoire et d'Informatique\nMathématique (LACIM)\n\nLOCATION: \n MC 5417\n\nABSTRACT: The Mantaci–Reutenauer algebra is a subalgebra of the\ngroup algebra of signed permutations which has close ties to symme tric\nfunctions\, descents\, and characters. In this talk\, we explore its \nrepresentation theory and explain how it is governed by simple\noperatio ns on signed versions of classical combinatorial objects (i.e.\npartitions \, necklaces). This builds on a well-studied type A story for\nSolomon's \ "descent algebra\". The representation-theoretic data we will\nconsider in clude the Cartan matrix\, the representation type\, and a\nconjectural Ext -quiver\; we will explain these notions during the talk.\nThis is ongoing joint work with Alice Dell'Arciprete.\n\nTHERE WILL BE A PRE-SEMINAR PRESE NTING RELEVANT BACKGROUND AT THE\nBEGINNING GRADUATE LEVEL STARTING AT 1: 30PM IN MC 5417. DTSTAMP:20261024T174611Z END:VEVENT BEGIN:VEVENT UID:6adceee319825 DTSTART;TZID=America/Toronto:20261023T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20261023T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-sepehr-assadi-greedy-optimal-semi-streaming SUMMARY:Tutte Colloquium | Sepehr Assadi\, Greedy is Optimal for the\nSemi- Streaming Matching Problem CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Sepehr Assadi\n\nAFFILIATION:\n University of Waterl oo\n\nLOCATION:\n MC 5501\n\nABSTRACT: We prove that no single-pass semi-s treaming algorithm\n(deterministic or randomized) can achieve a better-tha n-half\napproximation to the maximum matching problem. This implies the\no ptimality of the naive greedy algorithm\, answering a longstanding\nopen q uestion in graph streaming literature since the introduction of\nthe model . Our proof consists of two main parts:\n\n 1. Blueprint framework: reduc ing the problem of proving lower bounds\nfor semi-streaming matching to co nstructing certain combinatorial\nobjects which we call blueprints\; and\, \n\n 2. Blueprint construction: an optimal construction of such\nblueprin ts usable within this framework.\n\n Putting these two parts together imp lies our semi-streaming matching\nlower bound.\n\nBased on joint work with Max Jiang and Mars Xiang in\nhttps://arxiv.org/abs/2607.14644 (STOC 2026) and\nhttps://arxiv.org/abs/2607.14656 (arXiv\; July 2026) DTSTAMP:20261024T174611Z END:VEVENT BEGIN:VEVENT UID:6adceee31a43f DTSTART;TZID=America/Toronto:20261005T110000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20261005T120000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read ing-group-kanstantsin-pashkovich-nearly-tight SUMMARY:CombOpt Reading Group | Kanstantsin Pashkovich\, Nearly Tight Upper \nBound for Matroid Intersection Prophet Inequality CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\nKanstantsin Pashkovich\n\nAFFILIATION:\n University of Waterloo\n\nROOM:\n MC 6029\n\nABSTRACT: In this talk\, I will go ove r the construction that shows a\nlower bound of d/log(d) for the prophet i nequality\, where the feasible\nset is the intersection of d matroids. Thi s talk is based on the paper\n\"A Nearly Tight Lower Bound for Matroid Int ersection Prophet\nInequalities\" by Dimitris Fotakis\, Charalampos Platan os\, Thanos\nTolias. DTSTAMP:20261024T174611Z END:VEVENT END:VCALENDAR