Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMaximal independent sets, variants of chain/antichain principle and cofinal subsets without AC
101
0
0.0
(
0
)
Authors
Amitayu Banerjee
Ask ChatGPT about the research
No Arabic abstract
In set theory without the Axiom of Choice (AC), we observe new relations of the following statements with weak choice principles. 1. Every locally finite connected graph has a maximal independent set. 2. Every locally countable connected graph has a maximal independent set. 3. If in a partially ordered set all antichains are finite and all chains have size $aleph_{alpha}$, then the set has size $aleph_{alpha}$ if $aleph_{alpha}$ is regular. 4. Every partially ordered set has a cofinal well-founded subset. 5. If $G=(V_{G},E_{G})$ is a connected locally finite chordal graph, then there is an ordering $<$ of $V_{G}$ such that ${w < v : {w,v} in E_{G}}$ is a clique for each $vin V_{G}$.
rate research
Read More
We study new relations of the following statements with weak choice principles in ZF and ZFA. 1. For every infinite set X, there exists a permutation of X without fixed points. 2. There is no Hausdorff space X such that every infinite subset of X contains an infinite compact subset. 3. If a field has an algebraic closure then it is unique up to isomorphism. 4. Variants of Chain/Antichain principle. 5. Any infinite locally finite connected graph has a spanning subgraph omitting some complete bipartite graphs. 6. Any infinite locally finite connected graph has a spanning m bush for any even integer m greater than 4. We also study the new status of different weak choice principles in the finite partition model (a type of permutation model) introduced by Bruce in 2016. Further, we prove that Van Douwens Choice Principle holds in two recently constructed known permutation models.
We have observations concerning the set theoretic strength of the following combinatorial statements without the axiom of choice. 1. If in a partially ordered set, all chains are finite and all antichains are countable, then the set is countable. 2. If in a partially ordered set, all chains are finite and all antichains have size $aleph_{alpha}$, then the set has size $aleph_{alpha}$ for any regular $aleph_{alpha}$. 3. CS (Every partially ordered set without a maximal element has two disjoint cofinal subsets). 4. CWF (Every partially ordered set has a cofinal well-founded subset). 5. DT (Dilworths decomposition theorem for infinite p.o.sets of finite width). 6. If the chromatic number of a graph $G_{1}$ is finite (say $k<omega$), and the chromatic number of another graph $G_{2}$ is infinite, then the chromatic number of $G_{1}times G_{2}$ is $k$. 7. For an infinite graph $G=(V_{G}, E_{G})$ and a finite graph $H=(V_{H}, E_{H})$, if every finite subgraph of $G$ has a homomorphism into $H$, then so has $G$. Further we study a few statements restricted to linearly-ordered structures without the axiom of choice.
In the 1970s, Lovasz built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings (FCT 1979). A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017). In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration. This paper is dedicated to the memory of Ker-I Ko.
Denote by $m(G)$ the largest size of a minimal generating set of a finite group $G$. We estimate $m(G)$ in terms of $sum_{pin pi(G)}d_p(G),$ where we are denoting by $d_p(G)$ the minimal number of generators of a Sylow $p$-subgroup of $G$ and by $pi(G)$ the set of prime numbers dividing the order of $G$.
Soare proved that the maximal sets form an orbit in $mathcal{E}$. We consider here $mathcal{D}$-maximal sets, generalizations of maximal sets introduced by Herrmann and Kummer. Some orbits of $mathcal{D}$-maximal sets are well understood, e.g., hemimaximal sets, but many are not. The goal of this paper is to define new invariants on computably enumerable sets and to use them to give a complete nontrivial classification of the $mathcal{D}$-maximal sets. Although these invariants help us to better understand the $mathcal{D}$-maximal sets, we use them to show that several classes of $mathcal{D}$-maximal sets break into infinitely many orbits.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
