Antichains in the homomorphism order of graphs

Dwight Duffus; Peter, L. Erdös; Jaroslav Nešetřil; Lajos Soukup

Displaying similar documents to “Antichains in the homomorphism order of graphs”

On graphs whose reduced energy does not exceed 3.

Lazić, Mirjana (2005)

Publications de l'Institut Mathématique. Nouvelle Série

Similarity:

A strongly non-Ramsey uncountable graph

Péter Komjáth (1997)

Fundamenta Mathematicae

Similarity:

It is consistent that there exists a graph X of cardinality $ℵ_{1}$ such that every graph has an edge coloring with $ℵ_{1}$ colors in which the induced copies of X (if there are any) are totally multicolored (get all possible colors).

Path partitions of planar graphs.

Glebov, A.N., Zambalaeva, D.Zh. (2007)

Sibirskie Ehlektronnye Matematicheskie Izvestiya [electronic only]

Similarity:

Graphs and models with finite chains.

Nurtazin, A.T. (2007)

Sibirskie Ehlektronnye Matematicheskie Izvestiya [electronic only]

Similarity:

The Farey graph.

Jones, Gareth A. (1987)

Séminaire Lotharingien de Combinatoire [electronic only]

Similarity:

Computing the domination number of grid graphs.

Alanko, Samu, Crevals, Simon, Isopoussu, Anton, Östergård, Patric, Pettersson, Ville (2011)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Discriminating between causal structures in Bayesian Networks given partial observations

Philipp Moritz, Jörg Reichardt, Nihat Ay (2014)

Kybernetika

Similarity:

Given a fixed dependency graph $G$ that describes a Bayesian network of binary variables $X_{1}, \dots, X_{n}$ , our main result is a tight bound on the mutual information $I_{c} (Y_{1}, \dots, Y_{k}) = \sum_{j = 1}^{k} H (Y_{j}) / c - H (Y_{1}, \dots, Y_{k})$ of an observed subset $Y_{1}, \dots, Y_{k}$ of the variables $X_{1}, \dots, X_{n}$ . Our bound depends on certain quantities that can be computed from the connective structure of the nodes in $G$ . Thus it allows to discriminate between different dependency graphs for a probability distribution, as we show from numerical experiments.

Analytic determinacy and 0# A forcing-free proof of Harrington’s theorem

Ramez Sami (1999)

Fundamenta Mathematicae

Similarity:

We prove the following theorem: Given a⊆ω and $1 \leq α < ω_{1}^{C K}$ , if for some $η < ℵ_{1}$ and all u ∈ WO of length η, a is $Σ_{α}^{0} (u)$ , then a is $Σ_{α}^{0}$ . We use this result to give a new, forcing-free, proof of Leo Harrington’s theorem: $Σ_{1}^{1}$ -Turing-determinacy implies the existence of $0$ .

A note on Tsirelson type ideals

Boban Veličković (1999)

Fundamenta Mathematicae

Similarity:

Using Tsirelson’s well-known example of a Banach space which does not contain a copy of $c_{0}$ or $l_{p}$ , for p ≥ 1, we construct a simple Borel ideal $I_{T}$ such that the Borel cardinalities of the quotient spaces $P (ℕ) / I_{T}$ and $P (ℕ) / I_{0}$ are incomparable, where $I_{0}$ is the summable ideal of all sets A ⊆ ℕ such that $\sum_{n \in A} 1 / (n + 1) < \infty$ . This disproves a “trichotomy” conjecture for Borel ideals proposed by Kechris and Mazur.

Entropy and growth of expanding periodic orbits for one-dimensional maps

A. Katok, A. Mezhirov (1998)

Fundamenta Mathematicae

Similarity:

Let f be a continuous map of the circle $S^{1}$ or the interval I into itself, piecewise $C^{1}$ , piecewise monotone with finitely many intervals of monotonicity and having positive entropy h. For any ε > 0 we prove the existence of at least $e^{(h - ε) n_{k}}$ periodic points of period $n_{k}$ with large derivative along the period, $| {(f^{n_{k}})}^{'} | > e^{(h - ε) n_{k}}$ for some subsequence $n_{k}$ of natural numbers. For a strictly monotone map f without critical points we show the existence of at least $(1 - ε) e^{h n}$ such points.

Chaotic continua of (continuum-wise) expansive homeomorphisms and chaos in the sense of Li and Yorke

Hisao Kato (1994)

Fundamenta Mathematicae

Similarity:

A homeomorphism f : X → X of a compactum X is expansive (resp. continuum-wise expansive) if there is c > 0 such that if x, y ∈ X and x ≠ y (resp. if A is a nondegenerate subcontinuum of X), then there is n ∈ ℤ such that $d (f^{n} (x), f^{n} (y)) > c$ (resp. $d i a m f^{n} (A) > c$ ). We prove the following theorem: If f is a continuum-wise expansive homeomorphism of a compactum X and the covering dimension of X is positive (dim X > 0), then there exists a σ-chaotic continuum Z = Z(σ) of f (σ = s or σ = u), i.e. Z is a nondegenerate...

Parametrized Cichoń's diagram and small sets

Janusz Pawlikowski, Ireneusz Recław (1995)

Fundamenta Mathematicae

Similarity:

We parametrize Cichoń’s diagram and show how cardinals from Cichoń’s diagram yield classes of small sets of reals. For instance, we show that there exist subsets N and M of $w^{w} \times 2^{w}$ and continuous functions $e, f : w^{w} \to w^{w}$ such that • N is $G_{δ}$ and $N_{x} : x \in w^{w}$ , the collection of all vertical sections of N, is a basis for the ideal of measure zero subsets of $2^{w}$ ; • M is $F_{σ}$ and $M_{x} : x \in w^{w}$ is a basis for the ideal of meager subsets of $2^{w}$ ; • $\forall x, y N_{e (x)} \subseteq N_{y} \Rightarrow M_{x} \subseteq M_{f (y)}$ . From this we derive that for a separable metric space X, •if for all Borel (resp. $G_{δ}$ ) sets...

Borel partitions of unity and lower Carathéodory multifunctions

S. Srivastava (1995)

Fundamenta Mathematicae

Similarity:

We prove the existence of Carathéodory selections and representations of a closed convex valued, lower Carathéodory multifunction from a set A in $A (ℰ \otimes ℬ (X))$ into a separable Banach space Y, where ℰ is a sub-σ-field of the Borel σ-field ℬ(E) of a Polish space E, X is a Polish space and A is the Suslin operation. As applications we obtain random versions of results on extensions of continuous functions and fixed points of multifunctions. Such results are useful in the study of random differential...