My recent 2-part talk on new aspects of ladder system uniformization at our local research seminar:
My lecture at the CIRM Set Theory Workshop (2017):
My invited lecture at the 4th European Set Theory Conference (2016):
unpublished papers
D. T. Soukup, Ladder system uniformization on trees II: growing trees, arxiv.
- Given a tree $T$ of height $\omg$, we say that a ladder system colouring $(f_\alpha)_{\alpha\in \lim\omg}$ has a $T$-uniformization if there is a function $\varphi$ defined on a subtree $S$ of $T$ so that for any $s\in S_\alpha$ of limit height and almost all $\xi\in dom (f_\alpha)$, $\varphi(s\upharpoonright \xi)=f_\alpha(\xi)$. Continuing previous investigations by J. Moore and the current author, our goal is to present further surprising differences between the existence of $T$-uniformizations and the classical theory of uniformizations on $\omg$. We prove that $\diamondsuit^+$ implies that for any ladder system $\mathbf C$, there is an Aronszajn tree $T$ so that any monochromatic colouring of $\mathbf C$ has a $T$-uniformization; we can make $T$ special or ensure that the uniformizations are defined on Suslin subtrees. Moreover, we prove that any ladder system colouring has a non-special $\sigma \mathbb Q$-uniformization. The latter result holds in ZFC and there is a single colouring of $\sigma\mathbb Q$ that witnesses this fact for all ladder system colourings.
D. T. Soukup, Ladder system uniformization on trees I: colouring ladders, arxiv.
- Suppose that $T$ is a tree of height $\omg$. We say that a ladder system colouring $(f_\alpha)_{\alpha\in \lim\omg}$ has a $T$-uniformization if there is a function $\varphi$ defined on a subtree $S$ of $T$ so that for any $s\in S_\alpha$ of limit height and almost all $\xi\in dom (f_\alpha)$, $\varphi(s\upharpoonright \xi)=f_\alpha(\xi)$. In sharp contrast to the classical theory of uniformizations on $\omg$, J. Moore proved that CH is consistent with the statement that any ladder system colouring has a $T$-uniformization (for any Aronszajn tree $T$). However, we show that if $S$ is a Suslin tree then (i) CH implies that there is a ladder system colouring without $S$-uniformization; (ii) the restricted forcing axiom $MA(S)$ implies that any ladder system colouring has an $\omg$-uniformization. For an arbitrary Aronszajn tree $T$, we show how diamond-type assumptions affect the existence of ladder system colourings without a $T$-uniformization. Finally, we prove that consistently for any Aronszajn tree $T$ and ladder system $\mathbf C$, there is a colouring of $\mathbf C$ without a $T$-uniformization.
- As early as the 17th century, Galileo Galilei wondered how to compare the
sizes of infinite sets. Fast forward almost four hundred years, and in the
summer of 2017, at the 6th European Set Theory Conference, a young model
theorist, Maryanthe Malliaris, and the well-known polymath, Saharon Shelah,
received the Hausdorff Medal for the most influential work in set theory
published in the last five years. Malliaris and Shelah made significant
breakthroughs both regarding a model theoretic classification problem (that is,
sorting certain objects into types), and proved that two well-studied infinite
quantities, $\mathfrak{p}$ and $\mathfrak{t}$, are in fact the same. This
latter result is the focus of our expository paper.
published papers
V. Fischer, D. C. Montoya, J. Schilhan, D. T. Soukup, Towers and gaps at uncountable cardinals, Fundamenta Mathematicae (to appear), preprint on arxiv.
- Our goal is to study the pseudo-intersection and tower numbers on uncountable regular cardinals, whether these two cardinal characteristics are necessarily equal, and related problems on the existence of gaps. First, we prove that either $\mf p(\kappa)=\mf t(\kappa)$ or there is a $(\mf p(\kappa),\lambda)$-gap of club-supported slaloms for some $\lambda\le \mf p(\kappa)$. While the existence of such gaps is unclear, this is a promising step to lift Malliaris and Shelah's proof of $\mf p=\mf t$ to uncountable cardinals. We do analyze gaps of slaloms and, in particular, show that $\mf p(\kappa)$ is always regular; the latter extends results of Garti. Finally, we turn to club variants of $\mf p(\kappa)$ and present a new model for the inequality $\mathfrak{p}(\kappa) = \kappa^+ \le \mathfrak{p}_{cl}(\kappa) = 2^\kappa$. In contrast to earlier arguments by Shelah and Spasojevic, we achieve this by adding $\kappa$-Cohen reals and then successively diagonalising the club-filter; the latter is shown to preserve a Cohen witness to $\mathfrak{p}(\kappa) = \kappa^+$.
V. Fischer, D. T. Soukup, More ZFC inequalities between cardinal invariants, Journal of Symbolic Logic (to appear), arxiv.
- Motivated by a recent result of D. Raghavan and S. Shelah, we present ZFC theorems on the bounding and various almost disjointness numbers, as well as on reaping and dominating families on uncountable, regular cardinals. We show that if $\kappa=\lambda^+$ and $\mathfrak b(\kappa)=\kappa^+$ then $\mathfrak a_e(\kappa)=\mathfrak a_p(\kappa)=\kappa^+$. If additionally $2^{\lt \lambda}=\lambda$ then $\mathfrak a_g(\kappa)=\kappa^+$ as well. Furthermore, we prove that $\mathfrak d(\kappa)\leq \mathfrak r_\sigma(\kappa)\leq \textrm{cof}([\mathfrak r(\kappa)]^\omega)$, and $\mathfrak d(\kappa)\leq \mathfrak r(\kappa)$ whenever $\mathfrak r(\kappa)\le\mathfrak b(\kappa)^{+\kappa}$ or $\textrm{cof}(\mathfrak r(\kappa))\leq \kappa$ holds.
S. D. Friedman, D. T. Soukup, On the complexity of classes of uncountable structures: trees on $\aleph_1$, Fundamenta Mathematicae (to appear), preprint on arxiv.
- We analyse the complexity of the class of (special) Aronszajn, Suslin and Kurepa trees in the projective hierarchy of the higher Baire-space $\omg^\omg$. First, we will show that none of these classes have the Baire property (unless they are empty). Moreover, under $(V=L)$, (a) the class of Aronszajn and Suslin trees is $\piii$-complete, (b) the class of special Aronszajn trees is $\siii$-complete, and (c) the class of Kurepa trees is $\Pi^1_2$-complete. We achieve these results by finding nicely definable reductions that map subsets $X$ of $\omg$ to trees $T_X$ so that $T_X$ is in a given tree-class $\mc T$ if and only if $X$ is stationary/non-stationary (depending on the class $\mc T$). Finally, we present models of CH where these classes have lower projective complexity.
A. Aranda, C. Laflamme, D. T. Soukup, R.
Woodrow, A universal partition result for infinite ${K}_n$-free and related graphs,
Discrete Mathematics (Volume 344, Issue 1, January 2021) , the results are part of
arxiv and DOI
- Given specific infinite ${K}_n$-free graphs $G$, we investigate the function $m\mapsto r(G,m)$ where $r(G,m)$ is the minimal $r$ so that any balanced $r$-colouring of the vertices of $G$ one can find an independent set which meets at least $m$ colour classes in a set of size $|V|$. Answering a conjecture of S. Thomass\'e, we express the exact value of $r(H_n,m)$ using Ramsey-numbers for finite digraphs, where $H_n$ is Henson's countable universal homogeneous $K_n$-free graph. Moreover, we deduce a new partition property of $H_n$ regarding balanced embeddings of bipartite graphs. We also look at shift graphs, orthogonality graphs on Euclidean spaces and unit distance graphs.
P. Ellis, A. Joó, D. T. Soukup, Reducing the dichromatic number via cycle reversions in infinite
digraphs, European Journal of Combinatorics (Volume 90, December 2020)
, arxiv
and DOI.
- We prove the following conjecture of S. Thomass\'e: for every (potentially
infinite) digraph $ D $ it is possible to iteratively reverse directed cycles
in such a way that the dichromatic number of the final reorientation $ D^{*} $
of $ D $ is at most two and each edge is flipped only finitely many times. In
addition, we guarantee that in every strong component of $ D^{*} $ all the
local edge-connectivities are finite and any edge is reversed at most twice.
C. Lambie-Hanson, D. T. Soukup, Extremal triangle-free and odd-cycle-free colourings, to appear in Acta Math. Hungarica (accepted March 2020), arxiv.
- The optimality of the Erdős-Rado theorem for pairs is witnessed by the
colouring $\Delta_\kappa: [2^\kappa]^2 \rightarrow \kappa$ recording the least
point of disagreement between two functions. This colouring has no
monochromatic triangles or, more generally, odd cycles. We investigate a number
of questions investigating the extent to which $\Delta_\kappa$ is an
\emph{extremal} such triangle-free or odd-cycle-free colouring. We begin by
introducing the notion of $\Delta$-regressive and almost $\Delta$-regressive
colourings and studying the structures that must appear as monochromatic
subgraphs for such colourings. We also consider the question as to whether
$\Delta_\kappa$ has the minimal cardinality of any \emph{maximal} triangle-free
or odd-cycle-free colouring into $\kappa$. We resolve the question positively
for odd-cycle-free colourings.
D. T. Soukup, P. J. Szeptycki, A 0-dimensional, Lindelöf space that is not strongly D, Topology and its Applications Volume 265, 15 September 2019, 106832 (submitted February 2019, accepted August 2019), DOI and arxiv.
- A topological space $X$ is strongly $D$ if for any neighbourhood assignment $\{U_x:x\in X\}$, there is a $D\subseteq X$ such that $\{U_x:x\in D\}$ covers $X$ and $D$ is locally finite in the topology generated by $\{U_x:x\in X\}$. We prove that $\diamondsuit$ implies that there is an $HFC_w$ space in $2^\omg$ (hence 0-dimensional, Hausdorff and hereditarily Lindelöf) which is not strongly $D$. We also show that any $HFC$ space $X$ is dually discrete and if additionally countable sets have Menger closure then $X$ is a $D$-space.
D. T. Soukup, Solved and Unsolved Problems (contributed problem in Topology), Newsletter of the European Mathematical Society (Issue March 2019), download.
R. Carroy, B. D. Miller, D. T. Soukup, The open graph dichotomy and the second level of the Borel hierarchy, to appear in Contemporary Mathematics, arxiv.
- We show that several dichotomy theorems concerning the second
level of the Borel hierarchy are special cases of the
$\aleph_0$-dimensional generalization of the open graph dichotomy,
which itself follows from the usual proof(s) of the perfect set theorem.
Under the axiom of determinacy, we obtain the generalizations of
these results from analytic metric spaces to separable metric spaces.
We also consider connections between cardinal invariants and the
chromatic numbers of the corresponding dihypergraphs.
A. Aranda, C. Laflamme, D. T. Soukup, R.
Woodrow, Balanced independent sets in graphs omitting large cliques, Journal of Combinatorial Theory Series B, Volume 137, July 2019, Pages 1-9, DOI
, arxiv.
- Our goal is to investigate a common relative of the independent transversal problem and the Dushnik-Erd\H os-Miller theorem in the class of infinite $K_n$-free graphs: we show that for any infinite $K_n$-free graph $G=(V,E)$ and $m\in \mathbb N$ there is a minimal $r=r(G,m)$ such that for any balanced $r$-colouring of the vertices of $G$ one can find an independent set which meets at least $m$ colour classes in a set of size $|V|$. We bound $r(G,m)$ using Ramsey-numbers for finite digraphs, and show that this bound is tight for certain graphs.
D. T. Soukup, A model with Suslin trees but no minimal uncountable linear orders other than $\omega_1$ and $-\omega_1$, Israel Journal of Mathematics (to appear, accepted November 2018), arxiv.
- We show that the existence of a Suslin tree does not necessarily imply that there are uncountable minimal linear orders other than $\omega_1$ and $-\omega_1$, answering a question of J. Baumgartner. This is done by a Jensen-type ccc iteration, proving that one can force CH together with a weak form of ladder system uniformization on trees, all while preserving a Suslin tree.
P. Komjáth, I. Leader, P. A. Russell, S. Shelah, D. T. Soukup, Z. Vidnyánszky Infinite monochromatic sumsets for colourings of the reals, Proc. Amer. Math. Soc. 147 (2019), 2673-2684 , DOI
, arxiv.
- N. Hindman, I. Leader and D. Strauss proved that it is consistent that there is a finite colouring of $\mathbb R$ so that no infinite sumset $X+X$ is monochromatic. Our aim in this paper is to prove a consistency result in the opposite direction: we show that, under certain set-theoretic assumptions, for any $c:\mathbb R\to r$ with $r$ finite there is an infinite $X\subseteq \mathbb R$ so that $c\upharpoonright X+X$ is constant.
The results are summarized in this video.
UPDATE: I learned from Jing Zhang (CMU) that he showed that for any 2-colouring of $N(\omega_1)$ there is an infinite set $X\subseteq N(\omega_1)$ so that $X+X$ is monochromatic. Moreover, he showed if one adds $\aleph_\omega$ Cohen reals to a model of GCH then for any finite colouring of $\mathbb R$ there is an infinite monochromatic sumset. Until now, we could only do this using large cardinals and our continuum was way above $\aleph_\omega$ (see our original paper).
P. Ellis, D. T. Soukup Cycle reversions and dichromatic number in tournaments, European Journal of Combinatorics, Volume 77, March 2019, Pages 31-48, DOI arxiv
- We show that if $D$ is a tournament of arbitrary size then $D$ has finite strong components after reversing a locally finite sequence of cycles. In turn, we prove that any tournament can be covered by two acyclic sets after reversing a locally finite sequence of cycles. This provides a partial solution to a conjecture of S. Thomassé.
UPDATE: Together with Attila Joó, the three of us managed to solve the general problem and showed that any digraph has dichromatic number 2 after an appropriate cycle reversion. Preprint coming soon.
D. T. Soukup, L. Soukup, Infinite combinatorics plain and simple,
Journal of Symbolic Logic, Volume 83, Issue 3 September 2018, pp. 1247-1281, DOI, arxiv
- We explore a general method based on trees of elementary submodels in order to present highly simplified proofs to numerous results in infinite combinatorics.
While countable elementary submodels have been employed in such settings already, we significantly broaden this framework by developing the corresponding technique for countably closed models of size continuum. The applications range from various theorems on paradoxical decompositions of the plane, to coloring sparse set systems, results on graph chromatic number and constructions from point-set topology. Our main purpose is to demonstrate the ease and wide applicability of this method in a form accessible to anyone with a basic background in set theory and logic. This is a good video summary.
D. T. Soukup,
Uncountable strongly surjective linear orders, Order, March 2019, Volume 36, Issue 1, pp 43–64, DOI, arxiv
-A linear order $L$ is strongly surjective if $L$ can be mapped onto any of its suborders in an order preserving way. We prove various results on the existence and non-existence of uncountable strongly surjective linear orders answering questions of Camerlo, Carroy and Marcone. In particular, $\diamondsuit^+$ implies the existence of a lexicographically ordered Suslin-tree which is strongly surjective and minimal; every strongly surjective linear order must be an Aronszajn type under $2^{\aleph_0}\lt 2^{\aleph_1}$ or in the Cohen and other canonical models (where $2^{\aleph_0}=2^{\aleph_1}$); finally, we prove that it is consistent with CH that there are no uncountable strongly surjective linear orders at all.
R. R. Dias, D. T. Soukup, On spaces
with $\sigma$-closed-discrete dense sets, Top. Proc. 52 (2018) pp. 245-264. (E-published on February 16, 2018) arxiv.
- The main purpose of this paper is to study $e$-separable spaces, originally introduced by Kurepa as $K_0'$ spaces; we call a space $X$ $e$-separable iff $X$ has a dense set which is the union of countably many closed discrete sets. We primarily focus on the behaviour of $e$-separable spaces under products and the cardinal invariants that are naturally related to $e$-separable spaces. Our main results show that the statement ``there is a product of at most $\mathfrak c$ many $e$-separable spaces that fails to be $e$-separable'' is equiconsistent with the existence of a weakly compact cardinal.
D. T. Soukup, Orientations of graphs
with uncountable chromatic number, Journal of Graph Theory. 2018;88:606–630, DOI
, arxiv
- A graph (digraph) has uncountable chromatic number if its vertices
cannot be covered by countably many independent (acyclic) sets. Our aim
is to investigate digraphs with uncountable chromatic number and
orientations of undirected graphs with uncountable chromatic number.
D. T. Soukup, Decompositions of
edge-colored infinite complete graphs into monochromatic paths II, Israel Journal of Mathematics 221 (2017), 235–273.
arxiv
- Answering a question of R. Rado, we show that every finite-edge
coloured infinite complete graph can be partitioned into
disjoint monochromatic paths of different colour.
M. Elekes, D. T. Soukup, L. Soukup, Z.
Szentmiklóssy, Decompositions of edge-colored infinite
complete graphs into monochromatic paths, Discrete Mathematics
Volume 340, Issue 8, August 2017, Pages 2053–2069.
arxiv
- We prove results about path decompositions of edge coloured infinite
complete graphs and hypergraphs.
D. T. Soukup, Trees, ladders and
graphs, Journal of Combinatorial Theory, Series B
115 (2015) 96–116. arxiv
- Answering a question of P. Erdős and A. Hajnal, we show that there is
a graph of chromatic number $\omega_1$ without an uncountable infinitely
connected subgraph. The construction builds on a diagonalization of length $\mathfrak{c}$ on the tree of closed subsets of a stationary, costationary subset of $\omega_1$.
D. T. Soukup, L. Soukup, Partitioning
bases of topological spaces, Comment. Math. Univ. Carolin.
55,4 (2014) 537-566.
arxiv
D. T. Soukup, L. Soukup, S. Spadaro, Comparing
weak versions of separability, Topology Appl. 160 (2013), no.
18, 2538–2566.
arxiv
D. T. Soukup, P. Szeptycki, The
union of two D-spaces may not be D, Fund. Math. 220 (2013),
no. 2, 129–137.
paper
D. T. Soukup, P. Szeptycki, A
counterexample in the theory of D-spaces, Topology Appl. 159
(2012), no. 10-11, 2669–2678. arxiv
D. T. Soukup, Constructing aD, non
D-spaces, Topology and its Applications, Volume 158 (2011),
no. 10, Pages 1219-1225. arxiv
D. T. Soukup, Xu Yuming, The
Collins-Roscoe mechanism and D-spaces, Acta Math. Hun. Vol.
131, Number 3 (2011), Pages 275-284. arxiv
D. T. Soukup, Properties D and aD are
different, Top. Proc. 38 (2011) Pages 279-299. arxiv
2017: 5th Heidelberg Laureate Forum. More info
here. Some coverage from Spiegel.
2017: Chromatic number - finite, infinite and uncountable
at the ÖMG-DMV-Congress 2017 in Salzburg, Austria. Here are my
slides.
2017: How to make infinite combinatorics simple? plenary talk
at the 6th European Set Thoery Conference, in Budapest, Hungary. The conference webpage,my
slides and a video.
2017: On spaces with small dense sets; semi-plenary talk
at the 51st Topology and Dynamics Conference, Jersey City. conference webpageMy
slides. The lecture video.
2016: Math & Stats
Departmental Colloquium, University of Calgary; the
abstract and my
slides
.
2016: Oberwolfach Graph Theory Workshop; invited
participant at the MFO.
2015: Sums and anti-Ramsey colourings; at the Young
Researcher's Mini Conference my
talk at Rényi.
2015: Problems on uncountable graphs; at
Independence Results in Mathematics and Challenges in Iterated Forcing
(University of East Anglia, Norwich) my
talk, a handout
and the workshop website.
2014: Davies-trees in infinite combinatorics; at
the Logic Colloquium, Vienna Austria my
talk and the conference website.
2014: Monochromatic path decompositions; at the
Ontario Combinatorics Workshop, Toronto, Canada my talk and the
conference website.
2013: Partitioning bases of topological spaces; at
the Erdős Centennial Conference, poster section, Budapest, Hungary, my poster and the
conference website.
2012: Constructing Lindelöf non-D-spaces ; at
Trends in Set Theory, Warsaw, Poland, my
slides and the conference website.
2012: Variations on (selective) separability; at
IVth Workshop on Coverings, Selections, and Games in Topology, Caserta,
Italy, my slides
and the conference website.
2011: Guessing clubs for aD, non D-spaces; at
Winterschool in Abstract Analysis, Section Set Theory and Topology,
Hejnice, Czech Republic, my slides
and the conference website.
2010: Crosslike constructions and refinements; at
Winterschool in Abstract Analysis, Section Set Theory and Topology,
Hejnice, Czech Republic, my
slides and the conference website.
notes, seminar talks
Minimal walks on finite random graphs (April 2019), talk at the Discrete Math Seminar (University of Hamburg).
- The aim of this talk is to outline a new project and some preliminary results concerning minimal walks on ordered random graphs. Suppose that G is a graph with a well-ordered vertex set $(V,\le)$ i.e., any subset W of the vertices has a smallest element. For example, any (total) order on a finite set is a well-order; the usual order of the rationals is not a well order since it contains infinite decreasing sequences. Now, given vertices $u\le v$, the minimal walk from $v$ to $u$ is the unique sequence $v=v_0,v_1... v_n$ so that $v_{i+1}$ is the $\le$-minimal neighbour of v_i that is bigger or equal to u with respect the vertex order. In other words, we walk down from v by always taking the $\le$-closest neighbour to u. We may or may not reach u, but the walk always terminates in finitely many steps. The analysis of such walks on sparse, uncountable graphs was initiated by S. Todorcevic in the 1980s; based on various characteristics of the walks, he produced a wealth of rainbow Ramsey colourings and various canonical linear orders. Our goal now is to study whether such walks on finite graphs can yield similarly interesting results. Looking at the Erdos-Renyi random model on vertices $\{0,1,...,n\}$, we will present results on the probability that the $n$ to 0 minimal walk does reach 0 and the expected number of steps.
Uniformization properties and graph edge colourings (February 2019), talk at the Set Theory Seminar at Bar-Ilan (Ramat Gan, Israel).
- Sierpinski's now classical result states that there is an edge 2-colouring of the complete graph on $\aleph_1$ vertices so that there are no uncountable monochromatic subgraphs. In the 1970s, Erdos, Galvin and Hajnal asked what other graphs with large chromatic number admit similar edge colourings i.e., with no 'large' monochromatic subgraphs. We plan to review some recent advances on this problem and in particular, connect the question to Shelah's ladder system uniformization theory.
HFC and D-spaces (February 2019), seminar talk at the Renyi Institute (Budapest, Hungary).
- A topological space $X$ is strongly $D$ if for any neighbourhood assignment $\{U_x:x\in X\}$, there is a $D\subseteq X$ such that $\{U_x:x\in D\}$ covers $X$ and $D$ is locally finite in the topology generated by $\{U_x:x\in X\}$. We prove that $\diamondsuit$ implies that there is an $HFC_w$ space in $2^{\omega_1}$ (hence 0-dimensional, Hausdorff and hereditarily Lindelöf) which is not strongly $D$. We also show that any $HFC$ space $X$ is dually discrete and if additionally, countable sets have Menger closure then $X$ is a $D$-space. Joint work with Paul Szeptycki (cf. preprint).
New aspects of ladder system uniformization (November and December 2018), seminar talk at the KGRC with videos for both Part I and Part II.
- After a brief overview of some classical results, we will survey new
applications of ladder system uniformization. In particular, we constrast
uniformizations defined on $\omega_1$ and uniformizations on trees of
height $\omega_1$. The latter, introduced by J. Moore, played a critical
role in understanding minimal uncountable linear orders under CH. One of
our rather surprising new results is that whenever $\diamondsuit^+$ holds,
for any ladder system $\mathbf C$ there is an Aronszajn tree $T$ so that
any monochromatic colouring of $\mathbf C$ has a $T$-uniformization (cf.
https://arxiv.org/abs/1806.03867).
Colouring the real numbers and sum-sets with repetitions (November 2018), seminar talk at the Cambridge Combinatorics Seminar.
- This talk will focus on relatives of Hindman’s finite sums theorem. In particular, we consider finite partitions of the set of real numbers and look for the existence of large (i.e., infinite or even uncountable) sets $X$ so that $X+X$ is fully contained in one class of the partition. In the case when repetitions are allowed, we discuss how the existence of even a countably infinite monochromatic sum-set heavily depends on the set-theoretic universe. However, the talk should be accessible to all with a minimal background in set theory.
- We present a weaker version of a recent result of D. Raghavan and S. Todorcevic that highlights their main combinatorial ideas in proving Galvin's conjecture (assuming the existence of some large cardinals). Using their arguments, we show that if there is a precipitous ideal on $\omega_1$ then for any uncountable set of reals $X$ and finite colouring $c:[X]^2\to \ell$ there is a homeomorphic copy $Y\subseteq X$ of $\mathbb Q$ so that $c\upharpoonright [Y]^2$ assumes at most two colours.
Chromatic number problems on infinite digraphs (June 2018), seminar talk at the research seminar of the Discrete Math group at the University of Hamburg.
- The dichromatic number of a digraph D is the minimal number of acyclic vertex sets needed to cover D. In this talk, motivated by a question of Erdős and Neumann-Lara, we will look at possible orientations of graphs with large chromatic number and in doing so, I aim to highlight some analogies and various differences between the behaviour of graphs with uncountable chromatic number and digraphs with uncountable dichromatic number. Furthermore, we look at a question of Thomassé: how much can the dichromatic number of a digraph be lowered by simply reversing cycles one after the other?
- The goal of this talk is to explore a general method based on trees of elementary submodels which can be used to highly simplify proofs to numerous results in infinite combinatorics. While countable elementary submodels have been employed in such settings already, we also present the corresponding technique with countably closed models of size continuum. The applications range from various theorems on paradoxical decompositions of the plane, to coloring sparse set systems, results on graph chromatic number and constructions from point-set topology. Our main purpose is to demonstrate the ease and wide applicability of this method in a form accessible to anyone with a basic background in set theory and logic.
D. T. Soukup, W. Weiss, Sums and
anti-Ramsey colourings of $\mathbb R$,
notes
- Hindman, Leader and Strauss proved that CH implies that there is a
2-colouring of the reals such that the set of pairwise sums formed from
an uncountable set is not monochromatic. We show that the same results
holds in ZFC.
Coloring problems on infinite graphs. talk
at
Miami University (Oxford, OH)
D. T. Soukup,
Hitchhiker's guide to coloring pairs of $\aleph_2$. note
D. T. Soukup,
Davies-trees in infinite combinatorics. seminar
talk at UTM
