Measurable Sets With Excluded Distances

For a set of distances D = {d ₁,..., d _k } a set A is called D-avoiding if no pair of points of A is at distance d _i for some i. We show that the density of A is exponentially small in k provided the ratios d ₁/d ₂, d ₂/d ₃, …, d _k-1/d _k are all small enough. This resolves a question of Székely, and generalizes a theorem of Furstenberg–Katznelson–Weiss, Falconer–Marstrand, and Bourgain. Several more results on D-avoiding sets are presented. Received: January 2007, Revision: February 2008, Accepted: February 2008     

Sampling in Paley-Wiener spaces on combinatorial graphs

A notion of Paley-Wiener spaces on combinatorial graphs is introduced. It is shown that functions from some of these spaces are uniquely determined by their values on some sets of vertices which are called the uniqueness sets. Such uniqueness sets are described in terms of Poincare-Wirtinger-type inequalities. A reconstruction algorithm of Paley-Wiener functions from uniqueness sets which uses the idea of frames in Hilbert spaces is developed. Special consideration is given to the -dimensional lattice, homogeneous trees, and eigenvalue and eigenfunction problems on finite graphs.

     

Links and cubic 3-polytopes

It is well known that a prime link diagram corresponds to a signed plane graph without cut vertices (Kauffman, 1989). In this paper, we present a new relation between prime links and cubic 3-polytopes. Let be the set of links such that each has a diagram whose corresponding signed plane graph is the graph of a cubic 3-polytope. We show that all nontrivial prime links, except -torus links and -pretzel links, can be obtained from by using some operation of untwining. Furthermore, we define the generalized cubic 3-polytope chains and then show that any nontrivial link can be obtained from by some untwining operations, where is the set of links corresponding to generalized cubic 3-polytope chains. These results are used to simplify the computation of the Kauffman brackets of links so that the computing can be done in a unified way for many infinite families of links.

     

On stable cutsets in claw-free graphs and planar graphs

A stable cutset in a connected graph is a stable set whose deletion disconnects the graph. Let $K_4$ and $K_{1,3}$ (claw) denote the complete (bipartite) graph on 4 and $1+3$ vertices. It is NP-complete to decide whether a line graph (hence a claw-free graph) with maximum degree five or a $K_4$-free graph admits a stable cutset. Here we describe algorithms deciding in polynomial time whether a claw-free graph with maximum degree at most four or whether a (claw, $K_4$)-free graph admits a stable cutset. As a by-product we obtain that the stable cutset problem is polynomially solvable for claw-free planar graphs, and also for planar line graphs.Thus, the computational complexity of the stable cutset problem is completely determined for claw-free graphs with respect to degree constraint, and for claw-free planar graphs. Moreover, we prove that the stable cutset problem remains NP-complete for $K_4$-free planar graphs with maximum degree five.     

Structural and electronic effects involving pyridine rings in 4-methylpyridine Cu4OX6L4 complexes. II. Correlations based on molecular structure of the Cu4OCl6(4-Mepy)4 complex

Correlations involving bond lengths and bond angles in the molecular structure of the Cu₄OCl₆(4-Mepy)₄ complex (4-Mepy = 4-methylpyridine) with four symmetrically independent molecules present in the unit cell showed that the donor-acceptor behavior involving the π-back donation into the pyridine rings of the 4-Mepy ligands is most effectively stimulated by a suitable orientation of the pyridine rings in the trigonal bipyramidal geometry. The pyridine ring planes are almost in parallel orientation with one of the three Cu-Cl bonds. The bond lengths of these Cu-Cl bonds are in a significant linear correlation with the Cu-N bond lengths and the bonds lengths of the pyridine rings. The pyridine rings orientation is affected by distortion of the trigonal bipyramidal geometry to tetragonal pyramidal coordination, by out-of plane pyridine rings deviation and in-plane pyridine rings tilting, by puckering of the pyridine rings and by the effects of the methyl groups. The pyridine rings in at least seven of the sixteen trigonal bipyramidal coordinations exhibit an orientation supporting the π-back bonding between the Cu(II) atoms and the pyridine rings.     

1,2,4-triazolium-cation-based energetic salts

3,4,5-Triamino-1,2,4-triazole (guanazine, 1) can be readily methylated with methyl iodide yielding methylguanazinium iodide (2). Salts containing the novel methylguanazinium cation with energetic anions were synthesised by metathesis reactions with silver azide (3), silver nitrate (4), silver perchlorate (5), sodium 5,5'-azotetrazolate (6), silver 5-nitrotetrazolate (7) and silver dinitramide (8), yielding a new family of heterocycle-based salts, which were fully characterised by analytical (mass spectrometry and elemental analysis) and spectroscopic methods (IR, Raman and NMR). In addition, the molecular structures of all compounds were confirmed by X-ray analysis, revealing extensive hydrogen-bonding in the solid state and densities between 1.399 (3) and 1.669 g cm(-3) (5). The hydrogen-bonded ring motifs are discussed in the formalism of graph-set analysis for hydrogen-bond patterns and compared to each other. Preliminary sensitivity testing of the crystalline compounds indicate surprisingly low sensitivities to both friction and impact, the highest friction and shock sensitivity being found for the perchlorate (5, 220 N) and the dinitramide (8, 20 J) salts, respectively. In addition, DSC analysis was used to assess the thermal stabilities of the compounds: 3-6 melt above 200 degrees C with concomitant decomposition, whereas 7 and 8 have clearly defined melting points at 162 and 129 degrees C, respectively, and with decomposition occurring about 30 degrees C above the melting point. Lastly all compounds have positive calculated heats of formation between 336 (4) and 4070 kJ kg(-1) (6) and calculated detonation velocities in the range between 8330 (7) and 8922 m s(-1) (6) making them of interest as new highly energetic materials with low sensitivity.     

A Totally(Δ+1)-colorable 1-planar Graph with Girth at Least Five

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge.In this paper,we prove that every 1-planar graph G with maximum degree Δ(G)≥12 and girth at least five is totally(Δ(G)+1)-colorable.     

An Enumeration of Certain Projective Ternary Two‐Weight Codes

We detail the enumeration of all two‐intersection sets of the five‐dimensional projective space over the field of order 3 that are invariant under an element of order 7, which include the examples of Hill (1973) and Gulliver (1996). Up to projective equivalence, there are 6,635 such two‐intersection sets.     

Asynchronous cellular automata and pattern classification

This article designs an efficient two‐class pattern classifier utilizing asynchronous cellular automata (ACAs). The two‐state three‐neighborhood one‐dimensional ACAs that converge to fixed points from arbitrary seeds are used here for pattern classification. To design the classifier, (1) we first identify a set of ACAs that always converge to fixed points from any seeds, (2) each ACA should have at least two but not huge number of fixed point attractors, and (3) the convergence time of these ACAs are not to be exponential. To address the second issue, we propose a graph, coined as fixed point graph of an ACA that facilitates in counting the fixed points. We further perform an experimental study to estimate the convergence time of ACAs, and find there are some convergent ACAs which demand exponential convergence time. Finally, we identify there are 73 (out of 256) ACAs which can be effective candidates as pattern classifier. We use each of the candidate ACAs on some standard datasets, and observe the effectiveness of each ACAs as pattern classifier. It is observed that the proposed classifier is very competitive and performs reliably better than many standard existing classifier algorithms. © 2016 Wiley Periodicals, Inc. Complexity 21: 370–386, 2016     

一个特殊6点图Q与nK_1,P_n及C_n的联图交叉数

图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是NP-难问题,因为其难度,能够确定交叉数的图类很少.通过圆盘画法途径,确定了一个特殊6点图与n个孤立点nK_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+2[n/2],cr(Q+P_n)=Z(6,n)+2[n/2]+1及cr(Q+C_n)=Z(6,n)+2[n/2]+3.