×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

## ALGEBRAIC STRUCTURES I

by: Cassidy Grimes

8

0

81

# ALGEBRAIC STRUCTURES I MATH 546

Cassidy Grimes

GPA 3.51

J. Griggs

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
J. Griggs
TYPE
Class Notes
PAGES
81
WORDS
KARMA
25 ?

## Popular in Mathematics (M)

This 81 page Class Notes was uploaded by Cassidy Grimes on Monday October 26, 2015. The Class Notes belongs to MATH 546 at University of South Carolina - Columbia taught by J. Griggs in Fall. Since its upload, it has received 8 views. For similar materials see /class/229528/math-546-university-of-south-carolina-columbia in Mathematics (M) at University of South Carolina - Columbia.

×

## Reviews for ALGEBRAIC STRUCTURES I

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15
Xiqohqa liven I ll A Channel Assignment Problem F Roberts 1988 Find an efficient assignment of channels fx 6 R to sites a E R2 so that two levels of interference are avoided 2d if Has y 3A f fy392d if x ZHS2A 11 We must minimize spanf maxm minm We consider the analogous problem for graphs G V G 1989 The problem can be reduced to the case d 1 and labelings f V gt O12 such that 2 if distxy 1 fx fy39 2 1 if distxy2 We consider the analogous problem for graphs G V G 1989 The problem can be reduced to the case d 1 and labelings f V gt O12 such that 2 if distxy 1 lflxl wl 2 1 if distxy2 Such an f is called a AIabeling and AGminf Spanf The graph problem differs from the real one when putting vertices u N 1 corresponding to very close locations u 1 but not very Close VAVAVAV yX A Network of Transmitters with a Hexagonal Cell Covering and the corresponding Triangular Lattice PA Complete Graphs Kn 4 span6 Complete Graphs Kn 4 span6 MK 2n 2 Cycles On 3 0 span4 Cycles On 1 4 3 0 span4 MC 4 for n 2 3 Problem Bound MG in terms of A Problem Bound MG in terms of A A 2 gt A g 4 paths or cycles Problem Bound MG in terms of A A 2 gt A g 4 paths or cycles A3 Problem Bound MG in terms of A A 2 gt A g 4 paths or cycles A 3 Example Petersen Graph Problem Bound MG in terms of A A 2 gt A g 4 paths or cycles A 3 Example Petersen Graph Problem Bound MG in terms of A A 2 gt A g 4 paths or cycles A 3 Example Petersen Graph A 9 Conjecture A3 gt A39 Conjecture A 3 gt A g 9 More generally we have the A2 Conjecture GYeh 1989 For all graphs of maximum degree A 2 2 MG 3 A2 Results ABounds on A o A g A2 2A by firstfit 3 Results ABounds on A o A g A2 2A by firstfit 3 EGwithAZAz A for infinitely many values A GYeh 1990 Results ABounds on A o A g A2 2A by firstfit 3 EGwithAZAz A for infinitely many values A GYeh 1990 A3A2A Chang and Kuo 1995 Results ABounds on A o A g A2 2A by firstfit 3 EGwithAZAz A for infinitely many values A GYeh 1990 9 A g A2 A Chang and Kuo 1995 9 AgllforA3 Jonas 1993 Results ABounds on A o A g A2 2A by firstfit 3 HewithAZAZ A I b for infinitely many values A Chang and Kuo 1995 AgA2A AgllforA3 AgA2A 1 GYeh 1990 Jonas 1993 Kr l and Skrekovski 2003 Results ABounds on A I I bbbb A g A2 2A by firstfit 3 ElGWithAZAZ A for infinitely many values A GYeh 1990 A g A2 A Chang and Kuo 1995 A g 11 for A 3 Jonas 1993 A g A2 A 1 Kr l and Skrekovski 2003 A g A2 A 2 Gongalves 2005 Results ABounds on A 0 I bbbbb A g A2 2A by firstfit 3 ElGWithAZAZ A for infinitely many values A GYeh 1990 A g A2 A Chang and Kuo 1995 A g 11 for A 3 Jonas 1993 A g A2 A 1 Kral and Skrekovski 2003 A g A2 A 2 Gongalves 2005 In particular A g 10 for A 3 Georges and Mauro investigated many connected graphs with A 3 Georges and Mauro investigated many connected graphs with A 3 They suspect that for such graphs A g 7 unless G is the Petersen graph A 9 Georges and Mauro investigated many connected graphs with A 3 They suspect that for such graphs A g 7 unless G is the Petersen graph A 9 Kang verified A g 9 when G is cubic and Hamiltonian Among many results verifying the conjecture for special classes of graphs we have Theorem GYeh 1992 For graphs G of diameter 2 A 3 A2 and this is sharp iff A 2 3 7 57 Determining A even for graphs of diameter two is NPcomplete GYeh Is A 3 v 1 Determining A even for graphs of diameter two is NPcomplete GYeh Is A 3 v 1 Fiala Kloks and Kratochvil 2001 Fix it IS A k Determining A even for graphs of diameter two is NPcomplete GYeh Is A 3 v 1 Fiaa Kloks and Kratochvil 2001 Polynomial k g 3 Fix it IS A k Determining A even for graphs of diameter two is NPcomplete GYeh Is A 3 v 1 Fiaa Kloks and Kratochvil 2001 Fix is Is A k Polynomial k g 3 NPComplete k 2 4 multigraphs via homomorphisms to Trees Let A maximum degree A in Figures Trees Let A maximum degree A in Figures Example A A 1 left and A A 2 right A1 Al A2 Trees Let A maximum degree A in Figures Example A A 1 left and A A 2 right A1 Al 0 1 Al 0 1 A2 0 A3 039 A3 AZ Theorem Yeh 1992 For a tree T MT A 1 or A 2 Trees Let A maximum degree A in Figures Example A A 1 left and A A 2 right A1 Al A 7g 0 1 Al 0 1 A2 0 A3 039 A3 AZ Theorem Yeh 1992 For a tree T MT A1 or A2 It is difficult to determine which though there is a polynomial algorithm ChangKuo 1995 General Version 3 1992 Integer Lk1 k2 kplabelings of a graph G 9 1617627 kp 2 O are integers A labeling f vertex set VG gt O12 such that 9 for all uv fv Z 167 if distuv 239 in G General Version 3 1992 Integer Lk1 k2 kplabelings of a graph G 9 21 22 kp 2 O are integers A labeling f vertex set VG gt O12 such that 9 for all uv fv Z 167 if distuv 239 in G The minimum span MG 121 122 o kp Inin Spanf More History of the Distance Labeling Problem 9 Hale 1980 Models radio channel assignment problems by graph theory Georges Mauro Calamoneri Sakai Chang Kuo Liu Jha Klavzar Vesel et al investigate L2 1abeings and more general integer 1061 k2labelings with 11 2 k2 We introduce Real LU k2 kplabelings of a graph G We introduce Real LU k2 kplabelings of a graph G Let f k1 kp with each kg 2 0 real Given graph G V E possibly infinite define LG to be the set of labelings f VG gt 0 00 such that fu fv 2 kd whenever d distgu v We introduce Real LU k2 kplabelings of a graph G Let f k1 kp with each kg 2 0 real Given graph G V E possibly infinite define LG to be the set of labelings f VG gt 0 00 such that fu fv 2 kd whenever d distgu v spanf supvfv infvfv We introduce Real LU k2 kplabelings of a graph G Let f k1 kp with each kg 2 0 real Given graph G V E possibly infinite define LG to be the set of labelings f VG gt 0 00 such that fu fv 2 kd whenever d distgu v spanf supvfv infvfv 17 1627 7161 inff LG Spanf39 An advantage of the concept of real number labelings SCALING PROPERTY For real numbers d ki 2 O AGdk1dk2dkp dAGk1k2kp 20 An advantage of the concept of real number labelings SCALING PROPERTY For real numbers d ki 2 O AGdlc1dlc2dkpdAGk1k2 rep 39 7 Example MG 21 22 kgMG k 1 where k 61162162 gt 0 reduces it from two parameters 1162 to just one Is 20 Theorem GJ cf GeorgesMauro 1995 For the path Pn on n vertices we have the minimum span MP is 1 Pn ngt7 21 Theorem GJ cf GeorgesMauro 1995 For the cycle On on n vertices we have the minimum span MO is 1 C5 C3 10 9 8 2k C4 7 k2 6 5 4 4 4k k 3 2 2 k 1 2k 0 12 1 2 3 4 5 k ACnlc1n 34 5 22 ctd The minimum span ACnk1n 2 6 depending on n mod 3 and mod 4 1m0d 2 2m0d 4 0m0d 4 k1 0m0d 4 0 1 2 3 4 5 k 23 THE DSET THEOREM for REAL LABELINGS GJ 2003 24 THE DSET THEOREM for REAL LABELINGS GJ 2003 Let G be a graph possibly infinite of bounded degree Let reals k1 210 2 0 Then there exists an optimal L091 122 kpIabeing f 24 THE DSET THEOREM for REAL LABELINGS GJ 2003 Let G be a graph possibly infinite of bounded degree Let reals k1 210 2 0 Then there exists an optimal L091 122 kplabeling f 0 with smallest label 0 9 with all labels fv in the Dset 24 THE DSET THEOREM for REAL LABELINGS GJ 2003 Let G be a graph possibly infinite of bounded degree Let reals k1 210 2 0 Then there exists an optimal L091 122 kplabeling f 0 with smallest label 0 9 with all labels fv in the Dset Dk1k2kpi le Gig6139 a7 6 O12 24 THE DSET THEOREM for REAL LABELINGS GJ 2003 Let G be a graph possibly infinite of bounded degree Let reals k1 210 2 0 Then there exists an optimal L091 122 kplabeling f 0 with smallest label 0 9 with all labels fv in the Dset Dk1k2kpi le Gig6139 a7 6 O12 Hence MG 21 22 kp e Dklhmkp 24 ctd Moreover if G is finite each label of f is of the form 7 aim where the coefficients a7 6 O12 and 7 a7 lt n the number of vertices gtiltgtiltgtiltgtiltgtiltgtiltgtilt 25 ctd Moreover if G is finite each label of f is of the form 7 aim where the coefficients a7 6 O12 and 7 a7 lt n the number of vertices gtiltgtiltgtiltgtiltgtiltgtiltgtilt Corollary If all 197 are integers then MG 21 22 kp agrees with the former integer Xs 25 ctd Moreover if G is finite each label of f is of the form 7 aim where the coefficients a e 0 1 2 and Z a lt n the number of vertices gtiltgtiltgtiltgtiltgtiltgtiltgtilt Corollary If all k are integers then MG 21 22 kp agrees with the former integer Xs Note The Dset Thm allows us to ignore some labels Example For 161162 5 3 it suffices to consider labels fv in D5 0 3 5 6 8 9 10 25 Theorem For the triangular lattice we have APAI1 16 14 12 11411 10 4k 438 8 90292 6k 28 6 4 11 2316 9k 2k3 2 37277 13113 o 1312 1 43 2 3 4 5 k 26 A Manhattan Network and the Square Lattice Pg 27 Theorem For the square lattice we have MP5 is 1 888 28 Equilateral Triangle Cell Covering and the Hexagonal Lattice PH 29 Theorem For the hexagonal lattice we have APHI1 10 53143 3O Piecewise Linearity 31 Piecewise Linearity PL Conjecture For any integer p 2 1 and any graph G of bounded maximum degree MG 3 is PL ie continuous and piecewiselinear with finitely many pieces as a function of I 121192 kp E 0 00 31 Piecewise Linearity PL Conjecture For any integer p 2 1 and any graph G of bounded maximum degree MG 3 is PL ie continuous and piecewiselinear with finitely many pieces as a function of I 121192 kp E 0 00 Finite Graph PL Theorem For any integerp 2 1 and any finite graph G MG is PL 31 Theorem p 2 For any graph G possibly infinite with finite maximum degree MG 1 1 is a piecewise linear function of k with finitely many linear pieces 32 Theorem p 2 For any graph G possibly infinite with finite maximum degree MG 1 1 is a piecewise linear function of k with finitely many linear pieces Moreover k GZ G l 39f0ltklt1A3 AGk1 a d gt T 37 XG 1kb IkaA for some constants a b E O1A3 1 where G2 G is the graph on VG in which edges join vertices that are at distance two in G 32 We make the stronger Delta Bound Conjecture For all p and A there is a constant c cAp such that for all graphs G of maximum degree A and all k1 lap there is an optimal labeling f 6 L061 kp in which the smallest label is 0 all labels are in D091 kp and of the form 7 am where all coefficients a7 3 c 33 We make the stronger Delta Bound Conjecture For all p and A there is a constant c cAp such that for all graphs G of maximum degree A and all k1 lap there is an optimal labeling f 6 L061 kp in which the smallest label is 0 all labels are in D091 kp and of the form 7 am where all coefficients a7 3 c Theorem This holds for p 2 33 Lambda Graphs A more general model for graph labelling has been introduced recently by Babilon Jell39nek Kral and Valtr A A graph G V E is a multigraph in which each edge is of one of p types Given reals k1 kp 2 O a labelling f V gt 0 00 is proper if for every edge e e E say it is type 239 the labels at the ends of e differ by at least lg The infimum of the spans of the proper labellings of G is denoted by A0021 lap We assume implicitly that for every choice of the parameters 167 the optimal span A0021 kp is finite For example this holds when XG lt oo 34 Given a graph G form Agraph H GP in which an edge joining vertices u v has type 239 distgu v 1 g 239 g p Thus the real number distance labelling is a special case of Agraphs 35 Given a graph G form Agraph H GP in which an edge joining vertices u v has type 239 distgu v 1 g 239 g p Thus the real number distance labelling is a special case of Agraphs Results on distancelabelling concerning continuity piecewiselinearity and the DSet Theorem can be extended to Agraphs Babilon et al 35 Kral has managed to prove the PL and Delta Bound Conjectures in the more general setting of Agraphs in a stronger form Theorem For every p X 2 1 there exist constants Cm DW such that the space 0 00 can be partitioned into at most Cm polyhedral cones K on each of which the optimal span A0021 12 of every lambda graph G with p types of edges and chromatic number at most X is a linear function of k1 kp Moreover for each K and G there is a proper labelling f of Agraph G in the form fv Z7 avlc at every vertex U which is optimal for all 121 lap E K where the integer coefficients 0 3 my 3 DEX 36 A surprising consequence is Corollary Kral There exist only finitely many piecewiselinear functions that can be the Afunction of a Agraph with given number of edges is and chromatic number at most X 37 Future Work c The A2 Conjecture 38 Future Work The A2 Conjecture 0 Better bounds Dkax on the coefficients 38 Future Work The A2 Conjecture 0 Better bounds Dkax on the coefficients 0 The leftrightquot behavior of MG 1 1 as a function of k 38 Future Work 0 0 J J The A2 Conjecture Better bounds Dkax on the coefficients The leftrightquot behavior of MG 1 1 as a function of 1 Cyclic analogues generalizing circular chromatic numbers 38 Future Work bbbb b The A2 Conjecture Better bounds Dkax on the coefficients The leftrightquot behavior of MG 1 1 as a function of 1 Cyclic analogues generalizing circular chromatic numbers Symmetry properties of optimal labellings of lattices 38 Congratulations Joel 39 Congratulations Joel 39

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com