American Math Society

Joint Summer Research Conferences
in the
Mathematical Sciences



 

Graph Coloring and Symmetry

Sunday, July 21- Thursday, July 25, 2002

Karen Collins (co-chair), Wesleyan University
Danny Krizanc (co-chair),
Wesleyan University
Alexander C. Russell (co-chair),
University of Connecticut

Mt. Holyoke College, South Hadley, Mass.



 More abstracts
  • Anthony Bonato, Homomorphisms, Amalgamation, and Pseudo-homogeneous Graphs, Department of Mathematics, Wilfrid Laurier University, Waterloo, Canada.

    A class of graphs K has the amalgamation property or (AP), if, roughly speaking, given two graphs in K with a common induced subgraph A, we can glue them together along A (and possibly some more) and remain in K. The class of all graphs has (AP), but many otherwise favorable classes of graphs do not have (AP). For example, the class of 2-colourable graphs does not have (AP). The study of (AP) began with Fraisse, who discovered connections with a strong symmetry condition called homogeneity.

    Wheeler proved that the class of uniquely n-colourable graphs has (AP). We will describe how this result can be extended to the general setting of uniquely G-colourable graphs (in the sense of Zhu), where G is a finite core graph. Our results give rise, for each finite core graph G, to a countably infinite universal pseudo-homogeneous G-colourable graph M(G). The graph M(G) may beviewed as a G-colourable version of the infinite random graphstudied by P. Cameron and others. Although we will only discuss graphs in the talk, the methods apply simultaneously to other relational structures, such as directed graphs or hypergraphs.

  • Seth Chaiken, Oriented Matroid Tutte Polynomials for Multidimensional Graph Resistance and Matrix Tree Theorems, Computer Science Department, University at Albany.

    Generalized homogenized graph resistance or conductance is an evaluated generalized Tutte polynomial of an oriented matroid in which some distinguished elements are disallowed from deletion or contraction. This quantity is the exterior product representing the intersection of two linear subspaces which are certain diagonally transformed graphic 1-cycle and 1-coboundary spaces. Each coefficient in the product can be interpreted with a matrix tree theorem. This intersection is the space of electrical network solutions with Ohm's law asserted only on the non-distinguished edges.

    With other choices of subspaces we get matrix-tree-like theorems for digraphs, signed graphs, and graph models for the active circuits used by electrical engineers. Conditions for existence and uniqueness of solutions for these and other models can be given in terms of matroid union and no-common-covector properties of a pair of oriented matroids, which generalize sign-solvability properties.

  • Timothy Y. Chow, Wide partitions, Latin tableaux, and Rota's basis conjecture.

    Joint work with C. Kenneth Fan. Say that mu is a subpartition of an integer partition lambda if the multiset of parts of mu is a submultiset of the parts of lambda, and define an integer partition lambda to be wide if for every subpartition mu of lambda, mu >= mu' in dominance order (where mu' denotes the conjugate or transpose of mu). Then Brian Taylor and the first author have conjectured that an integer partition lambda is wide if and only if there exists a tableau of shape lambda such that (1) for all i, the entries in the ith row of the tableau are precisely the integers from 1 to lambda_i inclusive, and (2) for all j, the entries in the jth column of the tableau are pairwise distinct. This conjecture was originally motivated by Rota's basis conjecture and, if true, yields a new class of integer multiflow problems that satisfy maxflow-mincut and integrality. Wide partitions also yield a class of graphs that satisfy delta-conjugacy (in the sense of Greene and Kleitman), and the above conjecture implies that these graphs furthermore have a completely saturated stable set partition. We present several partial results, but the conjecture remains very much open.

  • Paola Flocchini, Sense of Direction and Graph Symmetries, University of Ottawa.

    Sense of Direction is a property of edge-labeled graphs that has been extensively studied in the distributed computing community, especially for its impact on communication complexity in distributed environments. In fact, its presence is known to drastically decrease the complexity of several problems and sometimes to solve problems otherwise unsolvable. In this talk I will introduce the notion of sense of direction, and overview its properties; in particular, I will show interesting relationships between minimal sense of direction and graph symmetries.

  • Evangelos Kranakis, Symmetry and Complexity of Boolean Functions, Carleton University, School of Computer Science.

    We study the problem of how the symmetry of a boolean function affects its circuit complexity. We survey results and propose open problems.

  • Daphne Der-Fen Liu, Fractional Chromatic Number for Distance Graphs with Large Clique Size, Department of Mathematics, California State University, Los Angeles, CA 90032, dliu@calstatela.edu

    Joint work with Xuding Zhu. Given a set M of positive integers, the distance graph generated by M, denoted by G(Z, M), has as the vertex set all integers Z, and in which i and j are adjacent whenever |i-j| falls in M. We give a characterization for the distance graphs G(Z, M) with clique size at least |M|, then determine their fractional chromatic numbers, except for one case. For the exceptional case, an upper bound and a lower bound for the fractional chromatic number are presented. These bounds are sharp enough to determine the chromatic number for such distance graphs. Consequences of our results include the confirmation of a conjecture of Rabinowitz and Proulx (SIAM J. Alg. Disc. Methods, 1985, 507-518) regarding the exact value of the fractional chromatic number of G(Z, M), with M={a, b, a+b} and gcd(a, b)=1. In addition, close relations of this topic to some number theory problems are presented.

  • Ross M. McConnell, Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs, Colorado State University

    Joint work with Dieter Kratsch, University of Metz, Kurt Mehlhorn, Max Planck Institute, Jerry Spinrad, Vanderbilt. A certifying algorithm for a decision problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer is correct. This is desirable among practitioners, who are reluctant to accept on faith that a program is bug-free, even when the underlying algorithm as been proven to be correct. Requiring algorithms to be certifying whenever possible has recently been been advocated by Mehlhorn.

    Linear-time algorithms for recognition of interval graphs and permutation graphs are well-known, but they are non-certifying, since they fail to provide supporting evidence when they reject a graph. We give linear-time certifying algorithms for these problems and show that the certificates of non-membership returned by them can be authenticated in O(V) time with trivial algorithms.

    Cindy Sawchuk, Mobile Agent Rendezvous Problem, Carelton University, School of Computer Science.

    Joint work with Evangelos Kranakis, Danny Krizanc, Nicola Santoro. Consider $k$ mobile agents on the nodes of a bi-directional ring network $R_n$ with $n$ nodes. The mobile agent rendezvous problem, MARVP[$k$], is a search optimization problem based on the following question:

    "How should $k$ mobile agents move along the vertices of the ring network $R_n$ in order to minimize the number of steps required for all of them to meet at the same node of the network?"

    The mobile agent rendezvous problem is especially interesting when the distributed environment is symmetric to every node. Typically, such symmetry is broken by using randomized protocols or non-uniform deterministic protocols. We prove that in a symmetric ring network $R_n$, the mobile agent rendezvous problem cannot be solved with a uniform deterministic protocol. For the non-symmetric ring network $R_n$, we study several uniform deterministic protocols in order to demonstrate how a mobile agents' memory size and knowledge of the network affect the time complexity of the rendezvous problem.

  • Claude Tardif, Chromatic numbers of Cayley graphs over Z_2^n, University of Regina.

    We will prove that the chromatic number of Cayley graphs over Z_2^n can never be equal to 3; if it is larger than 2, then it has to be at least 4. It is not known whether other holes exist in the range of the chromatic numbers of Cayley graphs over Z_2^n, or in the range of the chromatic numbers of Cayley graphs over other varieties of groups. This is joint work with Reza Naserasr of Simon Fraser University.

 

 

 

Brochure of Information

Joint Summer Research Conferences

Things to do in the Berkshires