M.Sc Thesis

M.Sc StudentKfir Ori
SubjectSystems of Representatives and Their Applications
DepartmentDepartment of Mathematics
Supervisor PROFESSOR EMERITUS Ron Aharoni


The study of the concept of independent systems of representatives )ISRs) has proven lately to be very fruitful in solving many combinatorial problems. In this thesis, we extend the study of ISRs in various directions.

A natural analogue for the concept of "an independent set" in graphs is that of "an acyclic set" in digraphs. By the same token, an analogue of the concept of graph coloring is that of decomposing the digraph into acyclic sets. We prove a sufficient condition for the existence of an acyclic system of representatives of a family of sets of vertices. We prove a weighted version of this result and use it to prove a fractional version of a strong acyclic coloring conjecture for digraphs.

Another direction of extending the notion of ISR's is studying fractional ISR's.  We prove a sufficient condition for the existence of a fractional ISR. We extend this result to formulate a condition for fractional matchability of a simplicial complex and a matroid.

We introduce the notion of cooperative coloring of graphs. A collection G1,…,Gk of graphs on the same set of vertices, is cooperatively colorable if one can decompose the ground set into sets A1,…,Ak, where Ai is independent in Gi for all i=1,…,k. We conjecture that every Δ+2 graphs with maximal degree Δ are cooperatively colorable. We prove some partial results.

The last chapter of this thesis is devoted to studying the relation between the topological connectivity of the matching complex of a hypergraph and its covering number.