Cell jamming in a collagen-based interface assay is tuned by collagen density and proteolysis.

Tumor cell invasion into heterogenous interstitial tissues consisting of network-, channel- or rift-like architectures involves both matrix metalloproteinase (MMP)-mediated tissue remodeling and cell shape adaptation to tissue geometry. Three-dimensional (3D) models composed of either porous or linearly aligned architectures have added to the understanding of how physical spacing principles affect migration efficacy; however, the relative contribution of each architecture to decision making in the presence of varying MMP availability is not known. Here, we developed an interface assay containing a cleft between two high-density collagen lattices, and we used this assay to probe tumor cell invasion efficacy, invasion mode and MMP dependence in concert. In silico modeling predicted facilitated cell migration into confining clefts independently of MMP activity, whereas migration into dense porous matrix was predicted to require matrix degradation. This prediction was verified experimentally, where inhibition of collagen degradation was found to strongly compromise migration into 3D collagen in a density-dependent manner, but interface-guided migration remained effective, occurring by cell jamming. The 3D interface assay reported here may serve as a suitable model to better understand the impact of in vivo-relevant interstitial tissue topologies on tumor invasion patterning and responses to molecular interventions.

Coloring triangle-free graphs with local list sizes.

We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of color made available to vertices of lower degree to be accordingly lower. One result concerns list coloring and correspondence coloring, while the other concerns fractional coloring. Our proof of the second illustrates the use of the hard-core model to prove a Johansson-type result, which may be of independent interest.

Single-conflict colouring.

Given a multigraph, suppose that each vertex is given a local assignment of k colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least k for which this is always possible given any set of local assignments we call the single-conflict chromatic number of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that single-conflict chromatic number of simple graphs embeddable on a surface of Euler genus g is O ( g 1 ∕ 4 log g ) as g → ∞ . This is sharp up to the logarithmic factor.

Occupancy fraction, fractional colouring, and triangle fraction.

Given ε > 0 , there exists f 0 such that, if f 0 ≤ f ≤ Δ 2 + 1 , then for any graph G on n vertices of maximum degree Δ in which the neighbourhood of every vertex in G spans at most Δ 2 ∕ f edges, (i)an independent set of G drawn uniformly at random has at least ( 1 ∕ 2 - ε ) ( n ∕ Δ ) log f vertices in expectation, and(ii)the fractional chromatic number of G is at most ( 2 + ε ) Δ ∕ log f . These bounds cannot in general be improved by more than a factor 2 asymptotically. One may view these as stronger versions of results of Ajtai, Komlós and Szemerédi and Shearer. The proofs use a tight analysis of the hard-core model.