Antichains in the homomorphism order of graphs

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

The search session has expired. Please query the service again.

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...