- Award ID(s):
- 1423615
- PAR ID:
- 10097780
- Date Published:
- Journal Name:
- International Conference on Discrete Geometry for Computer Imagery
- Volume:
- 11414
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Mestre, Julián ; Wirth, Anthony (Ed.)For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in O(n log n) time where n is the number of points. In contrast to the standard Euclidean MST, which is always plane (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings. Moreover, we study the problem of finding a minimum plane bichromatic spanning tree (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al. (2009), has a ratio of O(√n). It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an O(log n)-factor approximation algorithm for the general case.more » « less
-
The force response of cardiac muscle undergoing a quick stretch is conventionally interpreted to represent stretching of attached myosin crossbridges (phase 1) and detachment of these stretched crossbridges at an exponential rate (phase 2), followed by crossbridges reattaching in increased numbers due to an enhanced activation of the thin filament (phases 3 and 4). We propose that, at least in mammalian cardiac muscle, phase 2 instead represents an enhanced detachment rate of myosin crossbridges due to stretch, phase 3 represents the reattachment of those same crossbridges, and phase 4 is a passive-like viscoelastic response with power-law relaxation. To test this idea, we developed a two-state model of crossbridge attachment and detachment. Unitary force was assigned when a crossbridge was attached, and an elastic force was generated when an attached crossbridge was displaced. Attachment rate, f(x), was spatially distributed with a total magnitude f0. Detachment rate was modeled as g(x) = g0+ g1x, where g0 is a constant and g1 indicates sensitivity to displacement. The analytical solution suggested that the exponential decay rate of phase 2 represents (f0 + g0) and the exponential rise rate of phase 3 represents g0. The depth of the nadir between phases 2 and 3 is proportional to g1. We prepared skinned mouse myocardium and applied a 1% stretch under varying concentrations of inorganic phosphate (Pi). The resulting force responses fitted the analytical solution well. The interpretations of phases 2 and 3 were consistent with lower f0 and higher g0 with increasing Pi. This novel scheme of interpreting the force response to a quick stretch does not require enhanced thin-filament activation and suggests that the myosin detachment rate is sensitive to stretch. Furthermore, the enhanced detachment rate is likely not due to the typical detachment mechanism following MgATP binding, but rather before MgADP release, and may involve reversal of the myosin power stroke.
-
Abstract The discrete Green's functions are the pseudoinverse (or the inverse) of the Laplacian (or its variations) of a graph. In this article, we will give combinatorial interpretations of Green's functions in terms of enumerating trees and forests in a graph that will be used to derive further formulas for several graph invariants. For example, we show that the trace of the Green's function associated with the combinatorial Laplacian of a connected simple graph on vertices satisfies
where denotes the eigenvalues of the combinatorial Laplacian, denotes the number of spanning trees, and denotes the set of rooted spanning 2‐forests in . We will prove forest formulas for discrete Green's functions for directed and weighted graphs and apply them to study random walks on graphs and digraphs. We derive a forest expression of the hitting time for digraphs, which gives combinatorial proofs to old and new results about hitting times, traces of discrete Green's functions, and other related quantities. -
The noncrossing partition poset associated to a Coxeter group $W$ and Coxeter element $c$ is the interval $[1,c]_T$ in the absolute order on $W$. We construct a new model of noncrossing partititions for $W$ of classical affine type, using planar diagrams. The model in type $\afftype{A}$ consists of noncrossing partitions of an annulus. In type~$\afftype{C}$, the model consists of symmetric noncrossing partitions of an annulus or noncrossing partitions of a disk with two orbifold points. Following the lead of McCammond and Sulway, we complete $[1,c]_T$ to a lattice by factoring the translations in $[1,c]_T$, but the combinatorics of the planar diagrams leads us to make different choices about how to factor.more » « less
-
Abstract A graph is ‐
free if it has no induced subgraph isomorphic to , and |G | denotes the number of vertices of . A conjecture of Conlon, Sudakov and the second author asserts that:For every graph , there exists such that in every ‐free graph with |
G | there are two disjoint sets of vertices, of sizes at least and , complete or anticomplete to each other.The “sparse linear conjecture”: For every graph , there exists such that in every ‐free graph with , either some vertex has degree at least , or there are two disjoint sets of vertices, of sizes at least and , anticomplete to each other.
The sparse linear conjecture holds for all almost‐bipartite graphs .
For every almost‐bipartite graph , there exist such that for every graph with and maximum degree less than , and for every with , either contains induced copies of , or there are two disjoint sets with and , and with at most edges between them.
For every graph , there exists such that in every ‐free graph with vertices, either some vertex has degree at least , or there are two disjoint sets of vertices with , anticomplete to each other.