Oleg Verbitsky

Expository and Survey Writings

• • Logical complexity of graphs: a survey, with Oleg Pikhurko. In: Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics, Vol. 558, pages 129-179. American Mathematical Society (2011).

  • Around and beyond the isomorphism problem for interval graphs, with Johannes Köbler and Sebastian Kuhnert. Bulletin of the EATCS 107:43-71 (2012).

  •  A Ramsey treatment of symmetry, with Taras Banakh and Yaroslav Vorobets. The Electronic Journal of Combinatorics, vol. 7 (2000).

  •  Fermat's spiral and the line between Yin and Yang, with Taras Banakh and Yaroslav Vorobets. American Mathematical Monthly 117(9):786-800 (2010). An illustrative applet to this paper is provided by Roice Nelson in his blog. French digests of this paper are written by Serge Cantat and El Jj.

Graph Isomorphism. Combinatorial Refinement. Logical Complexity of Graphs

• • On the expressibility of the Reconstructional Color Refinement, with V. Arvind and J. Köbler. E-print (2024).

  • Gathering information about a graph by counting walks from a single vertex, with F. Fuhlbrück, J. Köbler, and M. Zhukovskii. E-print (2024).

  • Canonical labeling of sparse random graphs, with M. Zhukovskii. STACS'25. Vol. 327 of LIPIcs, pp. 75:1-75:20 (2025).

  • On a hierarchy of spectral invariants for graphs, with V. Arvind, F. Fuhlbrück, and J. Köbler. STACS'24. Vol. 289 of LIPIcs, pp. 45:1-45:18 (2024).

  • Canonization of a random circulant graph by counting walks, with M. Zhukovskii. WALCOM'24. Vol. 14549 of LNCS, pp. 319-334 (2024).

  • Canonization of a random graph by two matrix-vector multiplications, with M. Zhukovskii. ESA'23. Vol. 274 of LIPIcs, pp. 100:1-100:13 (2023).

  • On the Weisfeiler-Leman dimension of Fractional Packing, with V. Arvind, F. Fuhlbrück, and J. Köbler. Information and Computation 288, Article 104803 (2022).

  • Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm, with F. Fuhlbrück and J. Köbler. SIAM Journal on Discrete Mathematics 35(3):1792-1853 (2021).

  • The Weisfeiler-Leman algorithm and recognition of graph properties, with F. Fuhlbrück, J. Köbler, and I. Ponomarenko. Theoretical Computer Science 895:96-114 (2021).

  • Local WL Invariance and hidden shades of regularity, with F. Fuhlbrück and J. Köbler. Discrete Applied Mathematics 305:191-198 (2021).

  • On Weisfeiler-Leman invariance: Subgraph counts and related graph properties, with V. Arvind, F. Fuhlbrück, and J. Köbler. Journal of Computer and System Sciences 113:42-59 (2020).

  • On the first-order complexity of Induced Subgraph Isomorphism, with M. Zhukovskii. Logical Methods in Computer Science 15(1):25.1--25.24 (2019)

  • Tight bounds on the asymptotic descriptive complexity of Subgraph Isomorphism, with M. Zhukovskii. Transactions on Computational Logic 20(2):9.1-9.18 (2019).

  • The descriptive complexity of Subgraph Isomorphism without numerics, with M.Zhukovskii. Theory of Computing Systems 63(4):902-921 (2019).

  • On the speed of constraint propagation and the time complexity of arc consistency testing, with C. Berkholz.  Journal of Computer and System Sciences (91)104-114 (2018).

  • Graph Isomorphism, color refinement, and compactness, with V. Arvind, J. Köbler, and G. Rattan. Computational Complexity 26(3):627-685 (2017).

  • Circular-arc hypergraphs: Rigidity via connectedness, with J. Köbler and S. Kuhnert. Discrete Applied Mathematics 217(2):220-228 (2017).

• • On the isomorphism problem for Helly circular-arc graphs, with J. Köbler and S. Kuhnert. Information and Computation 247:266-277 (2016).

  • Solving the canonical representation and Star System problems for proper circular-arc graphs in Logspace, with J. Köbler and S. Kuhnert. Journal of Discrete Algorithms 38-41:38-49 (2016).

  • Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth, with A. Krebs.  LICS'15, pp. 689-700 (2015).

  • Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy, with C. Berkholz and A. Krebs. ACM Transactions on Computational Logic 16(3):21.1-21.26 (2015).

  • On the dynamic width of the 3-colorability problem, with A. Atserias and A. Dawar. E-print (2014).

  • Around and beyond the isomorphism problem for interval graphs, with J. Köbler and S. Kuhnert. Bulletin of the EATCS 107:43-71 (2012).

  • Interval graphs: canonical representation in Logspace, with J. Köbler, S. Kuhnert, and B. Laubner. SIAM Journal on Computing 40(5):1292--1315 (2011).

  • Logical complexity of graphs: a survey, with O. Pikhurko. In: Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics, Vol. 558, pages 129-179. Americal Mathematical Society (2011).

  • From invariants to canonization in parallel, with J. Köbler. CSR'08. Vol. 5010 of LNCS, pp. 216-227 (2008).

  • Planar graphs: logical complexity and parallel isomorphism tests. STACS'07. Vol. 4393 of LNCS, pp. 682-693 (2007).

  • First order definability of trees and sparse random graphs, with T. Bohman, A. Frieze, T. Luczak, O. Pikhurko, C. Smyth, and J. Spencer. Combinatorics, Probability and Computing 16:375-400 (2007).

  • Decomposable graphs and definitions with no quantifier alternation, with O. Pikhurko and J. Spencer. European Journal of Combinatorics 28:2264-2283 (2007).

  • Testing graph isomorphism in parallel by playing a game, with M. Grohe. ICALP'06. Vol. 4051 of LNCS, pp. 3-14 (2006).

  • The first order definability of graphs: upper bounds for quantifier depth, with O. Pikhurko and H. Veith. Discrete Applied Mathematics 154:2511-2529 (2006).

  • Succinct definitions in the first order theory of graphs, with O. Pikhurko and J. Spencer. Annals of Pure and Applied Logic 139:74-109 (2006).

  • How complex are random graphs in first order logic?, with J.-H. Kim, O. Pikhurko, and J. Spencer. Random Structures and Algorithms 26:119-145 (2005).

  • Descriptive complexity of finite structures: saving the quantifier rank, with O. Pikhurko. Journal of Symbolic Logic 70:419-450 (2005).

  • The first order definability of graphs with separators via the Ehrenfeucht game. Theoretical Computer Science 343:158-176 (2005).

Graph Drawing

• • The complexity of drawing graphs on few lines and few planes, with S. Chaplick, K. Fleszar, F. Lipp, A. Ravsky, and A. Wolff. Journal of Graph Algorithms and Applications 27(6):459-488 (2023).

  • Drawing graphs on few lines and few planes, with S. Chaplick, K. Fleszar, F. Lipp, A. Ravsky, and A. Wolff. Journal of Computational Geometry 11(1):433–475 (2020).

  • Untangling planar graphs from a specified vertex position - Hard cases, with M. Kang, O. Pikhurko, A. Ravsky, and M. Schacht. Discrete Applied Mathematics 159:789-799 (2011).

  • On collinear sets in straight line drawings, with A. Ravsky. Graph-Theoretic Concepts in Computer Science. Vol. 6986 of LNCS, pp. 295-306 (2011).

  • On the obfuscation complexity of planar graphs. Theoretical Computer Science 396:294-300 (2008).

Computational Complexity

• • On the computational complexity of the forcing chromatic number, with F. Harary and W. Slany. SIAM Journal on Computing 37:1-19 (2007).

  • Zero-knowledge proofs of the conjugacy of permutation groups. Bulletin of the Lviv University, Series in Mechanics and Mathematics 61:195-205 (2003).

  • On the double coset membership problem for permutation groups. In: Algebraic structures and their applications, Institute of Mathematics, Ukrainian Academy of Sciences, Kyiv, pp. 351-363 (2002).

  • Error reduction by parallel repetition - a negative result, with U. Feige. Combinatorica 22:461-478 (2002).

  • Remarks on a query-based variant of the parallel repetition theorem. The International Journal of Foundations of Computer Science 12:517-531 (2001).

  • Arthur-Merlin games in boolean decision trees, with R. Raz, G. Tardos, and N. Vereshchagin. Journal of Computer and System Sciences 59:346-372 (1999).

  • Towards the parallel repetition conjecture. Theoretical Computer Science 157:277-282 (1996).

  • On the hardness of approximating some optimization problems that are supposedly easier than MAX CLIQUE. Combinatorics, Probability and Computing 4:167-180 (1995).

  • On the possibility of performing any multi-prover interactive proof in a bounded number of rounds. Izvestiya. Mathematics. 42:561-586 (1994).

  • Optimal algorithms for coNP-sets and the problem EXP=?NEXP.  Math. Notes 50:796-801 (1992).

Ramsey Problems and Other Combinatorial Themes

• • Fermat's spiral and the line between Yin and Yang, with T. Banakh and Y. Vorobets. American Mathematical Monthly 117(9):786-800 (2010).

  • A Ramsey treatment of symmetry, with T. Banakh and Y. Vorobets. The Electronic Journal of Combinatorics, vol. 7 (2000).

  • Ramsey-type problems for spaces with symmetry, with T. Banakh and Y. Vorobets. Izvestiya. Mathematics. 64:1091-1127 (2000).

  • Structural properties of extremal asymmetric colorings. Algebra and Discrete Mathematics 4:92-117 (2003).

  • On asymmetric colorings of integer grids, with T. Banakh and I. Kmit. Ars Combinatoria 62:257-271 (2002).

  • Symmetric subsets of lattice paths. INTEGERS: an electronic journal of combinatorial number theory 0(A05):1-16 (2000).

  • On isomorphism-invariant antistochastic properties of random graphs, with S. Kiselev,  A. Kupavskii, and M. Zhukovskii.  SIAM J. Discrete Mathematics 38(4):3043-3078 (2024).

  • New bounds for the optimal density of covering single-insertion codes via the Turán density, with O. Pikhurko and M. Zhukovskii. E-print (2024).

Combinatorial Games

• These two papers address a mirror strategy for variations of the game of Sim:

  • On the lengths of symmetry breaking-preserving games on graphs, with F. Harary and W. Slany. Theoretical Computer Science 313:427-446 (2004).

  • A symmetric strategy in graph avoidance games, with F. Harary and W. Slany. In: More Games of No Chance , Mathematical Sciences Research Institute Publications, Vol. 42, pp. 369-381, Cambridge University Press (2002).

• This paper was motivated by the Planarity Game:

  • On the obfuscation complexity of planar graphs. Theoretical Computer Science 396:294-300 (2008).