An official website of the United States government
Free, publicly-accessible full text available October 29, 2026
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
We consider a variation on Maker-Breaker games on graphs or digraphs where the edges have random costs. We assume that Maker wishes to choose the edges of a spanning tree, but wishes to minimise his cost. Meanwhile Breaker wants to make Maker's cost as large as possible.more » « lessFree, publicly-accessible full text available April 11, 2026
-
The greedy and nearest-neighbor TSP heuristics can both have $$\log n$$ approximation factors from optimal in worst case, even just for $$n$$ points in Euclidean space. In this note, we show that this approximation factor is only realized when the optimal tour is unusually short. In particular, for points from any fixed $$d$$-Ahlfor's regular metric space (which includes any $$d$$-manifold like the $$d$$-cube $[0,1]^d$ in the case $$d$$ is an integer but also fractals of dimension $$d$$ when $$d$$ is real-valued), our results imply that the greedy and nearest-neighbor heuristics have additive errors from optimal on the order of the optimal tour length through random points in the same space, for $d>1$.more » « less
-
We consider the rank of a class of sparse Boolean matrices of size $$n \times n$$. In particular, we show that the probability that such a matrix has full rank, and is thus invertible, is a positive constant with value about $0.2574$ for large $$n$$. The matrices arise as the vertex-edge incidence matrix of 1-out 3-uniform hypergraphs. The result that the null space is bounded in expectation, can be contrasted with results for the usual models of sparse Boolean matrices, based on the vertex-edge incidence matrix of random $$k$$-uniform hypergraphs. For this latter model, the expected co-rank is linear in the number of vertices $$n$$, \cite{ACO}, \cite{CFP}. For fields of higher order, the co-rank is typically Poisson distributed.more » « less
-
We discuss the length $$\vL_{c,n}$$ of the longest directed cycle in the sparse random digraph $$D_{n,p},p=c/n$$, $$c$$ constant. We show that for large $$c$$ there exists a function $$\vf(c)$$ such that $$\vL_{c,n}/n\to \vf(c)$$ a.s. The function $$\vf(c)=1-\sum_{k=1}^\infty p_k(c)e^{-kc}$$ where $$p_k$$ is a polynomial in $$c$$. We are only able to explicitly give the values $$p_1,p_2$$, although we could in principle compute any $$p_k$$.more » « less
Full Text Available