Let
Seeded graph matching via large neighborhood statistics
We study a noisy graph isomorphism problem, where the goal is to perfectly recover the vertex correspondence between two edge‐correlated graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. We show that it is possible to achieve the information‐theoretic limit of graph sparsity in time polynomial in the number of vertices
- NSF-PAR ID:
- 10166755
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 57
- Issue:
- 3
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 570-611
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract be the random directed graph on n vertices where each of thepossible arcs is present independently with probability p . A celebrated result of Frieze shows that ifthen typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in is typically . We also prove a hitting‐time version of this statement, showing that in the random directed graph process, as soon as every vertex has in‐/out‐degrees at least 1, there are typically directed Hamilton cycles. -
more » « less
Abstract Given a graph
, its auxiliary square‐graph is the graph whose vertices are the non‐edges of and whose edges are the pairs of non‐edges which induce a square (i.e., a 4‐cycle) in . We determine the threshold edge‐probability at which the Erdős–Rényi random graph begins to asymptotically almost surely (a.a.s.) have a square‐graph with a connected component whose squares together cover all the vertices of . We show , a polylogarithmic improvement on earlier bounds on due to Hagen and the authors. As a corollary, we determine the threshold at which the random right‐angled Coxeter group a.a.s. becomes strongly algebraically thick of order 1 and has quadratic divergence. -
more » « less
Abstract In this paper, we are interested in the following question: given an arbitrary Steiner triple system
on vertices and any 3‐uniform hypertree on vertices, is it necessary that contains as a subgraph provided ? We show the answer is positive for a class of hypertrees and conjecture that the answer is always positive. -
more » « less
Abstract A graph is said to be
‐universal if it contains every graph with n vertices and maximum degree at most Δ as a subgraph. Dellamonica, Kohayakawa, Rödl and Ruciński used a “matching‐based” embedding technique introduced by Alon and Füredi to show that the random graphis asymptotically almost surely ‐universal for , a threshold for the property that every subset of Δ vertices has a common neighbor. This bound has become a benchmark in the field and many subsequent results on embedding spanning graphs of maximum degree Δ in random graphs are proven only up to this threshold. We take a step towards overcoming limitations of former techniques by showing that is almost surely ‐universal for . -
more » « less
Abstract Let
be integers with , and set . Erdős proved that when , each n ‐vertex nonhamiltonian graphG with minimum degreehas at most edges. He also provides a sharpness example for all such pairs . Previously, we showed a stability version of this result: for n large enough, every nonhamiltonian graphG onn vertices withand more than edges is a subgraph of . In this article, we show that not only does the graph maximize the number of edges among nonhamiltonian graphs with n vertices and minimum degree at leastd , but in fact it maximizes the number of copies of any fixed graphF whenn is sufficiently large in comparison withd and. We also show a stronger stability theorem, that is, we classify all nonhamiltonian n ‐vertex graphs withand more than edges. We show this by proving a more general theorem: we describe all such graphs with more than copies of for any k .
