An v×v matrix W is type-II if

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.

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.

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=K_n admits a rational decomposition into copies of K_k, provided 2 £ k £ n. This is done by choosing each K_k 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 n₀ so that any circulant G on n ³ n₀ vertices, of degree at least n-m, admits a rational decomposition into copies of K_k (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.

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 S_n, 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 S_n. 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).

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.

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.

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 b_i denote the number of blocks of size i. Drake and Larson shows that there are only 6 possible block distributions (b₈, b₇, b₅, b₄), 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.

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.

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.

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 K_p with V(K_p) = Z_p 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.

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 d_C(n) minimizes over all connected subgraphs of T_¥; i.e., S must be a tree. The function d_G(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 d_C(n) and d_G(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 ±(2^k-1), and supply partition interpretations of d_C(n) and d_G(n) as well.

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

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.

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.