skip to main content

Title: On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices

Given ak‐vertex graphHand an integern, what are then‐vertex graphs with the maximum number of induced copies ofH? This question is closely related to the inducibility problem introduced by Pippenger and Golumbic in 1975, which asks for the maximum possible fraction ofk‐vertex subsets of ann‐vertex graph that induce a copy ofH. Huang, Lee, and the first author proved that for a randomk‐vertex graphH, almost surely then‐vertex graphs maximizing the number of induced copies ofHare the balanced iterated blow‐ups ofH. In this article, we consider the case where the graphHis obtained by deleting a small number of vertices from a random Cayley graphof an abelian group. We prove that in this case, almost surely alln‐vertex graphs maximizing the number of induced copies ofHare balanced iterated blow‐ups of.

more » « less
Author(s) / Creator(s):
 ;  ;  
Publisher / Repository:
Wiley Blackwell (John Wiley & Sons)
Date Published:
Journal Name:
Random Structures & Algorithms
Page Range / eLocation ID:
p. 554-615
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Letbe integers with, and set. Erdős proved that when, eachn‐vertex nonhamiltonian graphGwith minimum degreehas at mostedges. He also provides a sharpness examplefor all such pairs. Previously, we showed a stability version of this result: fornlarge enough, every nonhamiltonian graphGonnvertices withand more thanedges is a subgraph of. In this article, we show that not only does the graphmaximize the number of edges among nonhamiltonian graphs withnvertices and minimum degree at leastd, but in fact it maximizes the number of copies of any fixed graphFwhennis sufficiently large in comparison withdand. We also show a stronger stability theorem, that is, we classify all nonhamiltoniann‐vertex graphs withand more thanedges. We show this by proving a more general theorem: we describe all such graphs with more thancopies offor anyk.

    more » « less
  2. Abstract

    A graph is said to be‐universal if it contains every graph withnvertices 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 thatis almost surely‐universal for.

    more » « less
  3. Abstract

    In this paper, we study the existence of perfect matchings and Hamiltonian cycles in the preferential attachment model. In this model, vertices are added to the graph one by one, and each time a new vertex is created it establishes a connection withmrandom vertices selected with probabilities proportional to their current degrees. (Constantmis the only parameter of the model.) We prove that if, then asymptotically almost surely there exists a perfect matching. Moreover, we show that there exists a Hamiltonian cycle asymptotically almost surely, provided that. One difficulty in the analysis comes from the fact that vertices establish connections only with vertices that are “older” (ie, are created earlier in the process). However, the main obstacle arises from the fact that edges in the preferential attachment model are not generated independently. In view of that, we also consider a simpler setting—sometimes called uniform attachment—in which vertices are added one by one and each vertex connects tomolder vertices selected uniformly at random and independently of all other choices. We first investigate the existence of perfect matchings and Hamiltonian cycles in the uniform attachment model, and then extend the argument to the preferential attachment version.

    more » « less
  4. 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 verticesn. Moreover, we show the number of seeds needed for perfect recovery in polynomial‐time can be as low asin the sparse graph regime (with the average degree smaller than) andin the dense graph regime, for a small positive constant. Unlike previous work on graph matching, which used small neighborhoods or small subgraphs with a logarithmic number of vertices in order to match vertices, our algorithms match vertices if their large neighborhoods have a significant overlap in the number of seeds.

    more » « less
  5. Abstract

    For a given graphH, we say that a graphGonnvertices isH‐saturated ifHis not a subgraph ofG, but for any edgethe graphcontains a subgraph isomorphic to H. The set of all valuesmfor which there exists anH‐saturated graph onnvertices andmedges is called the edge spectrum forH‐saturated graphs. In the present article, we study the edge spectrum forH‐saturated graphs whenHis a path or a star. In particular, we show that the edge spectrum for star‐saturated graphs consists of all integers between the saturation number and extremal number, and the edge spectrum of path‐saturated graphs includes all integers from the saturation number to slightly below the extremal number, but in general will include gaps just below the extremal number. We also investigate the second largest‐saturated graphs as well as some structural results about path‐saturated graphs that have edge counts close to the extremal number.

    more » « less