October 20, University of Prince Edward Island, AARMS Special Session

The Graphs and Games Research Group will host the AARMS Special Session of the Science Atlantic Math, Stats and CS Conference 2013.  It will be held on Sunday, October 20th on the campus of the University of Prince Edward Island.  The session will feature two plenary talks, intermixed with problem solving sessions.  The plenary speakers are Andrew Beveridge (Macalester College) and Ortrud Oellermann (University of Winnipeg). Some problems will be posted on this site prior to the event, but there will be opportunity for participants to share problems on the day. 

 

Registration for the AARMS Special Session is separate from the general conference registration.  To register for the Sunday Session please email the following information to sfinbow@stfx.ca:

 

Name:

University:

Whether you are an undergraduate student, graduate student, or faculty member.

 

Conference Registration is not required if you are only attending the Sunday Special Session. 

  

Accommodations

Our official conference hotel is the Rodd Royalty Inn in Charlottetown.  Please see http://conferences.upei.ca/samscs2013/accommodations/ for more information. 

There are also a limited number of rooms available at the Inns at Great George ( http://www.thegreatgeorge.com/ ) at the UPEI preferred customer rate of $149 a night.   Just let them know that you are attending a conference at UPEI.

Oct 18-19: Science Atlantic Conference

This year's Blundon Lecturer is Anthony Bonato (Ryerson University).  His lecture, entitled "Six dimensions of separation in social networks" takes place on the evening of Friday, Oct 18th.

If you are interested in giving a talk, there is a contributed talks session of to be held Saturday afternoon as part of the Science Atlantic Conference.

Go to  http://conferences.upei.ca/samscs2013/ for conference registration and abstract submission. 

Special Session Schedule for October 20th

8:30-9:30     Plenary Talk by Dr Ortrud Oellermann, University of Winnipeg

9:30-10:00   Introduction to Problems

10:00-10:30 Refreshments

10:30-12:00 Problem Solving Groups

12:00-1:30   Lunch

1:30-2:30     Plenary Talk by Dr. Andrew Beveridge, Macalester College

2:30-4:00     Problem Solving Groups

Dr Ortrud Oellermann (Joint work with P. Lafrance and T. Pressey)

Abstract: Reconstructing a Graph from its Digitally Convex Sets

Reconstructing a graph from partial information about its structure dates back to the 1940s when Ulam and Kelly conjectured that every graph of order at least three can be reconstructed uniquely (up to isomorphism) from the collection of its vertex deleted subgraphs. Since then several other reconstruction problems have been studied. We begin by surveying some known results. In the second part of the talk we introduce the definition of the digital convexity of a graph. A set S of vertices in a graph, with vertex set V, is digitally convex if for all v in V, N[v] a subset of N[S] implies v is in S. We consider the problem of determining whether a graph can be determined uniquely from the family of its digitally convex sets. In particular we show that every tree can be determined uniquely from its digitally convex sets. Given the family of digitally convex sets of a graph it can be determined in polynomial time if these are those of a tree. We highlight several results that were obtained in the process of verifying the last result.

Dr. Andrew Beveridge

Abstract: Maker-Breaker Games on Random Geometric Graphs

In a Maker-Breaker game on a graph $G$, Breaker and Maker alternately claim edges of $G$. Maker wins if, after all edges have been claimed, the graph induced by his edges has some desired property. We consider three Maker-Breaker games played on the Random Geometric Graph. For each game, we show that if we add edges between $n$ points chosen uniformly at random in the unit square by order of increasing edge-length then, with probability tending to one as $n \rightarrow \infty$, the graph becomes Maker's win the very moment it satis fies a simple necessary condition. In particular, with high probability, Maker wins the connectivity game as soon as the minimum degree of is at least 2; Maker wins the Hamilton cycle game as soon as the minimum degree is at least 4; and Maker wins the perfect matching game as soon as the minimum degree is at least 2 and every edge has at least 3 neighboring vertices.

Graph Theory Workshop, May 26-28, Dalhousie University. For more details see the next page.

Research Workshop at St Francis Xavier, July 30-31.

       For more details see the Research Workshop page.

Games @ Grenfell, September 20-21, Sir Wilfred Grenfell College, Nfld.

For more details see  the Games @ Grenfell page.