On non-strong jumping numbers and density structures of hypergraphs

Estimating Turán densities of hypergraphs is believed to be one of the most challenging problems in extremal set theory. The concept of ‘jump’ concerns the distribution of Turán densities. A number α∈[0,1) is a jump for r-uniform graphs if there exists a constant c>0 such that for any family F of r-uniform graphs, if the Turán density of F is greater than α, then the Turán density of F is at least α+c. A fundamental result in extremal graph theory due to Erd?s and Stone implies that every number in [0,1) is a jump for graphs. Erd?s also showed that every number in [0,r!/r^r) is a jump for r-uniform hypergraphs. Furthermore, Frankl and Rödl showed the existence of non-jumps for hypergraphs. Recently, more non-jumps were found in [r!/r^r,1) for r-uniform hypergraphs. But there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we propose a new but related concept-strong-jump and describe several sequences of non-strong-jumps. It might help us to understand the distribution of Turán densities for hypergraphs better by finding more non-strong-jumps.     

Critical behavior of the absorbing state transition in the contact process with relaxing immunization

We introduce a model for the Contact Process with relaxing immunization CPRI  . In this model, local memory is introduced by a time and space dependence of the contamination probability. The model has two parameters: a typical immunization time τ$\tau$ and a maximum contamination probability a$a$. The system presents an absorbing state phase transition whenever the contamination probability a$a$ is above a minimum threshold. For short immunization times, the system evolves to a statistically stationary active state. Above _τc(a)${\tau }_c\left(a\right)$, immunization predominates and the system evolves to the absorbing vacuum state. We employ a finite-size scaling analysis to show that the transition belongs to the standard directed percolation universality class. The critical immunization time diverges in the limit of a→1$a\to 1$. In this regime, the density of active sites decays exponentially as τ$\tau$ increases, but never reaches the vacuum state in the thermodynamic limit.     

Local symmetry and chirality of molecular faces

The concept of local symmetry has been applied to faces of planar sites such as carbon–carbon double bonds and aromatic rings with the principal results being as follows. The two faces of a planar site must have the same local symmetry group. This local symmetry group is limited to the polar point groups. For cyclic compounds, directed cycles must have chirotopic faces although the reverse is not necessarily true: chirotopic faces are possible for both directed and undirected cycles. A number of examples are provided to illustrate these results. Received: 30 June 1999 / Accepted: 4 October 1999 / Published online: 19 April 2000     

Hypergraph coloring up to condensation

Improving a result of Dyer, Frieze and Greenhill [Journal of Combinatorial Theory, Series B, 2015], we determine the q‐colorability threshold in random k‐uniform hypergraphs up to an additive error of , where . The new lower bound on the threshold matches the “condensation phase transition” predicted by statistical physics considerations [Krzakala et al., PNAS 2007].     

Quasi-random 2- colorings of point sets

Given an arbitrary set of N points on the plane, one can two-color the points red and blue in such a way that the difference of the numbers of red and blue points in any half-plane has absolute value less than N^1/4(log N)⁴. This is essentially best possible.     

Exact algorithms and applications for Tree-like Weighted Set Cover

We introduce an NP-complete special case of the Weighted Set Cover problem and show its fixed-parameter tractability with respect to the maximum subset size, a parameter that appears to be small in relevant applications. More precisely, in this practically relevant variant we require that the given collection C of subsets of a base set S should be “tree-like”. That is, the subsets in C can be organized in a tree T such that every subset one-to-one corresponds to a tree node and, for each element s of S, the nodes corresponding to the subsets containing s induce a subtree of T. This is equivalent to the problem of finding a minimum edge cover in an edge-weighted acyclic hypergraph. Our main result is an algorithm running in O(3^kmn) time where k denotes the maximum subset size, n:=|S|, and m:=|C|. The algorithm also implies a fixed-parameter tractability result for the NP-complete Multicut in Trees problem, complementing previous approximation results. Our results find applications in computational biology in phylogenomics and for saving memory in tree decomposition based graph algorithms.