61 citations · 83 across the 10 of their papers we have counts for
Showing 2024Show all
2 papers · 1 filter
math.CO2024
A logarithmic approximation of linearly ordered colourings
Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima +1
A linearly ordered (LO) -colouring of a hypergraph assigns to each vertex a colour from the set in such a way that each hyperedge has a unique maximum eleme…
cs.CC2024
On Small-depth Frege Proofs for PHP
Johan Håstad
We study Frege proofs for the one-to-one graph Pigeon Hole Principle defined on the grid where is odd. We are interested in the case where each formula in the proof…