An official website of the United States government
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 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
-
We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding graph parameter $$\zeta(G)$$ for a given graph $$G$$ is called the localization number. In this paper, we improve the bounds for dense random graphs determining an asymptotic behaviour of $$\zeta(G)$$. Moreover, we extend the argument to sparse graphs.more » « less
-
We consider the following question. We have a dense regular graph $$G$$ with degree $$\a n$$, where $$\a>0$$ is a constant. We add $m=o(n^2)$ random edges. The edges of the augmented graph $G(m)$ are given independent edge weights $$X(e),e\in E(G(m))$$. We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph, but scaled by a factor $$\a^{-1}$$. We consider spanning trees, shortest paths and perfect matchings in (pseudo-random) bipartite graphs.more » « less
-
We study two biased Maker-Breaker games played on the complete digraph $$\vec{K}_n$$. In the strong connectivity game, Maker wants to build a strongly connected subgraph. We determine the asymptotic optimal bias for this game viz. $$\frac{n}{\log n}$$. In the Hamiltonian game, Maker wants to build a Hamiltonian subgraph. We determine the asymptotic optimal bias for this game up to a constant factor.more » « less
-
We discuss the length {\red $$L_{c,n}$$} of the longest cycle in a sparse random graph {\red $$G_{n,p},$$ $p=c/n$,} $$c$$ constant. We show that for large $$c$$ there exists a function $f(c)$ such that $$L_{c,n}/n\to f(c)$$ a.s. The function $$f(c)=1-\sum_{k=1}^\infty p_k(c)e^{-kc}$$ where $$p_k{\red (c)}$$ 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$$. We see immediately that the length of the longest path is also asymptotic to $f(c)n$ w.h.p.more » « less
Full Text Available