Sharp Bounds For Some Multicolor Ramsey Numbers

Let H ₁,H ₂, . . .,H _k+1 be a sequence of k+1 finite, undirected, simple graphs. The (multicolored) Ramsey number r(H ₁,H ₂,...,H _k+1) is the minimum integer r such that in every edge-coloring of the complete graph on r vertices by k+1 colors, there is a monochromatic copy of H _i in color i for some 1ik+1. We describe a general technique that supplies tight lower bounds for several numbers r(H ₁,H ₂,...,H _k+1) when k2, and the last graph H _k+1 is the complete graph K _m on m vertices. This technique enables us to determine the asymptotic behaviour of these numbers, up to a polylogarithmic factor, in various cases. In particular we show that r(K ₃,K ₃,K _m ) = (m ³ poly logm), thus solving (in a strong form) a conjecture of Erdos and Sós raised in 1979. Another special case of our result implies that r(C ₄,C ₄,K _m ) = (m ² poly logm) and that r(C ₄,C ₄,C ₄,K _m ) = (m ²/log² m). The proofs combine combinatorial and probabilistic arguments with spectral techniques and certain estimates of character sums.* Research supported in part by a State of New Jersey grant, by a USA Israeli BSF grant and by a grant from the Israel Science Foundation. Research supported by NSF grant DMS 9704114.     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

Fly Cheaply: On the Minimum Fuel Consumption Problem

In planning a flight, stops at intermediate airports are sometimes necessary to minimize fuel consumption, even if a direct flight is available. We investigate the problem of finding the cheapest path from one airport to another, given a set of n airports in ² and a function l: ² × ² → ⁺ representing the cost of a direct flight between any pair. Given a source airport s, the cheapest-path map is a subdivision of ² where two points lie in the same region iff their cheapest paths from s use the same sequence of intermediate airports. We show a quadratic lower bound on the combinatorial complexity of this map for a class of cost functions. Nevertheless, we are able to obtain subquadratic algorithms to find the cheapest path from s to all other airports for any well-behaved cost function l: our general algorithm runs in O(n^{4/3 +} ) time, and a simpler, more practical variant runs in O(n^{3/2 +} ) time, while a special class of cost functions requires just O(n log n) time.     

The Moore Bound for Irregular Graphs

 What is the largest number of edges in a graph of order n and girth g? For d-regular graphs, essentially the best known answer is provided by the Moore bound. This result is extended here to cover irregular graphs as well, yielding an affirmative answer to an old open problem ([4] p. 163, problem 10). Received: June 27, 2000 Final version received: July 3, 2001     

Automated chemical resonance generation and structure filtration for kinetic modeling

This work discusses efficient and automated methods for constructing a set of representative resonance structures for arbitrary chemical species, including radicals and biradicals, consisting of the elements H, C, O, N, and S. Determining the representative reactive structures of chemical species is crucial for identification of reactive sites and consequently applying the correct reaction templates to generate the set of important reactions during automated chemical kinetic model generation. We describe a fundamental set of resonance pathway types, accounting for simple resonating structures, as well as global approaches for polycyclic aromatic species. Automatically discovering potential localized structures along with filtration to identify the representative structures was shown to be robust and relatively fast. The algorithms discussed here were recently implemented in the Reaction Mechanism Generator (RMG) software. The final structures proposed by this method were found to be in reasonable agreement with quantum chemical computation results of localized structure contributions to the resonance hybrid.     

Implanted biofuel cell operating in a living snail

Implantable biofuel cells have been suggested as sustainable micropower sources operating in living organisms, but such bioelectronic systems are still exotic and very challenging to design. Very few examples of abiotic and enzyme-based biofuel cells operating in animals in vivo have been reported. Implantation of biocatalytic electrodes and extraction of electrical power from small living creatures is even more difficult and has not been achieved to date. Here we report on the first implanted biofuel cell continuously operating in a snail and producing electrical power over a long period of time using physiologically produced glucose as a fuel. The "electrified" snail, being a biotechnological living "device", was able to regenerate glucose consumed by biocatalytic electrodes, upon appropriate feeding and relaxing, and then produce a new "portion" of electrical energy. The snail with the implanted biofuel cell will be able to operate in a natural environment, producing sustainable electrical micropower for activating various bioelectronic devices.     

8-(p-CF3-cinnamyl)-modified purine nucleosides as promising fluorescent probes

Natural nucleotides are not useful as fluorescent probes because of their low quantum yields. Therefore, a common methodology for the detection of RNA and DNA is the application of extrinsic fluorescent dyes coupled to bases in oligonucleotides. To overcome the many limitations from which fluorescent nucleotide-dye conjugates suffer, we have developed novel purine nucleosides with intrinsic fluorescence to be incorporated into oligonucleotide probes. For this purpose we synthesized adenosine and guanosine fluorescent analogues 7-25, conjugated at the C8 position with aryl/heteroaryl moieties either directly, or via alkenyl/alkynyl linkers. Directly conjugated analogues 7-14, exhibited high quantum yields, φ >0.1, and short λ(em) (<385 nm). Alkynyl conjugated analogues 22-25, exhibited low quantum yields, φ <0.075, and λ(em)<385 nm. The alkenyl conjugated analogues 15-21, exhibited λ(em) 408-459 nm. While analogues 15,16, and 20 bearing an EDG on the aryl moiety, exhibited φ <0.02, analogues 17, and 21 with EWG on the aryl moiety, exhibited extremely high quantum yields, φ ≈ 0.8, suggesting better intramolecular charge transfer. We determined the conformation of selected adenosine analogues. Directly conjugated analogue 8 and alkynyl conjugated analogue 22, adapted the syn conformation, whereas alkenyl conjugated analogue 15 adapted the anti conformation. Based on the long emission wavelengths, high quantum yields, anti conformation and base-paring compatibility, we suggest analogues 17 and 21 for further development as fluorescent probes for the sensitive detection of genetic material.     

An Autonomous Chemical Robot Discovers the Rules of Inorganic Coordination Chemistry without Prior Knowledge

We present a chemical discovery robot for the efficient and reliable discovery of supramolecular architectures through the exploration of a huge reaction space exceeding ten billion combinations. The system was designed to search for areas of reactivity found through autonomous selection of the reagent types, amounts, and reaction conditions aiming for combinations that are reactive. The process consists of two parts where reagents are mixed together, choosing from one type of aldehyde, one amine and one azide (from a possible family of two amines, two aldehydes and four azides) with different volumes, ratios, reaction times, and temperatures, whereby the reagents are passed through a copper coil reactor. Next, either cobalt or iron is added, again from a large number of possible quantities. The reactivity was determined by evaluating differences in pH, UV‐Vis, and mass spectra before and after the search was started. The algorithm was focused on the exploration of interesting regions, as defined by the outputs from the sensors, and this led to the discovery of a range of 1‐benzyl‐(1,2,3‐triazol‐4‐yl)‐N‐alkyl‐(2‐pyridinemethanimine) ligands and new complexes: [Fe(L¹)₂](ClO₄)₂ ( 1 ); [Fe(L²)₂](ClO₄)₂ ( 2 ); [Co₂(L³)₂](ClO₄)₄ ( 3 ); [Fe₂(L³)₂](ClO₄)₄ ( 4 ), which were crystallised and their structure confirmed by single‐crystal X‐ray diffraction determination, as well as a range of new supramolecular clusters discovered in solution using high‐resolution mass spectrometry.     

A Ramsey‐type problem and the Turán numbers*

For each n and k, we examine bounds on the largest number m so that for any k‐coloring of the edges of K_n there exists a copy of K_m whose edges receive at most k?1 colors. We show that for , the largest value of m is asymptotically equal to the Turá number , while for any constant then the largest m is asymptotically larger than that Turá number. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 120–129, 2002     

On the density of sets of vectors

Answering a question of Erdös, Sauer [4] and independently Perles and Shelah [5] found the maximal cardinality of a collection $\text{F}$ of subsets of a set: N of cardinality n such that for every subset M ? N of cardinality $\text{m |{C ∩ M: C ?}\text{F}\text{}| < 2}{}^{\mathrm{m}}$. Karpovsky and Milman [3] generalised this result. Here we give a short proof of these results and further extensions.