Regularity and perturbation results for mixed second order elliptic problems

We study a mixed boundary value problem for elliptic second order equations obtaining optimal regularity results under weak assumptions on the data. We also consider the dependence of the solution with respect to perturbations of the boundary sets carrying the Dirichlet and the Neumann conditions.     

Kaleidoscope of life: A 24-neighbourhood outer-totalistic cellular automaton

One of the challenges of cellular automaton research is finding models with a low complexity and at the same time a rich dynamics. A measure of low complexity is the number of states in the model and the number of transition rules to switch between those states. In this paper, we propose a 2-dimensional 2-state cellular automaton that-though governed by a single simple transition rule-has a sufficiently rich dynamics to be computationally universal. According to the transition rule, a cell’s state is determined by the sum of the states of the cells at orthogonal or diagonal distances one or two from the cell (distance-2 Moore neighbourhood), but not by the previous state of the cell itself. Notwithstanding its simplicity, this model is able to generate a great variety of patterns, including several types of stable configurations, oscillators and patterns that move over cellular space (gliders). We prove the computational universality of the model by constructing a universal set of logic gates (NOT and AND) from these patterns. A key element in this proof is the shifting of phases and positions of signals such that they meet the input requirements of the logic gates. Similarities of the model with classical spin systems are also discussed.     

Tunable magnetism through edge functionalization in zigzag green phosphorene nanoribbons

Ab initio density-functional theory calculations with spin polarization are performed to explore magnetic properties in zigzag green phosphorene nanoribbons (ZGPNRs) with no passivation or edge-saturated by H, OH and O chemical species. It is found that antiferromagnetic order at intra-edges is the most energetically favorable for the pristine and oxygen passivated ribbons, while H- or OH-saturated ZGPNRs show nonmagnetic order. It indicates that edge states arising from the unsaturated bonds are vital for the formation of the magnetic moment in the ZGPNRs. The magnitude of the edge magnetism in the pristine and O-saturated ZGPNRs is comparable to that in zigzag black phosphorene nanoribbons. Electronic band structures, spin densities and spd-orbital projected density of states for the studied pristine and O-passivated ZGPNRs are further analyzed to study their electronic properties. The magnetic and electronic properties discovered in the ZGPNRs may suggest potential applications in future spintronics and electronics.     

Nonlinear edge modes in a honeycomb electrical lattice near the Dirac points

We examine - both experimentally and numerically - a two-dimensional nonlinear driven electrical lattice with honeycomb structure. Drives are considered over a range of frequencies both outside (below and above) and inside the band of linear modes. We identify a number of discrete breathers both existing in the bulk and also (predominantly) ones arising at the domain boundaries, localized either along the arm-chair or along the zig-zag edges. The types of edge-localized breathers observed and computed emerge in distinct frequency bands near the Dirac-point frequency of the dispersion surface while driving the lattice subharmonically (in a spatially homogeneous manner). These observations/computations can represent a starting point towards the exploration of the interplay of nonlinearity and topology in an experimentally tractable system such as the honeycomb electrical lattice.     

Connectivity keeping edges in graphs with large minimum degree

The old well-known result of Chartrand, Kaugars and Lick says that every k-connected graph G with minimum degree at least 3k/2 has a vertex v such that G−v is still k-connected. In this paper, we consider a generalization of the above result [G. Chartrand, A. Kaigars, D.R. Lick, Critically n-connected graphs, Proc. Amer. Math. Soc. 32 (1972) 63–68]. We prove the following result:Suppose G is a k-connected graph with minimum degree at least 3k/2+2. Then G has an edge e such that G−V(e) is still k-connected.The bound on the minimum degree is essentially best possible.     

Edge ranking and searching in partial orders

We consider a problem of searching an element in a partially ordered set (poset). The goal is to find a search strategy which minimizes the number of comparisons. Ben-Asher, Farchi and Newman considered a special case where the partial order has the maximum element and the Hasse diagram is a tree (tree-like posets) and they gave an O(n⁴log³n)-time algorithm for finding an optimal search strategy for such a partial order. We show that this problem is equivalent to finding edge ranking of a simple tree corresponding to the Hasse diagram, which implies the existence of a linear-time algorithm for this problem.Then we study a more general problem, namely searching in any partial order with maximum element. We prove that such a generalization is hard, and we give an -approximate polynomial-time algorithm for this problem.     

Degree constrained subgraphs

In this paper, we present new structural results about the existence of a subgraph where the degrees of the vertices are pre-specified. Further, we use these results to prove a 16-edge-weighting version of a conjecture by Karoński, ?uczak and Thomason, an asymptotic 2-edge-weighting version of the same conjecture, and a version of Louigi's Conjecture.     

Size of Monochromatic Double Stars in Edge Colorings

We show that in every r-coloring of the edges of K _n there is a monochromatic double star with at least \(\frac{n(r+1)+r-1}{r^2}\) vertices. This result is sharp in asymptotic for r = 2 and for r≥ 3 improves a bound of Mubayi for the largest monochromatic subgraph of diameter at most three. When r-colorings are replaced by local r-colorings, our bound is \(\frac{n(r+1)+r-1}{r^2+1}\).