共查询到20条相似文献,搜索用时 10 毫秒
1.
Working in the context of restricted forms of the Axiom of Choice, we consider the problem of splitting the ordinals below λ of cofinality θ into λ many stationary sets, where θ < λ are regular cardinals. This is a continuation of [4] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
2.
3.
Barbara Majcher‐Iwanow 《Mathematical Logic Quarterly》2005,51(5):450-461
Generalizing model companions from model theory we define companions of pieces of canonical partitions of Polish G‐spaces. This unifies several constructions from logic. The central problem of the paper is the existence of companions which form a G‐orbit which is a Gδ‐set. We describe companions of some typical G‐spaces. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
4.
Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{th} for all h∈V(H) where th∈V(T) depends on h; or ? maps G□{h} to {sh}□ T for all h∈V(H) where sh∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008 相似文献
5.
Kyriakos Keremedis 《Mathematical Logic Quarterly》2001,47(2):205-210
We show that the axiom of choice AC is equivalent to the Vector Space Kinna‐Wagner Principle, i.e., the assertion: “For every family 𝒱= {Vi : i ∈ k} of non trivial vector spaces there is a family ℱ = {Fi : i ∈ k} such that for each i ∈ k, Fi is a non empty independent subset of Vi”. We also show that the statement “every vector space over ℚ has a basis” implies that every infinite well ordered set of pairs has an infinite subset with a choice set, a fact which is known not to be a consequence of the axiom of multiple choice MC. 相似文献
6.
7.
Abstact: We introduce generalizations of earlier direct methods for constructing large sets of t‐designs. These are based on assembling systematically orbits of t‐homogeneous permutation groups in their induced actions on k‐subsets. By means of these techniques and the known recursive methods we construct an extensive number of new large sets, including new infinite families. In particular, a new series of LS[3](2(2 + m), 8·3m ? 2, 16·3m ? 3) is obtained. This also provides the smallest known ν for a t‐(ν, k, λ) design when t ≥ 16. We present our results compactly for ν ≤ 61, in tables derived from Pascal's triangle modulo appropriate primes. © 2000 John Wiley & Sons, Inc. J Combin Designs 9: 40–59, 2001 相似文献
8.
A set of trivial necessary conditions for the existence of a large set of t‐designs, LS[N](t,k,ν), is for i = 0,…,t. There are two conjectures due to Hartman and Khosrovshahi which state that the trivial necessary conditions are sufficient in the cases N = 2 and 3, respectively. Ajoodani‐Namini has established the truth of Hartman's conjecture for t = 2. Apart from this celebrated result, we know the correctness of the conjectures for a few small values of k, when N = 2 and t ≤ 6, and also when N = 3 and t ≤ 4. In this article, we show that similar results can be obtained for infinitely many values of k. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 144–151, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10027 相似文献
9.
Difference systems of sets (DSS) are combinatorial configurations that arise in connection with code synchronization. This paper proposes a new method to construct DSSs, which uses known DSSs to partition some of the cosets of Zv relative to subgroup of order k, where v = km is a composite number. As applications, we obtain some new optimal DSSs. 相似文献
10.
Patrizio Cintioli 《Mathematical Logic Quarterly》2011,57(5):517-523
Given a reducibility ?r, we say that an infinite set A is r‐introimmune if A is not r‐reducible to any of its subsets B with |A\B| = ∞. We consider the many‐one reducibility ?m and we prove the existence of a low1 m‐introimmune set in Π01 and the existence of a low1 bi‐m‐introimmune set. 相似文献
11.
《Journal of Graph Theory》2018,87(4):460-474
An odd k‐edge‐coloring of a graph G is a (not necessarily proper) edge‐coloring with at most k colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4‐edge‐colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5‐edge‐colorable, with one particular exception that is odd 6‐edge‐colorable. In this article, we prove that connected loopless graphs are odd 4‐edge‐colorable, with two particular exceptions that are respectively odd 5‐ and odd 6‐edge‐colorable. Moreover, a color class can be reduced to a size at most 2. 相似文献
12.
Karl‐Heinz Diener 《Mathematical Logic Quarterly》2000,46(4):563-568
We will prove that some so‐called union theorems (see [2]) are equivalent in ZF0 to statements about the transitive closure of relations. The special case of “bounded” union theorems dealing with κ‐hereditary sets yields equivalents to statements about the transitive closure of κ‐narrow relations. The instance κ = ω1 (i. e., hereditarily countable sets) yields an equivalent to Howard‐Rubin's Form 172 (the transitive closure Tc(x) of every hereditarily countable set x is countable). In particular, the countable union theorem (Howard‐Rubin's Form 31) and, a fortiori, the axiom of countable choice imply Form 172. 相似文献
13.
In 1968, Vizing made the following two conjectures for graphs which are critical with respect to the chromatic index: (1) every critical graph has a 2‐factor, and (2) every independent vertex set in a critical graph contains at most half of the vertices. We prove both conjectures for critical graphs with many edges, and determine upper bounds for the size of independent vertex sets in those graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 113–118, 2004 相似文献
14.
Let G be a connected, nonbipartite vertex‐transitive graph. We prove that if the only independent sets of maximal cardinality in the tensor product G × G are the preimages of the independent sets of maximal cardinality in G under projections, then the same holds for all finite tensor powers of G, thus providing an affirmative answer to a question raised by Larose and Tardif (J Graph Theory 40(3) (2002), 162–171). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 295‐301, 2009 相似文献
15.
Jang Soo Kim 《Journal of Combinatorial Theory, Series A》2011,118(3):879-898
We give combinatorial proofs of the formulas for the number of multichains in the k-divisible noncrossing partitions of classical types with certain conditions on the rank and the block size due to Krattenthaler and Müller. We also prove Armstrong's conjecture on the zeta polynomial of the poset of k-divisible noncrossing partitions of type A invariant under a 180° rotation in the cyclic representation. 相似文献
16.
In this article, we investigate the existence of large sets of 3‐designs of prime sizes with prescribed groups of automorphisms PSL(2,q) and PGL(2,q) for q < 60. We also construct some new interesting large sets by the use of the computer program DISCRETA. The results obtained through these direct methods along with known recursive constructions are combined to prove more extensive theorems on the existence of large sets. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 210–220, 2007 相似文献
17.
David Défossez 《Journal of Graph Theory》2009,62(2):139-156
In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k0 such that they are all k0 ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ2 P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009 相似文献
18.
A set of propositional connectives is said to be functionally complete if all propositional formulae can be expressed using only connectives from that set. In this paper we give sufficient and necessary conditions for a one‐element set of propositional connectives to be functionally complete. These conditions provide a simple and elegant characterization of functionally complete one‐element sets of propositional connectives (of arbitrary arity). (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
19.
David Dfossez 《Journal of Graph Theory》2006,53(3):233-249
We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K4‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006 相似文献
20.
Ricardo Abreu Blaya Juan Bory Reyes Alí Guzmán Adán Uwe Kaehler 《Mathematische Nachrichten》2015,288(13):1451-1475
Quaternionic analysis is regarded as a broadly accepted branch of classical analysis referring to many different types of extensions of the Cauchy‐Riemann equations to the quaternion skew field . It relies heavily on results on functions defined on domains in or with values in . This theory is centred around the concept of ψ‐hyperholomorphic functions related to a so‐called structural set ψ of or respectively. The main goal of this paper is to develop the nucleus of the ‐hyperholomorphic function theory, i.e., simultaneous null solutions of two Cauchy‐Riemann operators associated to a pair of structural sets of . Following a matrix approach, a generalized Borel‐Pompeiu formula and the corresponding Plemelj‐Sokhotzki formulae are established. 相似文献