Random Structures and Algorithms
Издатель: Wiley · ISSN 10429832 · 14 статей
-
Random Triangulations of the d‐Sphere With Minimum Volume
ABSTRACT We study a higher‐dimensional analogue of the random traveling salesman problem: Let the complete ‐dimensional simplicial complex on vertices be equipped with i.i.d. volumes on its facets, uniformly random in . What is the...
-
Extreme Local Statistics in Random Graphs: Maximum Tree Extension Counts
ABSTRACT We consider maximum rooted tree extension counts in random graphs, that is, we consider where counts the number of copies of a given tree in rooted at vertex . We determine the asymptotics of when the random graph is not too...
-
Cycle Lengths in the Percolated Hypercube
ABSTRACT Let be the random subgraph of the ‐dimensional binary hypercube obtained after edge‐percolation with probability . It was shown recently by the authors that, for every , there is some such that, if , then typically contains a...
-
Random Burning of the Euclidean Torus
ABSTRACT The burning number of a graph is the minimal number of steps that are needed to burn all of its vertices, with the following burning procedure: at each step, one can choose a point to set on fire, and the fire propagates...
-
On the Mixing Time of Glauber Dynamics for the Hard‐Core and Related Models on G(n,d/n)
ABSTRACT In this work, we study the mixing time of the single‐site Glauber dynamics for the Hard‐core model on the sparse random graph with fugacity . We show that for the typical instances of and for fugacity , the mixing time of...
-
The Asymptotic χ‐Boundedness of Hereditary Families
ABSTRACT A family of graphs is asymptotically ‐bounded with bounding function if almost every graph in the family satisfies . A graph is ‐free if it does not contain as an induced subgraph. We ask which hereditary families are...
-
Gaussian to Log‐Normal Transition for Independent Sets in a Percolated Hypercube
ABSTRACT Independent sets in graphs, that is, subsets of vertices where no two are adjacent, have long been studied, particularly as a model for hard‐core gas in various settings such as lattices and random graphs. The ‐dimensional...
-
On Almost Gallai Colorings in Complete Graphs
ABSTRACT We investigate a rainbow analog of the Ruzsa–Szemerédi problem. For , we say that a coloring of is almost ‐Gallai if no two rainbow ‐cliques share an edge. Motivated by a lemma of Berkowitz on bounding the modulus of the...
-
Uniform Turán Density—Palette Classification
ABSTRACT In the 1980s, Erdős and Sós initiated the study of Turán hypergraph problems with a uniformity condition on the distribution of edges, that is, determining density thresholds for the existence of a hypergraph in a host...
- Issue Information
-
Random Turán Problems for Hypergraph Expansions
ABSTRACT Given an ‐uniform hypergraph , we define its ‐uniform expansion to be the hypergraph obtained from by inserting distinct vertices into each edge of , and we define to be the largest ‐free subgraph of the random hypergraph . We...
-
On the Local Resilience of Random Geometric Graphs With Respect to Connectivity and Long Cycles
ABSTRACT Given an increasing graph property , a graph is ‐resilient with respect to if, for every spanning subgraph where each vertex keeps more than a ‐proportion of its neighbors, has property . We study the above notion of local...
-
Asymptotic Bounds and Online Algorithms for Average‐Case Matrix Discrepancy
ABSTRACT We study the matrix discrepancy problem in the average‐case setting. Given a sequence of symmetric matrices , its discrepancy is defined as the minimal spectral norm over all signed sums with . Our contributions are twofold....
-
Robustness of the Sauer–Spencer Theorem
ABSTRACT We prove a robust version of a graph embedding theorem of Sauer and Spencer. To state this sparser analogue, we define to be a random subgraph of obtained by retaining each edge of independently with probability , and let be...