Proof. We prove the statement by induction on $|V(G)|$ . In the base case $|V(G)|=1$ , there is a unique vertex v of G, so $w(N_G(v))=w(\emptyset )=0$ and hence our target probability of the appearance of v in a randomly drawn independent set is $f(0)=1$ . This is easily achieved by letting $\mathcal {D}$ be the probability distribution that always picks $\{v\}$ , establishing the induction base.

For the induction step, let us assume that G is a triangle-free graph on at least two vertices and that we have already proven the claim of the theorem for all triangle-free graphs with strictly less vertices than G.

Let $K \subseteq [0,1]$ be the set of all $\delta \in [0,1]$ such that for every strictly positive weight function $w:V(G)\rightarrow \mathbb {R}_+$ there exists a probability distribution $\mathcal {D}$ on the independent sets of G such that $\mathbb {P}_{I\sim D}[v\in I]\ge f\left (\frac {w(N_G(v))}{w(v)}\right )-\delta $ for every $v\in V(G)$ . Since f takes values in $[0,1]$ , we trivially have $1\in K$ . Furthermore, we claim that the set K is closed (and thus compact). To see this, note that $K=\bigcap _{w:V(G)\rightarrow \mathbb {R}_+} K_w$ , where $K_w$ is the set of all $\delta \in [0,1]$ for which there exists a probability distribution $\mathcal {D}$ on the independent sets of G satisfying $\mathbb {P}_{I\sim \mathcal {D}}[v\in I]\ge f\left (\frac {w(N_G(v))}{w(v)}\right )-\delta $ for every $v\in V(G)$ . Since intersections of closed sets are closed, it suffices to show that $K_w$ is closed for every fixed $w:V(G)\rightarrow \mathbb {R}_+$ . Now, consider the following linear program ( $\mathcal {I}(G)$ denotes the collection of all independent sets in G):

$$ \begin{align*} \text{min}~~ &y\\ \text{s.t.}~~ y+\sum_{I\in \mathcal{I}(G): v \in I}{x_I}&\ge f\left(\frac{w(N_G(v))}{w(v)}\right)~~(\forall v \in V(G)), \\ \sum_{I\in \mathcal{I}(G)} x_I&=1 \\ x_I &\ge 0~~(\forall I \in \mathcal{I}(G)). \end{align*} $$

It can easily be checked that this linear program is bounded and feasible, and hence has a unique optimum $y^\ast $ . Further, since the constraints of the program encode a probability distribution $\mathcal {D}$ on independent sets with $\mathbb {P}_{I\sim \mathcal {D}}[v\in I]\ge f\left (\frac {w(N_G(v))}{w(v)}\right )-y$ , we can see that $K_w=[y^\ast ,1]$ is indeed a closed set as desired.

This shows that K is indeed compact and hence has a unique minimum $\delta _0 \in K$ . Our goal is to show that $0\in K$ (equivalently, $\delta _0=0$ ), since this clearly establishes the induction hypothesis for G. So, toward a contradiction, let us assume $\delta _0>0$ in the following.

Let us define $\delta :=\delta _0-\frac {\delta _0^2}{8}$ . Then, since $\delta \in (0,\delta _0)$ and hence $\delta \notin K$ , there exists a positive weight function $w:V(G)\rightarrow \mathbb {R}_+$ such that there exists no probability distribution on the independent sets of G for which every vertex v is contained in an independent set drawn from the distribution with probability at least $f\left (\frac {w(N_G(v))}{w(v)}\right )-\delta $ . Since the latter formula is scale-invariant, we may assume without loss of generality throughout the rest of the proof that $w(V(G))=1$ .

Let us pick and fix some $\varepsilon \in (0,1)$ (for now arbitrarily, later on we will assign a concrete value). Let $w':V(G)\rightarrow \mathbb {R}^+$ be a modified vertex-weighting of G, defined as $w'(v):=w(v)\cdot \exp \left (\varepsilon w(N_G(v))\right )$ for every $v\in V(G)$ .

Since $\delta _0\in K$ , there must exist a probability distribution $\mathcal {D}$ on the independent sets of G such that

$$ \begin{align*}\mathbb{P}_{I\sim \mathcal{D}}[v\in I]\ge f\left(\frac{w'(N_G(v))}{w'(v)}\right)-\delta_0\end{align*} $$

for every $v\in V(G)$ .

For a vertex $u\in V(G)$ , let us denote by $\overline {N}_G(u):=\{u\}\cup N_G(u)$ the closed neighborhood of u and by $G_u:=G-\overline {N}_G(u)$ the graph obtained from G by deleting this closed neighborhood. By the inductive assumption, for every $u\in V(G)$ there exists a probability distribution $\mathcal {D}_u$ on $G_u$ such that $\mathbb {P}_{I\sim \mathcal {D}_u}[v \in I]\ge f\left (\frac {w'(N_{G_u}(v))}{w'(v)}\right )$ for every $v\in V(G_u)$ .

Let us now define $\varepsilon :=\frac {\delta _0}{4} \in (0,1)$ , and let us consider the following process to generate a random independent set I of G:

• • With probability $1-\varepsilon $ (we call this event A), draw I randomly from the distribution $\mathcal {D}$ and return I.

• • With probability $\varepsilon $ (we call this event $B:=A^{\mathsf {c}}$ ), do the following: First, sample randomly a vertex $u\in V(G)$ where u equals any given vertex x with probability exactly $w(x)$ . Then, randomly draw an independent set $I_u$ from the distribution $\mathcal {D}_u$ and return the independent set $I:=\{u\}\cup I_u$ .

In the following, let $\mathcal {D}'$ denote the probability distribution on independent sets of G that is induced by the random independent set I created according to the above process. By our choice of the weight function w, there must exist some vertex $v\in V(G)$ such that

$$ \begin{align*}\mathbb{P}_{I\sim \mathcal{D}'}[v\in I]<f\left(\frac{w(N_G(v))}{w(v)}\right)-\delta.\end{align*} $$

Our intermediate goal is to give a lower bound on $\mathbb {P}_{I\sim \mathcal {D}'}[v\in I]$ .

To estimate this probability, we stick with the random process described above. We then have

$$ \begin{align*} \mathbb{P}_{I\sim \mathcal{D}'}[v\in I] &=(1-\varepsilon)\mathbb{P}_{I\sim \mathcal{D}'}[v\in I|A]+\varepsilon \mathbb{P}_{I\sim \mathcal{D}'}[v\in I|B]\\ &=(1-\varepsilon)\mathbb{P}_{I\sim \mathcal{D}}[v\in I]+\varepsilon\sum_{x\in V(G)}\mathbb{P}_{I\sim \mathcal{D}'}[v\in I|B \wedge \{u=x\}]w(x)\\ &=(1-\varepsilon)\mathbb{P}_{I\sim \mathcal{D}}[v\in I]+\varepsilon w(v)+\varepsilon\sum_{x\in V(G)\setminus \overline{N}_G(v)}\mathbb{P}_{I\sim \mathcal{D}_x}[v\in I]w(x).\end{align*} $$

By our choice of the distributions $\mathcal {D}$ and $\mathcal {D}_x$ , $x\in V(G)$ , we have

$$ \begin{align*} &(1-\varepsilon)\mathbb{P}_{I\sim \mathcal{D}}[v\in I]+\varepsilon\sum_{x\in V(G)\setminus \overline{N}_G(v)}\mathbb{P}_{I\sim \mathcal{D}_x}[v\in I]w(x)\\ &\ge (1-\varepsilon)\left(f\left(\frac{w'(N_G(v))}{w'(v)}\right)-\delta_0\right)+\varepsilon \sum_{x\in V(G)\setminus \overline{N}_G(v)}f\left(\frac{w'(N_{G_x}(v))}{w'(v)}\right)w(x)\\ &=-(1-\varepsilon)\delta_0+(1-\varepsilon)f\left(\frac{w'(N_G(v))}{w'(v)}\right)+\sum_{x\in V(G)\setminus \overline{N}_G(v)}\varepsilon w(x)f\left(\frac{w'(N_{G_x}(v))}{w'(v)}\right).\end{align*} $$

Since $(1-\varepsilon )+\sum _{x\in V(G)\setminus \overline {N}_G(v)}\varepsilon w(x)=(1-\varepsilon )+\varepsilon \left (1-w(\overline {N}_G(v))\right )=1-\varepsilon w(\overline {N}_G(v))$ , the convexity of f implies that

$$ \begin{align*}(1-\varepsilon)f\left(\frac{w'(N_G(v))}{w'(v)}\right)+\sum_{x\in V(G)\setminus \overline{N}_G(v)}\varepsilon w(x)f\left(\frac{w'(N_{G_x}(v))}{w'(v)}\right)\ge\end{align*} $$

$$ \begin{align*}\left(1-\varepsilon w(\overline{N}_G(v))\right)f\left(\frac{(1-\varepsilon)w'(N_G(v))+\sum_{x\in V(G)\setminus \overline{N}_G(v)}\varepsilon w(x)w'(N_{G_x}(v))}{w'(v)\left(1-\varepsilon w(\overline{N}_G(v))\right)}\right).\end{align*} $$

The next claim gives a simple upper bound for the expression in the argument of f above.

Claim 2.2. We have that

$$ \begin{align*}\frac{(1-\varepsilon)w'(N_G(v))+\sum_{x\in V(G)\setminus \overline{N}_G(v)}\varepsilon w(x)w'(N_{G_x}(v))}{w'(v)\left(1-\varepsilon w(\overline{N}_G(v))\right)} \le \frac{w(N_G(v))}{w(v)}\cdot e^{\varepsilon (w(v)-w(N_G(v)))}.\end{align*} $$

Proof.

We have

$$ \begin{align*} &(1-\varepsilon) w'(N_G(v))+\sum_{x\in V(G)\setminus \overline{N}_G(v)}\varepsilon w(x)w'(N_{G_x}(v))\\ &=\sum_{y\in N_G(v)}{(1-\varepsilon)w'(y)}+\sum_{x\in V(G)\setminus \overline{N}_G(v)}\varepsilon w(x)\sum_{y\in N_G(v)\setminus \overline{N}_G(x)}{w'(y)}\\ &=\sum_{y\in N_G(v)}\left((1-\varepsilon)+\sum_{x\in V(G)\setminus (\overline{N}_G(v)\cup \overline{N}_G(y))}\varepsilon w(x)\right)w'(y)\\ &=\sum_{y\in N_G(v)}\left(1-\varepsilon+\varepsilon(1-w(\overline{N}_G(v)\cup \overline{N}_G(y)))\right)w'(y)\\ &=\sum_{y\in N_G(v)}\left(1-\varepsilon w(\overline{N}_G(v)\cup \overline{N}_G(y))\right)w'(y). \end{align*} $$

Note that for every $y\in N_G(v)$ , we have $\overline {N}_G(v)\cup \overline {N}_G(y)=N_G(v)\cup N_G(y)$ . Furthermore, since G is triangle-free, the sets $N_G(v)$ and $N_G(y)$ are disjoint, and thus we have $w(\overline {N}_G(v)\cup \overline {N}_G(y))=w(N_G(v))+w(N_G(y))$ . This implies

$$ \begin{align*} &\frac{(1-\varepsilon)w'(N_G(v))+\sum_{x\in V(G)\setminus \overline{N}_G(v)}\varepsilon w(x) w'(N_{G_x}(v))}{w'(v)\left(1-\varepsilon w(\overline{N}_G(v))\right)}\\ &=\frac{ 1}{w'(v)}\sum_{y\in N_G(v)}{\frac{1-\varepsilon w(N_G(v))-\varepsilon w(N_G(y))}{1-\varepsilon w(\overline{N}_G(v))}w'(y)}\\ &=\frac{ 1}{w'(v)}\sum_{y\in N_G(v)}{\left(1-\varepsilon \frac{w(N_G(y))-w(v)}{1-\varepsilon w(\overline{N}_G(v))}\right)w'(y)}\\ &\le \frac{ 1}{w'(v)}\sum_{y\in N_G(v)}{\left(1-\varepsilon (w(N_G(y))-w(v))\right)w'(y)}\\ &\le \frac{1}{w'(v)}\sum_{y\in N_G(v)}\exp\left(-\varepsilon (w(N_G(y))-w(v))\right)\cdot w(y)\exp\left(\varepsilon w(N_G(y))\right)\\ &=\frac{1}{w'(v)}\exp\left(\varepsilon w(v)\right)w(N_G(v))\\ &=\frac{w(N_G(v))}{w(v)}\cdot \exp\left(\varepsilon(w(v)-w(N_G(v)))\right), \end{align*} $$

where we used the definition of $w'$ in the last and third to last line. This concludes the proof of the claim.

Using Claim 2.2 and the previously established inequalities (using that f is monotonically decreasing), it follows that $\mathbb {P}_{I\sim \mathcal {D}'}[v\in I]$ is lower-bounded by

$$ \begin{align*}\varepsilon w(v)-(1-\varepsilon)\delta_0+\left(1-\varepsilon w(\overline{N}_G(v))\right)f\left(\frac{w(N_G(v))}{w(v)}\cdot \exp\left(\varepsilon (w(v)-w(N_G(v)))\right)\right).\end{align*} $$

Let us now go about estimating the above expression. By Taylor expansion, it is not hard to verify that the inequality $\exp (z)\le 1+z+z^2$ holds for every $z\in [-1,1]$ . Let us set $x:=\frac {w(N_G(v))}{w(v)}$ , $z:=\varepsilon (w(v)-w(N_G(v)))$ and $y:=x\cdot \exp (z)$ . Note that since f is convex and differentiable, we have the inequality $f(y)\ge f(x)+f'(x)(y-x)$ . Since $w(v), w(N_G(v))\le w(V(G))=1$ , we obtain $|z|\le \varepsilon <1$ and thus $y\le x(1+z+z^2)$ . Since f is monotonically decreasing, we have $f'(x)<0$ . Putting these facts together, it follows that

$$ \begin{align*}&f\left(\frac{w(N_G(v))}{w(v)}\cdot \exp\left(\varepsilon (w(v)-w(N_G(v)))\right)\right)=f(y)\\ &\ge f(x)+f'(x)(y-x)\\ &\ge f(x)+f'(x)\cdot x\cdot (z+z^2)\\ & \ge f(x)+xzf'(x)-\varepsilon^2,\end{align*} $$

where we used that $|x\cdot f'(x)|\le 1$ for every $x>0$ and that $|z|\le \varepsilon $ in the last line. Plugging this estimate into the above lower bound for $\mathbb {P}_{I\sim \mathcal {D}'}[v\in I]$ and using that by our choice of v, we have $\mathbb {P}_{I\sim \mathcal {D}'}[v\in I]<f\left (\frac {w(N_G(v))}{w(v)}\right )-\delta $ , we find:

$$ \begin{align*} &f(x)-\delta>\mathbb{P}_{I\sim \mathcal{D}'}[v\in I]\\ &\ge -(1-\varepsilon)\delta_0+\varepsilon w(v)+(1-\underbrace{\varepsilon (w(v)+w(N_G(v)))}_{\le \varepsilon})\cdot (f(x)+\underbrace{xzf'(x)-\varepsilon^2}_{\le \varepsilon})\\ &>-(1-\varepsilon)\delta_0+\varepsilon w(v)+f(x)+xzf'(x)-2\varepsilon^2-\varepsilon(w(v)+w(N_G(v)))f(x). \end{align*} $$

Rearranging yields

$$ \begin{align*}\delta_0-\delta>\varepsilon\delta_0-2\varepsilon^2+\varepsilon w(v)+xzf'(x)-\varepsilon (w(v)+w(N_G(v)))f(x).\end{align*} $$

Using that $x=\frac {w(N_G(v))}{w(v)}$ and $z=\varepsilon w(v) (1-x)$ , we can simplify as follows.

$$ \begin{align*} &\varepsilon w(v)+xzf'(x)-\varepsilon(w(v)+w(N_G(v)))f(x)\\ &=\varepsilon w(v)\left(1+x(1-x)f'(x)-(1+x)f(x)\right)=0, \end{align*} $$

where we used the differential equation satisfied by f in the last step. Hence, we have proven the inequality $\delta _0-\delta>\varepsilon \delta _0-2\varepsilon ^2$ . Recalling our definitions $\delta :=\delta _0-\frac {\delta _0^2}{8}$ and $\varepsilon :=\frac {\delta _0}{4}$ we can now see that the above inequality implies $\frac {\delta _0^2}{8}>\frac {\delta _0^2}{8}$ , which is absurd. This is the desired contradiction, which shows that our initial assumption, namely that $\delta _0>0$ , was wrong. Hence, we have shown that $\delta _0=0$ , establishing the inductive claim for G. This concludes the proof of the theorem by induction.

Proof of Theorem 1.2.

Let G be any given triangle-free graph, and let $w:V(G)\rightarrow \mathbb {R}_+$ be defined as $w(v):=1$ for every $v\in V(G)$ . Then $\frac {w(N_G(v))}{w(v)}=d_G(v)$ for every vertex $v\in V(G)$ , and hence by Theorem 2.1 there exists a probability distribution $\mathcal {D}$ on independent sets of G such that

$$ \begin{align*}\mathbb{P}_{I\sim \mathcal{D}}[v\in I]\ge f(d_G(v))\end{align*} $$

for every $v\in V(G)$ . Since $f(x)=(1-o(1))\frac {\ln (x)}{x}$ , this establishes Theorem 1.2.

Proof of Theorem 1.4.

The statement of Theorem 1.4 is equivalent to showing that for every fixed $\delta>0$ and n sufficiently large in terms of $\delta $ , every triangle-free graph G on n vertices satisfies $\chi _f(G)\le (\sqrt {2}+\delta )\sqrt {\frac {n}{\ln n}}$ . Let $\varepsilon>0$ and $0<c<1$ (only depending on $\delta $ ) be chosen such that $\sqrt {2/c}+\varepsilon <\sqrt {2}+\delta $ . By Proposition 3.1 there exists $n_0=n_0(\varepsilon ,c)\in \mathbb {N}$ such that every triangle-free graph G with $n\ge n_0$ vertices that admits an h-coloring for some demand function h satisfying $h(v)\ge c\frac {\ln d_G(v)}{d_G(v)}$ for all $v\in V(G)$ has fractional chromatic number at most $(\sqrt {2/c}+\varepsilon )\sqrt {\frac {n}{\ln n}}\le (\sqrt {2}+\delta )\sqrt {\frac {n}{\ln n}}$ . By [Reference Kelly and Postle40, Proposition 1.4 (c)] the latter statement is equivalent to the following: Every triangle-free graph on $n\ge n_0$ vertices that admits a probability distribution on its independent sets such that each vertex v is included with probability at least $c\frac {\ln d_G(v)}{d_G(v)}$ in a randomly drawn independent set has fractional chromatic number at most $(\sqrt {2}+\delta )\sqrt {\frac {n}{\ln n}}$ .

Since $c<1$ , Theorem 1.2 implies that there exists a constant $D=D(c)$ such that every triangle-free graph of minimum degree at least D admits a probability distribution on its independent sets where each vertex v is included in a randomly drawn independent set with probability at least $c\frac {\ln d_G(v)}{d_G(v)}$ . Putting this together with the statement above, we immediately obtain that every triangle-free graph on $n\ge n_0$ vertices with minimum degree at least D has fractional chromatic number at most $(\sqrt {2}+\delta )\sqrt {\frac {n}{\ln n}}$ .

Let $n_1$ be an integer chosen large enough such that $(\sqrt {2}+\delta )\sqrt {\frac {n_1}{\ln n_1}}>\max \{D+1,n_0\}$ . We now claim that every triangle-free graph on $n\ge n_1$ vertices has fractional chromatic number at most $(\sqrt {2}+\delta )\sqrt {\frac {n}{\ln n}}$ , which is the statement that we wanted to prove initially. Let G be any given triangle-free graph on $n\ge n_1$ vertices. Let $G'$ be the subgraph of G obtained by repeatedly removing vertices of degree less than D from G, until no such vertices are left ( $G'$ is the so-called D-core of G). Then $G'$ is a triangle-free graph that is either empty or has minimum degree at least D. Hence, we either have $|V(G')|<n_0$ and thus $\chi _f(G')<n_0$ , or $|V(G')|\ge n_0$ and thus $\chi _f(G')\le (\sqrt {2}+\delta )\sqrt {\frac {|V(G')|}{\ln |V(G')|}}\le (\sqrt {2}+\delta )\sqrt {\frac {n}{\ln n}}$ .

Pause to verify that $\chi _f(G)\le \max \{\chi _f(G-v),d_G(v)+1\}$ holds for every graph G and every vertex $v\in V(G)$ . Repeated application of this fact combined with the definition of $G'$ now implies that

$$ \begin{align*}\chi_f(G)\le \max\{\chi_f(G'),D+1\}\le \max\left\{n_0,(\sqrt{2}+\delta)\sqrt{\frac{n}{\ln n}},D+1\right\}=(\sqrt{2}+\delta)\sqrt{\frac{n}{\ln n}},\end{align*} $$

as desired. Here, we used our choice of $n_1$ and that $n\ge n_1$ in the last step. This concludes the proof.

Proof of Theorem 1.5.

Let G be any given triangle-free graph with m edges. To prove the upper bound on the fractional chromatic number, without loss of generality it suffices to consider the case when G has no isolated vertices. By definition of the fractional chromatic number, we have to show that there exists a probability distribution on the independent sets of G for which a randomly drawn independent set contains any given vertex of G with probability at least $ (1-o(1))(\ln m)^{2/3}/(18 m)^{1/3}$ . To construct such a distribution, we consider the following process to generate a random independent set I in G. With probability $1/3$ pick I as in Theorem 2.1 with the weight function defined as $w_1(v):=1$ for every $v\in V(G)$ , with probability $1/3$ we pick I as in Theorem 2.1 using the weight function $w_2(v):=d_G(v)$ for every $v\in V(G)$ , and with probability $1/3$ we pick a random vertex u in G with $\mathbb {P}[u=v]=d_G(v)/2m$ for every $v\in V(G)$ and let I be its neighborhood (which is clearly an independent set in G).

It follows that

$$ \begin{align*}\mathbb{P}[v\in I]\geq \frac{1}{3} f(d_G(v))+\frac{1}{3} f(S_G(v)/d_G(v)) + \frac{1}{3} \frac{S_G(v)}{2m},\end{align*} $$

for every $v\in V(G)$ , where $S_G(v)$ denotes the sum of degrees over all neighbors of v in G. It suffices to show that the right-hand side is at least $(1-o(1)) (\ln m)^{2/3}/(18 m)^{1/3}$ for all vertices v.

Observe that if either $d_G(v)< m^{1/3}$ or $S_G(v)/d_G(v) < m^{1/3}$ , then the desired inequality is already satisfied with room to spare from the first and second terms, respectively. Otherwise, if $d_G(v)\geq m^{1/3}$ and $S_G(v)/d(v) \geq m^{1/3}$ , we have

$$ \begin{align*} &\frac{1}{3} f(d_G(v))+\frac{1}{3} f(S_G(v)/d_G(v)) + \frac{1}{3} \frac{S_G(v)}{2m}\\ &\qquad = \frac{1}{3} \frac{(1-o(1))\ln d_G(v)}{d_G(v)} +\frac{1}{3} \frac{(1-o(1))\ln(S_G(v)/d_G(v))}{S_G(v)/d_G(v)} + \frac{1}{3} \frac{S_G(v)}{2m}\\ &\qquad \geq \frac{1}{3} \frac{(1-o(1))\ln(m^{1/3})}{d(v)} +\frac{1}{3} \frac{(1-o(1))\ln(m^{1/3})}{S_G(v)/d_G(v)} + \frac{1}{3} \frac{S_G(v)}{2m}\\ &\qquad \geq \left(\frac{(1-o(1))\ln(m^{1/3})}{d_G(v)} \cdot \frac{(1-o(1))\ln(m^{1/3})}{S_G(v)/d_G(v)} \cdot \frac{S_G(v)}{2m}\right)^{1/3}, \end{align*} $$

where the last line follows by the AM–GM inequality. Simplifying yields a lower bound of $(1-o(1))\left (\frac {\ln (m)^2}{18m}\right )^{1/3}$ , as desired.

Claim 4.2. For any function $f:\mathbb {R}\rightarrow \mathbb {R}$ such that $f(0)=0$ we have

$$ \begin{align*}\mathbb{E}_{w}\left[f(w_{k-1}(v_k))\right]=\mathbb{E}_{\tilde{w}}\left[f(\tilde{w}_{k-1}(v_k)) e^{-X} \right].\end{align*} $$

Proof.

We can encode each possible sequence of weight functions $(w_0, w_1, \dots , w_{k-1})$ of the process w as a sequence $a\in \{1,2\}^{k-1}$ where $a_i$ denotes whether, in step i, randomness chooses the first or the second bullet point. In other words, $a_i=1$ if and only if $v_i\in I$ .

Note that if $a_i=1$ for any index i where $v_i\in N_L(v_k)$ then this sequence will result in $w_{k-1}(v_k)=0$ . Thus, such a sequence does not contribute to the value of $\mathbb {E}_{w}\left [f(w_{k-1}(v_k))\right ]$ . Similarly, if $a_i=a_j=1$ for any two neighboring vertices $v_i$ and $v_j$ , then the probability of the corresponding sequence is $0$ , which means it also does not contribute to $\mathbb {E}_{w}\left [f(w_{k-1}(v_k))\right ]$ .

Let $A\subseteq \{1,2\}^{k-1}$ denote the set of sequences that do not match either of the aforementioned conditions. Then any $a\in A$ can be interpreted as a possible sequence of weight functions $(w_0, \dots , w_{k-1})$ and $(\tilde {w}_0, \dots , \tilde {w}_{k-1})$ produced by either process w or $\tilde {w}$ . Note that, by definition of w and $\tilde {w}$ , the same sequence of choices a will produce the same sequence of weight functions in either process. Let us denote this common sequence by $w^a$ , and let us denote by $\mathbb {P}_w[a]$ and $\mathbb {P}_{\tilde {w}}[a]$ the probabilities that the sequence of choices of the respective processes equals a.

By comparing the transition probabilities of w and $\tilde {w}$ , we immediately get

$$ \begin{align*} \frac{\mathbb{P}_w[a]}{\mathbb{P}_{\tilde{w}}[a]} &= \exp\left(-\sum_{v_i\in N_L(v_k)} w^a_{i-1}(v_i)\right) =\exp\left(-\sum_{v_i\in N_L(v_k)} w^a_{k-1}(v_i)\right) \end{align*} $$

for all $a\in A$ , where the last equality follows by observing that no vertex $v_i$ has its weight updated after step $i-1$ . Thus

$$ \begin{align*} \mathbb{E}_{w}[f(w_{k-1}(v_k)] &=\sum_{a\in A} f(w^a_{k-1}(v_k)) \mathbb{P}_w[a]\\ &=\sum_{a\in A} f(w^a_{k-1}(v_k))\exp\left(-\sum_{v_i\in N_L(v_k)} w^a_{k-1}(v_i)\right)\mathbb{P}_{\tilde{w}}[a]\\ &=\mathbb{E}_{\tilde{w}}[f(\tilde{w}_{k-1}(v_k))e^{-X} ].\\[-34pt] \end{align*} $$

Claim 4.3. Suppose $v_i\in N_L(v_k)$ . Then $\tilde {w}_t(v_i)$ is a martingale in t for $t=0, \dots , k-1$ .

Proof.

By definition of $\tilde {w}$ , the only steps j where the value of $\tilde {w}(v_i)$ is updated are those where $v_j\in N_L(v_i)$ . Note that $v_j\not \in N_L(v_k)$ as otherwise $v_i, v_j, v_k$ would form a triangle. Thus $\tilde {w}(v_i)$ is updated according to

$$ \begin{align*}\tilde{w}_j(v_i) = \begin{cases} 0&\text{ with probability }1-e^{-\tilde{w}_{j-1}(v_j)}\\ \tilde{w}_{j-1}(v_i)e^{\tilde{w}_{j-1}(v_j)}&\text{ with probability }e^{-\tilde{w}_{j-1}(v_j)}.\end{cases}\end{align*} $$

It is easy to see that this is preserved in expectation.

Claim 4.4.

$$ \begin{align*}\mathbb{E}_{\tilde{w}}[X] = \sum_{v_i \in N_L(v_k)} w_0(v_i).\end{align*} $$

Proof.

By Claim 4.3, $\mathbb {E}_{\tilde {w}}[X]=\sum _{v_i\in N_L(v_k)}\mathbb {E}_{\tilde {w}}[\tilde {w}_{k-1}(v_i)] = \sum _{v_i\in N_L(v_k)}\mathbb {E}_{\tilde {w}}[\tilde {w}_{0}(v_i)]. $

Claim 4.5.

$$ \begin{align*}\tilde{w}_{k-1}(v_k)=w_0(v_k) e^X.\end{align*} $$

Proof.

By definition of $\tilde {w}$ , $\tilde {w}(v_k)$ increases by a factor $e^{\tilde {w}_{i-1}(v_i)}=e^{\tilde {w}_{k-1}(v_i)}$ for each step i where $v_i\in N_L(v_k)$ . For any other step, $\tilde {w}(v_k)$ is unchanged.

Claim 4.6.

$$ \begin{align*}\mathbb{P}_{w}[v_k\in I] = \mathbb{E}_{\tilde{w}}\left[ \left(1-e^{-w_0(v_k) e^X}\right)e^{-X} \right].\end{align*} $$

Proof.

By the definition of w and I we have $\mathbb {P}_{w}[v_k\in I] = \mathbb {E}_{w}[1-e^{-w_{k-1}(v_k)}].$ Let $f(x)=1-e^{-x}$ . By Claim 4.2, noting that $f(0)=0$ , we get

$$ \begin{align*}\mathbb{E}_{w}[1-e^{-w_{k-1}(v_k)}] = \mathbb{E}_{w}[f(w_{k-1}(v_k))] = \mathbb{E}_{\tilde{w}}[f(\tilde{w}_{k-1}(v_k))e^{-X} ].\end{align*} $$

By Claim 4.5, $\tilde {w}_{k-1}(v_k)=w_0(v_k) e^X$ . Combining these gives the desired equality.

Proof of Theorem 4.1.

By Claim 4.4, we know that X is a non-negative random variable satisfying

$$ \begin{align*}\mathbb{E}_{\tilde{w}}[X] = \sum_{v_i \in N_L(v_k)} w_0(v_i) \leq \frac12 \ln\left( \frac1{w_0(v_k)} \right).\end{align*} $$

Moreover, by Claim 4.6, we have that

$$ \begin{align*}\mathbb{P}_{w}[v_k \in I]=\mathbb{E}_{\tilde{w}}\left[\left(1-e^{-w_0(v_k) e^X}\right)e^{-X}\right].\end{align*} $$

In order to estimate this expectation given the aforementioned conditions on X, we need the following somewhat technical inequalities.

Claim 4.8. For any real numbers $x>0$ and $0<w<1.79328$ we have

$$ \begin{align*}\left(1-e^{-w e^x}\right)e^{-x} \geq (1-e^{-w})\left(1-\frac{x}{\ln(1.79328/w)}\right).\end{align*} $$

Proof.

Observe that $\left (1-e^{-w e^x}\right )e^{-x}$ is non-negative. Moreover, it is easy to check that its second derivative in x equals

$$ \begin{align*}e^{-x-w e^x}\left(e^{w e^x} - 1 - we^x - w^2 e^{2x}\right),\end{align*} $$

which, by Claim 4.7 (1), is negative whenever $we^x < 1.79328$ , that is, $x<\ln (1.79328/w)$ . Hence the inequality in the lemma holds for $0\leq x \leq \ln (1.79328/w)$ as the inequality clearly holds at both endpoints, and the function is concave on the interval between these points. But for larger x, the inequality also holds as the right-hand side then turns negative.

Given these inequalities, the theorem follows by straightforward calculations. By Claim 4.8 and since $\mathbb {E}_{\tilde {w}}[X]\le \frac {1}{2}\ln \left (\frac {1}{w_0(v_k)}\right )$ , we have:

$$ \begin{align*} \mathbb{P}_{w}[v_k\in I] &\geq \mathbb{E}_{\tilde{w}}\left[\left(1-e^{-w_0(v_k)}\right)\left(1-\frac{X}{\ln(1.79328/w_0(v_k))}\right)\right]\\ &\geq \left(1-e^{-w_0(v_k)}\right)\left(1-\frac{\ln(1/w_0(v_k))}{2\ln(1.79328/w_0(v_k))}\right), \end{align*} $$

which by Claim 4.7 (2) is at least $\frac {w_0(v_k)}{2}$ , as desired.

Proof of Theorem 1.7.

Let G be a triangle-free d-degenerate graph with degeneracy order $v_1, \dots , v_n$ such that $|N_L(v_i)|\leq d$ for all vertices $v_i$ . Assume $d\geq 2.$ We apply Theorem 4.1 with $w_0\equiv \frac {\ln d -\ln \ln d}{2d}.$ One immediately checks that $0<w_0(v_k)<1$ and

$$ \begin{align*}\frac12 \ln w_0(v_k) + \sum_{v_i\in N_L(v_k)} w_0(v_i) \leq \frac12 \ln\left(\frac12 \left(\ln d - \ln\ln d\right)\right)-\frac12 \ln\ln d\leq 0,\end{align*} $$

which implies that

$$ \begin{align*}\mathbb{P}[v_k\in I] \geq \frac12 w_0(v_k)=\left(\frac14-o(1)\right)\frac{\ln d}{d}.\\[-38pt] \end{align*} $$

Proof of Theorem 1.8.

We apply Theorem 4.1 with $w_0(v_i):=\frac 12 p(v_i)$ . Observe that

$$ \begin{align*}p(v_k) \leq \prod_{v_i\in N_L(v_k)}\left(1-p(v_i)\right) \leq \exp\left(-\sum_{v_i\in N_L(v_k)} p(v_i)\right),\end{align*} $$

which implies that $\ln p(v_k) + \sum _{v_i\in N_L(v_k)} p(v_i) \leq 0$ and hence $\frac 12 \ln w_0(v_k) + \sum _{v_i\in N_L(v_k)} w(v_i)\leq -\frac 12 \ln 2 < 0.$ Moreover, clearly $0<w_0(v_i)<\frac 12$ for all $v_i$ . Hence

$$ \begin{align*}\mathbb{P}[v_k\in I] \geq \frac12 w_0(v_k)=\frac14 p(v_k),\end{align*} $$

as desired.