All Questions
Tagged with combinatorial-designs graph-theory
12 questions
56
votes
21
answers
14k
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, ...
23
votes
2
answers
3k
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$. ...
- 156k
15
votes
1
answer
886
views
Scrambling a “Connections” grid
Given a 4-by-4 array of distinct words, is it possible to scramble the array in four different ways in such a fashion that each possible word-pair appears adjacently in one of the five arrays (the ...
- 19.7k
11
votes
5
answers
506
views
What are efficient pooling designs for RT-PCR tests?
I realize this is long, but hopefully I think it may be worth the reading for people interested in combinatorics and it might prove important to Covid-19 testing. Slightly reduced in edit.
The ...
- 14.4k
7
votes
2
answers
434
views
Minimum covers of complete graphs by $4$-cycles
I am interested in coverings of the (edge set of the) complete graph $K_n$ by cycles of length $4$. It is clear that such coverings exist for each $n \ge 4$. I need to find the minimum number of $4$-...
- 337
6
votes
3
answers
678
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 ...
- 69
4
votes
2
answers
221
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 $v,k$, ...
- 6,962
4
votes
3
answers
780
views
Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?
I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form ...
- 43
4
votes
1
answer
70
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 ...
- 1,081
3
votes
1
answer
83
views
For which sets of $(n, m, k)$ does there exist an edge-labelling (using $k$ labels) on $K_n$, such that every single-labelled subgraph is $K_m$?
Or, equivalently - for what sets of $(n, m, k)$ is it possible, for a group* of $n$ people, to arrange $k$ days of "meetings", such that every day the group is split into subgroups of $m$ people, and ...
- 131
0
votes
0
answers
84
views
Bounds for smallest non-trivial designs
Given $s>t\ge 2$, let $N(s,t)$ be the smallest integer $n>s$ such that there exists an “$(n;s;t;1)$-design” (i.e., a collection of $s$-subsets $e_1,\dots,e_m$ of $[n]:=\{1,\dots,n\}$, such that ...
- 3,499
0
votes
0
answers
91
views
Steiner-like systems with large edges and many intersections
Let $l\geq 3$ be an integer. Is there $n\in\mathbb{N}$ and a hypergraph $H=(\{1,\ldots,n\},E)$ with the following properties?
for all $e\in E$ we have $|e| \geq l$
$e_1\neq e_2 \in E \implies |e_1 \...
- 48.9k