Canonical Antichains of Unit Interval and Bipartite Permutation Graphs

We study unit interval graphs and bipartite permutation graphs partially ordered by the induced subgraph relation. It is known that neither of these classes is well-quasi-ordered, since each of them contains an infinite antichain. We show that in both cases the antichains are canonical in the sense that any subclass of unit interval or bipartite permutation graphs containing only finitely many graphs from the respective antichain is well-quasi-ordered.     

On a generalization of the Hadwiger–Nelson problem

For a field F and a quadratic form Q defined on an n-dimensional vector space V over F, let QG _Q , called the quadratic graph associated to Q, be the graph with the vertex set V where vertices u,w ∈ V form an edge if and only if Q(v ? w) = 1. Quadratic graphs can be viewed as natural generalizations of the unit-distance graph featuring in the famous Hadwiger–Nelson problem. In the present paper, we will prove that for a local field F of characteristic zero, the Borel chromatic number of QG _Q is infinite if and only if Q represents zero non-trivially over F. The proof employs a recent spectral bound for the Borel chromatic number of Cayley graphs, combined with an analysis of certain oscillatory integrals over local fields. As an application, we will also answer a variant of question 525 proposed in the 22nd British Combinatorics Conference 2009 [6].     

Lower estimates of circuit complexity in the basis of antichain functions

The antichain function is a characteristic function of an antichain in the Boolean cube. The set of antichain functions is an infinite complete basis. We study the computational complexity of Boolean functions over an antichain functional basis. In this paper we prove an asymptotic lower bound of order $\sqrt n $ for the computational complexity of a linear function, a majority function, and almost all Boolean functions of n variables.     

Irreducible <Emphasis Type="Italic">A</Emphasis><Stack><Subscript>1</Subscript><Superscript>(1)</Superscript></Stack>-modules from modules over two-dimensional non-abelian Lie algebra

For any module V over the two-dimensional non-abelian Lie algebra b and scalar α ∈ C, we define a class of weight modules F ^α (V) with zero central charge over the affine Lie algebra A ₁ ⁽¹⁾ . These weight modules have infinitedimensional weight spaces if and only if V is infinite dimensional. In this paper, we will determine necessary and sufficient conditions for these modules F ^α(V) to be irreducible. In this way, we obtain a lot of irreducible weight A ₁ ⁽¹⁾ -modules with infinite-dimensional weight spaces.     

Cofinite subsets of asymptotic bases for the positive integers

Let A be an infinite set of integers containing at most finitely many negative terms. Let hA denote the set of all integers n such that n is a sum of h elements of A. Let F be a finite subset of A.Theorem. If hA contains an infinite arithmetic progression with difference d, and if $\text{gcd}\text{{a?a′¦a,a′∈AF} = d}$, then there exists q such that q(A\F) contains an infinite arithmetic progression. In particular, if A is an asymptotic basis, then A\F is an asymptotic basis if and only if gcd{a?a′|a,a′∈A\F} = 1.Theorem. If A is an asymptotic basis of order h, and if F?A, card(F) = k, and A\F is an asymptotic basis, then the exact order of A\F is O(h^k+1).     

Strengthened fixed point property and products in ordered sets

Strengthened fixed point property for ordered sets is formulated. It is weaker than the strong fixed point property due to Duffus and Sauer and stronger than the product property meaning that A × Y has the fixed point property whenever A has the former and Y has the latter. In particular, doubly chain complete ordered sets with no infinite antichain have the strengthened fixed point property whenever they have the fixed point property, which yields a transparent proof of the well-known theorem saying that doubly chain complete ordered sets with no infinite antichain have the product property whenever they have the fixed point property. The new proof does not require the axiom of choice. Presented at the Summer School on General Algebra and Ordered Sets, Malá Morávka, 4–10 September 2005.     

Smarandache n-Structure on CI-Algebras

In this paper, the notions of CI-algebras, Smarandache CI-algebra, Q-Smarandache filters and Q-Smarandache ideals are introduced. We show that a nonempty subset F of a CI-algebra X is a Q-Smarandache filter if and only if ${A(x,y) \subseteq F}$ , which A(x, y) is a Q-Smarandache upper set. Finally, we introduced the concepts of Smarandache BE-algebra, Smarandache dual BCK-algebra and Smarandache n-structure on CI-algebra.     

On countable unions of nonmeager sets in hereditarily Lindelöf spaces

It is well known that any Vitali set on the real line ? does not possess the Baire property. The same is valid for finite unions of Vitali sets. What can be said about infinite unions of Vitali sets? Let S be a Vitali set, S _r be the image of S under the translation of ? by a rational number r and F = {S _r : r is rational}. We prove that for each non-empty proper subfamily F′ of F the union ∪F′ does not possess the Baire property. We say that a subset A of ? possesses Vitali property if there exist a non-empty open set O and a meager set M such that A ? O \ M. Then we characterize those non-empty proper subfamilies F′ of F which unions ∪F′ possess the Vitali property.     

Irreducible posets with large height exist

The dimension of a poset (X, P) is the minimum number of linear extensions of P whose intersection is P. A poset is irreducible if the removal of any point lowers the dimension. If A is an antichain in X and X ? A ≠ Ø, then dim X ≤ 2 width ((X ? A) + 1. We construct examples to show that this inequality is best possible; these examples prove the existence of irreducible posets of arbitrarily large height. Although many infinite families of irreducible posets are known, no explicity constructed irreducible poset of height larger than four has been found.     

Who's who in fuzzy sets

In this paper some fuzzy relation equations provided with one solution on a finite set are characterized: we consider fuzzy relation equations H ° Q = T with Q?F(XxY) and card X ? cardY. After recalling the definition of equivalent fuzzy relation equations, we introduce the definition of ρ-equivalent ones, which allows us to constrain our research without loss of generality to fuzzy relation equations where T does not have zero-components.     

Cellularity of first countable spaces

In this paper, we find subspaces of the Pixley-Roy space on the irrationals which are

• 1.(1) a first countable ccc space which does not have a σ-linked base,
• 2.(2) for each n>1, a first countable space which has a σ-n-linked base but which does not have a (σ−n+1)-linked base and
• 3.(3) a first countable space which has, for each n>1, a σ-n-linked base but which does not have a σ-centered base.

It is consistent with ¬CH that (1) and (2) have cardinality ℵ₁. (3) is constructed from a graph G on the continuum c which is not the union of countably many complete subgraphs but has no uncountable pairwise incompatible family of finite complete subgraphs (complete subgraphs A and B are compatible if there is a complete subgraph C which contains A and B).     

A Ramsey-type theorem for traceable graphs

A graph G is traceable if there is a path passing through all the vertices of G. It is proved that every infinite traceable graph either contains arbitrarily large finite chordless paths, or contains a subgraph isomorphic to graph A, illustrated in the text. A corollary is that every finitely generated infinite lattice of length 3 contains arbitrarily large finite fences. It is also proved that every infinite traceable graph containing no chordless four-point path contains a subgraph isomorphic to K_ω,ω. The versions of these results for finite graphs are discussed.     

Frobenius morphisms and stable module categories of repetitive algebras

Let k be the algebraic closure of a finite field F_q and A be a finite dimensional k-algebra with a Frobenius morphism F.In the present paper we establish a relation between the stable module category of the repetitive algebra  of A and that of the repetitive algebra of the fixed-point algebra A~F.As an application,it is shown that the derived category of A~F is equivalent to the subcategory of F-stable objects in the derived category of A when A has a finite global dimension.     

Connection-graph and iteration-graph of monotone boolean functions

In this paper, we establish some relationships between the circuits of the connection-graph G_C(F), and the circuits of theiteration-graph G₁(F), of a monotone boolean function F. We first show that if G₁(F) contains an element circuit of length multiple of p? {2,3}, then G_C(F) contains an elementary circuit of length multiple of p; then we prove that if G_C(F) is a subgraph of a caterpillar, then G₁(F) is a subgraph of a tree; at last we exhibit an infinite family of monotone boolean functions {F_n; n = 2 × 5^q, q ≥ 1} such that any G_C(F_n) is a subgraph of a tree, and G₁(F_n) contains a circuit of length 2^q+1, i.e., of the order $\text{n}{}^{\mathrm{<mtext>log</mtext><mtext>2</mtext><mtext>log5</mtext>}}$.     

Nowhere-Zero 5-Flows and Even (1,2)-Factors

A graph G = (V, E) admits a nowhere-zero k-flow if there exists an orientation H = (V, A) of G and an integer flow ${\varphi:A \to \mathbb{Z}}$ such that for all ${a \in A, 0 < |\varphi(a)| < k}$ . Tutte conjectured that every bridgeless graphs admits a nowhere-zero 5-flow. A (1,2)-factor of G is a set ${F \subseteq E}$ such that the degree of any vertex v in the subgraph induced by F is 1 or 2. Let us call an edge of G, F-balanced if either it belongs to F or both its ends have the same degree in F. Call a cycle of G F-even if it has an even number of F-balanced edges. A (1,2)-factor F of G is even if each cycle of G is F-even. The main result of the paper is that a cubic graph G admits a nowhere-zero 5-flow if and only if G has an even (1,2)-factor.     

Braidings on the Category of Bimodules,Azumaya Algebras and Epimorphisms of Rings

Let A be an algebra over a commutative ring k. We prove that braidings on the category of A-bimodules are in bijective correspondence to canonical R-matrices, these are elements in A???A???A satisfying certain axioms. We show that all braidings are symmetries. If A is commutative, then there exists a braiding on ${}_A\mathcal{M}_A$ if and only if k→A is an epimorphism in the category of rings, and then the corresponding R-matrix is trivial. If the invariants functor $G = (-)^A:\ {}_A\mathcal{M}_A\to \mathcal{M}_k$ is separable, then A admits a canonical R-matrix; in particular, any Azumaya algebra admits a canonical R-matrix. Working over a field, we find a remarkable new characterization of central simple algebras: these are precisely the finite dimensional algebras that admit a canonical R-matrix. Canonical R-matrices give rise to a new class of examples of simultaneous solutions for the quantum Yang–Baxter equation and the braid equation.     

Palindromic widths of nilpotent and wreath products

We prove that the nilpotent product of a set of groups A ₁,…,A _s has finite palindromic width if and only if the palindromic widths of A _i ,i=1,…,s,are finite. We give a new proof that the commutator width of F _n ?K is infinite, where F _n is a free group of rank n≥2 and K is a finite group. This result, combining with a result of Fink [9] gives examples of groups with infinite commutator width but finite palindromic width with respect to some generating set.     

Some infinite families of Ramsey ($${\varvec{P}}_\mathbf{3},{\varvec{P}}_{{\varvec{n}}}$$)-minimal trees

For any given two graphs G and H, the notation \(F\rightarrow \) (G, H) means that for any red–blue coloring of all the edges of F will create either a red subgraph isomorphic to G or a blue subgraph isomorphic to H. A graph F is a Ramsey (G, H)-minimal graph if \(F\rightarrow \) (G, H) but \(F-e\nrightarrow (G,H)\), for every \(e \in E(F)\). The class of all Ramsey (G, H)-minimal graphs is denoted by \(\mathcal {R}(G,H)\). In this paper, we construct some infinite families of trees belonging to \(\mathcal {R}(P_3,P_n)\), for \(n=8\) and 9. In particular, we give an algorithm to obtain an infinite family of trees belonging to \(\mathcal {R}(P_3,P_n)\), for \(n\ge 10\).     

On Infinite–finite Duality Pairs of Directed Graphs

The $({\mathcal{A}},{\mathcal{D}})$ duality pairs play a crucial role in the theory of general relational structures and in Constraint Satisfaction Problems. The case where both sides are finite is fully characterized. The case where both sides are infinite seems to be very complex. It is also known that no finite–infinite duality pair is possible if we make the additional restriction that both classes are antichains. In this paper (which is the first one of a series) we start the detailed study of the infinite–finite case. Here we concentrate on directed graphs. We prove some elementary properties of the infinite–finite duality pairs, including lower and upper bounds on the size of ${\mathcal{D}}$ , and show that the elements of ${\mathcal{A}}$ must be equivalent to forests if ${\mathcal{A}}$ is an antichain. Then we construct instructive examples, where the elements of ${\mathcal{A}}$ are paths or trees. Note that the existence of infinite–finite antichain dualities was not previously known.     

Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes

Daligault, Rao and Thomassé asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this is not true for classes defined by infinitely many forbidden induced subgraphs. However, in the case of finitely many forbidden induced subgraphs the question remains open and we conjecture that in this case the answer is positive. The conjecture is known to hold for classes of graphs defined by a single forbidden induced subgraph H, as such graphs are well-quasi-ordered and are of bounded clique-width if and only if H is an induced subgraph of P ₄. For bigenic classes of graphs, i.e. ones defined by two forbidden induced subgraphs, there are several open cases in both classifications. In the present paper we obtain a number of new results on well-quasi-orderability of bigenic classes, each of which supports the conjecture.