Geodesic
Random independent sets in triangle-free graphs
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e156

Voir la notice de l'article provenant de la source Cambridge University Press

We establish several new results on the existence of probability distributions on the independent sets in triangle-free graphs where each vertex is present with a given probability. This setting was introduced and studied under the name of “fractional coloring with local demands” by Kelly and Postle and is closely related to the well-studied fractional chromatic number of graphs.Our first main result strengthens Shearer’s classic bound on independence number, proving that for every triangle-free graph G there exists a distribution over independent sets where each vertex v appears with probability $(1-o(1))\frac {\ln d_G(v)}{d_G(v)}$, resolving a conjecture by Kelly and Postle. This in turn implies new upper bounds on the fractional chromatic number of triangle-free graphs with a prescribed number of vertices or edges, which resolves a conjecture by Cames van Batenburg et al. and addresses yet another one by the same authors.Our second main result resolves Harris’ conjecture on triangle-free d-degenerate graphs, showing that such graphs have fractional chromatic number at most $(4+o(1))\frac {d}{\ln d}$. As previously observed by various authors, this in turn has several interesting consequences. A notable example is that every triangle-free graph with minimum degree d contains a bipartite induced subgraph of minimum degree $\Omega (\log d)$. This settles a conjecture by Esperet, Kang, and Thomassé.The main technique employed to obtain our results is the analysis of carefully designed random processes on vertex-weighted triangle-free graphs that preserve weights in expectation. The analysis of these processes yields weighted generalizations of the aforementioned results that may be of independent interest. 
Martinsson, Anders; Steiner, Raphael. Random independent sets in triangle-free graphs. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e156. doi: 10.1017/fms.2025.10112
@article{10_1017_fms_2025_10112,
     author = {Martinsson, Anders and Steiner, Raphael},
     title = {Random independent sets in triangle-free graphs},
     journal = {Forum of Mathematics, Sigma},
     pages = {e156},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2025.10112},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10112/}
}
TY  - JOUR
AU  - Martinsson, Anders
AU  - Steiner, Raphael
TI  - Random independent sets in triangle-free graphs
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e156
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10112/
DO  - 10.1017/fms.2025.10112
ID  - 10_1017_fms_2025_10112
ER  - 
%0 Journal Article
%A Martinsson, Anders
%A Steiner, Raphael
%T Random independent sets in triangle-free graphs
%J Forum of Mathematics, Sigma
%D 2025
%P e156
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10112/
%R 10.1017/fms.2025.10112
%F 10_1017_fms_2025_10112

[1] Ajtai, M., Erdős, P., Komlós, J. and Szemerédi, E., ‘Turán’s theorem for sparse graphs’, Combinatorica 1(4) (1981), 313–317.10.1007/BF02579451 Google Scholar | DOI

[2] Ajtai, M., Komlós, J. and Szemerédi, E., ‘A note on Ramsey numbers’, J. Combin. Theory Ser. A 29(3) (1980), 354–360.10.1016/0097-3165(80)90030-8 Google Scholar | DOI

[3] Alon, N., ‘Independence numbers of locally sparse graphs and a Ramsey type problem’, Random Struct. Algorithms 9(3) (1996), 271–278.10.1002/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO;2-U Google Scholar | DOI

[4] Alon, N., Krivelevich, M. and Sudakov, B., ‘Coloring graphs with sparse neighborhoods’, J. Combin. Theory Ser. B 77(1) (1999), 73–82.10.1006/jctb.1999.1910 Google Scholar | DOI

[5] Anderson, J., Bernshteyn, A. and Dhawan, A., ‘Colouring graphs with forbidden bipartite subgraphs’, Combin. Probab. Comput. 32(1) (2023), 45–67.10.1017/S0963548322000104 Google Scholar | DOI

[6] Anderson, J., Dhawan, A. and Kuchukova, A., ‘Coloring locally sparse graphs’, 2024, . 19271. Google Scholar | arXiv

[7] Bárány, J., ‘A short proof of Kneser’s conjecture’, J. Combin. Theory Ser. A 25(3) (1978), 325–326.10.1016/0097-3165(78)90023-7 Google Scholar | DOI

[8] Bernshteyn, A., Brazelton, T., Cao, R. and Kang, A., ‘Counting colorings of triangle-free graphs’, J. Combin. Theory Ser. B 161 (2023), 86–108.10.1016/j.jctb.2023.02.004 Google Scholar | DOI

[9] Bilu, Y., ‘Tales of Hoffman: Three extensions of Hoffman’s bound on the graph chromatic number’, J. Combin. Theory Ser. B 96(4) (2006), 608–613.10.1016/j.jctb.2005.10.002 Google Scholar | DOI

[10] Bohman, T. and Keevash, P., ‘Dynamic concentration of the triangle-free process’, Random Struct. Algorithms 58(2) (2021), 221–293.10.1002/rsa.20973 Google Scholar | DOI

[11] Bollobás, B., ‘The independence ratio of regular graphs’, Proc. Amer. Math. Soc. 83 (1981), 433–436.10.2307/2043545 Google Scholar | DOI

[12] Bonamy, M., Kelly, T., Nelson, P. and Postle, L., ‘Bounding by a fraction of for graphs without large cliques’, J. Combin. Theory Ser. B 157 (2022), 263–282.10.1016/j.jctb.2022.06.002 Google Scholar | DOI

[13] Bradshaw, P., Mohar, B. and Stacho, L., ‘Bipartite graphs are -choosable’, 2024, . Google Scholar | arXiv

[14] Cambie, S., Cames Van Batenburg, W., Davies, E. and Kang, R. J., ‘List packing number of bounded degree graphs’, Combin. Probab. Comput. 33(6) (2024), 807–828.10.1017/S0963548324000191 Google Scholar | DOI

[15] Cambie, S., Cames Van Batenburg, W., Davies, E. and Kang, R. J., ‘Packing list-colorings’, Random Struct. Algorithms 64(1) (2024), 62–93.10.1002/rsa.21181 Google Scholar | DOI

[16] Cames Van Batenburg, W., De Joannis De Verclos, R., Kang, R. J. and Pirot, F., ‘Bipartite induced density in triangle-free graphs’, Electron. J. Combin. 27(2) (2020), P2–34.10.37236/8650 Google Scholar | DOI

[17] Chung, F. R. K., Spectral Graph Theory, vol. 92 (Amer. Math. Soc., 1997). Google Scholar

[18] Cvetkovic, D., ‘Chromatic number and the spectrum of a graph’, Publ. Inst. Math. (Beograd) 14(28) (1972), 25–38. Google Scholar

[19] Davies, E., De Joannis De Verclos, R., Kang, R. J. and Pirot, F., ‘Coloring triangle-free graphs with local list sizes’, Random Struct. Algorithms 57(3) (2020), 730–744.10.1002/rsa.20945 Google Scholar PubMed | DOI

[20] Davies, E., De Joannis De Verclos, R., Kang, R. J. and Pirot, F., ‘Occupancy fraction, fractional colouring, and triangle fraction’, J. Graph Theory 97(4) (2021), 557–568.10.1002/jgt.22671 Google Scholar PubMed | DOI

[21] Davies, E. and Illingworth, F., ‘The -Ramsey problem for triangle-free graphs’, SIAM J. Discrete Math. 36(2) (2022), 1124–1134.10.1137/21M1437573 Google Scholar | DOI

[22] Davies, E., Jenssen, M., Perkins, W. and Roberts, B., ‘On the average size of independent sets in triangle-free graphs’, Proc. Amer. Math. Soc. 146(1) (2018), 111–124.10.1090/proc/13728 Google Scholar | DOI

[23] Davies, E. and Kang, R. J., ‘The hard-core model in graph theory’, 2025, . Google Scholar | arXiv

[24] Davies, E., Kang, R. J., Pirot, F. and Sereni, J., ‘Graph structure via local occupancy’, 2020, . Google Scholar | arXiv

[25] Descartes, B., ‘Solution to advanced problem no. 4526’, Amer. Math. Monthly 61(352) (1954), 216. Google Scholar

[26] Dhawan, A., ‘Bounds for the independence and chromatic numbers of locally sparse graphs’, 2024, .10.1007/s00026-025-00778-7 Google Scholar | arXiv | DOI

[27] Dvořák, Z., Sereni, J. and Volec, J., ‘Subcubic triangle-free graphs have fractional chromatic number at most ’, J. London Math. Soc. 89(3) (2014), 641–662.10.1112/jlms/jdt085 Google Scholar | DOI

[28] Erdős, P., ‘Some unsolved problems’, Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221–254. Google Scholar

[29] Erdős, P. and Hajnal, A., ‘Chromatic number of finite and infinite graphs and hypergraphs’, Discrete Math. 53 (1985), 281–285.10.1016/0012-365X(85)90148-7 Google Scholar | DOI

[30] Esperet, L., Kang, R. J. and Thomassé, S., ‘Separation choosability and dense bipartite induced subgraphs’, Combin. Probab. Comput. 28(5) (2019), 720–732.10.1017/S0963548319000026 Google Scholar | DOI

[31] Fiz Pontiveros, G., Griffiths, S. and Morris, R., ‘The triangle-free process and the Ramsey number ’, Mem. Amer. Math. Soc. 263 (2020), 125 pp. Google Scholar

[32] Guo, K. and Spiro, S., ‘New eigenvalue bound for the fractional chromatic number’, J. Graph Theory 106(1) (2024), 167–181.10.1002/jgt.23071 Google Scholar | DOI

[33] Harris, D. G., ‘Some results on chromatic number as a function of triangle count’, SIAM J. Discrete Math. 33(1) (2019), 546–563.10.1137/17M115918X Google Scholar | DOI

[34] Hoffman, A. J., ‘On eigenvalues and colorings of graphs’, in Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. Wisconsin, Madison, 1969), 1970. Google Scholar

[35] Hurley, E., De Joannis De Verclos, R. and Kang, R. J., ‘An improved procedure for colouring graphs of bounded local density’, in Proc. 2021 ACM-SIAM Symp. Discrete Algorithms (SODA) (SIAM, 2021), 135–148.10.1137/1.9781611976465.10 Google Scholar | DOI

[36] Hurley, E. and Pirot, F., ‘Uniformly random colourings of sparse graphs’, in Proc. 55th Annu. ACM Symp. Theory Comput. (STOC 2023) (ACM, New York, 2023), 1357–1370.10.1145/3564246.3585242 Google Scholar | DOI

[37] Janzer, B., Steiner, R. and Sudakov, B., ‘Chromatic number and regular subgraphs’, 2024, .10.1093/imrn/rnae171 Google Scholar | arXiv | DOI

[38] Johansson, A., ‘Asymptotic choice number for triangle free graphs’, Technical report 91-5, DIMACS, 1996. Google Scholar

[39] Kang, D., Kühn, D., Methuku, A. and Osthus, D., ‘Graph and hypergraph colouring via nibble methods: A survey’, in Proc. 8th Eur. Congr. Math. (2023), 771–823.10.4171/8ecm/11 Google Scholar | DOI

[40] Kelly, T. and Postle, L., ‘Fractional coloring with local demands and applications to degree-sequence bounds on the independence number’, J. Combin. Theory Ser. B 169 (2024), 298–337.10.1016/j.jctb.2024.07.002 Google Scholar | DOI

[41] Kwan, M., Letzter, S., Sudakov, B. and Tran, T., ‘Dense induced bipartite subgraphs in triangle-free graphs’, Combinatorica 40(2) (2020), 283–305.10.1007/s00493-019-4086-0 Google Scholar | DOI

[42] Kwan, M. and Wigderson, Y., ‘The inertia bound is far from tight’, Bull. London Math. Soc. 56(10) (2024), 3196–3208.10.1112/blms.13127 Google Scholar | DOI

[43] Li, Y., ‘Bipartite induced density in triangle-free graphs’, Master’s thesis, University of Amsterdam, 2024. Google Scholar

[44] Lovász, L., ‘Kneser’s conjecture, chromatic number, and homotopy’, J. Combin. Theory Ser. A 25(3) (1978), 319–324.10.1016/0097-3165(78)90022-5 Google Scholar | DOI

[45] Mohar, B., ‘Eigenvalues and colorings of digraphs’, Linear Algebra Appl. 432(9) (2010), 2273–2277.10.1016/j.laa.2009.05.027 Google Scholar | DOI

[46] Molloy, M., ‘The list chromatic number of graphs with small clique number’, J. Combin. Theory Ser. B 134 (2019), 264–284.10.1016/j.jctb.2018.06.007 Google Scholar | DOI

[47] Mycielski, J., ‘Sur le coloriage des graphs’, Colloq. Math. 3 (1955), 161–162.10.4064/cm-3-2-161-162 Google Scholar | DOI

[48] Nikiforov, V., ‘Chromatic number and spectral radius’, Linear Algebra Appl. 426(2–3) (2007), 810–814.10.1016/j.laa.2007.06.005 Google Scholar | DOI

[49] Pirot, F. and Sereni, J., ‘Fractional chromatic number, maximum degree, and girth’, SIAM J. Discrete Math. 35(4) (2021), 2815–2843.10.1137/20M1382283 Google Scholar | DOI

[50] Scheinerman, E. R. and Ullman, D. H.. Fractional Graph Theory: A Rational Approach to the Theory of Graphs (Dover Publications Inc., Minneola, New York, USA, 2011). Google Scholar

[51] Shearer, J. B.. ‘A note on the independence number of triangle-free graphs’, Discrete Math. 46(1) (1983), 83–87.10.1016/0012-365X(83)90273-X Google Scholar | DOI

[52] Shearer, J. B.. ‘A note on the independence number of triangle-free graphs, II’, J. Combin. Theory Ser. B 53(2) (1991), 300–307.10.1016/0095-8956(91)90080-4 Google Scholar | DOI

[53] Shearer, J. B.. ‘On the independence number of sparse graphs’. Random Struct. Algorithms 7(3) (1995), 269–271.10.1002/rsa.3240070305 Google Scholar | DOI

[54] Wilf, H. S.. ‘The eigenvalues of a graph and its chromatic number’, J. London Math. Soc., s1-42(1) (1967), 330–332.10.1112/jlms/s1-42.1.330 Google Scholar | DOI

[55] Zykov, A. A.. ‘On some properties of linear complexes’, Mat. Sbornik N.S. 24(66) (1949), 163–188. Google Scholar

Cité par Sources :