BEGIN:VCALENDAR
VERSION:2.0
PRODID:-// - ECPv6.16.3//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://aarms.math.ca
X-WR-CALDESC:Events for 
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20230301T153000
DTEND;TZID=UTC:20230301T163000
DTSTAMP:20260615T145439
CREATED:20230226T121131Z
LAST-MODIFIED:20230226T121131Z
UID:7132-1677684600-1677688200@aarms.math.ca
SUMMARY:Atlantic Graph Theory Seminar: Isaac McMullin and Ian George\, Dalhousie University
DESCRIPTION:Speaker 1: Isaac McMullin \nExistence of Optimal Split Reliability Polynomials\nOne of the most common models of robustness of a graph against random failures has all vertices operational\, but the edges independently operational with probability p. On one hand\, one can ask for the probability that all vertices can communicate (all-terminal reliability) while on the other hand\, we can ask that two specific vertices (or terminals) can communicate with each other (two-terminal reliability). While both of these questions have been well-studied\, they are both increasing functions of the edge probability. One new approach is split reliability\, where for two fixed vertices s and t\, we consider the probability that every vertex communicates with one of s or t\, but not both. The split reliability of G is a polynomial function of p that for connected graphs is 0 both at p=0 and at p=1. In this presentation\, we explore the existence for fixed numbers n>=2 and m>=n-1 of an optimal connected (n\,m)-graph G_(n\,m) for split reliability\, that is\, a connected graph with n vertices and m edges for which for any other such graph H\, the split reliability of G_(n\,m) is at least as large as that of H\, for all values of p in [0\,1]. Unlike the similar problems for all-terminal and two-terminal reliability\, where only partial results are known\, we completely solve the issue for split reliability\, where we show that there is an optimal (n\,m)-graph for split reliability if and only if n<=3\, m=n-1\, or n=m=4. \n  \n\n\nSpeaker 2: Ian George \nDegree Polynomials of Graphs \nIn this talk we introduce the Degree Polynomial of a graph.  This polynomial is defined to be the generating function of the sequence (a_0\, a_1\, a_2\, …) where a_k is the number of vertices of degree k in a graph.  Little has been published about this polynomial other than its behaviour under graph operations.  We will explore some basic properties of this polynomial\, and see what information it encodes about a graph.  Then we will discuss the roots of degree polynomials\, or degree roots\, giving some bounds and density results.  Along the way\, the degree polynomials and degree roots for certain families of graphs will be highlighted. \n\nThe talks will be held in room 227 in the Chase building at Dalhousie\, and streamed via zoom \nJoin Zoom Meeting\nhttps://us02web.zoom.us/j/86415230827?pwd=QUxLUnlMdWYzL05zSUJ4bnBCOUJnZz09\n\nMeeting ID: 864 1523 0827\nPasscode: 835547
URL:https://aarms.math.ca/event/atlantic-graph-theory-seminar-isaac-mcmullin-and-ian-george-dalhousie-university/
LOCATION:Online via Zoom
CATEGORIES:AARMS Atlantic Graph Theory Seminar
ORGANIZER;CN="jeannette Janssen":MAILTO:jeannette.janssen@dal.ca
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=UTC:20230308T153000
DTEND;TZID=UTC:20230308T163000
DTSTAMP:20260615T145439
CREATED:20230304T105511Z
LAST-MODIFIED:20230304T105511Z
UID:7138-1678289400-1678293000@aarms.math.ca
SUMMARY:Atlantic Graph Theory Seminar: Lucas Mol\, Thomson Rivers University
DESCRIPTION:Avoiding additive powers in words\nA word is a sequence of symbols taken from some finite alphabet. A square is a word of the form xx\, where x is a nonempty word. It is well-known that there are infinite words over an alphabet of size 3 that contain no squares. Suppose now that the alphabet is some finite subset of the integers. An additive square is a word of the form xx’\, where x and x’ have the same nonzero length and the same sum. Additive cubes\, fourth powers\, etc.\, are defined similarly. We present a method for proving that certain types of infinite words contain no additive k-powers. This is joint work with James Currie\, Narad Rampersad\, and Jeffrey Shallit.\n\n\n—————————————————————————————————————-\n\n\n\nJoin Zoom Meeting \nhttps://us02web.zoom.us/j/86415230827?pwd=QUxLUnlMdWYzL05zSUJ4bnBCOUJnZz09\n\nMeeting ID: 864 1523 0827\nPasscode: 835547
URL:https://aarms.math.ca/event/atlantic-graph-theory-seminar-lucas-mol-thomson-rivers-university/
LOCATION:Online via Zoom
CATEGORIES:AARMS Atlantic Graph Theory Seminar
ORGANIZER;CN="jeannette Janssen":MAILTO:jeannette.janssen@dal.ca
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=UTC:20230315T153000
DTEND;TZID=UTC:20230315T163000
DTSTAMP:20260615T145439
CREATED:20230315T123936Z
LAST-MODIFIED:20230315T123936Z
UID:7144-1678894200-1678897800@aarms.math.ca
SUMMARY:Atlantic Graph Theory Seminar: Caleb Jones and Rylo Ashmore (Memorial University)
DESCRIPTION:Speaker 1: Caleb Jones\, Memorial University\n \nTitle: Extending Graph Burning to Hypergraphs\n \nAbstract:\nWe introduce a round-based model much like graph burning which applies to hypergraphs. The rules for this new model are very natural\,and generalize the original model of graph burning. We also introduce a variant called lazy hypergraph burning\, along with a new parameter\, the lazy burning number. Interestingly\, lazily burning a graph is trivial\, while lazily burning a hypergraph can be quite complicated. Moreover\, the lazy burning model is a useful tool for analyzing the round-based model on hypergraphs. We obtain bounds on the burning number and lazy burning number of a hypergraph in terms of its parameters.\n \n \nSpeaker 2: Rylo Ashmore\, Memorial University\n \nTitle: Herding Cats Stuck in Trees.\n \nAbstract:\nIn the game of Cat Herding on a graph\, one player (the herder) will omnipresently delete edges\, while the other player (the cat) is on a vertex of the graph\, and will move along any path to a new vertex. Eventually\, the cat is isolated on a single vertex\, and the cat’s objective is to delay this event\, while the herder tries to hasten it. In an optimally played game\, the number of cuts the herder made to isolate the cat is the cat number of the graph. In this talk\, we will investigate this graph parameter for both dense and sparse graphs. We will see an argument that the asymptotic behaviour of the cat number of complete graphs is n^2/3. We also look at an unexpected connection between cat herding on trees and Fibonacci numbers. In particular\, we will see that trees with maximum cat number amongst graphs with n vertices have cat number asymptotically log_φ (n).\n\nZoom link: https://us02web.zoom.us/j/86415230827?pwd=QUxLUnlMdWYzL05zSUJ4bnBCOUJnZz09 \n\nMeeting ID: 864 1523 0827\nPasscode: 835547
URL:https://aarms.math.ca/event/atlantic-graph-theory-seminar-caleb-jones-and-rylo-ashmore-memorial-university/
LOCATION:Online via Zoom
CATEGORIES:AARMS Atlantic Graph Theory Seminar
ORGANIZER;CN="jeannette Janssen":MAILTO:jeannette.janssen@dal.ca
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=UTC:20230322T153000
DTEND;TZID=UTC:20230322T163000
DTSTAMP:20260615T145439
CREATED:20230319T132045Z
LAST-MODIFIED:20230319T132045Z
UID:7186-1679499000-1679502600@aarms.math.ca
SUMMARY:Atlantic Graph Theory Seminar: Mohammad Salavatipour\, U. Alberta
DESCRIPTION:Approximation Schemes for Resource Minimization for Fire Containment\nResource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of\nharmful spreading phenomena on a graph. In the RMFC problem on trees\, we are given an undirected\ntree G\, and a vertex r where the fire starts at\, called root. At each time step\, the firefighters\ncan protect up to B vertices of the graph while the fire spreads from burning vertices to all their\nneighbors that have not been protected so far. The task is to find the smallest B that allows for\nsaving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2\neven on trees unless P = NP. \nIn this talk we present an asymptotic QPTAS for RMFC on trees. More specifically\, let \eps > 0\,\nand F be an instance of RMFC where the optimum number of firefighters to save all the leaves is\nOPT(F). We present an algorithm which uses at most \ceil(1 + \eps )OPT(F)\rceil many firefighters at each\ntime step and runs in time n^O(\log\log n). This suggests that the existence of an asymptotic PTAS is\nplausible especially since the exponent is O(log log n). \n————————————————————-\nJoin Zoom Meeting\nhttps://us02web.zoom.us/j/86415230827?pwd=QUxLUnlMdWYzL05zSUJ4bnBCOUJnZz09 \nMeeting ID: 864 1523 0827\nPasscode: 835547
URL:https://aarms.math.ca/event/atlantic-graph-theory-seminar-mohammad-salavatipour-u-alberta/
LOCATION:Online via Zoom
CATEGORIES:AARMS Atlantic Graph Theory Seminar
ORGANIZER;CN="jeannette Janssen":MAILTO:jeannette.janssen@dal.ca
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=UTC:20230329T153000
DTEND;TZID=UTC:20230329T163000
DTSTAMP:20260615T145439
CREATED:20230325T113759Z
LAST-MODIFIED:20230325T113833Z
UID:7190-1680103800-1680107400@aarms.math.ca
SUMMARY:Atlantic Graph Theory Seminar: Calum MacRury\, University of Toronto
DESCRIPTION:Approximation Schemes for Resource Minimization for Fire Containment\nThe semi-random graph process is an example of an adaptive process for constructing a graph in which random edges are added step by step.  It is adaptive in that there is an online algorithm which has partial control over which random edges are added. Through intelligent decision-making\, the objective of the algorithm is to force the graph to satisfy a fixed graph property with high probability in as few rounds as possible. We first provide upper and lower bounds on the performance of an optimal algorithm when the property corresponds to being Hamiltonian or to containing a perfect matching. This part of the talk is based on joint works with Pawel Pralat and Jane Gao.Afterwards\, we introduce a formal definition of an adaptive random graph process which generalizes both the semi-random graph process\, as well as the Achlioptas process. In this model\, we define a condition called edge-replaceability  which we prove is sufficient for a property to have a sharp threshold. Intuitively\, a property has a sharp threshold if the optimal algorithm’s “success probability” transitions from almost $0$ to almost $1$ in a negligible number of steps.  We apply our result to the semi-random graph process to show that the properties of being Hamiltonian  and of containing a perfect matching each have a sharp threshold. This part of the talk is based on a joint work with Erlang Surya.
URL:https://aarms.math.ca/event/atlantic-graph-theory-seminar-calum-macrury-university-of-toronto/
LOCATION:Online via Zoom
CATEGORIES:AARMS Atlantic Graph Theory Seminar
ORGANIZER;CN="jeannette Janssen":MAILTO:jeannette.janssen@dal.ca
END:VEVENT
END:VCALENDAR