Strongly Regular Decompositions of the Complete Graph

We study several questions about amorphic association schemes and other strongly regular decompositions of the complete graph. We investigate how two commuting edge-disjoint strongly regular graphs interact. We show that any decomposition of the complete graph into three strongly regular graphs must be an amorphic association scheme. Likewise we show that any decomposition of the complete graph into strongly regular graphs of (negative) Latin square type is an amorphic association scheme. We study strongly regular decompositions of the complete graph consisting of four graphs, and find a primitive counterexample to A.V. Ivanov's conjecture which states that any association scheme consisting of strongly regular graphs only must be amorphic.     

Some implications on amorphic association schemes

We give an overview of results on amorphic association schemes. We give the known constructions of such association schemes, and enumerate most such association schemes on up to 49 vertices. Special attention is paid to cyclotomic association schemes. We give several results on when a strongly regular decomposition of the complete graph is an amorphic association scheme. This includes a new proof of the result that a decomposition of the complete graph into three strongly regular graphs is an amorphic association scheme, and the new result that a strongly regular decomposition of the complete graph for which the union of any two relations is again strongly regular must be an amorphic association scheme.     

Amorphic association schemes with negative Latin square-type graphs

Applying results from partial difference sets, quadratic forms, and recent results of Brouwer and Van Dam, we construct the first known amorphic association scheme with negative Latin square-type graphs and whose underlying set is a nonelementary abelian 2-group. We give a simple proof of a result of Hamilton that generalizes Brouwer's result. We use multiple distinct quadratic forms to construct amorphic association schemes with a large number of classes.     

C-algebras and algebras in plancherel duality

For an arbitrary (possibly noncommutative) C-algebra, a positivity condition generalizing the Krein condition for a commutative case is defined. We show that the class of positive C-algebras includes those arising in algebraic combinatorics from association schemes (possibly noncommutative). It is proved that the category of positive C-algebras is equivalent to the category of pairs of algebras in Plancherel duality, one of which is commutative.Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 240, 1997, pp. 53–66.     

Association schemes,fusion rings,C-algebras,and reality-based algebras where all nontrivial multiplicities are equal

Multiplicities corresponding to irreducible characters are defined for reality-based algebras. These algebras with a distinguished basis include fusion rings, C-algebras, and the adjacency algebras of finite association schemes. The definition of multiplicity generalizes that for schemes. For a broad class of these structures, which includes the adjacency algebras, it is proved that if all the nontrivial multiplicities are equal then the algebra is commutative, and is a C-algebra if its dimension is larger than two.     

有限Hopf C~*-代数的表示与对偶

设A是有限维Hopf C-代数,H是Hilbert空间.如果存在A在L(H)上的作用γ,在此作用下,L(H)成为具有共轭性质的模代数且H上内积是A-不变的,则A存在惟一的C-表示(θ,H),L(H)的A-不变子空间恰好是θ(A)的换位子.     

Association Schemes and Fusion Algebras (An Introduction)

We introduce the concept of fusion algebras at algebraic level, as a purely algebraic concept for the fusion algebras which appear in conformal field theory in mathematical physics. We first discuss the connection between fusion algebras at algebraic level and character algebras, a purely algebraic concept for Bose-Mesner algebras of association schemes. Through this correspondence, we establish the condition when the matrix S of a fusion algebra at algebraic level is unitary or symmetric. We construct integral fusion algebras at algebraic level, from association schemes, in particular from group association schemes, whose matrix S is unitary and symmetric. Finally, we consider whether the modular invariance property is satisfied or not, namely whether there exists a diagonal matrix T satisfying the condition (ST)³ = S ². We prove that this property does not hold for some integral fusion algebras at algebraic level coming from the group association scheme of certain groups of order 64, and we also prove that the (nonintegral) fusion algebra at algebraic level obtained from the Hamming association scheme H(d, q) has the modular invariance property.     

Finiteness of U‐rank implies simplicity in homogeneous structures

A (large) superstable homogeneous structure is said to be simple if every complete type over any set A has a free extension over any B ? A. In this paper we give a characterization for this property in terms of U‐rank. As a corollary we get that if the structure has finite U‐rank, then it is simple. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Imprimitive cometric association schemes: Constructions and analysis

Dualizing the “extended bipartite double” construction for distance-regular graphs, we construct a new family of cometric (or Q-polynomial) association schemes with four associate classes based on linked systems of symmetric designs. The analysis of these new schemes naturally leads to structural questions concerning imprimitive cometric association schemes, some of which we answer with others being left as open problems. In particular, we prove that any Q-antipodal association scheme is dismantlable: the configuration induced on any subset of the equivalence classes in the Q-antipodal imprimitivity system is again a cometric association scheme. Further examples are explored. Dedicated to the memory of Dom de Caen, 1956—2002.     

The quantum cohomology of flag varieties and the periodicity of the Schubert structure constants

We give conditions on a curve class that guarantee the vanishing of the structure constants of the small quantum cohomology of partial flag varieties F(k ₁, ..., k _r ; n) for that class. We show that many of the structure constants of the quantum cohomology of flag varieties can be computed from the image of the evaluation morphism. In fact, we show that a certain class of these structure constants are equal to the ordinary intersection of Schubert cycles in a related flag variety. We obtain a positive, geometric rule for computing these invariants (see Coskun in A Littlewood–Richardson rule for partial flag varieties, preprint). Our study also reveals a remarkable periodicity property of the ordinary Schubert structure constants of partial flag varieties.     

Strengthening Erdös–Pósa property for minor‐closed graph classes

Let ?? and ?? be graph classes. We say that ?? has the Erd?s–Pósa property for ?? if for any graph G ∈??, the minimum vertex covering of all ??‐subgraphs of G is bounded by a function f of the maximum packing of ??‐subgraphs in G (by ??‐subgraph of G we mean any subgraph of G that belongs to ??). Robertson and Seymour [J Combin Theory Ser B 41 (1986), 92–114] proved that if ?? is the class of all graphs that can be contracted to a fixed planar graph H, then ?? has the Erd?s–Pósa property for the class of all graphs with an exponential bounding function. In this note, we prove that this function becomes linear when ?? is any non‐trivial minor‐closed graph class. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:235‐240, 2011     

On the vertex connectivity of a relation in an association scheme

We prove that for a sufficiently closed association scheme, the Brouwer conjecture on the coincidence of the vertex connectivity and the degree of any its connected basis relation is true. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 55–62.     

A Linear Algebraic Approach to Metering Schemes

A metering scheme is a method by which an audit agency is able to measure the interaction between servers and clients during a certain number of time frames. Naor and Pinkas (Vol. 1403 of LNCS, pp. 576–590) proposed metering schemes where any server is able to compute a proof (i.e., a value to be shown to the audit agency at the end of each time frame), if and only if it has been visited by a number of clients larger than or equal to some threshold h during the time frame. Masucci and Stinson (Vol. 1895 of LNCS, pp. 72–87) showed how to construct a metering scheme realizing any access structure, where the access structure is the family of all subsets of clients which enable a server to compute its proof. They also provided lower bounds on the communication complexity of metering schemes. In this paper we describe a linear algebraic approach to design metering schemes realizing any access structure. Namely, given any access structure, we present a method to construct a metering scheme realizing it from any linear secret sharing scheme with the same access structure. Besides, we prove some properties about the relationship between metering schemes and secret sharing schemes. These properties provide some new bounds on the information distributed to clients and servers in a metering scheme. According to these bounds, the optimality of the metering schemes obtained by our method relies upon the optimality of the linear secret sharing schemes for the given access structure.     

Designs in Product Association Schemes

A number of important families of association schemes—such as the Hamming and Johnson schemes—enjoy the property that, in each member of the family, Delsarte t-designs can be characterised combinatorially as designs in a certain partially ordered set attached to the scheme. In this paper, we extend this characterisation to designs in a product association scheme each of whose components admits a characterisation of the above type. As a consequence of our main result, we immediately obtain linear programming bounds for a wide variety of combinatorial objects as well as bounds on the size and degree of such designs analogous to Delsarte's bounds for t-designs in Q-polynomial association schemes.     

𝔏-Rickart Modules

It is well known that the Rickart property of rings is not a left-right symmetric property. We extend the notion of the left Rickart property of rings to a general module theoretic setting and define 𝔏-Rickart modules. We study this notion for a right R-module M _R where R is any ring and obtain its basic properties. While it is known that the endomorphism ring of a Rickart module is a right Rickart ring, we show that the endomorphism ring of an 𝔏-Rickart module is not a left Rickart ring in general. If M _R is a finitely generated 𝔏-Rickart module, we prove that End _R (M) is a left Rickart ring. We prove that an 𝔏-Rickart module with no set of infinitely many nonzero orthogonal idempotents in its endomorphism ring is a Baer module. 𝔏-Rickart modules are shown to satisfy a certain kind of nonsingularity which we term “endo-nonsingularity.” Among other results, we prove that M is endo-nonsingular and End _R (M) is a left extending ring iff M is a Baer module and End _R (M) is left cononsingular.     

Equiarboreal graphs

A graphX is said to beequiarboreal if the number of spanning trees containing a specified edge inX is independent of the choice of edge. We prove that any graph which is a colour class in an association scheme (and thus any distance regular graph) is equiarboreal. We note that a connected equiarboreal graph withM edges andn vertices has edge-connectivity at leastM/(n−1).     

Simple <Emphasis Type="Italic">SL</Emphasis>(<Emphasis Type="Italic">n</Emphasis>)-modules with normal closures of maximal torus orbits

Let T be the subgroup of diagonal matrices in the group SL(n). The aim of this paper is to find all finite-dimensional simple rational SL(n)-modules V with the following property: for each point v∈V the closure [`(Tv)]\overline{Tv} of its T-orbit is a normal affine variety. Moreover, for any SL(n)-module without this property a T-orbit with non-normal closure is constructed. The proof is purely combinatorial: it deals with the set of weights of simple SL(n)-modules. The saturation property is checked for each subset in the set of weights.     

Primitive algebraic relations of skew derivations of prime rings

In [1], the question was posed as to whether or not all algebraic relations of skew derivations of prime rings follow from primitive algebraic relations. Here we argue to obtain a negative answer to a milder question, and namely, an example is constructed in which a pointed Hopf algebra H (generated as an algebra with unity by its relatively primitive elements) acts trivially on the generalized centroid C of a prime ring R, but not all algebraic relations of skew derivations (corresponding to relatively primitive elements in H) follow from primitive algebraic ones. The R in the counterexample is a free associative C-algebra. Supported by ISF grant No. RPS300 and by RFFR grant No. 95-01-01356a. Translated from Algebra i Logika, Vol. 36, No. 4, pp. 407–421, July–August, 1997.     

Proximity‐preserving labeling schemes

This article considers informative labeling schemes for graphs. Specifically, the question introduced is whether it is possible to label the vertices of a graph with short labels in such a way that the distance between any two vertices can be inferred from inspecting their labels. A labeling scheme enjoying this property is termed a proximity‐preserving labeling scheme. It is shown that, for the class of n‐vertex weighted trees with M‐bit edge weights, there exists such a proximity‐preserving labeling scheme using O(M log n + log²n) bit labels. For the family of all n‐vertex unweighted graphs, a labeling scheme is proposed that using O(log² n · κ · n^1/κ) bit labels can provide approximate estimates to the distance, which are accurate up to a factor of In particular, using O(log³n) bit labels, the scheme can provide estimates accurate up to a factor of $\sqrt{2 \log n}$. (For weighted graphs, one of the log n factors in the label size is replaced by a factor logarithmic in the network's diameter.) © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 167–176, 2000     

Detection and identification of cheaters in (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">n</Emphasis>) secret sharing scheme

In a (t, n) secret sharing scheme, a secret s is divided into n shares and shared among a set of n shareholders by a mutually trusted dealer in such a way that any t or more than t shares will be able to reconstruct this secret; but fewer than t shares cannot know any information about the secret. When shareholders present their shares in the secret reconstruction phase, dishonest shareholder(s) (i.e. cheater(s)) can always exclusively derive the secret by presenting faked share(s) and thus the other honest shareholders get nothing but a faked secret. Cheater detection and identification are very important to achieve fair reconstruction of a secret. In this paper, we consider the situation that there are more than t shareholders participated in the secret reconstruction. Since there are more than t shares (i.e. it only requires t shares) for reconstructing the secret, the redundant shares can be used for cheater detection and identification. Our proposed scheme uses the shares generated by the dealer to reconstruct the secret and, at the same time, to detect and identify cheaters. We have included discussion on three attacks of cheaters and bounds of detectability and identifiability of our proposed scheme under these three attacks. Our proposed scheme is an extension of Shamir’s secret sharing scheme.