Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms (1)

0
votes
0answers
72 views

Understanding Prof. Keevash's proof on the “Existence of Designs” [closed]

I have tried to read Prof. Kevvash's paper on the "Existence of designs". I am finding it very tough to read it linearly. I am comfortable with the nibble ideas and probabilistic methods in general. ...
3
votes
0answers
78 views

Number of cyclic difference sets

A subset $D=\{a_1,\ldots,a_k\}$ of $\mathbb{Z}/v\mathbb{Z}$ is said to be a $(v,k,\lambda)$-cycic difference set if for each nonzero $b\in\mathbb{Z}/v\mathbb{Z}$, there are exactly $\lambda$ ordered ...
1
vote
1answer
79 views

Number of points in an intersecting linear hypergraph

I first asked the question below at math.stackexchange.com ( http://math.stackexchange.com/questions/920442/number-of-points-in-an-intersecting-linear-hypergraph ) but somebody suggested I ask it in ...
6
votes
1answer
158 views

Is there a simple proof that there is no five mutually orthogonal Latin squares of order 6?

It is well known that there is a projective plane of order $n$ if and only if there exist a set of $n-1$ mutually orthogonal Latin squares. The first nontrivial case is $n=6$, which fails because of ...
3
votes
1answer
463 views

“Codes” in which a group of words are pairwise different at a certain position

I read the following problem, claimed to be in the IMO shortlist in 1988: A test consists of four multiple choice problems, each with three options, and the students should give an unique answer ...
10
votes
1answer
223 views

On the Steiner System S(4,5,11)

Is there a nice way to partition the edges of the complete 5-uniform hypergraph on 11 vertices into 7 copies of the Steiner system S(4,5,11)? If this is obvious or elementary, I apologize in advance. ...
4
votes
2answers
345 views

Can we sometimes define the parity of a set?

Suppose that ${n\choose k}, {n-1\choose k-1}, \ldots, {n-k+1\choose 1}$ are all even. (This happens for example if $k=2^\alpha-1$ and $n=2k$.) In this case, can we select ${n\choose k}/2$ sets of size ...
2
votes
1answer
106 views

Hitting sets (aka covers aka transversals) of Steiner triple systems

Does there exist a constant $c$ so that the lines of every Steiner triple system on $v$ points can be covered by $cv$ points? That is if $D \in STS(v)$ with point set $T=\{1,2,\ldots,v\}$ then ...
1
vote
0answers
53 views

Point sets with tangents through every point

Let $D=(P,L)$ be either a $(v,k,\lambda)$-design or a near-linear space (or, more generally, any incidence structure with "points" and sets of points which are called "blocks" or "lines") and let $S ...
3
votes
3answers
135 views

Isomorphism testing in STS(13)

What is the simplest isomorphism invariant which can distinguish between the two non-isomorphic Steiner triple systems on $13$ points? Train structure and cycle structure, as described here, do the ...
5
votes
2answers
167 views

Nonextendable partial Hadamard matrices

An $m\times n$ matrix with entries $\pm 1$ is said to be partial Hadamard if any two rows are orthogonal. See Reference for partial Hadamard matrices. Given $n\equiv 0\,(\mathrm{mod}\,4)$, what is the ...
3
votes
0answers
38 views

Balancing out edge multiplicites in a graph

Let $G$ be a multigraph with maximum edge multiplicity $t$ and minimum edge multiplicity $1$ (so that there is at least one 'ordinary' edge). Is there some simple graph $H$ such that the $t$-fold ...
3
votes
2answers
154 views

Is the domination number of a combinatorial design determined by the design parameters?

Let $D$ be a $(v,k,\lambda)$-design. By the domination number of $D$ I mean the domination number $\gamma(L(D))$ of the bipartite incidence graph of $D$. Is $\gamma(L(D))$ determined only by ...
8
votes
3answers
348 views

colorings of ${\mathbb Z}^d$ with constraints

For a lattice $\mathbb Z^d$, denote by lattice line any line that contains two (and thus infinitely many) lattice points. For $2\le k<n$, define a $(n,k)$-coloring, or $C_d(n,k)$ for short, ...
1
vote
1answer
280 views

Known results on cyclic difference sets

Is there any infinite family of $v$ for which all the $(v,k,\lambda)$-cyclic difference sets with $k-\lambda$ a prime power coprime to $v$ have been determined? A subset $D=\{a_1,\ldots,a_k\}$ of ...
0
votes
1answer
176 views

a block design question

Is it possible to show that every 1-design $D$ with $\lambda=4,k=4$ on $v$ points (for $v$ that is a multiple of $3$) contain some 1-design $Q$ with $\lambda=1,k=3$ on $v$ points such that every block ...
2
votes
1answer
135 views

Ranks of higher incidence matrices of designs

In 1978 Doyen, Hubaut and Vandensavel proved that if $S$ is a Steiner triple system $S(2,3,v)$ then the $GF(2)$ rank of its incidence matrix $N$ is $$ Rk_{2}(N)=v-(d_{p}+1), $$ where $d_{p}$ is the ...
1
vote
3answers
204 views

Constructions of $2-(v,3,3)$-designs

I am looking for ways to construct an infinite family of designs with parameters $2-(v,3,3)$ and apart from some doubling-type recursive constructions (such as in this paper) I haven't found anything ...
7
votes
0answers
348 views

Does $(\mathbb{Z}/n\mathbb{Z})^2$ ever admit a difference set when $n$ is odd?

A difference set of a group $G$ is a subset $D\subseteq G$ with the property that there exists an integer $\lambda>0$ such that for every non-identity member $g$ of $G$, there exist exactly ...
5
votes
1answer
478 views

What is the largest number of k-element subsets of a given n-element set S such that…

Given a set S of n elements. What is the largest number of k-element subsets of S such that every pair of these subsets has at most one common element?
14
votes
1answer
592 views

Octonions and the Fano plane.

Does the Fano plane mnemonic for octonion multiplication have any deeper meaning? http://upload.wikimedia.org/wikipedia/commons/2/2d/FanoPlane.svg The symmetry group of the Fano plane is PSL(2,7), ...
10
votes
1answer
332 views

Fano plane drawings: embedding PG(2,2) into the real plane

By a drawing of the Fano plane I mean a system of seven simple curves and seven points in the real plane such that every point lies on exactly three curves, and every curve contains exactly three ...
7
votes
0answers
166 views

Tenacious structure

Let $\def\A{\mathbb A}\def\F{\mathbb F}\F_3$ be the Galois field with three elements and let $\A^d=\A^d(\F_3)$ be the affine space of dimension $d$ over $\mathbb F_3$ —the subject is combinatorics and ...
2
votes
1answer
78 views

Lower bounds on cardinality of a union of blocks in a design

Let $D$ be a $(v,k,\lambda)$-design (repeated blocks are allowed). I would like to get a lower bound on the cardinality of the union of $s$ blocks. A naive application of inclusion-exclusion gives ...
3
votes
2answers
352 views

Is Ryser's conjecture on permanent minimizers still open?

Let $A(k,n)$ be the set of $\{0,1\}$ matrices of order $n$ with all their line sums equal to $k$. Conjecture number 5 on the list from Minc's book, attributed to Ryser, says that if $A(k,n)$ ...
2
votes
2answers
142 views

Resolvable designs from projective space

Resolvable designs are block designs with the additional property that the blocks can be partitioned into partitions of the points. It is easy to see that lines in affine space form a resolvable ...
3
votes
3answers
371 views

Orthogonal Latin Square 6*6

I need to make remarks about Tarry's Proof for the nonexistence of 6x6 Latin Squares as part of my final exam for a class I'm in. Problem is, I can't find it ANYWHERE on the internet. I can only find ...
1
vote
5answers
267 views

Pairwise balanced designs with $r=\lambda^{2}$

A while ago I asked how to construct an infinite family of $(v,b,r,k,\lambda)$-designs satisfying $r=\lambda^{2}$ and got very good answers from Yuichiro Fujiwara and Ken W. Smith. Now I'd like to up ...
9
votes
4answers
1k views

What are the major open problems in design theory nowaday?

I gather that the question whether the Bruck-Chowla-Ryser condition was sufficient used to top the list, but now that that's settled - what is considered the most interesting open question?
4
votes
2answers
254 views

Is there an infinite number of combinatorial designs with $r=\lambda^{2}$

A quick look at Ed Spence's page reveals two such examples: (7,3,3) and (16,6,3). If there is a known classification and/or name by which such designs go, I'd love to know about them too. EDIT: I ...
5
votes
1answer
225 views

Block design question

Given fixed values for $d \leq k \leq v$. I would like to find a set $B$ of $d$-sets of $[v]$ with the following properties: Every $k$-set of $[v]$ contains at least one element of $B$ Every ...
11
votes
5answers
464 views

Intersecting 4-sets

Is it possible to have more than $N = \binom{\lfloor n/2\rfloor}{2}$ subsets of an $n$-set, each of size 4, such that each two of them intersect in 0 or 2 elements? To see that $N$ is achievable, ...
2
votes
1answer
379 views

Popular elements in cross-intersecting families

Let $\mathcal{T}$ and $\mathcal{S}$ be two families of subsets of $[n]$ such that for all $T_i\in \mathcal{T}$ and $S_j\in \mathcal{S}$, $|T_i \cap S_j| \neq\emptyset$ $|T_i| , |S_j| \leq t = ...
-1
votes
1answer
300 views

Number of blocks in a t-(v,k,l) design with empty intersection with a given set U [closed]

Question Given a $t-(v,k,\lambda)$ design $(X,\mathcal{B})$ and a set $U\subset X$ with $|U|=u\leq t$, what is the number of blocks $B\in\mathcal{B}$ such that $B\cap U=\emptyset$? The answer is: ...
3
votes
1answer
337 views

Residual design (BIBD) with repeated blocks

Simple BIBD are defined as those designs in which incindence relation is "is element". So effectively blocks are subsets of points. Equivalently there should be no "repeating blocks" ie. blocks that ...
6
votes
3answers
580 views

Meeting management

A friend wants to have ten meetings of six people every day for five days with no pair of people meeting twice. Is this possible? It appears to be a question about maximal decomposition of a complete ...
5
votes
0answers
543 views

Status of Hadamard matrix conjecture

I would like to know if any progress has been made on Hadamard conjecture : There exists a Hadamard matrix of order $n=4k$ $\forall k \in \mathbb{N}$.
1
vote
1answer
331 views

The Symmetry of Steiner System S(5,8,24)

The group of automorphisms of S(5,8,24), M_{24}, is 5-transitive. Other than Symmetric groups are there any other 5-transitive groups? If not, would it be correct to say S(5,8,24) is the most ...
6
votes
4answers
1k views

Constructing Steiner Triple Systems Algorithmically

I want to create STS(n) algorithmically. I know there are STS(n)s for $n \cong 1,3 \mod 6$. But it is difficult to actually construct the triples. For STS(7) it is pretty easy and but for larger n I ...
3
votes
1answer
203 views

Lower bounding the maximum size of sets in a set family with union promise

The following problem has come up while working on the relationship between certificate and randomized decision tree complexities of boolean functions. However, I think it is of interest by itself and ...
2
votes
0answers
1k views

A generalization of covering designs and lottery wheels

This question is inspired by a recent problem . A $(v,k,t)$ covering design is a pair $(V,B)$ where $V$ is a set of $v$ points and $B$ is a family of $k$ point subsets (called blocks) such that ...
3
votes
2answers
1k views

How many elements with a hamming distance of 3 or less?

[This is a complete rewrite which makes some of the comments redundant or irrelevant.] Take a set of $50$ elements. How many subsets of size $5$ are needed so that every subset of size $5$ will ...
19
votes
2answers
2k views

Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?

The following problem is homework of a sort -- but homework I can't do! The following problem is in Problem 1.F in Van Lint and Wilson: Let $G$ be a graph where every vertex has degree $d$. ...
3
votes
3answers
2k views

What's the maximum determinant of the (0, 1) matrix from M(n, R)?

If there's no exact formula what's the nearest upper and lower bounds do you know?
4
votes
1answer
981 views

Solving a Diophantine equation related to Algebraic Geometry, Steiner systems and $q$-binomials?

The short version of my question is: 1)For which positive integers $k, n$ is there a solution to the equation $$k(6k+1)=1+q+q^2+\cdots+q^n$$ with $q$ a prime power? 2) For which positive ...
8
votes
1answer
617 views

Which Steiner systems come from algebraic geometry?

This question is motivated by the ongoing discussion under my answer to this question. I wrote the following there: A $(p, q, r)$ Steiner system is a collection of $q$-element subsets $A$ (called ...
23
votes
15answers
6k views

Linear Algebra Proofs in Combinatorics?

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...
11
votes
2answers
616 views

Is there a tournament schedule for 18 players, 17 rounds in groups of 6, which is balanced in pairs?

We are interested in a solution to the following scheduling problem, or any information about how to find it or its existence. This one comes from real life, so you will not only be helping a ...