Generating all subsets of a finite set with disjoint unions

If X is an n-element set, we call a family G⊂PX a k-generator for X if every x⊂X can be expressed as a union of at most k disjoint sets in G. Frein, Lévêque and Seb? conjectured that for n>2k, the smallest k-generators for X are obtained by taking a partition of X into classes of sizes as equal as possible, and taking the union of the power-sets of the classes. We prove this conjecture for all sufficiently large n when k=2, and for n a sufficiently large multiple of k when k?3.     

Structure and stability of triangle-free set systems

We define the notion of stability for a monotone property of set systems. This phenomenon encompasses some classical results in combinatorics, foremost among them the Erdos-Simonovits stability theorem. A triangle is a family of three sets such that , , are each nonempty, and . We prove the following new theorem about the stability of triangle-free set systems.

Fix . For every , there exist and such that the following holds for all : if and is a triangle-free family of -sets of containing at least members, then there exists an -set which contains fewer than members of .

This is one of the first stability theorems for a nontrivial problem in extremal set theory. Indeed, the corresponding extremal result, that for every triangle-free family of -sets of has size at most , was a longstanding conjecture of Erdos (open since 1971) that was only recently settled by Mubayi and Verstraëte (2005) for all .

     

The Unbalance of Set Systems

The unbalance of an intersecting family is defined as , where is the maximum degree of i.e. the maximum of over all vertices x. We show that the unbalance of a k-uniform intersecting family is at most when n ≥ 6k ³ and we determine all families achieving this bound.     

Clique number of Xor products of Kneser graphs

In this article we investigate a problem in graph theory, which has an equivalent reformulation in extremal set theory similar to the problems researched in “A general 2-part Erd?s-Ko-Rado theorem” by Gyula O.H. Katona, who proposed our problem as well. In the graph theoretic form we examine the clique number of the Xor product of two isomorphic $KG(N,k)$ Kneser graphs. Denote this number with $f(k,N)$. We give lower and upper bounds on $f(k,N)$, and we solve the problem up to a constant deviation depending only on k, and find the exact value for $f(2,N)$ if N is large enough. Also we compute that $f(k,k^2)$ is asymptotically equivalent to $k^2$.     

Fractional Hamiltonian systems with positive semi-definite matrix

We study the existence of solutions for the following fractional Hamiltonian systems $$ \left\{ \begin{array}{ll} - _tD^{\alpha}_{\infty}(_{-\infty}D^{\alpha}_{t}u(t))-\lambda L(t)u(t)+\nabla W(t,u(t))=0,\\[0.1cm] u\in H^{\alpha}(\mathbb{R},\mathbb{R}^n), \end{array} \right. ~~~~~~~~~~~~~~~~~(FHS)_\lambda $$ where $\alpha\in (1/2,1)$, $t\in \mathbb{R}$, $u\in \mathbb{R}^n$, $\lambda>0$ is a parameter, $L\in C(\mathbb{R},\mathbb{R}^{n^2})$ is a symmetric matrix, $W\in C^1(\mathbb{R} \times \mathbb{R}^n,\mathbb{R})$. Assuming that $L(t)$ is a positive semi-definite symmetric matrix, that is, $L(t)\equiv 0$ is allowed to occur in some finite interval $T$ of $\mathbb{R}$, $W(t,u)$ satisfies some superquadratic conditions weaker than Ambrosetti-Rabinowitz condition, we show that (FHS)$_\lambda$ has a solution which vanishes on $\mathbb{R}\setminus T$ as $\lambda \to \infty$, and converges to some $\tilde{u}\in H^{\alpha}(\R, \R^n)$. Here, $\tilde{u}\in E_{0}^{\alpha}$ is a solution of the Dirichlet BVP for fractional systems on the finite interval $T$. Our results are new and improve recent results in the literature even in the case $\alpha =1$.     

Further results on large set of disjoint pure Mendelsohn triple systems

In this article, we study a large set of disjoint pure Mendelsohn triple systems “with holes” (briefly LPHMTS), which is a generalization of large set of disjoint pure Mendelsohn triple systems (briefly LPMTS), and give some recursive constructions on LPHMTS. Using these constructions, we show that there exists LPMTS(2ⁿ + 2) for any n ≠ 2. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 274–290, 2000     

On set systems with a threshold property

For n,k and t such that 1<t<k<n, a set F of subsets of [n] has the (k,t)-threshold property if every k-subset of [n] contains at least t sets from F and every (k-1)-subset of [n] contains less than t sets from F. The minimal number of sets in a set system with this property is denoted by m(n,k,t). In this paper we determine m(n,4,3)exactly for n sufficiently large, and we show that m(n,k,2) is asymptotically equal to the generalized Turán number T_k-1(n,k,2).     

On large sets of disjoint Kirkman triple systems

In this paper, we introduce LR(u) designs and use these designs together with large sets of Kirkman triple systems (LKTS) and transitive KTS (TKTS) of order v to construct an LKTS(uv). Our main result is that there exists an LKTS(v) for v∈{3nm(2·13k+1)t;n?1,k?1,t=0,1,m∈{1,5,11,17,25,35,43}}.     

Fractional variational integrators for fractional variational problems

In this paper, the fractional variational integrators for a class of fractional variational problems are developed. The fractional discrete Euler-Lagrange equation is obtained. Based on the Grünwald-Letnikov method and Diethelm’s fractional backward differences, some fractional variational integrators are presented and the fractional variational errors are discussed. Some numerical examples are presented to illustrate these results.     

Maximum graphs with a unique minimum dominating set

We present a conjecture on the maximum number of edges of a graph that has a unique minimum dominating set. We verify our conjecture for some special cases and prove a weakened version of this conjecture in general.     

Incongruent restricted disjoint covering systems

We define an incongruent restricted disjoint covering system on [1,n] as a set of congruence classes such that each integer in the interval [1,n] belongs to exactly one class, and each class contains at least two members of the interval. In this paper we report some computational and structural results and present some open problems concerning such systems.     

Finding dominators via disjoint set union

The problem of finding dominators in a directed graph has many important applications, notably in global optimization of computer code. Although linear and near-linear-time algorithms exist, they use sophisticated data structures. We develop an algorithm for finding dominators that uses only a “static tree” disjoint set data structure in addition to simple lists and maps. The algorithm runs in near-linear or linear time, depending on the implementation of the disjoint set data structure. We give several versions of the algorithm, including one that computes loop nesting information (needed in many kinds of global code optimization) and that can be made self-certifying, so that the correctness of the computed dominators is very easy to verify.     

An improved recursive construction for disjoint Steiner quadruple systems

Let $D\left(n\right)$ be the number of pairwise disjoint Steiner quadruple systems (SQS) of order $n$. A simple counting argument shows that $D\left(n\right)\le n?3$ and a set of $n?3$ such systems is called a large set. No nontrivial large set was constructed yet, although it is known that they exist if  $n\equiv 2$ or $4\left(\mathrm{mod}6\right)$ is large enough. When $n\ge 7$ and $n\equiv 1$ or $5\left(\mathrm{mod}6\right)$, we present a recursive construction and prove a recursive formula on $D\left(4n\right)$, as follows: $$D\left(4n\right)\ge 2n+\min \left\{D\left(2n\right),2n?7\right\}.$$ The related construction has a few advantages over some of the previously known constructions for pairwise disjoint SQSs.     

Updating attribute reduction in incomplete decision systems with the variation of attribute set

In rough set theory, attribute reduction is a challenging problem in the applications in which data with numbers of attributes available. Moreover, due to dynamic characteristics of data collection in decision systems, attribute reduction will change dynamically as attribute set in decision systems varies over time. How to carry out updating attribute reduction by utilizing previous information is an important task that can help to improve the efficiency of knowledge discovery. In view of that attribute reduction algorithms in incomplete decision systems with the variation of attribute set have not yet been discussed so far. This paper focuses on positive region-based attribute reduction algorithm to solve the attribute reduction problem efficiently in the incomplete decision systems with dynamically varying attribute set. We first introduce an incremental manner to calculate the new positive region and tolerance classes. Consequently, based on the calculated positive region and tolerance classes, the corresponding attribute reduction algorithms on how to compute new attribute reduct are put forward respectively when an attribute set is added into and deleted from the incomplete decision systems. Finally, numerical experiments conducted on different data sets from UCI validate the effectiveness and efficiency of the proposed algorithms in incomplete decision systems with the variation of attribute set.     

The Extension Degree Conditions for Fractional Factor

In Gao’s previous work, the authors determined several degree conditions of a graph which admits fractional factor in particular settings. It was revealed that these degree conditions are tight if b = f(x) = g(x) = a for all vertices x in G. In this paper, we continue to discuss these degree conditions for admitting fractional factor in the setting that several vertices and edges are removed and there is a difference Δ between g(x) and f(x) for every vertex x in G. These obtained new degree conditions reformulate Gao’s previous conclusions, and show how Δ acts in the results. Furthermore,counterexamples are structured to reveal the sharpness of degree conditions in the setting f(x) =g(x) + Δ.