3-Color bipartite Ramsey number of cycles and paths

The -color bipartite Ramsey number of a bipartite graph is the least integer for which every -edge-colored complete bipartite graph contains a monochromatic copy of . The study of bipartite Ramsey numbers was initiated, over 40 years ago, by Faudree and Schelp and, independently, by Gyárfás and Lehel, who determined the 2-color Ramsey number of paths. In this paper we determine asymptotically the 3-color bipartite Ramsey number of paths and (even) cycles.     

Monochromatic paths in random tournaments

We prove that, with high probability, any 2‐edge‐coloring of a random tournament on n vertices contains a monochromatic path of length . This resolves a conjecture of Ben‐Eliezer, Krivelevich, and Sudakov and implies a nearly tight upper bound on the oriented size Ramsey number of a directed path.     

Fenchone Derivatives as a Novel Class of CB2 Selective Ligands: Design,Synthesis, X-ray Structure and Therapeutic Potential

A series of novel cannabinoid-type derivatives were synthesized by the coupling of (1S,4R)-(+) and (1R,4S)-(−)-fenchones with various resorcinols/phenols. The fenchone-resorcinol derivatives were fluorinated using Selectfluor and demethylated using sodium ethanethiolate in dimethylformamide (DMF). The absolute configurations of four compounds were determined by X-ray single crystal diffraction. The fenchone-resorcinol analogs possessed high affinity and selectivity for the CB2 cannabinoid receptor. One of the analogues synthesized, 2-(2′,6′-dimethoxy-4′-(2″-methyloctan-2″-yl)phenyl)-1,3,3-trimethylbicyclo[2.2.1]heptan-2-ol (1d), had a high affinity (K_i = 3.51 nM) and selectivity for the human CB2 receptor (hCB2). In the [³⁵S]GTPγS binding assay, our lead compound was found to be a highly potent and efficacious hCB2 receptor agonist (EC₅₀ = 2.59 nM, E_(max) = 89.6%). Two of the fenchone derivatives were found to possess anti-inflammatory and analgesic properties. Molecular-modeling studies elucidated the binding interactions of 1d within the CB2 binding site.     

Mutually exclusive hole and electron transfer coupling in cross stacked acenes

The topology of frontier molecular orbitals (FMOs) induces highly sensitive charge transfer coupling with variation in the intermolecular arrangement. A consistent optoelectronic property correlated to a specific aggregate architecture independent of the nature of the monomer is a rare phenomenon. Our theoretical investigation on stacked dimeric systems of linear [n]acenes (n = 2–5) and selected non-linear acenes with a D_2h point group reveals that the Greek cross (+) stacked orientation, irrespective of the molecular candidate, exhibits mutually exclusive hole and electron transfer couplings. The deactivation of either hole or electron transfer coupling is a consequence of the zero inter-orbital overlap between the highest occupied molecular orbitals (HOMOs) or lowest unoccupied molecular orbitals (LUMOs) of the monomers possessing gerade symmetry. In the Greek cross (+) stacked alignment, the (4n + 2) π-electronic acene systems with an odd number of benzenoids exhibit exclusive electron transfer coupling, while the even numbered acenes exhibit selective hole transfer coupling. The trend is reversed for representative 4n π-electronic acene systems. The effect of mutually exclusive charge transfer coupling in the hopping regime of charge transport was evaluated using semiclassical Marcus theory, and selective charge carrier mobility was exhibited by the Greek cross (+) stacks of the considered acene candidates. Additionally, the characteristic charge transfer coupling of the orthogonal acene stacks resulted in negligible short-range exciton coupling, inciting null exciton splitting at short interplanar distances. Engineering chromophores in precise angular orientations ensuring characteristic emergent properties can have tremendous potential in the rational design of advanced optoelectronic materials.

Acenes in the Greek cross (+) stack orientation exhibit selective hole and electron transfer coupling based on gerade symmetry in frontier molecular orbitals.     

Regular induced subgraphs of a random Graph

An old problem of Erd?s, Fajtlowicz, and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on vertices. Motivated by this problem, we consider the order of such a subgraph in a typical graph on vertices, i.e., in a binomial random graph . We prove that with high probability a largest induced regular subgraph of has about vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 235–250, 2011     

List Colouring When The Chromatic Number Is Close To the Order Of The Graph

Ohba has conjectured [7] that if G has 2 (G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this short note we prove the weaker version of the conjecture obtained by replacing 2 (G)+1 by * This research was partially supported by DIMACS and by CNRS/NSF collaboration grant. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey.     

List Coloring of Random and Pseudo-Random Graphs

choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n, p(n)) is almost surely whenever . A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well as the chromatic number) of any graph on n vertices with minimum degree at least in which no two distinct vertices have more than common neighbors is at most . Received: October 13, 1997     

Acyclic edge colorings of graphs

A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001     

Embedding nearly-spanning bounded degree trees

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1 − ε)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d ≥ 2 and 0 < ε < 1, there exists a constant c = c(d, ε) such that a random graph G(n, c/n) contains almost surely a copy of every tree T on (1 − ε)n vertices with maximum degree at most d. We also prove that if an (n, D, λ)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most λ in their absolute values) has large enough spectral gap D/λ as a function of d and ε, then G has a copy of every tree T as above. Research supported in part by a USA-Israeli BSF grant, by NSF grant CCR-0324906, by a Wolfensohn fund and by the State of New Jersey. Research supported in part by USA-Israel BSF Grant 2002-133, and by grants 64/01 and 526/05 from the Israel Science Foundation. Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.     

Discrete Kakeya-type problems and small bases

A subset U of a group G is called k-universal if U contains a translate of every k-element subset of G. We give several nearly optimal constructions of small k-universal sets, and use them to resolve an old question of Erdős and Newman on bases for sets of integers, and to obtain several extensions for other groups.