Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTwofold triple systems with cyclic 2-intersecting Gray codes
55
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a combinatorial design $mathcal{D}$ with block set $mathcal{B}$, the block-intersection graph (BIG) of $mathcal{D}$ is the graph that has $mathcal{B}$ as its vertex set, where two vertices $B_{1} in mathcal{B}$ and $B_{2} in mathcal{B} $ are adjacent if and only if $|B_{1} cap B_{2}| > 0$. The $i$-block-intersection graph ($i$-BIG) of $mathcal{D}$ is the graph that has $mathcal{B}$ as its vertex set, where two vertices $B_{1} in mathcal{B}$ and $B_{2} in mathcal{B}$ are adjacent if and only if $|B_{1} cap B_{2}| = i$. In this paper several constructions are obtained that start with twofold triple systems (TTSs) with Hamiltonian $2$-BIGs and result in larger TTSs that also have Hamiltonian $2$-BIGs. These constructions collectively enable us to determine the complete spectrum of TTSs with Hamiltonian $2$-BIGs (equivalently TTSs with cyclic $2$-intersecting Gray codes) as well as the complete spectrum for TTSs with $2$-BIGs that have Hamilton paths (i.e., for TTSs with $2$-intersecting Gray codes). In order to prove these spectrum results, we sometimes require ingredient TTSs that have large partial parallel classes; we prove lower bounds on the sizes of partial parallel clasess in arbitrary TTSs, and then construct larger TTSs with both cyclic $2$-intersecting Gray codes and parallel classes.
rate research
Read More
Three intersection theorems are proved. First, we determine the size of the largest set system, where the system of the pairwise unions is l-intersecting. Then we investigate set systems where the union of any s sets intersect the union of any t sets. The maximal size of such a set system is determined exactly if s+t<5, and asymptotically if s+t>4. Finally, we exactly determine the maximal size of a k-uniform set system that has the above described (s,t)-union-intersecting property, for large enough n.
Let $X$ be a $v$-set, $B$ a set of 3-subsets (triples) of $X$, and $B^+cupB^-$ a partition of $B$ with $|B^-|=s$. The pair $(X,B)$ is called a simple signed Steiner triple system, denoted by ST$(v,s)$, if the number of occurrences of every 2-subset of $X$ in triples $BinB^+$ is one more than the number of occurrences in triples $BinB^-$. In this paper we prove that $st(v,s)$ exists if and only if $vequiv1,3pmod6$, $v e7$, and $sin{0,1,...,s_v-6,s_v-4,s_v}$, where $s_v=v(v-1)(v-3)/12$ and for $v=7$, $sin{0,2,3,5,6,8,14}$.
The notion of cross intersecting set pair system of size $m$, $Big({A_i}_{i=1}^m, {B_i}_{i=1}^mBig)$ with $A_icap B_i=emptyset$ and $A_icap B_j eemptyset$, was introduced by Bollobas and it became an important tool of extremal combinatorics. His classical result states that $mle {a+bchoose a}$ if $|A_i|le a$ and $|B_i|le b$ for each $i$. Our central problem is to see how this bound changes with the additional condition $|A_icap B_j|=1$ for $i e j$. Such a system is called $1$-cross intersecting. We show that the maximum size of a $1$-cross intersecting set pair system is -- at least $5^{n/2}$ for $n$ even, $a=b=n$, -- equal to $bigl(lfloorfrac{n}{2}rfloor+1bigr)bigl(lceilfrac{n}{2}rceil+1bigr)$ if $a=2$ and $b=nge 4$, -- at most $|cup_{i=1}^m A_i|$, -- asymptotically $n^2$ if ${A_i}$ is a linear hypergraph ($|A_icap A_j|le 1$ for $i e j$), -- asymptotically ${1over 2}n^2$ if ${A_i}$ and ${B_i}$ are both linear hypergraphs.
Strongly walk-regular graphs can be constructed as coset graphs of the duals of projective three-weight codes whose weights satisfy a certain equation. We provide classifications of the feasible parameters in the binary and ternary case for medium size code lengths. Additionally some theoretical insights on the properties of the feasible parameters are presented.
A family $mathcal F$ has covering number $tau$ if the size of the smallest set intersecting all sets from $mathcal F$ is equal to $s$. Let $m(n,k,tau)$ stand for the size of the largest intersecting family $mathcal F$ of $k$-element subsets of ${1,ldots,n}$ with covering number $tau$. It is a classical result of ErdH os and Lovasz that $m(n,k,k)le k^k$ for any $n$. In this short note, we explore the behaviour of $m(n,k,tau)$ for $n<k^2$ and large $tau$. The results are quite surprising: For example, we show that $m(k^{3/2},k,tau) = (1-o(1)){n-1choose k-1}$ for $taule k-k^{3/4+o(1)}$. At the same time, $m(k^{3/2},k,tau)<e^{-ck^{1/2}}{nchoose k}$ if $tau>k-frac 12k^{1/2}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
