17 citations · 78 across the 27 of their papers we have counts for
31 papers
Circular Chromatic Numbers, Signability, Relation Algebras, and Network Satisfaction Problems
Manuel Bodirsky, Santiago Guzmán-Pro, Moritz Jahn +2
In this paper, we characterize finite graphs with circular chromatic number less than 3 in terms of the existence of certain signings (-labellings studied in the conte…
Network Satisfaction over Four-Atom Relation Algebras: Complexity and Representations
Manuel Bodirsky, Moritz Jahn, Simon Knäuer +2
Andréka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable. Cristani and Hirsch showed that the netw…
Counting big Ramsey degrees of the homogeneous and universal -free graph
Jan Hubička, Matěj Konečný, Štěpán Vodseďálek +1
Big Ramsey degrees of Fraïssé limits of finitely constrained free amalgamation classes in finite binary languages have been recently fully characterised by Balko, Chodounský, Dobri…
On Big Ramsey degrees of universal -edge-labeled hypergraphs
Jan Hubička, Matěj Konečný, Stevo Todorcevic +1
We show that the big Ramsey degrees of every countable universal -uniform -edge-labeled hypergraph are infinite for every . Together with a recent result of Braunfel…
Oscillating subalgebras of the atomless countable Boolean algebra
Dana Bartošová, David Chodounský, Barbara Csima +6
We show that the big Ramsey degree of the Boolean algebra with 3 atoms within the countable atomless Boolean algebra is infinite.
Twenty years of Nešetřil's classification programme of Ramsey classes
Jan Hubička, Matěj Konečný
In the 1970s, structural Ramsey theory emerged as a new branch of combinatorics. This development came with the isolation of the concepts of the -Ramsey property and Ra…
Extension property for partial automorphisms of the -partite and semigeneric tournaments
Jan Hubička, Colin Jahel, Matěj Konečný +1
We present a proof of the extension property for partial automorphisms (EPPA) for classes of finite -partite tournaments for , and for the class of finit…
Ramsey theorem for trees with successor operation
Martin Balko, David Chodounský, Natasha Dobrinen +4
We prove a general Ramsey theorem for trees with a successor operation. This theorem is a common generalization of the Carlson-Simpson Theorem and the Milliken Tree Theorem for reg…
EPPA numbers of graphs
David Bradley-Williams, Peter J. Cameron, Jan Hubička +1
If is a graph, and its induced subgraphs, and an isomorphism, we say that is a \emph{partial automorphism} of . In 1992, Hrushovski proved that…
Big Ramsey degrees in the metric setting
Tristan Bice, Noé de Rancourt, Jan Hubička +1
Oscillation stability is an important concept in Banach space theory which happens to be closely connected to discrete Ramsey theory. For example, Gowers proved oscillation stabili…
Type-respecting amalgamation and big Ramsey degrees
Andrés Aranda, Samuel Braunfeld, David Chodounský +4
We give an infinitary extension of the Nešetřil-Rödl theorem for category of relational structures with special type-respecting embeddings.
Characterisation of the big Ramsey degrees of the generic partial order
Martin Balko, David Chodounský, Natasha Dobrinen +4
As a result of 33 intercontinental Zoom calls, we characterise big Ramsey degrees of the generic partial order. This is an infinitary extension of the well known fact that finite p…
Big Ramsey Degrees and Infinite Languages
Samuel Braunfeld, David Chodounský, Noé de Rancourt +3
This paper investigates big Ramsey degrees of unrestricted relational structures in (possibly) infinite languages. Despite significant progress in the study of big Ramsey degrees,…
Exact big Ramsey degrees for finitely constrained binary free amalgamation classes
Martin Balko, David Chodounský, Natasha Dobrinen +4
We characterize the big Ramsey degrees of free amalgamation classes in finite binary languages defined by finitely many forbidden irreducible substructures, thus refining the recen…
Ramsey expansions of 3-hypertournaments
Gregory Cherlin, Jan Hubička, Matěj Konečný +1
We study Ramsey expansions of certain homogeneous 3-hypertournaments. We show that they exhibit an interesting behaviour and, in one case, they seem not to submit to current gold-s…
Big Ramsey degrees and forbidden cycles
Martin Balko, David Chodounský, Jan Hubička +3
Using the Carlson-Simpson theorem, we give a new general condition for a structure in a finite binary relational language to have finite big Ramsey degrees
Big Ramsey degrees of the generic partial order
Martin Balko, David Chodounský, Natasha Dobrinen +4
As a result of 33 intercontinental Zoom calls, we characterise big Ramsey degrees of the generic partial order in a similar way as Devlin characterised big Ramsey degrees of the ge…
Big Ramsey degrees of 3-uniform hypergraphs are finite
Martin Balko, David Chodounský, Jan Hubička +2
We prove that the universal homogeneous 3-uniform hypergraph has finite big Ramsey degrees. This is the first case where big Ramsey degrees are known to be finite for structures in…
Simplicity of the automorphism groups of generalised metric spaces
David M. Evans, Jan Hubička, Matěj Konečný +2
Tent and Ziegler proved that the automorphism group of the Urysohn sphere is simple and that the automorphism group of the Urysohn space is simple modulo bounded automorphisms. A k…
Big Ramsey degrees of 3-uniform hypergraphs
Martin Balko, David Chodounský, Jan Hubička +2
Given a countably infinite hypergraph and a finite hypergraph , the big Ramsey degree of in is the least number such that, fo…
Extending partial automorphisms of -partite tournaments
Jan Hubička, Colin Jahel, Matěj Konečný +1
We prove that for every the class of all finite -partite tournaments (orientations of complete -partite graphs) has the extension property for partial automorphisms…
Extending partial isometries of antipodal graphs
Matěj Konečný
We prove EPPA (extension property for partial automorphisms) for all antipodal classes from Cherlin's list of metrically homogeneous graphs, thereby answering a question of Aranda…
EPPA for two-graphs and antipodal metric spaces
David Evans, Jan Hubička, Matěj Konečný +1
We prove that the class of finite two-graphs has the extension property for partial automorphisms (EPPA, or Hrushovski property), thereby answering a question of Macpherson. In oth…
A combinatorial proof of the extension property for partial isometries
Jan Hubička, Matěj Konečný, Jaroslav Nešetřil
We present a short and self-contained proof of the extension property for partial isometries of the class of all finite metric spaces.