Local Shearer bound Thanks: A.M.: Institute of Theoretical Computer Science, Department of Computer Science, ETH Zürich, Switzerland. Thanks: anders.martinsson@inf.ethz.ch Thanks: R.S.: Institute for Operations Research, Department of Mathematics, ETH Zürich, Switzerland. Thanks: raphaelmario.steiner@math.ethz.ch . Thanks: The research of R.S. was funded by the SNSF Ambizione Grant No. 216071 of the Swiss National Science Foundation. Anders Martinsson, Raphael Steiner Abstract . We prove the following local strengthening of Shearer’s classic bound on the independence number of triangle-free graphs: For every triangle-free graph G G there exists a probability distribution on its independent sets such that every vertex v v of G G is contained in a random independent set drawn from the distribution with probability ( 1 − o ⁡ ( 1 ) ) ​ ln ⁡ d ⁡ ( v ) d ⁡ ( v ) (1-o(1))\frac{\ln d(v)}{d(v)} . This resolves the main conjecture raised by Kelly and Postle (2018) about fractional coloring with local demands, which in turn confirms a conjecture by Cames van Batenburg et al. (2018) stating that every n n -vertex triangle-free graph has fractional chromatic number at most ( 2 + o ⁡ ( 1 ) ) ​ n ln ⁡ ( n ) (\sqrt{2}+o(1))\sqrt{\frac{n}{\ln(n)}} . Addressing another conjecture posed by Cames van Batenburg et al., we also establish an analogous upper bound in terms of the number of edges. To prove these results we establish a more general technical theorem that works in a weighted setting. As a further application of this more general result, we obtain a new spectral upper bound on the fractional chromatic number of triangle-free graphs: We show that every triangle-free graph G G satisfies χ f ​ ( G ) ≤ ( 1 + o ⁡ ( 1 ) ) ​ ρ ⁡ ( G ) ln ⁡ ρ ⁡ ( G ) \chi_{f}(G)\leq(1+o(1))\frac{\rho(G)}{\ln\rho(G)} where ρ ⁡ ( G ) \rho(G) denotes the spectral radius. This improves the bound implied by Wilf’s classic spectral estimate for the chromatic number by a ln ⁡ ρ ⁡ ( G ) \ln\rho(G) factor and makes progress towards a conjecture of Harris on fractional coloring of degenerate graphs. 1. Introduction One of the most fundamental problems in all of combinatorics concerns bounding the famous Ramsey number R(\ell,k) , which may be defined as the smallest number n such that every graph on n vertices contains either a clique of size \ell or an independent set of size k . The first highly challenging instance of this general problem is the determination of the Ramsey-numbers R(3,k) , posed as a price-money question by Erdős already back in 1961 [ 22 ] (see also this Erdős problem page entry ). Currently, the best known asymptotic bounds are \left(\frac{1}{4}-o(1)\right)\frac{k^{2}}{\ln k}\leq R(3,k)\leq(1+o(1))\frac{k^{2}}{\ln k}. The lower bound was established by an analysis of the famous triangle-free process independently by Fiz Pontiveros, Griffiths and Morris [ 25 ] and Bohman and Keevash [ 8 ] in 2013. Proving an upper bound on R(3,k) is equivalent to establishing a lower bound on the independence number \alpha(G) (i.e., the size of a largest independent set in G ) for all triangle-free graphs on n vertices. It turns out that the upper bound on R(3,k) stated above is a straightforward consequence of a much more general such lower bound on the independence number of triangle-free graphs, established in a landmark result by Shearer in 1983 [ 44 ] . Shearer’s classic bound states that every triangle-free graph on n vertices with average degree \overline{d} satisfies \alpha(G)\geq\frac{(1-\overline{d})+\overline{d}\ln\overline{d}}{(\overline{d}-1)^{2}}n=(1-o(1))\frac{\ln\overline{d}}{\overline{d}}n , which improves over the easy lower bound \alpha(G)\geq\frac{n}{\overline{d}+1} which follows from Turán’s theorem by roughly a \ln\overline{d} -factor. In a refinement of this result, Shearer [ 45 ] proved in 1991 that every triangle-free graph satisfies \alpha(G)\geq\sum_{v\in V(G)}g(d_{G}(v)) , where d_{G}(v) denotes the degree of v in G and g(d)=(1-o(1))\frac{\ln d}{d} is a recursively defined function. This bound is slightly better than Shearer’s first bound in terms of the average degree for graphs with unbalanced degree sequences. These two classic bounds on the independence number of triangle-free graphs due to Shearer have found widespread application across many topics in extremal combinatorics and nowadays form one of its basic tools. By a result of Bollobás [ 9 ] , it is known that Shearer’s bounds are tight up to a multiplicative factor of 2 . Because of the relation to the Ramsey-numbers R(3,k) discussed above, any constant factor improvement of Shearer’s longstanding bounds would be a major breakthrough in Ramsey theory. Due to this, a lot of research has been devoted to finding strengthenings and generalizations of Shearer’s bounds: We refer to [ 34 ] for a recent survey covering Shearer’s bound and related results in the theory of graph coloring and to [ 1 , 15 , 16 , 18 , 19 , 20 , 42 ] for some (mostly recent) extensions and generalizations of Shearer’s bounds. The study of lower bounds on the independence number, such as the aforementioned bounds of Shearer, is closely connected to the theory of graph coloring. Recall that in a proper graph coloring vertices are assigned colors such that neighboring vertices have distinct colors, and the chromatic number \chi(G) of a graph G is the smallest amount of colors required to properly color G . It is easily seen by the definition (by considering a largest “color class”) that every graph G on n vertices has an independent set of size at least \frac{n}{\chi(G)} . An even stronger lower bound on the independence number is provided by the well-known fractional chromatic number \chi_{f}(G) of the graph. The fractional chromatic number has many different equivalent definitions (see the standard textbook [ 43 ] on fractional coloring as a reference). Here, we shall find the following definition convenient: \chi_{f}(G) is the minimum real number r\geq 1 such that there exists a probability distribution on the independent sets of G such that a random independent set I sampled from this distribution contains any given vertex v\in V(G) with probability at least \frac{1}{r} . By considering the expected size of a random set drawn from such a distribution, one immediately verifies that \alpha(G)\geq\frac{n}{\chi_{f}(G)} holds for every graph G . In general, the latter lower bound \frac{n}{\chi_{f}(G)} on the independence number is stronger than the lower bound \frac{n}{\chi(G)} , as there are graphs (namely, the so-called Kneser graphs [ 5 , 38 ] ) for which \chi_{f}(G) is much smaller than \chi(G) . Given these lower bounds of the independence number in terms of the (fractional) chromatic number, it is natural to ask whether there are analogues or strengthenings of Shearer’s bounds that provide corresponding upper bounds for the (fractional) chromatic number. A prime example of such a result is a recent breakthrough of Molloy [ 40 ] , who proved that \chi(G)\leq(1+o(1))\frac{\Delta}{\ln\Delta} for every triangle-free graph G with maximum degree \Delta , where the o(1) -term vanishes as \Delta\rightarrow\infty . This strengthened a previous bound of the form O\left(\frac{\Delta}{\ln\Delta}\right) due to Johansson [ 33 ] and recovers Shearer’s independence number bound in the case of regular graphs in a stronger form. As with Shearer’s bound, it is known that Molloy’s bound is optimal up to a factor of 2 , and improving the constant 1 to any constant below 1 would be a major advance in the field. Several interesting strengthenings and generalizations of Johansson’s and Molloy’s results have been proved in the literature, see e.g. [ 2 , 3 , 4 , 6 , 10 , 11 , 15 , 31 , 32 , 42 ] for some selected examples. Our results. In this paper, we shall be concerned with the following conjecture from 2018 posed by Kelly and Postle [ 35 ] that claims a “local strengthening” of Shearer’s bounds that can also be seen as a degree-sequence generalization of Molloy’s bound for fractional coloring. Conjecture 1.1 (Local fractional Shearer/Molloy, cf. Conjecture 2.2, Proposition 1.4 in [ 35 ] ) . For every triangle-free graph there exists a probability distribution on its independent sets such that every vertex v\in V(G) appears with probability at least (1-o(1))\frac{\ln d_{G}(v)}{d_{G}(v)} in a random independent set chosen from the distribution. Here, the o(1) term represents any function that tends to 0 as the degree grows. To see that this conjecture indeed forms a strengthening of Shearer’s bounds, note that the expected size of a random independent set drawn from a distribution as given by the conjecture is \sum_{v\in V(G)}(1-o(1))\frac{\ln d_{G}(v)}{d_{G}(v)}, which recovers Shearer’s second (stronger) lower bound [ 45 ] on the independence number up to lower-order terms. But on top of that, and this explains the word “local” in the name of the conjecture, the distribution in Conjecture 1.1 guarantees that every vertex can be expected to be contained in the random independent set a good fraction of the time (and lower degree vertices are contained proportionally more frequently). This relates back to the previously discussed fractional chromatic number, and, for instance, directly implies that \chi_{f}(G)\leq(1+o(1))\frac{\Delta(G)}{\ln\Delta(G)} for every triangle-free graph, which recovers the fractional version of Molloy’s bound. Adding to that, Conjecture 1.1 connects to several other notions of graph coloring discussed in detail by Kelly and Postle, see in particular [ 35 , Proposition 1.4] which provides many different equivalent formulations of Conjecture 1.1 . One of these involves the notion of fractional coloring with local demands introduced by Dvořák, Sereni and Volec [ 21 ] . Following Kelly and Postle [ 35 ] , given a graph G and a so-called demand function h:V(G)\rightarrow[0,1] that assigns to each vertex its individual “demand”, and h -coloring of a graph G is a mapping c:V(G)\rightarrow 2^{[0,1]} that assigns to every vertex v\in V(G) a measurable subset c(v)\subseteq[0,1] of measure at least h(v) , in such a way that adjacent vertices in G are assigned disjoint subsets. Since the function h does not have to be constant but can depend on local information concerning the vertex v in G , this setting extends the usual paradigm of graph coloring in a local manner. Kelly and Postle [ 35 , Proposition 1.4] proved that Conjecture 1.1 is equivalent to the statement that every triangle-free graph has an h -coloring, where h:V(G)\rightarrow[0,1] is a function depending only on the vertex-degrees such that h(v)=(1-o(1))\frac{\ln d_{G}(v)}{d_{G}(v)} . We refer to the extensive introduction of [ 35 ] for further applications of the conjecture. In one of their main results, Kelly and Postle [ 35 , Theorem 2.3] proved a relaxation of Conjecture 1.1 , replacing the bound (1-o(1))\frac{\ln d_{G}(v)}{d_{G}(v)} with the asymptotically weaker \left(\frac{1}{2e}-o(1)\right)\frac{\ln d_{G}(v)}{d_{G}(v)\ln\ln d_{G}(v)} . As the first main result of this paper, we fully resolve Conjecture 1.1 . Theorem 1.2 . For every triangle-free graph G there exists a probability distribution \mathcal{D} on the independent sets of G such that \mathbb{P}_{I\sim D}[v\in I]\geq(1-o(1))\frac{\ln(d_{G}(v))}{d_{G}(v)} for every v\in V(G) . Here the o(1) represents a function of d_{G}(v) that tends to 0 as the degree grows. A pleasing consequence of Theorem 1.2 is that it can also be used to fully resolve another conjecture about fractional coloring raised in 2018 by Cames van Batenburg, de Joannis de Verclos, Kang and Pirot [ 12 ] : Motivated by the aforementioned problem of estimating the Ramsey-number R(3,k) , in 1967 Erdős asked the fundamental question of determining the maximum chromatic number of triangle-free graphs. An observation of Erdős and Hajnal [ 23 ] combined with Shearer’s bound implies an upper bound (2\sqrt{2}+o(1)))\sqrt{\frac{n}{\ln n}} for this problem. In recent work of Davies and Illingworth [ 17 ] , this upper bound was improved by a \sqrt{2} -factor to the current state of the art (2+o(1))\sqrt{\frac{n}{\ln n}} . The current best lower bound for this quantity is (1/\sqrt{2}-o(1))\sqrt{\frac{n}{\ln n}} , coming from the aforementioned lower bounds on R(3,k) [ 25 , 8 ] . Cames van Batenburg et al. [ 12 ] recently studied the natural analogue of this question for fractional coloring and made the following conjecture. Conjecture 1.3 (cf. Conjecture 4.3 in [ 12 ] ) . As n\rightarrow\infty , every triangle-free graph on n vertices has fractional chromatic number at most (\sqrt{2}+o(1))\sqrt{\frac{n}{\ln n}} . In one of their main results [ 12 , Theorem 1.4] , Cames van Batenburg et al. proved the fractional version of the result of Davies an Illingworth, namely an upper bound (2+o(1))\sqrt{\frac{n}{\ln n}} on the fractional chromatic number. Using a connection between Conjectures 1.1 and 1.3 proved by Kelly and Postle [ 35 , Proposition 5.2] , we are able to confirm Conjecture 1.3 too. Theorem 1.4 . The maximum fractional chromatic number among all n -vertex triangle-free graphs is at most (\sqrt{2}+o(1))\sqrt{\frac{n}{\ln(n)}}. We also prove a similar upper bound on the fractional chromatic number of triangle-free graphs in terms of the number of edges, as follows. Theorem 1.5 . The maximum fractional chromatic number among triangle-free graphs with m edges is at most (18^{1/3}+o(1))\frac{m^{1/3}}{(\ln m)^{2/3}}. Theorem 1.5 comes very close to confirming another conjecture of Cames van Batenburg et al. [ 12 , Conjecture 4.4] , stating that every triangle-free graph with m edges has fractional chromatic number at most (16^{1/3}+o(1))m^{1/3}/(\ln m)^{2/3}. In fact, we suspect that the constant 16^{1/3} in this conjecture may be due to a miscalculation on their end. In particular, the authors of [ 12 ] claim that their conjectured bound on the fractional chromatic number can be verified in the special case of d –regular triangle–free graphs using the upper bound \chi_{f}(G)\leq\min\left((1+o(1))d/\ln d,n/d\right). However, assuming n=(1+o(1))d^{2}/\ln d and thus m=(1/2+o(1))d^{3}/\ln d , this upper bound simplifies to (1+o(1))d/\ln d=(1+o(1))(2m)^{1/3}/(\ln m^{1/3})^{2/3}=(1+o(1))(18m)^{1/3}/(\ln m)^{2/3} . To prove our main result, Theorem 1.2 , in Section 2 we establish a key technical result that goes beyond Theorem 1.2 and generalizes it to a vertex-weighted setting (Theorem 2.1 ). As a consequence of this more general result, we obtain a new spectral upper bound on the fractional chromatic number of triangle-free graphs, stated below. In the following, as is standard, \rho(G) denotes the spectral radius of G , i.e., the spectral radius of its adjacency matrix. Theorem 1.6 . Every triangle-free graph G satisfies \chi_{f}(G)\leq(1+o(1))\frac{\rho(G)}{\ln\rho(G)}, where the o(1) term represents a function of \rho(G) that tends to 0 as \rho(G) grows. Theorem 1.6 lines up nicely with a rich area of research that is concerned with spectral bounds on the (fractional) chromatic number, see e.g. Chapter 6 of the textbook on spectral graph theory [ 13 ] by Chung and [ 7 , 14 , 26 , 29 , 37 , 39 , 41 ] for some small selection of articles on the topic. On the one hand, Theorem 1.6 relates to Wilf’s classic spectral bound [ 46 ] on the chromatic number, which states that every connected graph G satisfies \chi(G)\leq\rho(G)+1 with equality if and only if G is an odd cycle or a complete graph. Theorem 1.6 shows that at least for the fractional chromatic number, a \ln\rho(G) -factor can be saved compared to Wilf’s bound when the graph is assumed to be triangle-free. On the other hand, it is easy to see that \rho(G)\leq\Delta(G) for every graph G and in fact, Hayes [ 28 ] proved that moreover, every d -degenerate graph G satisfies \rho(G)\leq 2\sqrt{d(\Delta(G)-d)} . This implies that \rho(G) is asymptotically smaller than the maximum degree \Delta(G) for many graphs, which means that Theorem 1.6 may be regarded as a substantial strengthening of the upper bound \chi_{f}(G)\leq(1+o(1))\frac{\Delta(G)}{\ln\Delta(G)} implied by Molloy’s result [ 40 ] . Theorem 1.6 also relates to a conjecture of Harris [ 27 ] , stating that every triangle-free d -degenerate graph G satisfies \chi_{f}(G)\leq O(\frac{d}{\ln d}) . A proof of this conjecture would have significant ramifications for other problems in graph theory, such as the resolution of a conjecture by Esperet, Kang and Thomassé [ 24 ] on bipartite induced subgraphs, (see [ 12 , 36 ] for a discussion). Since the spectral radius \rho(G) is sandwiched between the degeneracy and the maximum degree of the graph, Theorem 1.6 can be seen as a first step of moving from Molloy’s (1+o(1))\frac{\Delta(G)}{\ln\Delta(G)} upper bound to the smaller bound conjectured by Harris. It would be interesting to strengthen Theorem 1.6 to a bound for the chromatic number, as follows. Conjecture 1.7 . Every triangle-free graph G satisfies \chi(G)\leq(1+o(1))\frac{\rho(G)}{\ln\rho(G)} . Organization. The rest of the paper is structured as follows: In the Section 2 we establish our main technical result, Theorem 2.1 . In the following Section 3 we then derive our main results from Theorem 2.1 . 2. Key technical result In this section, we present the proof of our key technical result, Theorem 2.1 below, which generalizes Theorem 1.2 to a vertex-weighted setting. In the following, we denote by 1 1 1 We remark that the function f is the same function that was used by Shearer in his first paper [ 44 ] . f:[0,\infty)\rightarrow\mathbb{R}_{+} the unique continuous extension of x\rightarrow\frac{(1-x)+x\ln(x)}{(x-1)^{2}} from [0,\infty)\setminus\{0,1\} to [0,\infty) . It is not hard to check that f exists and has the following properties: • f(0)=1,f(1)=\frac{1}{2} , • f is convex, • f is strictly monotonically decreasing, • f is continuously differentiable on (0,\infty) and satisfies the following differential equation: x(x-1)f^{\prime}(x)+(x+1)f(x)=1 for every x>0 , • |xf^{\prime}(x)|<1 for every x>0 , and • f(x)=(1-o(1))\frac{\ln(x)}{x} as x\rightarrow\infty . In the following, given a weight function w:V(G)\rightarrow\mathbb{R}_{+} on the vertices of a graph G and a subset X\subseteq V(G) , w(X):=\sum_{v\in X}{w(v)} denotes the total weight of X . In this section our goal shall be to establish the following statement, which represents the main technical contribution of the paper at hand and from which all our main results (Theorems 1.2 , 1.4 , 1.5 , 1.6 ) can be deduced without much work (this will be done in the following section). We believe that the more general result offered by Theorem 2.1 may be of independent interest. Theorem 2.1 . For every triangle-free graph G and every strictly positive weight function w:V(G)\rightarrow\mathbb{R}_{+} on the vertices there exists a probability distribution \mathcal{D} on the independent sets of G such that \mathbb{P}_{I\sim\mathcal{D}}[v\in I]\geq f\left(\frac{w(N_{G}(v))}{w(v)}\right) for every vertex v\in V(G) . 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]\geq 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]\geq 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 ): min \displaystyle y \displaystyle\text{s.t.}\penalty\ \penalty\ y+\sum_{I\in\mathcal{I}(G):v\in I}{x_{I}} \displaystyle\geq f\left(\frac{w(N_{G}(v))}{w(v)}\right)\penalty\ \penalty\ (\forall v\in V(G)), \displaystyle\sum_{I\in\mathcal{I}(G)}x_{I} \displaystyle=1 \displaystyle x_{I} \displaystyle\geq 0\penalty\ \penalty\ (\forall I\in\mathcal{I}(G)). 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]\geq 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, towards 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 w.l.o.g 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^{\prime}:V(G)\rightarrow\mathbb{R}^{+} be a modified vertex-weighting of G , defined as w^{\prime}(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 \mathbb{P}_{I\sim\mathcal{D}}[v\in I]\geq f\left(\frac{w^{\prime}(N_{G}(v))}{w^{\prime}(v)}\right)-\delta_{0} 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]\geq f\left(\frac{w^{\prime}(N_{G_{u}}(v))}{w^{\prime}(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}^{\prime} 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 \mathbb{P}_{I\sim\mathcal{D}^{\prime}}[v\in I]0 and that |z|\leq\varepsilon in the last line. Plugging this estimate into the above lower bound for \mathbb{P}_{I\sim\mathcal{D}^{\prime}}[v\in I] and using that by our choice of v , we have \mathbb{P}_{I\sim\mathcal{D}^{\prime}}[v\in I]\mathbb{P}_{I\sim\mathcal{D}^{\prime}}[v\in I] \displaystyle\geq-(1-\varepsilon)\delta_{0}+\varepsilon w(v)+(1-\varepsilon(w(v)+w(N_{G}(v))))\cdot(f(x)+\underbrace{xzf^{\prime}(x)-2\varepsilon^{2}}_{<0}) \displaystyle>-(1-\varepsilon)\delta_{0}+\varepsilon w(v)+f(x)+xzf^{\prime}(x)-2\varepsilon^{2}-\varepsilon(w(v)+w(N_{G}(v)))f(x). Rearranging yields \delta_{0}-\delta>\varepsilon\delta_{0}-2\varepsilon^{2}+\varepsilon w(v)+xzf^{\prime}(x)-\varepsilon(w(v)+w(N_{G}(v)))f(x). Using that x=\frac{w(N_{G}(v))}{w(v)} and z=\varepsilon w(v)(1-x) , we can simplify as follows. \displaystyle\varepsilon w(v)+xzf^{\prime}(x)-\varepsilon(w(v)+w(N_{G}(v)))f(x) \displaystyle=\varepsilon w(v)\left(1+x(1-x)f^{\prime}(x)-(1+x)f(x)\right)=0, 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. ∎ 3. Proofs of Theorems 1.2 , 1.4 , 1.5 , 1.6 In this section we use Theorem 2.1 established in the previous sections to deduce our three main results. Let us start with Theorem 1.2 , which is a simple corollary of Theorem 2.1 by simply using the all- 1 weight assignment. 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 \mathbb{P}_{I\sim\mathcal{D}}[v\in I]\geq f(d_{G}(v)) for every v\in V(G) . Since f(x)=(1-o(1))\frac{\ln(x)}{x} , this establishes Theorem 1.2 . ∎ Next, let us deduce Theorem 1.4 . This, in fact, can be derived from Theorem 1.2 using the following relationship between Conjectures 1.1 and 1.3 proved by Kelly and Postle [ 35 , Proposition 5.2] : Proposition 3.1 . For every \varepsilon,c>0 , the following holds for sufficiently large n . Let G be a triangle-free graph on n vertices with demand function h such that h(v)\geq c\frac{\ln d_{G}(v)}{d_{G}(v)} for every v\in V(G) . If G has an h -coloring, then \chi_{f}(G)\leq(\sqrt{2/c}+\varepsilon)\sqrt{\frac{n}{\ln n}}. With this statement at hand, we can now easily deduce Theorem 1.4 . 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)\leq(\sqrt{2}+\delta)\sqrt{\frac{n}{\ln n}} . Let \varepsilon>0 and 0\max\{D+1,n_{0}\} . We now claim that every triangle-free graph on n\geq 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\geq n_{1} vertices. Let G^{\prime} be the subgraph of G obtained by repeatedly removing vertices of degree less than D from G , until no such vertices are left ( G^{\prime} is the so-called the D -core of G ). Then G^{\prime} is a triangle-free graph that is either empty or has minimum degree at least D . Hence, we either have |V(G^{\prime})|0 for every v\in V(G) . Now interpret the entries of the vector \mathbf{u} as a strictly positive weight assignment to the vertices of G . Then, by Theorem 2.1 , there exists a probability distribution \mathcal{D} on the independent sets of G such that for every v\in V(G) , we have \mathbb{P}_{I\sim D}[v\in I]\geq f\left(\frac{\sum_{x\in N_{G}(v)}\mathbf{u}_{x}}{\mathbf{u}_{v}}\right)=f(\rho(G)). By definition of the fractional chromatic number, this implies that \chi_{f}(G)\leq\frac{1}{f(\rho(G))} , as desired. This concludes the proof. ∎