|
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
|