10
votes
1answer
125 views

Which graphs can be drawn using straight lines with no disjoint edges?

What is the class of graphs that can be drawn using only straight lines with no two edges disjoint? Edges are disjoint when they don't cross and they don't share a vertex. Vertices should be in ...
5
votes
1answer
130 views

Number of combinations such that each pair of combinations has at most x elements in common?

I am doing research on the sense of smell and have a combinatorics problem: I have 128 different odors (n) and I mix them in mixtures of 10 (r). There are 2.26846154e+14 different mixtures. What I ...
1
vote
1answer
58 views

Has this variation of blocking set been studied before?

Given a collection of sets $F$, a set which intersects all sets in the $F$ in at least one element is called a blocking set (or hitting set). The blocking number $τ(F)$ of a family $F$ is the minimum ...
2
votes
1answer
838 views

Prove that the maximum number of edges in a graph with no even cycles is floor(3(n-1)/2)

The question is in the title. I can see why the bound is sharp (for example, a lot of triangles sharing one common vertex if n is odd, or the same but with one spare edge hanging out if n is even). ...
1
vote
1answer
249 views

How do I approach this combinatorics problem about composition?

The question is from Bogart's A composition of the integer k into n parts is a list of n positive integers that add to k. How many compositions are there of an integer k into n parts. To ...