Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

Error Estimates for Two Filters Based on Polynomial Interpolation for Recovering a Function from Its Fourier Coefficients

In this paper we derive error estimates for two filters based on piecewise polynomial interpolations of zeroth and first degrees. For a piecewise smooth function f(x) in [0,1], we show that, if all the discontinuity points of f(x) are nodes then, using these filters, we can reconstruct point values of f(x) accurately even near discontinuity points. If f(x) is a piecewise constant or a linear function, the reconstruction formulas are exact. We also propose reconstruction formulas such that we can compute the (approximate ) point values of f(x) using the fast Fourier transform, even when using non-uniform meshes. Several numerical experiments are also provided to illustrate the results.     

Noisy colored point set matching

We propose a process for determining approximated matches, in terms of the bottleneck distance, under color preserving rigid motions, between two colored point sets A,B∈R², |A|≤|B|. We solve the matching problem by generating all representative motions that bring A close to a subset B^′ of set B and then using a graph matching algorithm. We also present an approximate matching algorithm with improved computational time. In order to get better running times for both algorithms we present a lossless filtering preprocessing step. By using it, we determine some candidate zones which are regions that contain a subset S of B such that A may match one or more subsets B^′ of S. Then, we solve the matching problem between A and every candidate zone. Experimental results using both synthetic and real data are reported to prove the effectiveness of the proposed approach.     

Ordering arc-reversal operations when eliminating variables in lazy AR propagation

This paper considers the problem of ordering arc-reversal operations and breaking ties in cost measures when eliminating variables in Lazy AR Propagation (LPAR). In particular, the paper presents the BreakTies algorithm for breaking ties in cost measures when selecting the next arc to reverse in a variable elimination operation. BreakTies is based upon using a sequence of cost measures instead of randomly selecting an arc to reverse when multiple arcs share the same cost. The paper reports on an experimental evaluation of LPAR for belief update in Bayesian networks considering six sequences of five cost measures for breaking ties using BreakTies. The experimental results show that using BreakTies to select the next arc to reverse in a variable elimination operation can improve performance of LPAR.     

On Two Measures of Problem Instance Complexity and their Correlation with the Performance of SeDuMi on Second-Order Cone Problems

We evaluate the practical relevance of two measures of conic convex problem complexity as applied to second-order cone problems solved using the homogeneous self-dual (HSD) embedding model in the software SeDuMi. The first measure we evaluate is Renegar's data-based condition measure C(d), and the second measure is a combined measure of the optimal solution size and the initial infeasibility/optimality residuals denoted by S (where the solution size is measured in a norm that is naturally associated with the HSD model). We constructed a set of 144 second-order cone test problems with widely distributed values of C(d) and S and solved these problems using SeDuMi. For each problem instance in the test set, we also computed estimates of C(d) (using Peña’s method) and computed S directly. Our computational experience indicates that SeDuMi iteration counts and log (C(d)) are fairly highly correlated (sample correlation R = 0.675), whereas SeDuMi iteration counts are not quite as highly correlated with S (R = 0.600). Furthermore, the experimental evidence indicates that the average rate of convergence of SeDuMi iterations is affected by the condition number C(d) of the problem instance, a phenomenon that makes some intuitive sense yet is not directly implied by existing theory.     

A parallel implementation of overlapping Schwarz method for the dual reciprocity method

We present a parallel algorithm for the overlapping domain decomposition boundary integral equation method for two dimensional partial differential equations. In addition to the improvement of the ill-conditioning and the computational efficiency achieved by domain partitioning, using a parallel computer with p processors can offer up to p times efficiency. Assuming direct solution is used throughout, partitioning the domain into p subregions and employing a processor for each subproblem, overall, result in p² times efficiency over using a single domain and a single processor, taking into account that a sequential algorithm of the underlying method can improve the computational efficiency at least p times over using a single domain. Some numerical results showing the efficiency of the parallel technique will be presented.     

Potentials and reduced games for share functions

A value function for cooperative games with transferable utility assigns to every game a distribution of the payoffs. A value function is efficient if for every such a game it exactly distributes the worth that can be obtained by all players cooperating together. An approach to efficiently allocate the worth of the ‘grand coalition’ is using share functions which assign to every game a vector whose components sum up to one. Every component of this vector is the corresponding players’ share in the total payoff that is to be distributed. In this paper we give characterizations of a class of share functions containing the Shapley share function and the Banzhaf share function using generalizations of potentials and of Hart and Mas-Colell's reduced game property.     

An aperiodic hexagonal tile

We show that a single prototile can fill space uniformly but not admit a periodic tiling. A two-dimensional, hexagonal prototile with markings that enforce local matching rules is proven to be aperiodic by two independent methods. The space-filling tiling that can be built from copies of the prototile has the structure of a union of honeycombs with lattice constants of n²a, where a sets the scale of the most dense lattice and n takes all positive integer values. There are two local isomorphism classes consistent with the matching rules and there is a nontrivial relation between these tilings and a previous construction by Penrose. Alternative forms of the prototile enforce the local matching rules by shape alone, one using a prototile that is not a connected region and the other using a three-dimensional prototile.     

Detection of point-like scatterers using one type of scattered elastic waves

In this paper, we are concerned with the detection of point-like obstacles using elastic waves. We show that one type of waves, either the P or the S scattered waves, is enough for localizing the points. We also show how the use of S incident waves gives better resolution than the P waves. These affirmations are demonstrated by several numerical examples using a MUSIC type algorithm.     

Traveling waves for non-local delayed diffusion equations via auxiliary equations

In this paper, we study the existence of traveling wave solutions for a class of delayed non-local reaction-diffusion equations without quasi-monotonicity. The approach is based on the construction of two associated auxiliary reaction-diffusion equations with quasi-monotonicity and a profile set in a suitable Banach space by using the traveling wavefronts of the auxiliary equations. Under monostable assumption, by using the Schauder's fixed point theorem, we then show that there exists a constant c_∗>0 such that for each c>c_∗, the equation under consideration admits a traveling wavefront solution with speed c, which is not necessary to be monotonic.     

Randomness notions and partial relativization

We study the computational complexity of an oracle set using a number of notions of randomness that lie between Martin-L?f randomness and 2-randomness in terms of strength. These notions are weak 2-randomness, weak randomness relative to ???, Demuth randomness and Schnorr randomness relative to ???. We characterize the oracles A such that ML[A] ? C, where C is such a randomness notion and ML[A] denotes the Martin-L?f random reals relative to A, using a new meta-concept called partial relativization. We study the reducibility associated with weak 2-randomness and relate it with LR-reducibility.     

On the maximal number of pairwise orthogonal Steiner triple systems

For some time it has been known that for prime powers p^k = 1 + 3 · 2^st there exists a pair of orthogonal Steiner triple systems of order p^k. In fact, such a pair can be constructed using the method of Mullin and Nemeth for constructing strong starters. We use a generalization of the construction of Mullin and Nemeth to construct sets of mutually orthogonal Steiner triple systems for many of these prime powers. By using other techniques we show that a set of mutually orthogonal Steiner triple systems of any given size can be constructed for all but a finite number of such prime powers.     

Combining evolutionary and stochastic gradient techniques for system identification

In the present contribution, a novel method combining evolutionary and stochastic gradient techniques for system identification is presented. The method attempts to solve the AutoRegressive Moving Average (ARMA) system identification problem using a hybrid evolutionary algorithm which combines Genetic Algorithms (GAs) and the Least Mean Squares LMS algorithm. More precisely, LMS is used in the step of the evaluation of the fitness function in order to enhance the chromosomes produced by the GA. Experimental results demonstrate that the proposed method manages to identify unknown systems, even in cases with high additive noise. Furthermore, it is observed that, in most cases, the proposed method finds the correct order of the unknown system without using a lot of a priori information, compared to other system identification methods presented in the literature. So, the proposed hybrid evolutionary algorithm builds models that not only have small MSE, but also are very similar to the real systems. Except for that, all models derived from the proposed algorithm are stable.     

The ordinary quiver of a weight three block of the symmetric group is bipartite

Suppose F is a field of characteristic p?5, and that B is a p-block of the symmetric group Sn of defect 3. We prove that the Ext¹-quiver of B is bipartite, with the bipartition being described in a simple way using the leg-lengths of p-hooks of partitions.     

Existence and Regularity of Solutions to Model for Liquid Mixture of He-He

Existence and regularity of solutions to model for liquid mixture of ³He-⁴He is considered in this paper. First, it is proved that this system possesses a unique global weak solution in H¹(ω,C×R) by using Galerkin method. Secondly, by using an iteration procedure, regularity estimates for the linear semigroups, it is proved that the model for liquid mixture of ³He-⁴He has a unique solution in H^k(ω,C×R) for all k ≥ 1.     

An assessment of streamline curvature effects on the mixing region of a turbulent plane jet in crossflow

The flow field of a turbulent plane jet in a weak or moderate crossflow, which is characterised by mild streamline curvature, has been investigated computationally. The values of the jet-to-crossflow velocity ratios chosen are 6, 9 and 10. The time-averaged Navier–Stokes equations are solved on a staggered Cartesian grid using the standard k–ϵ model and the k–ϵ model with streamline curvature modification. The predictions using both the models are compared with available experimental data. It has been shown that by accounting for the effect of streamline curvature in the k–ϵ model results in good prediction of this flow configuration.     

Optimal approximation and quantisation

A number of interesting functionals F(X) of a finite point set X in the Euclidean space can be represented as integrals of a function η that depends on the integration variable y and X restricted onto a certain set C(y,X) that is determined by y and X and satisfies separation and uniform boundedness conditions. For instance, C(y,X) can be the Voronoi cell generated by X that contains y. We single out the general properties of C and η that ensure that the normalised infimum of F(X) over all sets X with cardinality n converges to a limit that can be identified using a particular form of η. The considered functionals include those that appear in quantisation problems for probability measures, and in finding the optimal approximation of a function by splines, tangent planes and triangulated surfaces. For instance, it is shown that the minimum Lβ-approximation error (normalised by nβ) of a sufficiently smooth bivariate convex function f using the convex triangulation converges to the L1/(β+1)-norm of the determinant of the second derivative of f times a certain absolute constant.     

Factoring matrices with a tree-structured sparsity pattern

Let A be a matrix whose sparsity pattern is a tree with maximal degree d_max. We show that if the columns of A are ordered using minimum degree on |A|+|A|^∗, then factoring A using a sparse LU with partial pivoting algorithm generates only O(d_maxn) fill, requires only O(d_maxn) operations, and is much more stable than LU with partial pivoting on a general matrix. We also propose an even more efficient and just-as-stable algorithm called sibling-dominant pivoting. This algorithm is a strict partial pivoting algorithm that modifies the column preordering locally to minimize fill and work. It leads to only O(n) work and fill. More conventional column pre-ordering methods that are based (usually implicitly) on the sparsity pattern of |A|^∗|A| are not as efficient as the approaches that we propose in this paper.     

Very large cliques are easy to detect

It is known that, for every constant k?3, the presence of a k-clique (a complete sub-graph on k vertices) in an n-vertex graph cannot be detected by a monotone boolean circuit using much fewer than n^k gates. We show that, for every constant k, the presence of an (n-k)-clique in an n-vertex graph can be detected by a monotone circuit using only a logarithmic number of fanin-2 OR gates; the total number of gates does not exceed O(n²logn). Moreover, if we allow unbounded fanin, then a logarithmic number of gates is enough.     

Examples from trees, related to discrete subsets, pseudo-radiality and ω-boundedness

We construct some examples using trees. Some of them are consistent counterexamples for the discrete reflection of certain topological properties. All the properties dealt with here were already known to be non-discretely reflexive if we assume CH and we show that the same is true assuming the existence of a Suslin tree. In some cases we actually get some ZFC results. We construct also, using a Suslin tree, a compact space that is pseudo-radial but it is not discretely generated. With a similar construction, but using an Aronszajn tree, we present a ZFC space that is first countable, ω-bounded but is not strongly ω-bounded, answering a question of Peter Nyikos.