Splitting stationary sets from weak forms of Choice

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)     

Gδ‐pieces of canonical partitions of G‐spaces

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)     

Odd‐angulated graphs and cancelling factors in box products

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□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈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     

The Vector Space Kinna‐Wagner Principle is Equivalent to the Axiom of Choice

We show that the axiom of choice AC is equivalent to the Vector Space Kinna‐Wagner Principle, i.e., the assertion: “For every family 𝒱= {V_i : i ∈ k} of non trivial vector spaces there is a family ℱ = {F_i : i ∈ k} such that for each i ∈ k, F_i is a non empty independent subset of V_i”. 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.     

New large sets of t‐designs

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·3^m ? 2, 16·3^m ? 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     

Some results on the existence of large sets of t‐designs

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     

Difference systems of sets based on cosets partitions

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.     

Low sets without subsets of higher many‐one degree

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 low₁ m‐introimmune set in Π⁰₁ and the existence of a low₁ bi‐m‐introimmune set.     

Odd 4‐edge‐colorability of graphs

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.     

On κ‐hereditary Sets and Consequences of the Axiom of Choice

We will prove that some so‐called union theorems (see [2]) are equivalent in ZF⁰ 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 κ = ω₁ (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.     

Independent sets and 2‐factors in edge‐chromatic‐critical graphs

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     

Independent sets of maximal size in tensor powers of vertex‐transitive graphs

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     

Chain enumeration of k-divisible noncrossing partitions of classical types

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.     

New large sets of t‐designs with prescribed groups of automorphisms

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     

Complexity of clique‐coloring odd‐hole‐free graphs

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 k₀ such that they are all k₀ ‐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 Σ₂ 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     

Simple characterization of functionally complete one‐element sets of propositional connectives

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)     

Clique‐coloring some classes of odd‐hole‐free graphs

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 K₄‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006     

On some structural sets and a quaternionic ‐hyperholomorphic function theory

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.