Réunion d'hiver 2008 de la SMC
Hôtel Marriott, Ottawa (Ontario) du 6 au 8 décembre

Org: Daniel Panario et Brett Stevens (Carleton)

ADA CHAN, York University, 4700 Keele Street, Toronto, Ontario, M3J 1P3
Type-II matrices and the Hamming Scheme

An v×v matrix W is type-II if


= ì
if i=j,
for all i,j = 1,...,v.

Each type-II matrix W gives the Bose-Mesner algebra of an association scheme, called the Nomura algebra of W. Jaeger, Matsumoto and Nomura showed that W belongs to its Nomura algebra if and only if c W is a spin model for some non-zero scalar c. Note that spin models give link invariants. Jaeger, Matsumoto and Nomura's result motivates us to determine the Bose-Mesner algebras that are the Nomura algebra of type-II matrices.

In this talk, we show that the Bose-Mesner algebra of the Hamming scheme H(n,q) cannot be the Nomura algebra of a type-II matrix when q ³ 3.

CHARLIE COLBOURN, Arizona State University, Tempe, Arizona, USA
Distributing Hash Families and Covering Arrays

A (k,v)-hash function is a function from a domain of size k to a range of size v. An (N;k,v)-hash family is a set of N (k,v)-hash functions. A perfect hash family PHF(N;k,v,t) (of strength t) is an (N;k,v)-hash family with the property that for every t-subset of the domain, at least one of the N functions maps the subset onto t distinct elements of the range. Perfect hash families have arisen in numerous cryptographic applications and in the recursive construction of many allied types of combinatorial arrays. In particular they provide one of the best explicit construction techniques for covering arrays, which in turn arise in software testing, circuit testing, and the like.

Distributing hash families are introduced in order to unify three constructions for covering arrays using perfect hash families, Turán families, and intersecting codes. This unification underlies both an improvement in the sizes of the covering arrays produced, and a generalization to numerous additional parameter sets. For strengths three through six, the construction improves frequently on the sizes of the smallest covering arrays previously known.

PETER DUKES, University of Victoria, Victoria, BC, Canada
Rational decomposition of circulant graphs with large degree

A rational decomposition of a graph G into copies of an unlabelled subgraph H is a nonnegative rational weighting of the copies of H in G such that the total inherited weight on any edge of G equals 1. It is easy to see that the complete graph G=Kn admits a rational decomposition into copies of Kk, provided 2 £ k £ n. This is done by choosing each Kk with multiplicity \binomn-2k-2-1. We consider this question when G-the graph being decomposed-is a circulant of almost full degree. Given integers m ³ 1 and k ³ 2, there exists sufficiently large n0 so that any circulant G on n ³ n0 vertices, of degree at least n-m, admits a rational decomposition into copies of Kk (and hence any graph with an edge on at most k vertices). This is the result I will present, using linear algebra and difference families as the main proof techniques.

This is joint work with Alan C. H. Ling.

PENNY HAXELL, University of Waterloo
On the coprimality graph

A conjecture of Entringer states that the vertex set of every tree with n vertices can be labelled with 1,¼,n such that each pair of adjacent vertices get coprime labels. We prove this for all large n by considering the coprimality graph Sn, whose vertex set is {1,...,n} and where ij is an edge if and only if i and j are coprime. Then Entringer's conjecture says that every tree with n vertices is a subgraph of Sn. We also show that some more general classes of graphs also have the property that every member occurs as a spanning subgraph of S(n).

JEANNETTE JANSSEN, Dalhousie University, Halifax, NS
Infinite geometric graphs

A new generation of models for complex networks has led to renewed interest in geometric graphs, that is, graphs where the vertices are points in a metric space, and existence of edges depends on the distance between vertices. We study a class of infinite graphs that occur as the limits of common geometric graph models.

We study graphs whose vertex set is a countable, dense subset of a metric space, and that satisfy the geometrically e.c. property, which is a geometric version of the existentially closed property that defines the infinite random graph. We establish that graphs with the geometrically e.c. property are uniquely defined by the property and the "shape" of the vertex set in certain metrics, while there are infinitely many non-isomorphic geometrically e.c. graphs with the same vertex set in other metrics. We also establish a strong connection with locally random geometric graphs: graphs whose vertex set is a subset of a metric space, and pairs of vertices that are within a threshold distance of each other are connected independently at random with probability p.

This is joint work with Anthony Bonato.

GRAEME KEMKES, University of California, San Diego, 9500 Gilman Drive 0112, La Jolla, CA 92093-0112, USA
The chromatic number of a random d-regular graph

Achlioptas and Moore recently announced a proof that a random d-regular graph asymptotically almost surely (a.a.s.) has chromatic number k-1, k, or k+1, where k is the smallest integer satisfying d < 2(k-1)log(k-1). In this paper we prove that, asymptotically almost surely, it is not k+1. This provides an alternate proof of the results of Shi and Wormald that the chromatic number of a random 4-regular graph is a.a.s. 3 and, for a random 6-regular graph, a.a.s. 4. It also establishes, for example, the previously-unknown result that the chromatic number of a random 10-regular graph is a.a.s. 5.

Our proof applies the small subgraph conditioning method to the number of balanced k-colourings, where a colouring is balanced if the number of vertices of each colour is equal.

This is joint work with Xavier Pérez and Nick Wormald.

CLEMENT LAM, Concordia University
A search for PBD(30,K) where K does not contain a divisor of 6

Let K be a set of positive integers. A pairwise balanced design PBD(v,K) consists of a finite set V of cardinality v (whose elements are called points) and a family of subsets of V (called blocks) that has the property that every pair of distinct points lies in precisely one block, and the size of each block lies in K. Suppose K contains no divisors of 6. In 1983 and 1984, Drake and Larson determine all positive integers v such that a proper PBD(v,K) exists, with the possible exception of v = 30. Furthermore, they determined that for v=30, the only possible block sizes are {4,5,7,8}. Let bi denote the number of blocks of size i. Drake and Larson shows that there are only 6 possible block distributions (b8, b7, b5, b4), namely (1,1,14,41), (0,3,24,22), (0,3,15,37), (0,1,27,24), (0,1,24,29) and (0,1,15,44). In 2004, Grüttmüller and Streso eliminated the first of these. In this talk, we report the results of a computer search which eliminated the remaining five cases.

Joint work with Ronald Mullin and Narges Simjour.

KAREN MEAGHER, University of Regina, Regina, SK
An algebraic approach to Erdös-Ko-Rado-type theorems

The Erdös-Ko-Rado theorem is a major result in extremal set theory. This theorem describes the exact size and structure of the largest system of sets (with a fixed size) that has the property that any two sets in the system have non-trivial intersection. This theorem is particularly appealing since, with modest constraints, the largest such system is simply the collection of all sets (with a fixed size) that contain a fixed element.

Variations of this theorem hold for objects other than sets, for example, there is a version of the Erdös-Ko-Rado theorem for permutations, integer sequences, matchings and subspaces of a vector space. In each of these cases, the size of the largest intersecting system of these objects can be proven using algebraic graph theory. In this talk, I will explain this approach to Erdös-Ko-Rado-type theorems and show similarities between these problems.

LUCIA MOURA, University of Ottawa, Ottawa, Canada
Some problems involving covering arrays and graphs

Covering arrays are combinatorial structures that connect problems in design theory, extremal set theory and graph theory, and that have applications in software and network testing. In this talk, we will discuss recent generalizations of covering arrays, namely error locating arrays and covering arrays avoiding forbidden edges. We will focus on a common graph theoretical framework and its relationship to the edge clique covering problem.

ALEX ROSA, McMaster University, Hamilton, Ontario
On a problem of Marco Buratti

Let p=2n+1 be a prime, let L be any list of 2n elements, each from the set {1,2,...,n}. Marco Buratti asked whether there exists a Hamiltonian path H in Kp with V(Kp) = Zp such that the set of edge-lengths of H comprises L. He conjectured that the answer is yes for every list L.

We present some initial ideas, approaches and results towards the complete solution of Buratti's conjecture. We also suggest an extension of Buratti's conjecture for the case when p is any natural number.

FRANK RUSKEY, University of Victoria
Isoperimetric sequences for infinite complete binary trees and their relation to meta-Fibonacci sequences and signed almost binary partitions

We consider here some isoperimetric problems on the infinite binary tree T¥ whose leaves are all at the same level. In each case we are concerned with a function that depends on the number of edges in the cut (S,[`(S)]), where S is a subset of size n of the vertices of T¥, possibly subject to additional constraints. The function dC(n) minimizes over all connected subgraphs of T¥; i.e., S must be a tree. The function dG(n) minimizes over all subgraphs of T¥ that are collections of complete binary trees. The function d(n) minimizes over all unrestricted subgraphs of T¥.

We determine the values of dC(n) and dG(n) in terms of certain well-known "meta-Fibonacci" sequences, and hence can determine the values in O(n) arithmetic operations (on numbers that are O(n)). A simple recurrence relation for d(n) is derived, giving rise to an algorithm that also uses O(n) arithmetic operations to evaluate d(n).

We also show that d(n) is equal to the least number of parts in any partition of n into parts that are of the form ±(2k-1), and supply partition interpretations of dC(n) and dG(n) as well.

This work done in collaboration with Sunil Chandran and Anita Das.

MATEJA SAJNA, University of Ottawa
The probabilistic transitive closure of bipolar weighted digraphs

A bipolar weighted digraph is a digraph together with a weight function and a sign function on the arcs such that the weight of each arc lies in the interval [0,1] and no two parallel arcs have the same sign. Bipolar weighted digraphs are natural models for so-called fuzzy cognitive maps, which are used in science, engineering, and the social sciences to represent a body of knowledge. It has been noted in the literature that a (sensibly defined) transitive closure of a bipolar weighted digraph contains useful new information for the fuzzy cognitive map that it models.

It is natural to define the transitive closure of a bipolar digraph D=(V,A) as a bipolar digraph D*=(V,A*) such that an arc (u,v) of sign s is in A* if and only if D has a directed (u,v)-walk of sign s (where the sign of a directed walk is defined as the product of signs of all its arcs). But what weight should be assigned to the arc (u,v) in D* if D is a bipolar weighted digraph? We describe two natural ways to define the transitive closure of a bipolar weighted digraph-the fuzzy transitive closure and the probabilistic transitive closure-and explain our preference for the second, albeit computationally much harder option. Namely, while a version of Roy-Warshall's algorithm efficiently computes the fuzzy transitive closure of a bipolar weighted digraph, the problem is computationally hard for the probabilistic transitive closure. However, we shall describe several approaches that allow for efficient computation at least for the types and sizes of fuzzy cognitive maps that we have dealt with in practice.

This is joint work with Keven Poulin.

CATHY YAN, Department of Mathematics, Texas A&M University, College Station, TX 77843-3368
Crossings and nestings of two edges in set partitions

Let p and l be two set partitions with the same number of blocks. Assume p is a partition of [n]. For any integer l,m ³ 0, let T(p,l) be the set of partitions of [n+l] whose restrictions to the last n elements are isomorphic to p, and T(p,l,m) the subset of T(p,l) consisting of those partitions with exactly m blocks. Similarly define T(l,l) and T(l,l,m). We prove that if the statistic cr (ne), the number of crossings (nestings) of two edges, coincides on the sets T(p,l) and T(l,l) for l = 0,1, then it coincides on T(p,l,m) and T(l,l,m) for all l,m ³ 0. These results extend the ones obtained by Klazar on the distribution of crossings and nestings for matchings.

WENAN ZANG, University of Hong Kong, Hong Kong, China
Packing Circuits in Matroids

The purpose of this talk is to present a characterization of all matroids M that satisfy the following minimax relation: For any nonnegative integral weight function w defined on E(M),

Maximum {k: M has k circuits (repetition allowed) such that
                            each element e of M is used at most 2w(e) times by these circuits}
    = Minimum ì

x Î X 
w(x): X is a collection of elements (repetition allowed)
                            of M such that every circuit in M meets X at least twice ü
This characterization contains a complete solution to a research problem on 2-edge-connected subgraph polyhedra posed by Cornuéjols, Fonlupt, and Naddef in 1985.

Joint work with Guoli Ding.


l'Université Carleton Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences

© Société mathématique du Canada, 2008 :