Search

Delsarte theory, more specifically the study of codes and designs in association schemes, has proved invaluable in studying an increasing assortment of association schemes in recent years. Tools motivated by the study of error-correcting codes in the Hamming scheme and combinatorial $t$-designs in the Johnson scheme apply equally well in association schemes with irrational eigenvalues. We assume here that we have a commutative association scheme with irrational eigenvalues and wish to study its Delsarte $T$-designs. We explore when a $T$-design is also a $T'$-design where $T'\supseteq T$ is controlled by the orbits of a Galois group related to the splitting field of the association scheme. We then study Delsarte designs in the association schemes of finite groups, with a detailed exploration of the dicyclic groups., Comment: 22 pages, 1 figure

A $k$-dispersed labelling of a graph $G$ on $n$ vertices is a labelling of the vertices of $G$ by the integers $1, \dots , n$ such that $d(i,i+1) \geq k$ for $1 \leq i \leq n-1$. $DL(G)$ denotes the maximum value of $k$ such that $G$ has a $k$-dispersed labelling. In this paper, we study upper and lower bounds on $DL(G)$. Computing $DL(G)$ is NP-hard. However, we determine the exact values of $DL(G)$ for cycles, paths, grids, hypercubes and complete binary trees. We also give a product construction and we prove a degree-based bound., Comment: To be published in Australasian Journal of Combinatorics

We show that any two Hadamard graphs on the same number of vertices are quantum isomorphic. This follows from a more general recipe for showing quantum isomorphism of graphs arising from certain association schemes. The main result is built from three tools. A remarkable recent result of Man\v{c}inska and Roberson shows that graphs $G$ and $H$ are quantum isomorphic if and only if, for any planar graph $F$, the number of graph homomorphisms from $F$ to $G$ is equal to the number of graph homomorphisms from $F$ to $H$. A generalization of partition functions called "scaffolds" affords some basic reduction rules such as series-parallel reduction and can be applied to counting homomorphisms. The final tool is the classical theorem of Epifanov showing that any plane graph can be reduced to a single vertex and no edges by extended series-parallel reductions and Delta-Wye transformations. This last sort of transformation is available to us in the case of exactly triply regular association schemes. The paper includes open problems and directions for future research., Comment: 21 pages

We give a tight bound for the triple intersection numbers of Paley graphs. In particular, we show that any three vertices have a common neighbor in Paley graphs of order larger than 25., Comment: 3 pages

We introduce the concept of group state transfer on graphs, summarize its relationship to other concepts in the theory of quantum walks, set up a basic theory, and discuss examples. Let $X$ be a graph with adjacency matrix $A$ and consider quantum walks on the vertex set $V(X)$ governed by the continuous time-dependent unitary transition operator $U(t)= \exp(itA)$. For $S,T\subseteq V(X)$, we says $X$ admits "group state transfer" from $S$ to $T$ at time $\tau$ if the submatrix of $U(\tau)$ obtained by restricting to columns in $S$ and rows not in $T$ is the all-zero matrix. As a generalization of perfect state transfer, fractional revival and periodicity, group state transfer satisfies natural monotonicity and transitivity properties. Yet non-trivial group state transfer is still rare; using a compactness argument, we prove that bijective group state transfer (the optimal case where $|S|=|T|$) is absent for almost all $t$. Focusing on this bijective case, we obtain a structure theorem, prove that bijective group state transfer is "monogamous", and study the relationship between the projections of $S$ and $T$ into each eigenspace of the graph. Group state transfer is obviously preserved by graph automorphisms and this gives us information about the relationship between the setwise stabilizer of $S\subseteq V(X)$ and the stabilizers of naturally defined subsets obtained by spreading $S$ out over time and crudely reversing this process. These operations are sufficiently well-behaved to give us a topology on $V(X)$ which is likely to be simply the topology of subsets for which bijective group state transfer occurs at that time. We illustrate non-trivial group state transfer in bipartite graphs with integer eigenvalues, in joins of graphs, and in symmetric double stars. The Cartesian product allows us to build new examples from old ones., Comment: 15 pages, 2 figures

Let $X$ be a finite set and let $\mathsf{Mat}_X(\mathbb{C})$ denote the algebra of matrices with rows and columns indexed by $X$ and entries from the complex numbers acting on $\mathbb{C}^X$ with standard basis $\{ \hat{x} \mid x\in X\}$. For a digraph $G=(V(G),E(G))$, function $R:[m] \rightarrow V(G)$ with $r_j := R(j)$, and a function $w$ from the arcs of $G$ to $\mathsf{Mat}_X(\mathbb{C})$, we define the "scaffold" $\mathsf{S}(G,R;w)$ as the sum over all functions $\varphi$ from $V(G)$ to $X$ of the $m$-fold tensors $\widehat{\varphi(r_1)} \otimes \widehat{\varphi(r_2)} \otimes \cdots \otimes \widehat{\varphi(r_m)}$ scaled by the product of the entries $w(e)_{\varphi(a),\varphi(b)}$ over all arcs $e=(a,b)$ of $G$. Scaffolds can be used to count, among other things, digraph homomorphisms and association scheme parameters such as generalized intersection numbers. They also arise in the the theory of link invariants and spin models. These diagrams were introduced in the late 1980s by Arnold Neumaier and have been used implicitly by various authors working with association schemes. We revisit results of several authors, rephrasing their proofs in terms of these diagrams and certain rules of manipulation (or "moves") on diagrams. Our goal is to collect and present, in a uniform fashion, Neumaier's original idea extended to tensors and its used by various authors. Sometimes the term "star-triangle diagram" appears for what we, in this paper, call "scaffolds". Restricting to the case where edge weights are chosen from a coherent algebra, we explore the vector space $\mathsf{W}((G,R); \mathbb{A})$ spanned by all scaffolds defined on rooted diagram $(G,R)$ and establish a connection to graph minors. We end with a conjecture about planar scaffolds that draws a connection between association scheme duality and the duality of plane graphs., Comment: 60 pages, 176 auxiliary files of diagrams; revision to correct typographical errors and add a few minor observations

Over the last twenty five years, advances in the collection and analysis of fMRI data have enabled new insights into the brain basis of human health and disease. Individual behavioral variation can now be visualized at a neural level as patterns of connectivity among brain regions. Functional brain imaging is enhancing our understanding of clinical psychiatric disorders by revealing ties between regional and network abnormalities and psychiatric symptoms. Initial success in this arena has recently motivated collection of larger datasets which are needed to leverage fMRI to generate brain-based biomarkers to support development of precision medicines. Despite methodological advances and enhanced computational power, evaluating the quality of fMRI scans remains a critical step in the analytical framework. Before analysis can be performed, expert reviewers visually inspect raw scans and preprocessed derivatives to determine viability of the data. This Quality Control (QC) process is labor intensive, and the inability to automate at large scale has proven to be a limiting factor in clinical neuroscience fMRI research. We present a novel method for automating the QC of fMRI scans. We train machine learning classifiers using features derived from brain MR images to predict the "quality" of those images, based on the ground truth of an expert's opinion. We emphasize the importance of these classifiers' ability to generalize their predictions across data from different studies. To address this, we propose a novel approach entitled "FMRI preprocessing Log mining for Automated, Generalizable Quality Control" (FLAG-QC), in which features derived from mining runtime logs are used to train the classifier. We show that classifiers trained on FLAG-QC features perform much better (AUC=0.79) than previously proposed feature sets (AUC=0.56) when testing their ability to generalize across studies.

We consider ordered pairs $(X,\mathcal{B})$ where $X$ is a finite set of size $v$ and $\mathcal{B}$ is some collection of $k$-element subsets of $X$ such that every $t$-element subset of $X$ is contained in exactly $\lambda$ "blocks" $B\in \mathcal{B}$ for some fixed $\lambda$. We represent each block $B$ by a zero-one vector $\mathbf{c}_B$ of length $v$ and explore the ideal $\mathcal{I}(\mathcal{B})$ of polynomials in $v$ variables with complex coefficients which vanish on the set $\{ \mathbf{c}_B \mid B \in \mathcal{B}\}$. After setting up the basic theory, we investigate two parameters related to this ideal: $\gamma_1(\mathcal{B})$ is the smallest degree of a non-trivial polynomial in the ideal $\mathcal{I}(\mathcal{B})$ and $\gamma_2(\mathcal{B})$ is the smallest integer $s$ such that $\mathcal{I}(\mathcal{B})$ is generated by a set of polynomials of degree at most $s$. We first prove the general bounds $t/2 < \gamma_1(\mathcal{B}) \le \gamma_2(\mathcal{B}) \le k$. Examining important families of examples, we find that, for symmetric 2-designs and Steiner systems, we have $\gamma_2(\mathcal{B}) \le t$. But we expect $\gamma_2(\mathcal{B})$ to be closer to $k$ for less structured designs and we indicate this by constructing infinitely many triple systems satisfying $\gamma_2(\mathcal{B})=k$., Comment: 26 pages, 1 figure

Maryam Mirzakhani, the first female (and first Iranian) Fields Medalist, passed away on July 14, 2017 at the age of 40. This short note remembers her 1996 article in the Bulletin of the Institute of Combinatorics and its Applications and her early years as a mathematician., Comment: 8 pages, 2 diagrams, 1 photograph

Let $(X,\mathcal{R})$ be a commutative association scheme and let $\Gamma=(X,R\cup R^\top)$ be a connected undirected graph where $R\in \mathcal{R}$. Godsil (resp., Brouwer) conjectured that the edge connectivity (resp., vertex connectivity) of $\Gamma$ is equal to its valency. In this paper, we prove that the deletion of the neighborhood of any vertex leaves behind at most one non-singleton component. Two vertices $a,b\in X$ are called "twins" in $\Gamma$ if they have identical neighborhoods: $\Gamma(a)=\Gamma(b)$. We characterize twins in polynomial association schemes and show that, in the absence of twins, the deletion of any vertex and its neighbors in $\Gamma$ results in a connected graph. Using this and other tools, we find lower bounds on the connectivity of $\Gamma$, especially in the case where $\Gamma$ has diameter two. Among the applications of these results, we find that the only connected relations in symmetric association schemes which admit a disconnecting set of size two are those which are ordinary polygons., Comment: 17 pages, three figures

In this paper, we study the existence of $(v,m,k,\lambda)$-strong external difference families (SEDFs). We use character-theoretic techniques to show that no SEDF exists when $v$ is prime, $k > 1$ and $m > 2$. In the case where $v$ is the product of two distinct odd primes, some necessary conditions are derived, which can be used to rule out certain parameter sets. Further, we show that, when $m=3$ or $4$ and $v > m$, a $(v,m,k,\lambda)$-SEDF does not exist., Comment: Revision notes: Result on abelian 2-groups has been retracted. Other minor errors corrected; notational consistency is improved

Let $X \subset {\mathbb R}^m$ be a spherical code (i.e., a finite subset of the unit sphere) and consider the ideal of all polynomials in $m$ variables which vanish on $X$. Motivated by a study of cometric ($Q$-polynomial) association schemes and spherical designs, we wish to determine certain properties of this ideal. After presenting some background material and preliminary results, we consider the case where $X$ is the set of shortest vectors of one of the exceptional lattices $E_6$, $E_7$, $E_8$, $\Lambda_{24}$ (the Leech lattice) and determine for each: (i) the smallest degree of a non-trivial polynomial in the ideal, and (ii) the smallest $k$ for which the ideal admits a generating set of polynomials all of degree $k$ or less. As it turns out, in all four cases mentioned above, these two values coincide, as they also do for the icosahedron, our introductory example. The paper concludes with a discussion of these two parameters, two open problems regarding their equality, and a few remarks concerning connections to cometric association schemes., Comment: 21 pages

Inspired by some intriguing examples, we study uniform association schemes and uniform coherent configurations, including cometric Q-antipodal association schemes. After a review of imprimitivity, we show that an imprimitive association scheme is uniform if and only if it is dismantlable, and we cast these schemes in the broader context of certain --- uniform --- coherent configurations. We also give a third characterization of uniform schemes in terms of the Krein parameters, and derive information on the primitive idempotents of such a scheme. In the second half of the paper, we apply these results to cometric association schemes. We show that each such scheme is uniform if and only if it is Q-antipodal, and derive results on the parameters of the subschemes and dismantled schemes of cometric Q-antipodal schemes. We revisit the correspondence between uniform indecomposable three-class schemes and linked systems of symmetric designs, and show that these are cometric Q-antipodal. We obtain a characterization of cometric Q-antipodal four-class schemes in terms of only a few parameters, and show that any strongly regular graph with a ("non-exceptional") strongly regular decomposition gives rise to such a scheme. Hemisystems in generalized quadrangles provide interesting examples of such decompositions. We finish with a short discussion of five-class schemes as well as a list of all feasible parameter sets for cometric Q-antipodal four-class schemes with at most six fibres and fibre size at most 2000, and describe the known examples. Most of these examples are related to groups, codes, and geometries., Comment: 42 pages, 1 figure, 1 table. Published version, minor revisions, April 2013

Association schemes were originally introduced by Bose and his co-workers in the design of statistical experiments. Since that point of inception, the concept has proved useful in the study of group actions, in algebraic graph theory, in algebraic coding theory, and in areas as far afield as knot theory and numerical integration. This branch of the theory, viewed in this collection of surveys as the "commutative case," has seen significant activity in the last few decades. The goal of the present survey is to discuss the most important new developments in several directions, including Gelfand pairs, cometric association schemes, Delsarte Theory, spin models and the semidefinite programming technique. The narrative follows a thread through this list of topics, this being the contrast between combinatorial symmetry and group-theoretic symmetry, culminating in Schrijver's SDP bound for binary codes (based on group actions) and its connection to the Terwilliger algebra (based on combinatorial symmetry). We propose this new role of the Terwilliger algebra in Delsarte Theory as a central topic for future work., Comment: 36 pages

Let $\Omega=\{1,2,...,n\}$ where $n \ge 2$. The {\em shape} of an ordered set partition $P=(P_1,..., P_k)$ of $\Omega$ is the integer partition $\lambda=(\lambda_1,...,\lambda_k)$ defined by $\lambda_i = |P_i|$. Let G be a group of permutations acting on $\Omega$. For a fixed partition $\lambda$ of n, we say that G is {\em $\lambda$-transitive} if G has only one orbit when acting on partitions P of shape $\la$. A corresponding definition can also be given when G is just a set. For example, if $\lambda=(n-t,1,...,1)$, then a $\lambda$-transitive group is the same as a t-transitive permutation group and if $\lambda=(n-t,t)$, then we recover the t-homogeneous permutation groups. In this paper, we use the character theory of the symmetric group $S_n$ to establish some structural results regarding $\lambda$-transitive groups and sets. In particular, we are able to generalize a theorem of Livingstone and Wagner about t-homogeneous groups. We survey the relevant examples coming from groups. While it is known that a finite group of permutations can be at most 5-transitive unless it contains the alternating group, we show that it is possible to construct a non-trivial t-transitive set of permutations for each positive integer t. We also show how these ideas lead to a split basis for the association scheme of the symmetric group., Comment: 13 pages