
THEMATIC PROGRAMS 

April 20, 2014  
Special Year on Graph Theory and Combinatorial Optimization ProgramSeminar Series at the Fields InstituteThanks are due to André Kündgen, who is organizing the series.Thursday, May 25, 3:30  4:30 p.m. Daniel Kobler , The Fields Institute Partitioning a graph to satisfy all vertices: theoretical results and algorithmic approach
Abstract: Monday, May 15, 3:30  4:30 p.m. Radhika Ramamurthi , Department of Mathematics, University of
Illinois Total Ramsey colorings (a.k.a. split colorings) of graphs and hypergraphs
Abstract: Given integers n,m and r, we want to color the vertices and edges of the complete graph on n vertices with r colors in two rounds. We lose if, at the end of two rounds, there is a totally monochromatic mclique, that is a clique in which all vertices and edges have the same color. In the first round, we color all the edges. We then challenge the devil to color the vertices from the same r colors. The threshold below which we always win (assuming intelligent play) is exactly the Ramsey number R_r(m). We investigate the threshold when the players roles are reversed  i.e. the devil does Round 1 and we do Round 2. This parameter was introduced by Erdos and Gyarfas as a generalization of split graphs. We present improved upper and lower bounds and generalize the problem to hypergraphs. Tuesday, May 16, 3:30  4:30 p.m.
Wednesday, May 17, 3:30  4:30 p.m. Andreas Jakoby , Department of Computer Science, University
of Toronto Scheduling Dynamic Graphs
Abstract: In parallel and distributed computing scheduling low level tasks on the available hardware is a fundamental problem. Traditionally, one has assumed that the set of tasks to be executed is known beforehand. Then the scheduling constraints are given by a precedence graph. Nodes represent the elementary tasks and edges the dependencies among tasks. This static approach is not appropriate in situations where the set of tasks is not known exactly in advance, for example, when different options how to continue a program may be granted. In this talk a new model for parallel and distributed programs, the dynamic process graph, will be introduced, which represents all possible executions of a program in a compact way. The size of this representation is small  in many cases only logarithmically with respect to the size of any execution. An important feature of our model is that the encoded executions are directed acyclic graphs having a "regular" structure that is typical of programs. Dynamic process graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. With respect to such a compact representation we investigate the complexity of different aspects of the scheduling problem: the question whether a legal schedule exists at all and how to find an optimal schedule. Our analysis takes into account communication delays between processors exchanging data. Precise characterizations of the computational complexity of various variants of this compact scheduling problem will be given. The results range from easy, that is NLcomplete, to very hard, namely NEXPTIMEcomplete. Jason Brown , Department of Mathematics and Statistics, Dalhousie University May 1 Graphs and Their Polynomials I: Complexes and Generating Polynomials
Abstract: A number of polynomials have arisen in
the study of graphs, most notably chromatic polynomials and reliability
polynomials. Each has associated results and open problems. Yet underlying
many graph polynomials is a common setting. We describe here such groundwork
based on underlying abstract simplicial complexes and their face polynomials.
The approach taken gives way to a broader mode of investigation of many
graph parameters, and we shall provide another example in the guise
of independence polynomials. May 2 Graphs and Their Polynomials II: Roots of Graph Polynomials Abstract: May 3, Graphs and Their Polynomials III: The Connection to Commutative Algebra Abstract: Note: Work discussed includes joint
work with Carl Hickman, Richard Nowakowski, Karl Dilcher, Alan Sokal
and David Wagner. May 3, 3:30  4:30 Structured families of graphs Derek Corneil , Department of Computer Science, University of Toronto Abstract: April 26, 2000 Colouring graphs with nearly $\Delta$ colours Mike Molloy , Department of Computer Science, University of Toronto (joint work with Bruce Reed) Abstract: We consider graphs whose maximum degree is some constant $\Delta$. We are interested in the complexity of $k$colourability of such graphs. These graphs are trivially $k$colourable if $k=\Delta+1$, and Brooks' Theorem makes it easy to test for $k$colourability when $k=\Delta$. Maffray and Preissman showed that when $\Delta=4$ and $k=3$, the problem is NPcomplete. This raises the question for which values of $k$ is $k$colourability tractible. A few years ago, EmbdenWeinert, Hougardy and Kreuter proved that this problem is NPcomplete when $k\leq K(\Delta)\approx \Delta+1\sqrt{\Delta}$. We then proved that the problem can be solved in polynomial time if $k\geq \Delta+1\epsilon\sqrt{\Delta}$ for a small positive constant $\epsilon$. In this lecture we present our more recent proof that the problem can be solved in polynomial time for every $k>K(\Delta)$, as long as $\Delta$ is sufficiently large. A consequence of our work is a characterization of graphs with chromatic number close to $\Delta$, which is very similiar to Brooks' Theorem. April 25, 2000
Algorithms for ATfree Graphs Ekkehard Koehler , Department of Mathematics, Technische Universitaet Berlin
Abstract: What is an Asteroidal Triple and why is it of any interest to us? Those and similiar questions will be tackled in the first part of the talk. We will survey some structural and algorithmic results for this graph class and consider different characterizations. In the second part of the talk we will look at the recognition of ATfree graphs. We will examine several algorithms for this problem. One of them uses an interesting auxiliary graph, the knotting graph, which is helpful not only for ATfree graphs and enables us to recognize ATfree graphs in an elegant way. April 20, 2000 Reducible Configurations for the Barnette Conjecture Tom Fowler , Department of Mathematics, Universite du Quebec a Montreal
Abstract: Define a configuration (which should roughly be thought of as a plane subgraph in a triangulation) to be reducible if it cannot appear in a minimum counterexample to the Barnett conjecture. We present partial progress toward the Barnette Conjecture by exhibiting some reducible configurations April 18  April 19 Combinatorial Optimization and the SAT problem Oliver Kullman , Department of Computer Science, University of Toronto
Abstract: The broader perspective is to understand the complexity problems in NP (better algorithms, better upper bounds, better lower bounds). In order to make even small progress, it seems necessary to seriously examine NPcompleteness and to attack problems in NP by using many reformulations and relaxations in terms of graph theory, linear programming and propositional logic. In this 2part lecture (aimed at a general audience from computer science and combinatorial optimization) we present (new) notions and results related to the concept of "autarky". A partial assignment of truth values to variables is called an "autarky" for a conjunctive normal form (a set of clauses), if every clause "touched" by the partial assignment is in fact satisfied by it. We show interesting connections of this notion to the field of resolution refutations ("lean" clause sets not having nontrivial autarkies), linear programming ("linear autarkies"), matching theory ("matching autarkies") and matroid theory ("matchinglean" clause sets as cyclic transversal matroids). Speakers slides April 11
Complexity of recognition of intersection graphs Jan Kratochvil
Abstract: This talk is a part of the minisymposium on "Geometric Representations of Graphs" (April 1114, 2000 at The Fields Institute). There will be two other lectures by Prof. Kratochvil, and three lectures by Prof. Sue Whiteside. For more information visit the Symposium web page: Geometric Representations of Graphs April 4, The Power of Lexicographic Breadth First Search (LBFS) Derek Corneil , Department of Computer Science, University of Toronto
Abstract: In particular it has been shown that LBFS can be used both alone and in multiple sweeps to recognize various restricted families of graphs as well as to determine specific properties on such graphs. In this talk we survey these results and indicate open problems in the area. March 2830 Discharging Techniques in Practice Petr Hlineny , The Fields Institute
Abstract: We will give an overview of this technique in the three talks of this miniseries: In the first talk we will formulate the basic principles of the discharging method and give some simple examples. The second talk will be a "discharging method tutorial", focusing on how to apply this technique in practice. In the third talk we present a more involved application of discharging: we give a proof that there is no finite planar cover of the graph $K_{4,4}e$. March 22 Minimal Hereditary Dominating Pair Graphs Natasa Przulj , Department of Computer Science, University of Toronto
Abstract: March 21, 3:30  4:30 Graph Imperfection Colin McDiarmid ,Department
of Statistics, University of Oxford
Abstract: March 14, 3:30  4:30 On frequent sets of Boolean matrices Zoltán Füredi ,
University of Illinois, UrbanaChampaign and Renyi Institute, Budapest
Abstract: Given a Boolean matrix and a threshold t, a subset of columns is {\it frequent} if there are at least t rows having an entry of1 in each corresponding position. This concept is used in the algorithmic, combinatorial approach to knowledge discovery and data mining. Examples are given of families that can be represented by a small matrix with threshold t, but that require a significantly larger matrix if the threshold is less than t. We also discuss connections to circuit complexity. The results presented here are purely combinatorial and we apply extremal hypergraph theory. We slightly improve Jukna's (1995) exponential lower bound to t 2^{n/t}. This lecture is a part of the minisymposium on "Extremal Graph Theory" (Monday March 13  Thursday March 16). There will be several other lectures by Professor Furedi and Professor Simonovits in the minisymposium.
March 9, 2:10  3:10 On sum coloring of graphs Mohammad Reza Salavatipour , Department of Computer Science, University of Toronto
Abstract: We prove the NPhardness of finding the vertex strength for graphs with $\Delta=6$ and also give some logarithmic upper bounds for the vertex strength of graphs with small chromatic number. A linear time algorithm is presented for the sum coloring of chain bipartite graphs. The edge sum coloring problem and the edge strength of a graph are defined similarly. We prove that the edge sum coloring and the edge strength problems are both NPcomplete for cubic graphs. Also we give a polynomial time algorithm to solve the edge sum coloring problem on trees. March 7 The LovászSchrijver operator and the stable set polytope Laszlo Liptak , The Fields Institute
Abstract: We summarize the properties of these operators, and examine the special case when the graph is $\alpha$critical with stability number $\alpha(G)$, and the facet $\sum_{v\in V(G)} x_v\leq \alpha(G)$ can be derived in two steps. February 29, 2000 Embedding partial Steiner triple systems and beyond Prof. Curt Lindner
Abstract:
This lecture is a part of the minisymposium on "Triple Systems and their Generalizations". There will be a second lecture by Prof. Lindner in the minisymposium on March 1 from 10:0010:50. March 1, Pivoting to Find a Second DegreeConstrained Spanning Tree (joint work with Jack Edmonds) Kathie Cameron, Wilfrid Laurier University
Abstract: February 22 Mick gets more than pie Dimitris Achlioptas , Microsoft Research
Abstract:(can also be found here.) Let $X$ be a set of $n$ Boolean variables and denote by $C(X)$ the set of all 3clauses over $X$, i.e.\ the set of all $8 {n \choose 3}$ possible disjunctions of three distinct, noncomplementary literals of variables in $X$. Let $F(n,m)$ be a random 3SAT formula formed by selecting, with replacement, $m$ clauses uniformly at random from $C(X)$ and taking their conjunction. Finally, let us say that a sequence of events ${\cal E}_n$ occurs with high probability (w.h.p.) if $\lim_{n \rightarrow \infty} \Pr[{\cal E}_n]=1$. The {\em satisfiability threshold conjecture\/} asserts that there exists a constant $r_3$ such that $F(n,rn)$ is \as satisfiable for $r <r_3$ and \as unsatisfiable for $r > r_3$. Experiments suggest $r_3 \approx 4.2$. We prove $r_3 > 3.145$ improving over the previous best lower bound $r_3 > 3.003$ due to Frieze and Suen. For this, we introduce a new satisfiability heuristic and analyze its performance. The framework we develop for the analysis of our heuristic also allows us to recover most of the previous lower bounds in a uniform manner and with very little effort. February 23 Some properties of DNA graphs (joint work with various people) Daniel Kobler , The Fields Institute
Abstract: February 8 Factoring Boolean Functions using Graph Partitioning (joint work with Aviad Mintz) Martin Charles Golumbic , BarIlan University, RamatGan, Israel
Abstract: In this paper, we present an algorithm for factoring that uses graph partitioning rather than division. Central to our approach is to combine this with the use of special classes of boolean functions, such as readonce functions, to devise new combinatorial algorithms for logic minimization. Our method has been implemented in the SIS environment, and an empirical evaluation indicates that we usually get significantly better results than algebraic factoring and are quite competitive with boolean factoring but with lower computation costs. Thursday, February 10 at 2:10  3:00
pm
On centroid branches of trees from certain
families Amram Meir , York University
Abstract: We obtain various results concerning the sizes etc of the centroid branches in large random trees from certain families. February 1 3
Colouring of Mixed Hypergraphs Vitaly Voloshin , The Moldovan Academy of Sciences
Abstract: A mixed hypergraph is a triple H=(X,C,D) where X is the vertex set, C is the family of Cedges and D is the family of Dedges. A proper colouring of H is a mapping from X onto a set of colours such that:
It may very well be that a mixed hypergraph has no colourings; then it is called uncolourable. In a colourable mixed hypergraph, the minimum (maximum) number of colours for which there exists a colouring using all the colours is called the lower (upper) chromatic number. A feasible partition is a partition of X such that the colouring constraints 1) and 2) hold for the partition classes. The numbers of all feasible partitions form a vector called the chromatic spectrum. In mixed hypergraphs, many old problems admit natural generalizations; many new problems arise; many properties have no analogue. Basic paper : V.Voloshin. On the upper chromatic number of a hypergraph. Australasian J. of Comb. 11, 1995, p. 2545. In the 3 lectures we will discuss the following questions:
January 25  27 Knots, Graphs and Complexity John Mighton , University of Toronto
Abstract The graphs appear to offer a new approach to a number of open problems in Knot Theory. We will also discuss how the graphs may be used (via the Jones polynomial) to give upper bounds in Complexity Theory. 
