On a generalization of the Evans Conjecture

The Evans Conjecture states that a partial Latin square of order n with at most n-1 entries can be completed. In this paper we generalize the Evans Conjecture by showing that a partial r-multi Latin square of order n with at most n-1 entries can be completed. Using this generalization, we confirm a case of a conjecture of Häggkvist.     

On the topology of the Kasparov groups and its applications

In this paper we establish a direct connection between stable approximate unitary equivalence for *-homomorphisms and the topology of the KK-groups which avoids entirely C^*-algebra extension theory and does not require nuclearity assumptions. To this purpose we show that a topology on the Kasparov groups can be defined in terms of approximate unitary equivalence for Cuntz pairs and that this topology coincides with both Pimsner's topology and the Brown-Salinas topology. We study the generalized Rørdam group , and prove that if a separable exact residually finite dimensional C^*-algebra satisfies the universal coefficient theorem in KK-theory, then it embeds in the UHF algebra of type 2^∞. In particular such an embedding exists for the C^*-algebra of a second countable amenable locally compact maximally almost periodic group.     

Convolutions of singular measures and applications to the Zakharov system

Uniform L²-estimates for the convolution of singular measures with respect to transversal submanifolds are proved in arbitrary space dimension. The results of Bennett-Bez are used to extend previous work of Bejenaru-Herr-Tataru. As an application, it is shown that the 3D Zakharov system is locally well-posed in the full subcritical regime.     

Some applications of free Fisher information on frame theory

We introduce the notion of operator-valued free Fisher information with respect to a positive map of a random variable in an operator-valued noncommutative probability space and point out its close relations to the modular frames arising from conditional expectations. Then we can apply this notion on the study of frame theory, especially on the disjointness problem of modular frames arising from conditional expectations.     

Scattering matrices of regular coverings of graphs

We give a decomposition formula for the determinant on the bond scattering matrix of a regular covering of G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we express the determinant on the bond scattering matrix of a regular covering of G by means of its L-functions.     

Binary relations and reduced hypergroups

Different partial hypergroupoids are associated with binary relations defined on a set H. In this paper we find sufficient and necessary conditions for these hypergroupoids in order to be reduced hypergroups. Given two binary relations ρ and σ on H we investigate when the hypergroups associated with the relations ρ∩σ, ρ∪σ and ρσ are reduced. We also determine when the cartesian product of two hypergroupoids associated with a binary relation is a reduced hypergroup.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

Super-simple, pan-orientable and pan-decomposable GDDs with block size 4

In this paper we study (4,2μ)-GDDs of type gⁿ possessing both the pan-decomposable property introduced by Granville, Moisiadis, Rees, On complementary decompositions of the complete graph, Graphs and Combinatorics 5 (1989) 57-61 and the pan-orientable property introduced by Grüttmüller, Hartmann, Pan-orientable block designs, Australas. J. Combin. 40 (2008) 57-68. We show that the necessary condition for a (4,2μ)-GDD satisfying both of these properties, namely (1) n≥4, μg(n−1)≡0 (mod 3), and (2) g−1,n are not both even if μ is odd are sufficient. When λ=2, our designs are super-simple.We also determine the spectrum of (4,2)-GDDs which are super-simple and possess some of the decomposable/orientable conditions, but are not pan-decomposable or pan-orientable. In particular, we show that the necessary conditions for a super-simple directable (4,2)-GDD of type gⁿ are sufficient.     

A note on the rank parity function

We provide some further theorems on the partitions generated by the rank parity function. New Bailey pairs are established, which are of independent interest.     

Bounding the size of square-free subgraphs of the hypercube

We investigate the maximum size of a subset of the edges of the n-cube that does not contain a square, or 4-cycle. The size of such a subset is trivially at most 3/4 of the total number of edges, but the proportion was conjectured by Erd?s to be asymptotically 1/2. Following a computer investigation of the 4-cube and the 5-cube, we improve the known upper bound from 0.62284… to 0.62256… in the limit.     

Moore bound for mixed networks

Mixed graphs contain both undirected as well as directed links between vertices and therefore are an interesting model for interconnection communication networks. In this paper, we establish the Moore bound for mixed graphs, which generalizes both the directed and the undirected Moore bound.     

Graph designs for the eight-edge five-vertex graphs

The existence of graph designs for the two nonisomorphic graphs on five vertices and eight edges is determined in the case of index one, with three possible exceptions in total. It is established that for the unique graph with vertex sequence (3, 3, 3, 3, 4), a graph design of order n exists exactly when and n≠16, with the possible exception of n=48. For the unique graph with vertex sequence (2,3,3,4,4), a graph design of order n exists exactly when , with the possible exceptions of n∈{32,48}.     

On symmetric graphs of valency five

A graph X, with a subgroup G of the automorphism group of X, is said to be (G,s)-transitive, for some s≥1, if G is transitive on s-arcs but not on (s+1)-arcs, and s-transitive if it is -transitive. Let X be a connected (G,s)-transitive graph, and G_v the stabilizer of a vertex v∈V(X) in G. If X has valency 5 and G_v is solvable, Weiss [R.M. Weiss, An application of p-factorization methods to symmetric graphs, Math. Proc. Camb. Phil. Soc. 85 (1979) 43-48] proved that s≤3, and in this paper we prove that G_v is isomorphic to the cyclic group Z₅, the dihedral group D₁₀ or the dihedral group D₂₀ for s=1, the Frobenius group F₂₀ or F₂₀×Z₂ for s=2, or F₂₀×Z₄ for s=3. Furthermore, it is shown that for a connected 1-transitive Cayley graph of valency 5 on a non-abelian simple group G, the automorphism group of is the semidirect product , where R(G) is the right regular representation of G and .     

A general two-sided matching market with discrete concave utility functions

In the theory of two-sided matching markets there are two standard models: (i) the marriage model due to Gale and Shapley and (ii) the assignment model due to Shapley and Shubik. Recently, Eriksson and Karlander introduced a hybrid model, which was further generalized by Sotomayor. In this paper, we propose a common generalization of these models by utilizing the framework of discrete convex analysis introduced by Murota, and verify the existence of a pairwise-stable outcome in our general model.     

On (d,1)-total numbers of graphs

A (d,1)-total labelling of a graph G assigns integers to the vertices and edges of G such that adjacent vertices receive distinct labels, adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least d. The span of a (d,1)-total labelling is the maximum difference between two labels. The (d,1)-total number, denoted , is defined to be the least span among all (d,1)-total labellings of G. We prove new upper bounds for , compute some for complete bipartite graphs K_m,n, and completely determine all for d=1,2,3. We also propose a conjecture on an upper bound for in terms of the chromatic number and the chromatic index of G.     

A new Bartholdi zeta function of a digraph II

We introduce a new type of the Bartholdi zeta function of a digraph D. Furthermore, we define a new type of the Bartholdi L-function of D, and give a determinant expression of it. We show that this L-function of D is equal to the L-function of D defined in [H. Mizuno, I. Sato, A new Bartholdi zeta function of a digraph, Linear Algebra Appl. 423 (2007) 498-511]. As a corollary, we obtain a decomposition formula for a new type of the Bartholdi zeta function of a group covering of D by new Bartholdi L-functions of D.     

Growth conditions, compact perturbations and operator subdecomposability, with applications to generalized Cesàro operators

We adapt recent results of Albrecht and Ricker to obtain conditions under which growth constraints on the left resolvent of a Banach space operator are preserved under suitable perturbations. As an application, we establish Bishop's property (β) for certain generalized Cesàro operators on the classical Hardy spaces Hp, 1<p<∞. Our methods also apply to unilateral weighted shifts whose weight sequence converges sufficiently rapidly as well as to perturbations of restrictions of a class of generalized scalar operators.     

The poset structures admitting the extended binary Golay code to be a perfect code

Brualdi et al. [Codes with a poset metric, Discrete Math. 147 (1995) 57-72] introduced the concept of poset codes, and gave an example of poset structure which admits the extended binary Golay code to be a 4-error-correcting perfect P-code. In this paper we classify all of the poset structures which admit the extended binary Golay code to be a 4-error-correcting perfect P-code, and show that there are no posets which admit the extended binary Golay code to be a 5-error-correcting perfect P-code.     

On (s,t)-supereulerian graphs in locally highly connected graphs

Given two nonnegative integers s and t, a graph G is (s,t)-supereulerian if for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y|≤t, there is a spanning eulerian subgraph H of G that contains X and avoids Y. We prove that if G is connected and locally k-edge-connected, then G is (s,t)-supereulerian, for any pair of nonnegative integers s and t with s+t≤k−1. We further show that if s+t≤k and G is a connected, locally k-edge-connected graph, then for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y≤t, there is a spanning eulerian subgraph H that contains X and avoids Y, if and only if G−Y is not contractible to K₂ or to K_2,l with l odd.