Eigenvalues of ‐Free Graphs and the Connectivity of Their Independence Complexes

Let G be a graph on n vertices, with maximal degree d, and not containing as an induced subgraph. We prove:

• 1.
• 2.

Here is the maximal eigenvalue of the Laplacian of G, is the independence complex of G, and denotes the topological connectivity of a complex plus 2. These results provide improved bounds for the existence of independent transversals in ‐free graphs.     

Large sets in finite fields are sumsets

For a prime p, a subset S of Zp is a sumset if S=A+A for some A⊂Zp. Let f(p) denote the maximum integer so that every subset S⊂Zp of size at least p−f(p) is a sumset. The question of determining or estimating f(p) was raised by Green. He showed that for all sufficiently large p, and proved, with Gowers, that f(p)<cp2/3log1/3p for some absolute constant c. Here we improve these estimates, showing that there are two absolute positive constants c₁,c₂ so that for all sufficiently large p,

     

Degrees and choice numbers

The choice number ch(G) of a graph G=(V, E) is the minimum number k such that for every assignment of a list S(v) of at least k colors to each vertex v∈V, there is a proper vertex coloring of G assigning to each vertex v a color from its list S(v). We prove that if the minimum degree of G is d, then its choice number is at least (½−o(1))log₂ d, where the o(1)‐term tends to zero as d tends to infinity. This is tight up to a constant factor of 2+o(1), improves an estimate established by the author, and settles a problem raised by him and Krivelevich. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 364–368, 2000     

Role-Aware Information Spread in Online Social Networks

Understanding the complex process of information spread in online social networks (OSNs) enables the efficient maximization/minimization of the spread of useful/harmful information. Users assume various roles based on their behaviors while engaging with information in these OSNs. Recent reviews on information spread in OSNs have focused on algorithms and challenges for modeling the local node-to-node cascading paths of viral information. However, they neglected to analyze non-viral information with low reach size that can also spread globally beyond OSN edges (links) via non-neighbors through, for example, pushed information via content recommendation algorithms. Previous reviews have also not fully considered user roles in the spread of information. To address these gaps, we: (i) provide a comprehensive survey of the latest studies on role-aware information spread in OSNs, also addressing the different temporal spreading patterns of viral and non-viral information; (ii) survey modeling approaches that consider structural, non-structural, and hybrid features, and provide a taxonomy of these approaches; (iii) review software platforms for the analysis and visualization of role-aware information spread in OSNs; and (iv) describe how information spread models enable useful applications in OSNs such as detecting influential users. We conclude by highlighting future research directions for studying information spread in OSNs, accounting for dynamic user roles.     

Properly colored hamilton cycles in edge-colored complete graphs

It is shown that, for ϵ>0 and n>n₀(ϵ), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1-1/\sqrt2-\epsilon)n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and n any such K contains a cycle of length k in which adjacent edges have distinct colors. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 179–186 (1997)     

Polychromatic Colorings of Plane Graphs

We show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by ⌊(3g−5)/4⌋ colors so that every color appears in every face. This is nearly tight, as there are plane graphs where all faces are incident to at least g vertices and that admit no vertex coloring of this type with more than ⌊(3g+1)/4⌋ colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by k colors in which all colors appear in every face is in ℘ for k=2 and is -complete for k=3,4. We refine this result for polychromatic 3-colorings restricted to 2-connected graphs which have face sizes from a prescribed (possibly infinite) set of integers. Thereby we find an almost complete characterization of these sets of integers (face sizes) for which the corresponding decision problem is in ℘, and for the others it is -complete. Research of N. Alon was supported in part by the Israel Science Foundation, by a USA–Israeli BSF grant, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research of R. Berke was supported in part by JSPS Global COE program “Computationism as a Foundation for the Sciences.” Research of K. Buchin and M. Buchin was supported by the Netherlands’ Organisation for Scientific Research (NWO) under BRICKS/FOCUS project no. 642.065.503. Research of P. Csorba was supported by DIAMANT, an NWO mathematics cluster. Research of B. Speckmann was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.022.707.     

Field-portable wide-field microscopy of dense samples using multi-height pixel super-resolution based lensfree imaging

We report a field-portable lensfree microscope that can image dense and connected specimens with sub-micron resolution over a large field-of-view of ~30 mm(2) (i.e., ~6.4 mm × ~4.6 mm) using pixel super-resolution and iterative phase recovery techniques. Weighing ~122 grams with dimensions of 4 cm × 4 cm × 15 cm, this microscope records lensfree in-line holograms of specimens onto an opto-electronic sensor-array using partially coherent illumination. To reconstruct the phase and amplitude images of dense samples (with >0.3 billion pixels in each image, i.e., >0.6 billion pixels total), we employ a multi-height imaging approach, where by using a mechanical interface the sensor-to-sample distance is dynamically changed by random discrete steps of e.g., ~10 to 80 μm. By digitally propagating back and forth between these multi-height super-resolved holograms (corresponding to typically 2-5 planes), phase and amplitude images of dense samples can be recovered without the need for any spatial masks or filtering. We demonstrate the performance of this field-portable multi-height lensfree microscope by imaging Papanicolaou smears (also known as Pap tests). Our results reveal the promising potential of this multi-height lensfree computational microscopy platform for e.g., pathology needs in resource limited settings.     

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.