Sergey Norin: Publications and Preprints

Graph Minors:
  1. Proper minor-closed families are small (with P. Seymour, R. Thomas and P. Wollan), J. Comb. Theory B 96 (2006), 754-757.
  2. New tools and results in graph minor structure theory, Surveys in Combinatorics 424 (2015), 221-260.
  3. Non-planar extensions of subdivisions of planar graphs (with R. Thomas), J. Comb. Theory B 121 (2016), 326-366.
  4. The extremal function for disconnected minors (with E. Csóka, I. Lo, H. Wu and L. Yepremyan), J. Comb. Theory B 126 (2017), 162-174.
  5. K6 minors in large 6-connected graphs (with K. Kawarabayashi, R. Thomas and P. Wollan), J. Comb. Theory B 129 (2018), 158-203.
  6. K6 minors in 6-connected graphs of bounded tree-width (with K. Kawarabayashi, R. Thomas and P. Wollan), J. Comb. Theory B 136 (2019), 1-32.
  7. Clustered Colouring in Minor-Closed Classes (with A. Scott, P. Seymour and D. R. Wood), Combinatorica 39 (2019), 1387–1412.
  8. A lower bound on the average degree forcing a minor (with B. Reed, A. Thomason and D. R. Wood), Electronic J. Comb. 27(2) (2020), #P2.4, 9pp.
  9. Asymptotic density of graphs excluding disconnected minors (with R. Kapadia and Y. Qian), J. Comb. Theory B 146 (2021), 151-175.
  10. Obstructions for partitioning into forests and outerplanar graphs (with R. Kim and S. Oum), Disc. Appl. Math. 146 (2022), 15-28.
  11. A new upper bound on the chromatic number of graphs with no odd Kt minor (with Z-X. Song), Combinatorica 42 (2022), 137–149.
  12. Islands in minor-closed classes. I. Bounded treewidth and separators (with Z. Dvorak)
  13. Breaking the degeneracy barrier for coloring graphs with no Kt minor (with L. Postle and Z-X. Song), submitted.
  14. Connectivity and choosability of graphs with no Kt minor (with L. Postle), submitted.
  15. Densities of minor-closed graph classes are rational (with R. Kapadia)
  16. Clustered colouring of graph classes with bounded treedepth or pathwidth (with A. Scott and D. R. Wood), submitted.
  17. Extremal functions for sparse minors (with K. Hendrey and D. R. Wood)
  18. Testability and local certification of monotone properties in minor-closed classes (with L. Esperet)
  19. Dense minors of graphs with independence number two (with P. Seymour)
Extremal Combinatorics:
  1. Undecidability of linear inequalities in graph homomorphism densities (with H. Hatami), J. Amer. Math. Soc., 24 (2011), 547-565.
  2. Turan graphs and the number of colorings, SIAM J. Discrete Math., 25 (2011), 260-266.
  3. Non-three-colorable common graphs exist (with H. Hatami, J. Hladky, D. Kral' and A. Razborov), Combin. Probab. Comput., 21 (2012), 734--742.
  4. On the number of pentagons in triangle-free graphs (with H. Hatami, J. Hladky, D. Kral' and A. Razborov), J. Combin. Theory Ser. A, 120 (2013), 722-732.
  5. The inducibility of blow-up graphs (with H. Hatami and J. Hirst), J. Combin. Theory Ser. B, 109 (2014), 196-212.
  6. Sparse halves in dense triangle-free graphs (with L. Yepremyan), J. Combin. Theory Ser. B, 115 (2015), 1-25.
  7. Erdős-Szekeres without induction (with Y. Yuditsky), Disc. and Comp. Geometry 55 (2016), 963-971.
  8. Turán number of generalized triangles (with L. Yepremyan), J. Combin. Theory Ser. A, 146 (2017), 312-343.
  9. Counting flags in triangle-free digraphs (with J. Hladky and D. Kral'), Combinatorica, 37 (2017), 49-76.
  10. Turán numbers of extensions (with L. Yepremyan), J. Comb. Theory A 155 (2018), 476-492.
  11. A bound on the inducibility of cycles (with D. Kral' and J. Volec), J. Comb. Theory A 161 (2019), 359-363.
  12. On the boundary of the region defined by homomorphism densities (with H. Hatami), J. Of Comb. 10 (2019), 203-219.
  13. A Turán theorem for extensions via an Erdős-Ko-Rado theorem for Lagrangians (with A. Bene Watts and L. Yepremyan), Combinatorica, 19 (2019), 1149–1171.
  14. Bounding the number of cycles in a graph in terms of its degree sequence (with Z. Dvořák, N. Morrison, J. A. Noel and L. Postle), European J. Combin. 91 (2021), 103206, 16 pp.
  15. The smallest matroids with no large independent flat (with P. Nelson), Electronic J. of Combin. 28(1) (2021), #P1.31, 10pp.
  16. Non-bipartite k-common graphs (with D. Kral', J. A. Noel, J.Volec and F. Wei), Combinatorica 42 (2022), 87–114.
  17. Triangle-independent sets vs. cuts (with Y. R. Sun), submitted.
  18. Asymptotics of Ramsey numbers of double stars (with Y. R. Sun and Y. Zhao), submitted.
  19. The inducibility of oriented stars (with P. Hu, J. Ma and H. Wu), submitted.
  20. The Spectrum of Triangle-free Graphs (with J. Balogh, F. C. Clemen, B. Lidický and J. Volec), submitted.
  21. Every graph is eventually Turán-good (with N. Morrison, JD Nir, P. Rzążewski and A. Wesolek)
Sparse Graph Classes:
  1. Small graph classes and bounded expansion (with Z. Dvorak), J. Comb. Theory B 100 (2010), 171-175.
  2. Strongly sublinear separators and polynomial expansion (with Z. Dvorak), SIAM J. Discrete Math. 30(2) (2016), 1095–1101.
  3. Treewidth of grid subsets (with E. Berger and Z. Dvorak), Combinatorica 38 (2018), 1337-1352.
  4. Orthogonal Tree Decompositions of Graphs (with V. Dujmovic, G. Joret, P. Morin and D. R. Wood), SIAM J. Discrete Math., 32 (2018), 839-863.
  5. Treewidth of graphs with balanced separations (with Z.Dvorak), J. Comb. Theory B 137 (2019), 137-144.
  6. Sublinear separators in intersection graphs of convex shapes (with Z. Dvorak and R. McCarty), SIAM J. Discrete Math., 35 (2021), 1149–1164.
  7. Three-dimensional graph products with unbounded stack-number (with D. Eppstein, R. Hickingbotham, L. Merker, M. T. Seweryn and D. R. Wood), submitted.
  8. Asymptotic dimension of intersection graphs (with Z.Dvorak), submitted.
Hereditary Graph Classes:
  1. The entropy of random-free graphons and properties (with H. Hatami), Combin. Probab. Comput., 22, (2013) 517-526.
  2. Excluding a substar and an anti-substar (with M. Chudnovsky, B. Reed and P. Seymour), SIAM J. Discrete Math., 29(1) (2015), 297–308.
  3. Typical structure of hereditary graph families. I. Apex-free families (with Y. Yuditsky), submitted.
  4. Typical structure of hereditary graph families. II. Exotic examples (with Y. Yuditsky), submitted.
  5. Typical structure of hereditary properties of binary matroids (with S. Grosser, H. Hatami and P. Nelson), submitted.

Matching Theory and Pfaffian Orientations:

  1. A new proof of a characterisation of Pfaffian bipartite graphs (with C. H. C. Little and Kee L. Teo),  J. Comb. Theory B 91 (2004), 123-126.
  2. Matching structure and Pfaffian orientations of graphs, PhD. Thesis, Georgia Institute of Technology (2005).
  3. Unions of perfect matchings in cubic graphs (with T. Kaiser and D. Kral'), in "Topics in Discrete Mathematics" (M. Klazar, J. Kratochvil, J. Matousek, R. Thomas, P. Valtr, eds.), Springer (2006), 225-230.
  4. Minimal bricks (with R. Thomas), J. Comb. Theory B 96 (2006), 505-513.
  5. Generating bricks (with R. Thomas), J. Comb. Theory B 97 (2007), 769-817.
  6. Pfaffian graphs, T-joins and crossing numbers, Combinatorica 28 (2008), 89-98.
      (Conference version: Drawing Pfaffian graphs, Graph Drawing, 12th International Symposium, Lecture Notes in Computer Science, 3383 (2005), 371-376.)
  7. Pfaffian labelings and signs of edge-colorings (with R. Thomas), Combinatorica 28 (2008), 99-111.
  8. Minimally non-Pfaffian graphs (with R. Thomas), J. Comb. Theory B 98 (2008), 1038-1055.
  9. Drawing 4-Pfaffian graphs on the torus, Combinatorica 29 (2009), 109-119.
  10. Exponentially many perfect matchings in cubic graphs (with L. Esperet, F. Kardos, A. King and D. Kral'), Adv. Math. 227 (2011), 1646-1664.
  11. Holographic algorithms without matchgates (with J. M. Lansberg and J. Morton), Linear Algebra Appl., 438 (2013), 782--795.
Graph Coloring:
  1. The circular chromatic index of flower snarks (with M. Ghebleh, D. Kral' and R. Thomas), Electronic Journal of Combinatorics, 13(1) (2006), #N20, 7pp.
  2. On two questions about circular choosability, J. Graph Theory 58 (2008), 261-269.
  3. Circular degree choosability (with X. Zhu), Electronic Journal of Combinatorics, 15(1) (2008), #R100, 8pp.
  4. Graphs with full rank 3-color matrix and few 3-colorings (with J.-S. Sereni), J. Comb. Theory B 98 (2008), 1115-1116.
  5. Circular choosability via combinatorial Nullstellensatz (with T.-L. Wong and X. Zhu), J. Graph Theory 59 (2008), 190-204.
  6. Circular consecutive choosability of k-choosable graphs (with D. Liu, Z. Pan and X. Zhu), J. Graph Theory 67 (2011), 178-197.
  7. List coloring with requests (with Z. Dvorak and L. Postle), J. Graph Theory 92 (2019), 191-206.
  8. Counterexamples to a conjecture of Harris on Hall ratio (with A. Blumenthal, B. Lidicky, R. R. Martin, F. Pfender and J. Volec), submitted.
  9. Weak diameter coloring of graphs on surfaces (with Z. Dvorak).
Analogies Between Graphs and Riemann Surfaces:
  1. Riemann-Roch and Abel-Jacobi theory on a finite graph (with M. Baker), Adv. Math. 215(2) (2007), 766-788.
  2. Harmonic morphisms and hyperelliptic graphs (with M. Baker), Int. Math. Res. Notices (2009), 42 pp.
  3. Jacobians of near-complete and threshold graphs (with P. Whalen), European J. Combin. 32 (2011), 1368--1376.
  4. Rank of divisors on tropical curves (with J. Hladky and D. Kral'), J. Combin. Theory Ser. A, 120 (2013), 1521-1538.
Game theory:
  1. Set intersections, perfect graphs, and voting in agreeable societies (with D. E. Berg, F. E. Su, R. Thomas and P. Wollan), Am. Math. Mon. 117 (2010), 27-39.
  2. A counterexample to a conjecture of Schwartz (with F. Brandt, M. Chudnovsky, I. Kim, G. Liu, A. Scott, P. Seymour and S. Thomasse), Soc. Choice Welf., 40(3) (2013), 739-743.
  3. Polylogarithmic Supports are required for Approximate Well-Supported Nash Equilibria below 2/3 (with Y. Anbalagan, R. Savani and A. Vetta), Web and Internet Economics, LNCS, 8289 (2013), 15--23.
  4. A Near-Optimal Mechanism for Impartial Selection (with N. Bousquet and A. Vetta), Web and Internet Economics, LNCS, 8877 (2014), 133-146.
  5. Large Supports are required for Well-Supported Nash Equilibria (with Y. Anbalagan, H. Huang, S. Lovett, A. Vetta and H. Wu), LIPIcs. APPROX/RANDOM 15 40 (2015), 78-84.
  6. Descending the Stable Matching Lattice: How many Strategic Agents are required to turn Pessimality to Optimality? (with N. Ndiaye and A. Vetta), submitted.
Other Topics:
  1. A polynomial lower bound for the size of a k-min-wise independent set of permutationsJ. Math. Sci. (N. Y.) 118 (2003), no. 2, 4994-5000.
  2. Markov bases of binary graph models of K4-minor free graphs (with D. Kral' and O. Pangrac), J. Comb. Theory A 117 (2010), 759-765.
  3. Flag algebras and the stable coefficients of the Jones polynomial (with S. Garoufalidis and T. Vuong), European J. Combin. 51 (2016), 165-189.
  4. Distribution of coefficients of rank polynomials for random sparse graphs, (with. D. Jakobson, C. MacRury and L. Turner), Electronic J. Combin. 25(4) (2018), #R5.40, 29pp.
  5. A distribution on triples with maximum entropy marginal, Forum of Math. Sigma 7 (2019), #E46, 12pp.
  6. Virtually fibering right-angled Coxeter groups (with K. Jankiewicz and D. Wise), J. Inst. Math. Jussieu 20 (2021), 957-987.
  7. Torsion groups do not act on 2-dimensional CAT(0) complexes (with D. Osajda and P. Przytycki), Duke Math. J. 171(6) (2022), 1379-1415.
  8. The Burning Number Conjecture holds asymptotically (with J. Turcotte)
  9. Connectivity of addable classes of forests, manuscript.