Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC

Amitayu Banerjee; Zalán Gyenis

Displaying similar documents to “Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC”

Counting linearly ordered spaces

Gerald Kuba (2014)

Colloquium Mathematicae

Similarity:

For a transfinite cardinal κ and i ∈ 0,1,2 let $ℒ_{i} (κ)$ be the class of all linearly ordered spaces X of size κ such that X is totally disconnected when i = 0, the topology of X is generated by a dense linear ordering of X when i = 1, and X is compact when i = 2. Thus every space in ℒ₁(κ) ∩ ℒ₂(κ) is connected and hence ℒ₁(κ) ∩ ℒ₂(κ) = ∅ if $κ < 2^{ℵ ₀}$ , and ℒ₀(κ) ∩ ℒ₁(κ) ∩ ℒ₂(κ) = ∅ for arbitrary κ. All spaces in ℒ₁(ℵ₀) are homeomorphic, while ℒ₂(ℵ₀) contains precisely ℵ₁ spaces up to homeomorphism. The...

Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC

Amitayu Banerjee (2023)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. $\circ$ $𝒫_{lf, c}$ (Every locally finite connected graph has a maximal independent set). $\circ$ $𝒫_{lc, c}$ (Every locally countable connected graph has a maximal independent set). $\circ$ CAC $_{1}^{ℵ_{α}}$ (If in a partially ordered set all antichains are finite and all chains have size $ℵ_{α}$ , then the set has size $ℵ_{α}$ ) if $ℵ_{α}$ is regular. $\circ$ CWF (Every partially ordered set has a...

Matchings in complete bipartite graphs and the $r$ -Lah numbers

Gábor Nyul, Gabriella Rácz (2021)

Czechoslovak Mathematical Journal

Similarity:

We give a graph theoretic interpretation of $r$ -Lah numbers, namely, we show that the $r$ -Lah number ${⌊\binom{n}{k}⌋}_{r}$ counting the number of $r$ -partitions of an $(n + r)$ -element set into $k + r$ ordered blocks is just equal to the number of matchings consisting of $n - k$ edges in the complete bipartite graph with partite sets of cardinality $n$ and $n + 2 r - 1$ ( $0 \leq k \leq n$ , $r \geq 1$ ). We present five independent proofs including a direct, bijective one. Finally, we close our work with a similar result for $r$ -Stirling numbers of the second kind. ...

On certain non-constructive properties of infinite-dimensional vector spaces

Eleftherios Tachtsis (2018)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In set theory without the axiom of choice ( $AC$ ), we study certain non-constructive properties of infinite-dimensional vector spaces. Among several results, we establish the following: (i) None of the principles AC $^{LO}$ (AC for linearly ordered families of nonempty sets)—and hence AC $^{WO}$ (AC for well-ordered families of nonempty sets)— $DC (< κ)$ (where $κ$ is an uncountable regular cardinal), and “for every infinite set $X$ , there is a bijection $f : X \to {0, 1} \times X$ ”, implies the statement “there exists a field $F$ such that...

On generalized derivations of partially ordered sets

Ahmed Y. Abdelwanis, Abdelkarim Boua (2019)

Communications in Mathematics

Similarity:

Let $P$ be a poset and $d$ be a derivation on $P$ . In this research, the notion of generalized $d$ -derivation on partially ordered sets is presented and studied. Several characterization theorems on generalized $d$ -derivations are introduced. The properties of the fixed points based on the generalized $d$ -derivations are examined. The properties of ideals and operations related with generalized $d$ -derivations are studied.

Modifications of the double arrow space and related Banach spaces C(K)

Witold Marciszewski (2008)

Studia Mathematica

Similarity:

We consider the class of compact spaces $K_{A}$ which are modifications of the well known double arrow space. The space $K_{A}$ is obtained from a closed subset K of the unit interval [0,1] by “splitting” points from a subset A ⊂ K. The class of all such spaces coincides with the class of separable linearly ordered compact spaces. We prove some results on the topological classification of $K_{A}$ spaces and on the isomorphic classification of the Banach spaces $C (K_{A})$ .

Saturation numbers for linear forests $P_{6} + t P_{2}$

Jingru Yan (2023)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is $H$ -saturated if it contains no $H$ as a subgraph, but does contain $H$ after the addition of any edge in the complement of $G$ . The saturation number, $sat (n, H)$ , is the minimum number of edges of a graph in the set of all $H$ -saturated graphs of order $n$ . We determine the saturation number $sat (n, P_{6} + t P_{2})$ for $n \geq \frac{10}{3} t + 10$ and characterize the extremal graphs for $n > \frac{10}{3} t + 20$ .

On distinguishing and distinguishing chromatic numbers of hypercubes

Werner Klöckl (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism. The restriction to proper labelings leads to the definition of the distinguishing chromatic number $χ_{D} (G)$ of G. Extending these concepts to infinite graphs we prove that $D (Q_{ℵ} ₀) = 2$ and $χ_{D} (Q_{ℵ} ₀) = 3$ , where $Q_{ℵ} ₀$ denotes the hypercube of countable dimension. We also show that $χ_{D} (Q ₄) = 4$ , thereby completing the investigation of finite hypercubes with respect to $χ_{D}$ . Our...

$C^{*}$ -points vs $P$ -points and $P^{♭}$ -points

Jorge Martinez, Warren Wm. McGovern (2022)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In a Tychonoff space $X$ , the point $p \in X$ is called a $C^{*}$ -point if every real-valued continuous function on $C ∖ {p}$ can be extended continuously to $p$ . Every point in an extremally disconnected space is a $C^{*}$ -point. A classic example is the space $𝐖^{*} = ω_{1} + 1$ consisting of the countable ordinals together with $ω_{1}$ . The point $ω_{1}$ is known to be a $C^{*}$ -point as well as a $P$ -point. We supply a characterization of $C^{*}$ -points in totally ordered spaces. The remainder of our time is aimed at studying when a point in a product space...

On the solvability of systems of linear equations over the ring $ℤ$ of integers

Horst Herrlich, Eleftherios Tachtsis (2017)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We investigate the question whether a system ${(E_{i})}_{i \in I}$ of homogeneous linear equations over $ℤ$ is non-trivially solvable in $ℤ$ provided that each subsystem ${(E_{j})}_{j \in J}$ with $| J | \leq c$ is non-trivially solvable in $ℤ$ where $c$ is a fixed cardinal number such that $c < | I |$ . Among other results, we establish the following. (a) The answer is ‘No’ in the finite case (i.e., $I$ being finite). (b) The answer is ‘No’ in the denumerable case (i.e., $| I | = ℵ_{0}$ and $c$ a natural number). (c) The answer in case that $I$ is uncountable and $c \leq ℵ_{0}$ is ‘No...

Note on improper coloring of $1$ -planar graphs

Yanan Chu, Lei Sun, Jun Yue (2019)

Czechoslovak Mathematical Journal

Similarity:

A graph $G = (V, E)$ is called improperly $(d_{1}, \dots, d_{k})$ -colorable if the vertex set $V$ can be partitioned into subsets $V_{1}, \dots, V_{k}$ such that the graph $G [V_{i}]$ induced by the vertices of $V_{i}$ has maximum degree at most $d_{i}$ for all $1 \leq i \leq k$ . In this paper, we mainly study the improper coloring of $1$ -planar graphs and show that $1$ -planar graphs with girth at least $7$ are $(2, 0, 0, 0)$ -colorable.

Complete pairs of coanalytic sets

Jean Saint Raymond (2007)

Fundamenta Mathematicae

Similarity:

Let X be a Polish space, and let C₀ and C₁ be disjoint coanalytic subsets of X. The pair (C₀,C₁) is said to be complete if for every pair (D₀,D₁) of disjoint coanalytic subsets of $ω^{ω}$ there exists a continuous function $f : ω^{ω} \to X$ such that $f^{- 1} (C ₀) = D ₀$ and $f^{- 1} (C ₁) = D ₁$ . We give several explicit examples of complete pairs of coanalytic sets.

Does the endomorphism poset $P^{P}$ determine whether a finite poset $P$ is connected? An issue Duffus raised in 1978

Jonathan David Farley (2023)

Mathematica Bohemica

Similarity:

Duffus wrote in his 1978 Ph.D. thesis, “It is not obvious that $P$ is connected and $P^{P} ≅ Q^{Q}$ imply that $Q$ is connected”, where $P$ and $Q$ are finite nonempty posets. We show that, indeed, under these hypotheses $Q$ is connected and $P ≅ Q$ .

Maximum bipartite subgraphs in $H$ -free graphs

Jing Lin (2022)

Czechoslovak Mathematical Journal

Similarity:

Given a graph $G$ , let $f (G)$ denote the maximum number of edges in a bipartite subgraph of $G$ . Given a fixed graph $H$ and a positive integer $m$ , let $f (m, H)$ denote the minimum possible cardinality of $f (G)$ , as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$ . In this paper we prove that $f (m, θ_{k, s}) \geq \frac{1}{2} m + Ω (m^{(2 k + 1) / (2 k + 2)})$ , which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write $K_{k}^{'}$ and $K_{t, s}^{'}$ for the subdivisions of $K_{k}$ and $K_{t, s}$ . We show that $f (m, K_{k}^{'}) \geq \frac{1}{2} m + Ω (m^{(5 k - 8) / (6 k - 10)})$ and $f (m, K_{t, s}^{'}) \geq \frac{1}{2} m + Ω (m^{(5 t - 1) / (6 t - 2)})$ , improving a result of Q. Zeng, J. Hou. We also give lower bounds on...

Generalized 3-edge-connectivity of Cartesian product graphs

Yuefang Sun (2015)

Czechoslovak Mathematical Journal

Similarity:

The generalized $k$ -connectivity $κ_{k} (G)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$ -edge-connectivity which is defined as $λ_{k} (G) = min {λ (S) : S \subseteq V (G)$ and $| S | = k}$ , where $λ (S)$ denotes the maximum number $ℓ$ of pairwise edge-disjoint trees $T_{1}, T_{2}, ..., T_{ℓ}$ in $G$ such that $S \subseteq V (T_{i})$ for $1 \leq i \leq ℓ$ . In this paper we prove that for any two connected graphs $G$ and $H$ we have $λ_{3} (G □ H) \geq λ_{3} (G) + λ_{3} (H)$ , where $G □ H$ is the Cartesian product of $G$ and $H$ . Moreover, the bound is sharp. We also...