Breaking the rhythm on graphs

We study graph colorings avoiding periodic sequences with large number of blocks on paths. The main problem is to decide, for a given class of graphs F, if there are absolute constants t,k such that any graph from the class has a t-coloring with no k identical blocks in a row appearing on a path. The minimum t for which there is some k with this property is called the rhythm threshold of F, denoted by t(F). For instance, we show that the rhythm threshold of graphs of maximum degree at most d is between (d+1)/2 and d+1. We give several general conditions for finiteness of t(F), as well as some connections to existing chromatic parameters. The question whether the rhythm threshold is finite for planar graphs remains open.     

On the Chaotic Behavior of a Third-Order Log-Domain Filter

Operation of log-domain filters revolves around the large-signal forward-active mode exponential current-voltage relationship of the bipolar junction transistor, which is used to map the input currents to the logarithmic domain, where the analog processing takes place, and to convert the filtered voltage waveforms back to the linear domain. Sometimes, the inherent internal nonlinearity of such circuits is the cause of unwanted externally-nonlinear effects. In this paper a differential third-order log-domain Chebyshev low-pass filter is designed by applying the method of operational simulation of doubly-terminated LC ladders. When the six grounded shunt capacitors of this filter are properly replaced with three half-sized floating capacitors, as is common practice in internally-linear fully-differential capacitively-loaded circuits, under particular conditions the resulting system exhibits limit-cycle oscillations, period-doubling bifurcations and chaotic behavior for zero-input. The presence of chaos is confirmed by extracting the spectrum of Lyapunov exponents of the system from the time series of the output voltage.     

The linear arboricity of graphs

Alinear forest is a forest in which each connected component is a path. Thelinear arboricity la(G) of a graphG is the minimum number of linear forests whose union is the set of all edges ofG. Thelinear arboricity conjecture asserts that for every simple graphG with maximum degree Δ=Δ(G), . Although this conjecture received a considerable amount of attention, it has been proved only for Δ≦6, Δ=8 and Δ=10, and the best known general upper bound for la(G) is la(G)≦⌈3Δ/5⌉ for even Δ and la(G)≦⌈(3Δ+2)/5⌉ for odd Δ. Here we prove that for everyɛ>0 there is a Δ₀=Δ₀(ɛ) so that la(G)≦(1/2+ɛ)Δ for everyG with maximum degree Δ≧Δ₀. To do this, we first prove the conjecture for everyG with an even maximum degree Δ and withgirth g≧50Δ. Research supported in part by Allon Fellowship, by a Bat Sheva de Rothschild grant, by the Fund for Basic Research administered by the Israel Academy of Sciences and by a B.S.F. Bergmann Memorial grant.     

Degrees of freedom versus dimension for containment orders

Given a family of sets L, where the sets in L admit k degrees of freedom, we prove that not all (k+1)-dimensional posets are containment posets of sets in L. Our results depend on the following enumerative result of independent interest: Let P(n, k) denote the number of partially ordered sets on n labeled elements of dimension k. We show that log P(n, k)nk log n where k is fixed and n is large.Research supported in part by Allon Fellowship and by a grant from Bat Sheva de Rothschild Foundation.Research supported in part by the Office of Naval Research, contract number N00014-85-K0622.     

Bipartite subgraphs

It is shown that there exists a positivec so that for any large integerm, any graph with 2m ²edges contains a bipartite subgraph with at least edges. This is tight up to the constantc and settles a problem of Erdös. It is also proved that any triangle-free graph withe>1 edges contains a bipartite subgraph with at least e/2+c e ^4/5 edges for some absolute positive constantc. This is tight up to the constantc.Research supported in part by a USA Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

The maximum size of a convex polygon in a restricted set of points in the plane

Assume we havek points in general position in the plane such that the ratio between the maximum distance of any pair of points to the minimum distance of any pair of points is at mostk, for some positive constant. We show that there exist at leastk ^1/4 of these points which are the vertices of a convex polygon, for some positive constant=(). On the other hand, we show that for every fixed>0, ifk>k(), then there is a set ofk points in the plane for which the above ratio is at most 4k, which does not contain a convex polygon of more thank ^1/3+ vertices.The work of the first author was supported in part by the Allon Fellowship, by the Bat Sheva de Rothschild Foundation, by the Fund for Basic Research administered by the Israel Academy of Sciences, and by the Center for Absorbtion in Science. Work by the second author was supported by the Technion V. P.R. Fund, Grant No. 100-0679. The third author's work was supported by the Natural Sciences and Engineering Research Council, Canada, and the joint project Combinatorial Optimization of the Natural Science and Engineering Research Council (NSERC), Canada, and the German Research Association (Deutsche Forschungsgemeinschaft, SFB 303).     

Covering graphs by the minimum number of equivalence relations

An equivalence graph is a vertex disjoint union of complete graphs. For a graphG, let eq(G) be the minimum number of equivalence subgraphs ofG needed to cover all edges ofG. Similarly, let cc(G) be the minimum number of complete subgraphs ofG needed to cover all its edges. LetH be a graph onn vertices with maximal degree ≦d (and minimal degree ≧1), and letG= \(\bar H\) be its complement. We show that $$\log _2 n - \log _2 d \leqq eq(G) \leqq cc(G) \leqq 2e^2 (d + 1)^2 \log _e n.$$ The lower bound is proved by multilinear techniques (exterior algebra), and its assertion for the complement of ann-cycle settles a problem of Frankl. The upper bound is proved by probabilistic arguments, and it generalizes results of de Caen, Gregory and Pullman.     

Angular broadening in core‐electron spectroscopy

The role of angular broadening in quantitative core‐electron spectroscopy is investigated using an analytic approach. It is shown why, practically, this effect remains relatively small for a broad range of parameters. A correction factor is derived, suggesting that the replacement of inelastic mean free path by an effective attenuation‐length parameter is not necessarily an optimal choice. The derived expression further proposes useful insight on the contribution of leading experimental parameters and, in particular, on the sharp increase of elastic‐scattering corrections above a (depth dependent) critical angle. Copyright © 2015 John Wiley & Sons, Ltd.     

Electron ionization LC‐MS with supersonic molecular beams—the new concept,benefits and applications

A new type of electron ionization LC‐MS with supersonic molecular beams (EI‐LC‐MS with SMB) is described. This system and its operational methods are based on pneumatic spray formation of the LC liquid flow in a heated spray vaporization chamber, full sample thermal vaporization and subsequent electron ionization of vibrationally cold molecules in supersonic molecular beams. The vaporized sample compounds are transferred into a supersonic nozzle via a flow restrictor capillary. Consequently, while the pneumatic spray is formed and vaporized at above atmospheric pressure the supersonic nozzle backing pressure is about 0.15 Bar for the formation of supersonic molecular beams with vibrationally cold sample molecules without cluster formation with the solvent vapor. The sample compounds are ionized in a fly‐though EI ion source as vibrationally cold molecules in the SMB, resulting in ‘Cold EI’ (EI of vibrationally cold molecules) mass spectra that exhibit the standard EI fragments combined with enhanced molecular ions. We evaluated the EI‐LC‐MS with SMB system and demonstrated its effectiveness in NIST library sample identification which is complemented with the availability of enhanced molecular ions. The EI‐LC‐MS with SMB system is characterized by linear response of five orders of magnitude and uniform compound independent response including for non‐polar compounds. This feature improves sample quantitation that can be approximated without compound specific calibration. Cold EI, like EI, is free from ion suppression and/or enhancement effects (that plague ESI and/or APCI) which facilitate faster LC separation because full separation is not essential. The absence of ion suppression effects enables the exploration of fast flow injection MS‐MS as an alternative to lengthy LC‐MS analysis. These features are demonstrated in a few examples, and the analysis of the main ingredients of Cannabis on a few Cannabis flower extracts is demonstrated. Finally, the advantages of EI‐LC‐MS with SMB are listed and discussed. Copyright © 2015 John Wiley & Sons, Ltd.     

Mass spectrometry of poly(methyl methacrylate) (PMMA) prepared by atom transfer radical polymerization (ATRP)

Poly(methyl methacrylate) (PMMA) was synthesized via atom transfer radical polymerization (ATRP). As a catalyst copper(I)thiocyanate (CuSCN) was used with N-n-pentyl-2-pyridylmethanimine as a ligand. Infrared spectroscopy and matrix assisted laser desorption ionization time-of-flight mass spectrometry were used to characterize the synthesized polymers. From this it was clear that at least to some extent thiocyanate was present as end groups of the PMMA chains. This observation is discussed in view of a phenomenon called halogen exchange, which has been reported before for bromine/chlorine exchange in ATRP.