3 papers
math.CO2025
From the Finite to the Infinite: Sharper Asymptotic Bounds on Norin's Conjecture via SAT
Markus Kirchweger, Tomáš Peitl, Bernardo Subercaseaux +1
Norin (2008) conjectured that any -edge-coloring of the hypercube in which antipodal edges receive different colors must contain a monochromatic path between some pair of…
cs.LO2025
Better Extension Variables in DQBF via Independence
Leroy Chew, Tomáš Peitl
We show that extension variables in (D)QBF can be generalised by conditioning on universal assignments. The benefit of this is that the dependency sets of such conditioned extensio…
cs.LO2025
Breaking Symmetries in Quantified Graph Search: A Comparative Study
Mikoláš Janota, Markus Kirchweger, Tomáš Peitl +1
Graph generation and enumeration problems often require handling equivalent graphs -- those that differ only in vertex labeling. We study how to extend SAT Modulo Symmetries (SMS),…