A factorization of the complete
k
-hypergraph
(
V
,
V
{
k
}
)
of index
s
≥
2
, simply a (
k
,
s
) factorization on
V
, is a partition
{
F
1
,
F
2
,
…
,
F
s
}
of the edge set
V
{
k
}
into
s
disjoint ...subsets such that each
k
-hypergraph
(
V
,
F
i
)
, called a factor, is a spanning subhypergraph of
(
V
,
V
{
k
}
)
. A (
k
,
s
) factorization
{
F
1
,
F
2
,
…
,
F
s
}
on
V
is symmetric if there is a subgroup
G
of the symmetric group
Sym
(
V
)
such that
G
induces a transitive action on
{
F
1
,
F
2
,
…
,
F
s
}
and for each
i
, the stabilizer
G
F
i
is transitive on both
V
and
F
i
. A symmetric factorization on
V
is homogeneous if all its factors admit a common transitive subgroup of
Sym
(
V
)
. In this paper, we give a complete classification of symmetric (
k
,
s
) factorizations on a set of size
n
under the assumption that
s
≥
2
and
6
≤
2
k
≤
n
. It is proved that, up to isomorphism, there are two infinite families and 29 sporadic examples of symmetric factorizations which are not homogeneous. Among these symmetric factorizations, only eight of them are not 1-factorizations.
In their paper, Bounds on the number of edges in hypertrees, G.Y. Katona and P.G.N. Szabó introduced a new, natural definition of hypertrees in k- uniform hypergraphs and gave lower and upper bounds ...on the number of edges. They also defined edge-minimal, edge-maximal and l-hypertrees and proved an upper bound on the edge number of l-hypertrees.
In the present paper, we verify the asymptotic sharpness of the
upper bound on the number of edges of k-uniform hypertrees given in the above mentioned paper. We also make an improvement on the upper bound of the edge number of 2-hypertrees and give a general extension construction with its consequences.
We give lower and upper bounds on the maximal number of edges of k-uniform edge-minimal hypertrees and a lower bound on the number of edges of k-uniform edge-maximal hypertrees. In the former case, the sharp upper bound is conjectured to be asymptotically
.
A Note on Two-Dimensional Optical Orthogonal Codes SHEN, Lin-Zhi; GUANG, Xuan
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
2015, Volume:
E98.A, Issue:
10
Journal Article
Peer reviewed
Let v=p1m1p2m2…ptmt be the canonical prime factorization of v. In this paper, we give a construction of optimal ((s+1)×v,s+1,1) two-dimensional optical orthogonal codes with both at most one-pulse ...per wavelength and at most one-pulse per time slot, where s | gcd(p1-1,p2-1,...,pt-1). The method is much simpler than that in 1. Optimal (m×v,k,1) two-dimensional optical orthogonal codes are also constructed based on the Steiner system S2,k,m.
Test response compaction for integrated circuits (ICs) with scan-based design-for-testability (DFT) support in the presence of unknown logic values (Xs) is investigated from a combinatorial ...viewpoint. The theoretical foundations of X-codes, employed in an X-tolerant compaction technique called X-compact, are examined. Through the formulation of a combinatorial model of X-compact, novel design techniques are developed for X-codes to detect a specified maximum number of errors in the presence of a specified maximum number of unknown logic values, while requiring only small fan-out. The special class of X-codes that results leads to an avoidance problem for configurations in combinatorial designs. General design methods and nonconstructive existence theorems to estimate the compaction ratio of an optimal X-compactor are also derived.
A
Steiner triple system of order
v
(briefly STS
(
v
)
) consists of a
v
-element set
X and a collection of 3-element subsets of
X, called
blocks, such that every pair of distinct points in
X is ...contained in a unique block. A
large set of disjoint STS
(
v
)
(briefly LSTS
(
v
)
) is a partition of all 3-subsets (triples) of
X into
v
-
2
STS
(
v
)
. In 1983–1984, Lu Jiaxi first proved that there exists an LSTS
(
v
)
for any
v
≡
1
or
3
(
mod
6
)
with six possible exceptions and a definite exception
v
=
7
. In 1989, Teirlinck solved the existence of LSTS
(
v
)
for the remaining six orders. Since their proof is very complicated, it is much desired to find a simple proof. For this purpose, we give a new proof which is mainly based on the 3-wise balanced designs and partitionable candelabra systems.
An Erdős–Ko–Rado set in a block design is a set of pairwise intersecting blocks. In this article we study Erdős–Ko–Rado sets in
2
-
(
v
,
k
,
1
)
designs, Steiner systems. The Steiner triple systems ...and other special classes are treated separately. For
k
≥
4
, we prove that the largest Erdős–Ko–Rado sets cannot be larger than a point-pencil if
r
≥
k
2
-
3
k
+
3
4
k
+
2
and that the largest Erdős–Ko–Rado sets are point-pencils if also
r
≠
k
2
-
k
+
1
and
(
r
,
k
)
≠
(
8
,
4
)
. For unitals we also determine an upper bound on the size of the second-largest maximal Erdős–Ko–Rado sets.
We study $r$-differential posets, a class of combinatorial objects introduced in 1988 by the first author, which gathers together a number of remarkable combinatorial and algebraic properties, and ...generalizes important examples of ranked posets, including the Young lattice. We first provide a simple bijection relating differential posets to a certain class of hypergraphs, including all finite projective planes, which are shown to be naturally embedded in the initial ranks of some differential poset. As a byproduct, we prove the existence, if and only if $r\geq 6$, of $r$-differential posets nonisomorphic in any two consecutive ranks but having the same rank function. We also show that the Interval Property, conjectured by the second author and collaborators for several sequences of interest in combinatorics and combinatorial algebra, in general fails for differential posets. In the second part, we prove that the rank function $p_n$ of any arbitrary $r$-differential poset has nonpolynomial growth; namely, $p_n\gg n^ae^{2\sqrt{rn}},$ a bound very close to the Hardy-Ramanujan asymptotic formula that holds in the special case of Young's lattice. We conclude by posing several open questions.
In this paper the triangle intersection problem for a pair of disjoint
S
(
2
,
4
,
v
)
s is investigated. Let
J
T
∗
(
v
)
denote the set of all integers
s
such that there exists a pair of disjoint
S
...(
2
,
4
,
v
)
s intersecting in
s
triangles. Let
b
v
=
v
(
v
−
1
)
/
12
. We establish that for any positive integer
v
≡
1
,
4
(
mod
12
)
,
v
≥
16
and
v
≠
25
,
28
,
37
,
J
T
∗
(
v
)
=
0
,
b
v
.