Inspect the vertices of a finite simple graph in uniformly random order, accepting each vertex if none of its neighbors has previously been accepted. Let $X_G$ be the number of accepted vertices. For every triangle-free graph with $n\ge2$ vertices and $e$ edges, we prove $\operatorname{Var}(X_G)\le e((n-2)/n)^2$, with equality precisely for edgeless graphs and connected stars. In particular, among trees of a given order, the star uniquely maximizes the variance, with value $(n-1)(n-2)^2/n^2$. Known expected vertex-deletion stability already yields the elementary baseline $\operatorname{Var}(X_G)\le e$. We obtain the sharp finite-order refinement by combining a stronger centered first-choice estimate with a triangle-free edge-count identity in the law of total variance.
We study the hard-core model on recursively defined sequences $(G_n)_{n\geq0}$ of graphs with a fixed number $k\geq 1$ of labeled vertices in each graph. The next graph in the sequence is constructed by taking a fixed number $m\geq 2$ of copies of the previous graph, connecting these copies by identifying some labeled...
For a graph $G$, let $h(G)$ be the minimum cardinality of a vertex set meeting every maximum independent set of $G$. We establish two complementary reduction principles for the Bollob\'as--Erd\H{o}s--Tuza conjecture: the conjecture for arbitrary graphs is equivalent to its restriction to regular graphs of any fixed pos...
Choose uniformly among the combinatorial types of convex three-dimensional polyhedra with a fixed admissible number $e$ of edges, and let $V_e$ be the number of vertices. This resolves a fixed-edge limit-distribution question posed by R\"udinger: if $\beta_e=V_e/(e+2)$, then $\sqrt e(\beta_e-1/2)\Rightarrow N(0,1/32)$,...
For a graph $G$, let $s^+(G)$ and $s^-(G)$ denote the sums of the squares of its positive and negative adjacency eigenvalues. We determine all equality cases in the conjecture of Elphick, Farber, Goldberg, and Wocjan that every connected graph $G$ on $n$ vertices satisfies \[ \min \{s^+(G),s^-(G)\}\ge n-1. \] Namely, e...
The likelihood of a finite simple undirected graph $G$ on $n$ vertices is the probability that the uniform sequential attachment process, which at each step joins a new vertex to a uniformly random subset of uniformly random size of the vertices already present, outputs a graph isomorphic to $G$. Dervovic, Mocherla and...
We prove that, whenever $ p \ge n^{-1/2 + o(1)} $, with high probability $ G(n, p) $ admits a fractional triangle decomposition, that is, a non-negative weight function on its triangles for which the total weight of all triangles containing each edge is equal to 1. This bound on $ p $ is optimal up to the asymptotic er...
Felix Joos, Zak Smith· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
