# Tagged Questions

The tag has no wiki summary.

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, ...
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$. ...
460 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, ...
613 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 ...
304 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 ...
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?
606 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 ...
345 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 ...
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 ...
449 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?
160 views

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 ...
518 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}$.
337 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 ...
960 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 ...
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?
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 ...
127 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 ...
359 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 ...
200 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 ...
37 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 ...
138 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 ...
100 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 ...
127 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 ...
76 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 ...
378 views

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 = ... 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 ... 3answers 196 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 ... 1answer 330 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 ... 1answer 242 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 ... 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 ...
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 ...
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: ...