Search for: All records

Abstract We study the locations of complex zeroes of independence polynomials of bounded-degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free regions for bounded-degree graphs include Shearer’s result on the optimal zero-free disc, along with several recent results on other zero-free regions. Much less is known for hypergraphs. We make some steps towards an understanding of zero-free regions for bounded-degree hypergaphs by proving that all hypergraphs of maximum degree$$\Delta$$have a zero-free disc almost as large as the optimal disc for graphs of maximum degree$$\Delta$$established by Shearer (of radius$$\sim 1/(e \Delta )$$). Up to logarithmic factors in$$\Delta$$this is optimal, even for hypergraphs with all edge sizes strictly greater than$$2$$. We conjecture that for$$k\ge 3$$,$$k$$-uniformlinearhypergraphs have a much larger zero-free disc of radius$$\Omega (\Delta ^{- \frac{1}{k-1}} )$$. We establish this in the case of linear hypertrees. 

Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost$$f(\cdot )$$ $f(·)$due to an ordering$$\sigma $$ $\sigma$of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ ${min}_{\sigma }{\sum }_{i\in \left[n\right]}f\left(E_{i,\sigma }\right)$, where$$E_{i,\sigma }$$ $E_{i,\sigma }$is the set of items mapped by$$\sigma $$ $\sigma$to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a$$(2-\frac{1+\ell _{f}}{1+|E|})$$ $(2-\frac{1+{\ell }_f}{1+\left|E\right|})$-approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ ${\ell }_f=\frac{f\left(E\right)}{{max}_{x\in E}f\left(\left\{x\right\}\right)}$satisfies$$1 \le \ell _f \le |E|$$ $1\le {\ell }_f\le \left|E\right|$. Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ $(2-\frac{1+r\left(E\right)}{1+\left|E\right|})$-approximation for the matroid MLOP, where$$f = r$$ $f=r$is the rank function of a matroid. We further show that minimum latency vertex cover is$$\frac{4}{3}$$ $\frac{4}{3}$-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest. 

Ribonucleic acid (RNA) secondary structures and branching properties are important for determining functional ramifications in biology. While energy minimization of the Nearest Neighbor Thermodynamic Model (NNTM) is commonly used to identify such properties (number of hairpins, maximum ladder distance, etc.), it is difficult to know whether the resultant values fall within expected dispersion thresholds for a given energy function. The goal of this study was to construct a Markov chain capable of examining the dispersion of RNA secondary structures and branching properties obtained from NNTM energy function minimization independent of a specific nucleotide sequence. Plane trees are studied as a model for RNA secondary structure, with energy assigned to each tree based on the NNTM, and a corresponding Gibbs distribution is defined on the trees. Through a bijection between plane trees and 2-Motzkin paths, a Markov chain converging to the Gibbs distribution is constructed, and fast mixing time is established by estimating the spectral gap of the chain. The spectral gap estimate is obtained through a series of decompositions of the chain and also by building on known mixing time results for other chains on Dyck paths. The resulting algorithm can be used as a tool for exploring the branching structure of RNA, especially for long sequences, and to examine branching structure dependence on energy model parameters. Full exposition is provided for the mathematical techniques used with the expectation that these techniques will prove useful in bioinformatics, computational biology, and additional extended applications. 

Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of annvertex graph, and need to output a clique. We show that if the input graph is drawn at random from(and hence is likely to have a clique of size roughly), then for everyδ<2 and constantℓ, there is anα<2 (that may depend onδandℓ) such that no algorithm that makesn^δprobes inℓrounds is likely (over the choice of the random graph) to output a clique of size larger than. 

Abstract We study the volume growth of metric balls as a function of the radius in discrete spaces and focus on the relationship between volume growth and discrete curvature. We improve volume growth bounds under a lower bound on the so-called Ollivier curvature and discuss similar results under other types of discrete Ricci curvature. Following recent work in the continuous setting of Riemannian manifolds (by the 1st author), we then bound the eigenvalues of the Laplacian of a graph under bounds on the volume growth. In particular, $$\lambda _2$$ of the graph can be bounded using a weighted discrete Hardy inequality and the higher eigenvalues of the graph can be bounded by the eigenvalues of a tridiagonal matrix times a multiplicative factor, both of which only depend on the volume growth of the graph. As a direct application, we relate the eigenvalues to the Cheeger isoperimetric constant. Using these methods, we describe classes of graphs for which the Cheeger inequality is tight on the 2nd eigenvalue (i.e. the 1st nonzero eigenvalue). We also describe a method for proving Buser’s Inequality in graphs, particularly under a lower bound assumption on curvature.