Notes on combinatorial set theory

We shall prove some unconnected theorems: (1) (G.C.H.) \omega _{\alpha + 1} \to \left( {\omega _\alpha + \xi } \right)_2^2 when ℵ_α is regular, │ξ│⁺<ωα. (2) There is a Jonsson algebra in ℵ_α+n, and \aleph _{a + n} \not \to \left[ {\aleph _{a + n} } \right]_{\aleph _{a + n} }^{n + 1} if 2^{\aleph _{ - - } } = \aleph _{a + n} \cdot (3) If λ>ℵ₀ is a strong limit cardinal, then among the graphs with ≦λ vertices each of valence <λ there is a universal one. (4)(G.C.H.) If f is a set mapping on \omega _{a + 1} (ℵ_α regular) │f(x)∩f(y│<ℵ_α, then there is a free subset of order-type ζ for every ζ<ω_α+1.     

A combinatorial approach for Keller's conjecture

The statement, that in a tiling by translates of ann-dimensional cube there are two cubes having common (n-1)-dimensional faces, is known as Keller's conjecture. We shall prove that there is a counterexample for this conjecture if and only if the following graphs _n has a 2 ⁿ size clique. The 4 ⁿ vertices of _n aren-tuples of integers 0, 1, 2, and 3. A pair of thesen-tuples are adjacent if there is a position at which the difference of the corresponding components is 2 modulo 4 and if there is a further position at which the corresponding components are different. We will give the size of the maximal cliques of _n forn5.     

A combinatorial constraint satisfaction problem dichotomy classification conjecture

We further generalise a construction–the fibre construction–that was developed in an earlier paper of the first two authors. The extension in this paper gives a polynomial-time reduction of for any relational system H to for any relational system P that meets a certain technical partition condition, that of being K₃-partitionable.Moreover, we define an equivalent condition on P, that of being block projective, and using this show that our construction proves NP-completeness for exactly those CSPs that are conjectured to be NP-complete by the CSP dichotomy classification conjecture made by Bulatov, Jeavons and Krohkin, and by Larose and Zádori. We thus provide two new combinatorial versions of the dichotomy classification conjecture.As with our previous version of the fibre construction, we are able to address restricted versions of the dichotomy conjecture. In particular, we reduce the Feder–Hell–Huang conjecture to the dichotomy classification conjecture, and we prove the Kostochka–Nešetřil–Smolíková conjecture. Although these results were proved independently by Jonsson et al. and Kun respectively, we give different, shorter, proofs.     

A combinatorial proof of Dyson's conjecture

Dyson's conjecture, already proved by Gunson, Wilson and Good, is given a direct combinatorial proof.     

A counterexample to the dominating set conjecture

The metric polytope met _n is the polyhedron associated with all semimetrics on n nodes and defined by the triangle inequalities x _ij − x _ik − x _jk ≤ 0 and x _ij + x _ik + x _jk ≤ 2 for all triples i, j, k of {1,..., n}. In 1992 Monique Laurent and Svatopluk Poljak conjectured that every fractional vertex of the metric polytope is adjacent to some integral vertex. The conjecture holds for n ≤ 8 and, in particular, for the 1,550,825,600 vertices of met₈. While the overwhelming majority of the known vertices of met₉ satisfy the conjecture, we exhibit a fractional vertex not adjacent to any integral vertex.     

A theorem in combinatorial matrix theory

Let Z be a matrix of order n, and suppose that the elements of Z consist of only two elements x and y, which are elements of a field F. We call Z an (x,y)-matrix over F. In this paper we study the matrix equation ZEZ^T = D+λJ, where Z is a nonsingular (x,y)-matrix over F, Z^T is the transpose of Z, D and E are nonsingular diagonal matrices, J is the matrix of 1's and λ is an element of F. Our main theorem shows that the column sums of Z are severely restricted. This result generalizes a number of earlier investigations that deal with symmetric block designs and related configurations. The problems that emerge are of interest from both a combinatorial and a matrix theoretic point of view.     

The dual spectral set conjecture

Suppose that where are real numbers such that and The union is not assumed to be disjoint. It is shown that the translates , , tile the real line for some bounded measurable set if and only if the exponentials , , form an orthogonal basis for some bounded measurable set

     

Normalized difference set tiling conjecture

A difference set tiling in a group G is a collection of its difference sets that partition . It can exist in an abelian as well as in a nonabelian group. A tiling is normalized if a product of elements in each difference set equals 1. All known cases in abelian groups are normalized. Ćustić, Krčadinac, and Zhou made a conjecture that this is necessary. We will call it a normalized tiling conjecture (NTC). Using character theory, we prove that NTC is true for where v is odd. Also, if difference set has a multiplier, we prove that NTC is also true.     

A combinatorial theory of minimal social situations

A minimal social situation is a game‐like situation in which there are two actors, each of them has two possible actions, and both evaluate the outcomes of their joint actions in terms of two categories (say, ‘success’ and ‘failure'). By fixing actors and actions and varying ‘payoffs’ the set of 256 ‘configurations’ is obtained. This set decomposes into 43 ‘structural forms’, or equivalence classes with respect to the relation of isomorphism defined on it. This main theorem and other results concerning related configurations (minimal decision situations) are derived in this paper by means of certain tools of group theory. Some extensions to larger structures are proved in the Appendix. In the introductory section after a brief explanation of the meaning given to the terms ‘structure’ and ‘isomorphism’ in mathematics (Bourbaki) it is shown how these terms can be used to formalize the concept of ‘social form’.     

A lattice-valued set theory

A lattice-valued set theory is formulated by introducing the logical implication which represents the order relation on the lattice. Received: 27 September 1996 / Revised version: 14 July 1997     

The combinatorial rigidity conjecture is false for cubic polynomials

We show that there exist two cubic polynomials with connected Julia sets which are combinatorially equivalent but not topologically conjugate on their Julia sets. This disproves a conjecture by McMullen from 1995.

     

A restriction on the combinatorial structure of counterexamples to the Jacobian conjecture at infinity

A constraint on the combinatorial structure of a meromorphic immersion of a (+1)-pair (v, l) in the space ?² with one dicritical component is found.     

A unified treatment of fuzzy set theory and Boolean-valued set theory—Fuzzy set structures and normal fuzzy set structures

This is Part I of a two-part paper; the purpose of this two-part paper is (a) to develop new concepts and techniques in the theory of infinite-dimensional programming, and (b) to obtain fruitful applications in continuous time programming. Part I deals with the development of continuous time analogues to those concepts which are the cornerstones of finite-dimensional programming theory. Specifically, a constraint qualification analogous to that found in finite-dimensional programming and a continuous time version of Farkas' theorem are developed. The latter result, stated in terms of convex and polar cones, is then employed in conjunction with the newly-developed constraint qualification to establish necessary conditions and a duality theory for a class of nonlinear continuous time programming problems. This approach to duality permits the imposition of assumptions that are less stringent than those needed for duality in previous formulations of the nonlinear problem.     

PIE-sums: A combinatorial tool for partition theory

PIE-sums are introduced. The method of inclusion-exclusion is applied to a wide range of partition identities which are herein proved for the first time by methods other than generating functions. A general structure is given to these varied identities, and several new examples are presented. The connection between partition identities and Möbius function identities is examined, and the foundations are given for developing this technique.     

Matching theory and Barnette's conjecture

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14]. These allow us to check whether a graph we generated is a brace.     

Embedding processes in combinatorial game theory

Berlekamp asked the question “What is the habitat of ∗2?” (See Guy, 1996 [6].) It is possible to generalize the question and ask “For a game G, what is the largest n such that ∗n is a position of G?” This leads to the concept of the nim dimension. In Santos and Silva (2008) [8] a fractal process was proposed for analyzing the previous questions. For the same purpose, in Santos and Silva (2008) [9], an algebraic process was proposed. In this paper we implement a third idea related to embedding processes. With Alan Parr’s traffic lights, we exemplify the idea of estimating the “difficulty” of the game and proving that its nim dimension is infinite.