| |
More
Problems |
 |
|
Problem of the month (Graph Theory):
Characterize those simple graphs G with
the following two properties: between each
pair of vertices u and v in
G we have that (1) there exist a pair
of vetex-disjoint
paths, and (2) any set of vertex-disjoint paths
betweeen u and v has at
most two elements.
(Note: simple means no loops and at
most one edge joining any pair of distinct
vertices in the graph. Also, P1,...,Pn
are vetex-disjoint paths between u
and v if they
are paths from u to v and if
no two of them share a vertex except for u,v).
|
|
Problem of the month (matrix theory):
Let A and B be positive semidefinite
matrices (symmetric matrices with all nonnegative
eigenvalues).
Show that if trace(AB) = 0, then in fact
AB = 0.
|
|
Problem of the month (elementary group theory):
Find two groups A and B such
that there is a surjective
homomorphism from each one to the other, but there
is no isomorphism
between them.
|
|
 Problem
of the month (plane geometry):
Take a triangle ABC and a point P strictly inside
it.
Draw the lines AP, BP, and CP passing from vertices
through P.
These lines intersect the triangle ABC at points
A', B',
and C', respectively.
(a) Prove that the area of triangle A'B'C' is
less than 1/2 that of ABC.
(b) Can you do better than 1/2?
|
|
Problem
of the month (convex linear recurrences):
Let r(1),...,r(k)
be nonnegative real numbers summing to 1
and let a(1),...,a(k)
be arbitrary complex numbers. For n >
k,
define
a(n) = r(1)a(n-1)
+ .... + r(k)a(n-k).
Furthermore, suppose that there exists a consecutive
pair r(i) and r(i+1)
with nonzero product.
(a) Prove that the limit of a(n)
as n goes to infinity exists.
(b) If k = 2 and r(1)
= r(2) = 1/2, what is the limit in terms
of
a(1) and a(2)?
(c) Can you determine this limit in general?
(d) Are the supplimental hypotheses necessary
for this
limit to exist?
|
|
Problem
of the month (minimal cardinality group generators):
Let G be a finite group of size
|G|.
(a) Prove that the smallest number of elements
of G
necessary to generate it is less than or equal
to log |G|.
(Hint: Assume S is a set of k
generators and consider
the chain of subgroups that they induce).
(b) Is the bound in (a) tight?
|
|
|
|
|
|
