TAILIEUCHUNG - Báo cáo toán học: "Colorings and Nowhere-Zero Flows of Graphs in Terms of Berlekamp’s Switching Game"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Colorings and Nowhere-Zero Flows of Graphs in Terms of Berlekamp’s Switching Game. | Colorings and Nowhere-Zero Flows of Graphs in Terms of Berlekamp s Switching Game Uwe Schauz Department of Mathematics and Statistics King Fahd University of Petroleum and Minerals Dhahran 31261 Saudi Arabia schauz@ Submitted Jul 22 2010 Accepted Mar 14 2011 Published Mar 24 2011 Mathematics Subject Classifications 91A43 05C15 05C50 05C20 94B05 Abstract We work with a unifying linear algebra formulation for nowhere-zero flows and colorings of graphs and matrices. Given a subspace code U Zk - . the bond or the cycle space over Zk of an oriented graph - we call a nowhere-zero tuple f E z k a flow of U if f is orthogonal to U .In order to detect flows we view the subspace U as a light pattern on the n-dimensional Berlekamp Board Zk with kn light bulbs. The lights corresponding to elements of U are ON the others are OFF. Then we allow axis-parallel switches of complete rows columns etc. The core result of this paper is that the subspace U has a flow if and only if the light pattern U cannot be switched off. In particular a graph G has a nowhere-zero k-flow if and only if the Zk-bond space of G cannot be switched off. It has a vertex coloring with k colors if and only if a certain corresponding code over Zk cannot be switched off. Similar statements hold for Tait colorings and for nowhere-zero points of matrices. Studying different normal forms to equivalence classes of light patterns we find various new equivalents . for the Four Color Problem Tutte s Flow Conjectures and Jaeger s Conjecture. Two of our equivalents for colorability and existence of nowhere zero flows of graphs include as special cases results by Matiyasevich by Balazs Szegedy and by Onn. Alon and Tarsi s sufficient condition for k-colorability also arrives remarkably as a generalized full equivalent. Introduction While working at Bell Labs in the 1960s Elwyn Berlekamp built a 10 X 10 grid of light bulbs. The grid had an array of 100 switches in the back to control each light bulb .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học