discrete-math

[sleek swallow]

In any case, I've seen a treatment of ZFC set theory (Geometric Anatomy of Theoretical Physics), where no distinction is made between elements and sets. Soooo, in that situation, it's not really helpful to force that distinction.

Well, phi is a subset of any set and what you've given is a set.

Hence, phi is a subset of that set.

[pastel wolf]

I mean I think of it moreso as a relation than an actual distinction between types, but sometimes it's just more convenient

You've just proven a statement by citing the statement, though

[sleek swallow]

Huh

Okay, have you seen the proof of the following statement: Let x be the empty set and let A be any given set. Then, x is a subset of A.

Have you seen the proof of that?

[pastel wolf]

I'm aware it's true. It just seems completely synthetic and odd. The logic you wrote earlier was pretty straightforward, it just doesn't make much intuitive sense.

[sleek swallow]

It's synthetic because it's vacuously true. It's true only because the antecedent is false. Then, ex falso quodlibet tells us, then, that the implication actually does hold. Since the biconditional is true, by definition, we conclude that the empty set is a subset of any given set.

Now, the set containing the empty set, last time I checked, is a set and so, the empty set must be contained within it. Indeed, if you take the power set of that set containing the empty set, you'll see the empty set being listed as a subset.

^I hope I'm clear enough lol. My bad if I'm not.

[pastel wolf]

I suppose a more intuitive way of looking at it is that for all sets A, the intersection of ø and A = ø which implies ø is a subset of A

[sleek swallow]

????????

That is clearly not true

Oh wait fuck my bad

[dapper rose]

no the implication isn't there

[sleek swallow]

I'm stupid

The implication you gave is wrong but the intersection is fine.

Let A & B be two sets:

A is a subset of B iff, for all elements in A, an element belonging to A implies that the element belongs to B. As far as I can see, the intersection has nothing to do with that.

[dapper rose]

hmm actually $B\cap A=B\implies B\subseteq A$

[vital dew]

EpicGuy4227:

[stray reef]

that's an iff

[dapper rose]

yeah it can be

[pastel wolf]

That's what I was thinking epic, yeah. Though without the guarantee of a proper subset

[sleek swallow]

Oh fuck lol shite

[pastel wolf]

That personally seems much more intuitive to me since the left side states all elements of B are in A, which is the definition of a subset

[sleek swallow]

I do remember proving that but it was sort of not the biggest idea presented so I didn't bother keeping it in my head.

[pastel wolf]

Oh good so it is true

[sleek swallow]

I kind of approach set theory as an extension of logic, so everything is reducible to some tautology.

[pastel wolf]

I mean I haven't taken set theory or discrete or anything. Highest I've gone up to so far has been Cal 3. But I've been working on discrete problems to help some people out. That statement seemed right and I could give reasoning for it but it's not like I had paper in front of me and formally proved it

Hadn't seen it before so whenever you guys started questioning it I started to second guess myself

[sleek swallow]

Not the most careful proof lmao

[pastel wolf]

Is there a reason you guys are using the proper subset?

Shouldn't it have no guarantee its proper?

[sleek swallow]

Urm okay, so the book that I use doesn't make that distinction. It basically starts off with the axioms of ZFC and just doesn't bother to make a distinction between proper subsets and subsets.

I think it will do it later but I haven't gotten to that point yet

[pastel wolf]

Ah alright. I knew there was some contention there but just wanted to ask

[dapper rose]

$\subseteq$ is normal subset

[vital dew]

EpicGuy4227:

[dapper rose]

not proper

[pastel wolf]

Wait seriously? Huh.... Yeah I don't like that.

[sleek swallow]

Actually, let me prove this a little carefully.

[pastel wolf]

Well... Oh yeah actually it makes sense.

It's almost like an amalgamation of = and the proper subset

For some reason I had it in my head it was the other way around

[dapper rose]

back to the original question, $\subset$ sometimes means subset and sometimes means proper subset

[vital dew]

EpicGuy4227:

[sleek swallow]

^Yea

Depends on the book

My book doesn't make the distinction (for right now).

[pastel wolf]

I imagine in most cases it doesn't matter

Anyway, thanks for dealing with me tripping all over myself. If any of you want to look over that question I posted almost 11 hours ago that'd be nice but it's pretty late and I should probably go.

I had posted work and just wanted someone to look over it but no one ever did

[sleek swallow]

Urm didn't write everything down cos a lot of it is quite obvious lol.

@pastel wolf Urm, I tried looking at the stuff you posted but it's unintelligible cos your handwriting is very messy. Could you write it up nicely and send it again?

[pastel wolf]

I might tomorrow sometime

[sleek swallow]

Sure.

[hardy yoke]

All of people know at least 2 languages. 15 people know French, 24 German, 21 Italian. 8 know all three. Would the right answer be 15+24+21-8?

[hardy yoke]

We have positive number which contains 20 digits, it can't contain 0, it contains Exactly three 1's and five 2's. How many numbers exist with such rules. My solution: ```
8!/(5!3!) = 56 ways to arrange three 1's and five 2's.
20C12 = 125970 ways to rearrange rest 12 numbers in 20 spots.
7^12 = 13 841 287 201‬ ways to rearrange 12 numbers where position matters and repetitions are allowed. Digits 0,1,2 are excluded
56125970*13 841 287 201 = 97 640 869 127 758 320‬ the answer

Would be nice to know if this is right, I don't have an answer sheet 😢

[stray reef]

All of people know at least 2 languages. 15 people know French, 24 German, 21 Italian. 8 know all three. Would the right answer be 15+24+21-8?
depends on what the question was

[hardy yoke]

Total amount of people in the group.

[sleek swallow]

"it can't contain no 0" What does that mean?

[stray reef]

contains at all times the 1s and five 2s.
EXACTLY three or AT LEAST three?

[hardy yoke]

Exactly*

it can't contain 0*

[orchid jasper]

Are trees necessarily connected

[dapper rose]

yes, that follows immediately from definition

@orchid jasper

[lean creek]

@orchid jasper if it's disconnected, it's called a forest haha

[weary tiger]

Can anyone help me out with this question

[faint narwhal]

What have you tried?

[weary tiger]

This is the answer still dont really know hwo to do it

[lean creek]

yep

just use the identity

[weary tiger]

but this does not work for 9

9 choose 2

I mean

[faint narwhal]

what do you mean 9 choose 2?

Why doesn't it work?

[weary tiger]

since 9 choose 2 is not the same when you plug it into the formula n choose k plus 1

[lean creek]

don't assume they're the same k ig

write n as 2q+1

Sunny

This is the answer still dont really know hwo to do it

Dec 8, 2019, 2:40 AM

[weary tiger]

if n is odd sure

[lean creek]

you can also just do it like they told you to

[weary tiger]

yeah I dont know how to

[lean creek]

write out the explicit formula

and manipulate it with algebra so you get the result they want you to

you already know what you want to be looking for

[faint narwhal]

You're assuming that $\binom{n}{k} = \binom{n}{k+1}$

[vital dew]

Zopherus:

[faint narwhal]

This is known

You're trying to show that n must be odd

[weary tiger]

yes if the equation is true then n must be odd

[faint narwhal]

That's what you're trying to prove

[weary tiger]

I was gonna try it using contradiction but then I tried 9 choose 2 and since it didnt work for the equation got confused and did not know what to do so I looked at the answer which did not really help me at all

[lean creek]

I almost feel like contradiction is overkill

[faint narwhal]

I don't think you understand what it means to prove such an implication

[lean creek]

just write the formula

[faint narwhal]

Or what contradiction actually does

[lean creek]

and manipulate it

[weary tiger]

with contradiction wouldnt I assume n must be even

[faint narwhal]

And try to reach a contradiction yes

[weary tiger]

yeah

[lean creek]

n! / (k+1)! * (n-(k+1))! = (2k+1)! / (k+1)! * (2k+1-(k+1))! = (2k+1)! / (k+1)! * (2k-k)! = (2k+1)! / (k)! * (2k+1-k)! = n! / (k)! * (n-k)!

there u go

if you want to be thorough, you can also show that it breaks if I make n even

[faint narwhal]

That doesn't mean you should consider something like 9 choose 2

That doesn't really make sense

[weary tiger]

I wasnt considering it in my proof

outside of the proof I was just trying examples of n being an odd number too see if it actually worked

for example I tried n = 5

since it was saying n must be odd I thought it would work everytime n was odd

[lean creek]

I think it is in fact required that n be 2k+1

explicitly

for it to work

[faint narwhal]

It does work every time n is odd

But you must pick k such that $\binom{n}{k} = \binom{n}{k+1}$

[vital dew]

Zopherus:

[faint narwhal]

which is not true for all k

[weary tiger]

yes

so with a restricttion on k it would work

ahh

I think david is right about the 2k + 1 thing

[faint narwhal]

Stop just revealing the answers

[weary tiger]

so n + 2k + 1

[faint narwhal]

Let them figure it out

[lean creek]

alright

Zoph I have a question

[faint narwhal]

Shoot

[lean creek]

need to work through these

[faint narwhal]

what have you done

[lean creek]

just starting out and getting my head around the topic, brainstorming for now

I know 3 is true (fairly sure right, since topological minor is homeomorphic)

I feel pretty sure (?) that 1 & 2 are true as well

since subgraph seems like it can be fairly analogous to minor relation for most (?) intents and purposes (if not all, unsure if there might be a good counterexample...)

in which case it would be just asserting graph minor theorem

and #2 would just be special case of #1 i.e. Kruskal tree theorem

[faint narwhal]

Well, proving that things are well-quasi-ordered takes a few things

[lean creek]

yeah, something something with progressions

and show that I can find at least one pair that is increasing (I believe)

I feel like #4 is false

since it doesn't necessarily preserve "orientation"

[faint narwhal]

What do you mean by orientation

[lean creek]

I'm thinking specifically of a tree case

where I specify the root

but I might be able to embed the tree such that what started as the root no longer remains the root

not completely sure...

[faint narwhal]

Hm yeah, I need to sleep so can't think about this much, but it seems likely that 4 is false

I'm not sure about what you're saying though

[lean creek]

not sure either, will think about it more for sure

yep, all good, get some rest

[weary tiger]

thank you for the help

[lean creek]

yep np

@faint narwhal ah here's a better explanation of what I meant: since it's a subgraph relation (not induced), I get to choose which edges I retain. So vertices that were increasing in distance away from the root in the original tree, once I embed it, I can choose edges which retain the overall "structure" of the tree, but which invert the ordering of the vertices

[lean creek]

I think

[weary tiger]

can anyone tell me how to use the well ordering principle to prove mathematical induction

[sleek swallow]

Hmm? You want a proof given to you? Maybe google it and post the parts of it that you don’t understand over here?

If you just want to construct the proof on your own, here are 2 hints:

1. State the exact forms of the well ordering principle, the principle of mathematical induction.

2. Let P(n) be a statement that you want to prove about the positive integers, given that you know that:

   a. P(1) is true
   b. For all n, P(n) => P(n+1)

Let S be a subset of the positive integers that contains all the elements such that P(n) is false. (We’re proceeding by contradiction).

Then, show that S is empty if all the conditions that we’ve stated are true.

[weary tiger]

wait what?

okay i understsand the a. b.

[sleek swallow]

Yeap, those are the conditions for induction to hold, yes?

[weary tiger]

so I understand 2 in general

yes

[sleek swallow]

Okay, what’s the well-ordering principle?

@weary tiger Make sure you state it exactly as it is.

[weary tiger]

Given any two distinct integers x and y we know that we must have either x < y or y < x however this is also true if instead of being integers, x and y are rational numbers or real numbers

[sleek swallow]

? Haha let’s make it work a little more in our favour, yea?

It states that every non-empty subset of the positive integers contains a least element. That’s what will be super useful for us.

So, going back to our argument above, if we let S be the subset of the positive integers such that P(n) is false, then we can see that it must have a least element, yes?

[weary tiger]

byu least element you mean like an element with the lowest value

[sleek swallow]

Yes

So far, so good?

[weary tiger]

I dont get out P(n) being false means we must have a least element

[sleek swallow]

No no no.

We’ve defined S to be a subset of the positive integers such that P(n) is false. By the Well-Ordering Principle, S must have a least element because it’s a subset of the positive integers.

So, S is a subset of the positive integers => S has a least element

[weary tiger]

ahh okay so the subset S is a subset that make P(n) false

and because of the well ordering principle it must have a least element

[sleek swallow]

Yes.

[weary tiger]

alright I follow

[sleek swallow]

Let’s call that least element m.

[weary tiger]

m in Z+

yes?

[sleek swallow]

Now, we know that P(m) is false, correct?

P(m-1), then, has to be true. If it wasn’t, then m-1 would belong to S and would be the least element.

[weary tiger]

since P(n) is false all values of P are flase

so yes

[sleek swallow]

However, we also know that P(m-1) => P(m) is true. That is, the conditional is true. That means that P(m) must be true.

So we have shown that P(m) is true and false at the same time. That’s a contradiction.

[weary tiger]

wait P(m - 1) => P(m) is mathematical induction

[sleek swallow]

Hence, S has no least element. Since S has no least element, it must be empty.

[weary tiger]

so we can know that cause arent we trying to prove that?

[sleek swallow]

No. That’s an assumption, you see.

The thing that we’re trying to do is to show that if the following holds:

1. Well ordering principle
2. P(1) is true
3. P(n) => P(n+1)

Then, P(n) must hold.

[weary tiger]

or is it just obvious that we can say we know that?

[sleek swallow]

For all positive integers

[weary tiger]

okay okay continue

thanks for the help btw

my prof gave me a hint that it is likely this is a bonus q on the final so that is why i am trying to understand it '

[sleek swallow]

So, S is empty. If S is empty, that means that there are no integers that exist such that P(n) is false, assuming that all the conditions above are true.

[weary tiger]

there for p(n) is always true?

if all the condition above are true

[sleek swallow]

Therefore*

Yes

Remember, the three conditions that we assume to be true are:

1. Well ordering principle
2. P(1) is true.
3. P(n) => P(n+1)

Then you must show that P(n) holds from all three of those by way of contradiction.

[weary tiger]

so I state that there exist a positive intger set S such that P(n) is false

and because S is a set of postive integer i must have a element m with the lowest value

and since P(n) is false for the set S

P(m) is also false as m is in S

but since m is the lowest value element in S we know that m - 1 is true since it is not apart of S

and since we assumed number 3

[sleek swallow]

1. Let S be a subset of the positive integers such that P(n) is false.

2. If S is a subset of the positive integers, it must have a least element. We call that m.

3. P(m) is obviously false. P(m-1) has to be true by virtue of (m-1) not being in S. If it was, it would be the least element.

4. We know that P(m-1) => P(m) for all integers.

5. Hence, we have shown that P(m) has to be true. But we just said that it was false. Hence, it is true and false at the same time and that is an absurdity.

6. Hence, S cannot have a minimal element and so, it is empty. This proves that P(n) holds for all integers.

[weary tiger]

we know that P(m) must also be true resulting in a contradiction

[sleek swallow]

Your phrasing is off but you have the right idea. Just remember that a number cannot be false. That’s in reference to “m-1 is true”. A statement about a given number can be false, though.

[weary tiger]

i will rephrase that

P( m - 1) is true

[sleek swallow]

Yes. Be very clear about your phrasing. I don’t think your professor expects an excessive amount of formalism in your proof. Your class should be pretty basic, right?

[weary tiger]

so this is a method in which the well odering principle proves mathematical induction right?

yes it is an intro

class

[sleek swallow]

Yeaaa it is lol

That’s what I spent the past 20 minutes doing lol. You must make sure that you’re convinced by the argument presented

[weary tiger]

we can also use mathematical induction to prove the well ordering principle right?

[sleek swallow]

Yes, they are equivalent

[weary tiger]

yes that would be useful for future classes although my prof advised that since the exam is coming up if you still dont understand something make sure to atleast memorize then

thanks for the help btw

[sleek swallow]

Haha I’d say that that’s bad advice lol.

I’d rather fail the exam than go in having memorized stuff for it

Oh well

Yea no worries, just ask questions anytime

[weary tiger]

this is a proof by contradiction yes?

[sleek swallow]

Yes

[weary tiger]

so we assume that mathematical induction is fale

false*

[sleek swallow]

Now, you can try proving the well ordering principle from the principle of induction using a proof by contraposition.

Yes, we assume that induction doesn’t hold

Then we show that it leads to an absurdity

[weary tiger]

alright this makes sense thanks for explaining

[sleek swallow]

That, then, forces us to accept that induction must be true

Sure 🙂

[weary tiger]

Can anyone tellme w why f is true

[sour arrow]

The empty set is a subset of every set

[weary tiger]

yes

[stray reef]

$\varnothing \subseteq \text{anything}$

[vital dew]

Ann:

[sour arrow]

But also {empty set} contains the empty set

[stray reef]

that's d, kaynex

[sour arrow]

Oh yeah, tru

[weary tiger]

what is the difference between c and f

well I know the {} is the difference

since c is false

[stray reef]

$\subseteq$ is subset, $\subset$ is proper subset

[vital dew]

Ann:

[stray reef]

judging by the fact that your problem uses both of these symbols

$A \subset B$ iff ($A \subseteq B$ but $A \neq B$)

[vital dew]

Ann:

[weary tiger]

yes

I am aware of this

proper subset is only if there are some element in A that are not in B

[stray reef]

so?

what's the issue then?

[weary tiger]

c is

not subset

it is proper subset without the brackets

wait

[stray reef]

no see the thing is

[weary tiger]

is

f true since

there is also like the symbol empty set

plus empty set

[stray reef]

...

[sleek swallow]

We had a discussion about this very thing yesterday.

[stray reef]

i feel like there's a fundamental misunderstanding at play here

[weary tiger]

can we say 0 is the symbol for empty set since I dont know how to type the actual one

[sour arrow]

Oh I see.
∅ is a set that contains nothing.
{∅} is a set that contains another set.

[sleek swallow]

Okay, here's the thing about the subset relation.

If A & B are sets, then A is a subset of B iff x E A => x E B, for all x belonging to A.

Let C be the empty set. Then,

C is a subset of {C} iff x E C => x E {C}, for all x E C

The thing is, x E C is always FALSE.

So, we have an implication that has a false antecedent. Hence, the implication is true by ex falso quodlibet. The idea is that you can prove anything from a false antecedent.

@weary tiger

[weary tiger]

∅ = {}

while

{∅} = {{}}

makes sense

if this is the caser

[sleek swallow]

Uh yea, if ya want to think of it that way.

[sour arrow]

Yis. ∅ is not the same set as {∅}

[sleek swallow]

You can prove that the empty set is a subset of any set by using the argument I gave above.

An intuitive way to think about it is that a box containing an instrument is not the same thing as the instrument. They're related but not the same. So far so good?

[weary tiger]

can anyone tell me why h is true

@sleek swallow yeah I get it so far

[sleek swallow]

Well, okay, think about what C intersection D represents.

[weary tiger]

for example

{{q,w, e}} is different then {q, w, e}

[sleek swallow]

Yeap.

[weary tiger]

just like {q} and q are different

also C intersect D means in this case

[sleek swallow]

Look at the information you've been given and think very hard about C intersection D. Wht does it mean?

[weary tiger]

basically just 4n

since it is what is same in 2n and 4n

that is just 4n

[sleek swallow]

C is the set of all integers that are divisible by 2. D is the set of all integers that are divisible by 4. What would their intersection be?

[weary tiger]

set of all integers divisble by 4 no?

[sleek swallow]

Right, so it's the set of all integers that are divisible by 2 & 4. Now, what does B represent? The set of integers that are divisible by 8, right?

Now, is 4 divisible by 2 and 4?

[sour arrow]

That's Cbar, which I assume is the complement of C

[weary tiger]

intersect is something that is same in both

@sour arrow yes

[sleek swallow]

Oh right my bad, I didn't see that C bar.

Okay, so C bar is the set of all elements that are not divisible by 2. The intersection of C bar and D is?

[weary tiger]

before we get to the C intersect D is just 4n right

since

C contains {.... 2, 4, 6, 8....} and D contains {...4, 8...}

[sleek swallow]

Yea, C intersection D is just D.

[weary tiger]

so C bar is everything that is not divisble by 2 so odd numbers

[sleek swallow]

Yes. So, what's the intersection of Cbar and D?

[weary tiger]

nothing

empty set

[sleek swallow]

It's empty.

[weary tiger]

yes

[sleek swallow]

So is the empty set a subset of B?

Or Bbar?

[weary tiger]

it B bar and yes it is

so it make sense

I wasnt thinking of empty set thats where I messed uo

I though since it was nothing it was not a subset of B

ty!

[sleek swallow]

Go back and prove all set-theoretic statements that have been discussed in your class

That will help you more than just grinding through problems. You need to be familiar with the theory so you can do problems.

[weary tiger]

I think that this chapter on set is the one I am most confident on

but yes I do plan on going through the definition and statments of all chapters

[sleek swallow]

Yes, please do that. It'll be very important to get a good grasp of how everything works.

[weary tiger]

Can some one explain to me what is going on here

This is the question being asked

[sour arrow]

@weary tiger
Still looking for it?

[weary tiger]

when I got part a using a diff method as this was an assignment from earlier but yeah I still have no idea what the ta is doing here

[sleek swallow]

Urm still stuck on it, I assume?

[fossil otter]

what part confuses you in the proof?

[daring bane]

need to find out how many nonisomorphic graphs with vertices deg (3,3,3,3,3,3,2)
i found out that this is graph of 7 vertices and 12 edges
I used this formula to estimate at least how many graphs can i construct with these requirements
2^(nr. of vertices choose 2)
than i divided by n! and got that i can draw at least 417 non-isomoprhic graphs
but these aren't following the requirements of the vertices deg,

So how do i see how many of these graphs have 12 edges

[pale epoch]

shouldn't the graph have 8 vertices

if there is 8 numbers in the degree sequence

also, have you tried drawing the graph

see what you notice if you do

@daring bane

[daring bane]

Yes i have tried here is how it looks like

@pale epoch i have added one three mistakenly in the degree sequence

so the correct one is (3,3,3,3,3,3,2)

as in the picture

[pale epoch]

well, that makes it harder

i'll try to think of something

[daring bane]

@pale epoch If you want I can provide another case which may be easier

[pale epoch]

i mean, both examples this is the only graph up to isomorphism

you just have to find a good argument

for the second case, you can delete the vertex with degree 6

and get C_6

for the first graph you can argue similar

[daring bane]

ok thank you @pale epoch

[rapid herald]

hey

i have a question about the a* search

so the heuristic value, can it be much smaller than my edge paths?

or does it have to be similar, for ex my edge paths are all have a value of 100+, and for the heuristic i measured the literal straight line distance of it to the goal node on my computer

so the paths have a giant value whilst the heuristic value is like 9 or 10

does that make any difference?

<@&286206848099549185>

plz help

[rapid herald]

does anyone here know the a* search algorithm??

[fossil otter]

wait i think im wrong one sec lemme fix

[vital dew]

potapeno:

[fossil otter]

In your case the straight line distance satisfies this equation by the triangle inequality @rapid herald

[rapid herald]

so it has to be either an underestimate or equal to the smallest path?

[fossil otter]

i dont know if that answers your question

basically it has to be an understimate of the actual path

[rapid herald]

of the actual shortest path

right?

[fossil otter]

yeah

[rapid herald]

perfect, so the whole point of it is to avoid it from going to as many tangents as dijkstra does

[fossil otter]

exactly

[rapid herald]

yeah, makes complete sense

ty

[fossil otter]

the heuristic is to make it tend towards to actual solution

[olive dragon]

Hello, could someone please help me with some questions:

I found this:

Is there another way of solving this problem?

[obtuse lance]

have you heard of fermat's little theorem?

[olive dragon]

no

[obtuse lance]

it's pretty straight forward, if you have two relatively prime integers, like you do, then

$a^{p-1} \equiv 1 \mod p$

[vital dew]

Merosity:

[obtuse lance]

p being a prime number

11 and 17 are both prime so it works out fine

since you want the inverse,

$a^{p-2}*a \equiv 1 \mod p$

[vital dew]

Merosity:

[obtuse lance]

just separate this by exponent rules

notice, since that something multiplying a gives you 1

that means it's the inverse

this isn't the most efficient way either, but it is more direct than just checking everything

[opal crescent]

well you'd still have to find 10^15 mod 17

[obtuse lance]

there are some shortcuts I was considering offering, but I think they left

[opal crescent]

extended euclidean algo is quite ok here also

[olive dragon]

I'm watching a video on fermat's little theorem on YT

It doesn't seem like a nice method to solving this but doesn't hurt to learn

Mind giving an example using inputs from (a)? @opal crescent

It is easier to learn from examples rather than a general formula

[opal crescent]

finding an inverse mod 11 of 4 is equivalent to solving the diophantine equation 4x-11k=1

since 4 and 11 are relatively prime, a solution exists to this eq, and extended euclidean algo is gonna give us one

lemme type it up now

$$11 = 4 \cdot 2 + 3$$ $$4 = 3\cdot 1 + 1$$

[vital dew]

emeric75:

[opal crescent]

thought it would be longer lel

so yeah gcd(4,11)=1 what a surprise

and 1 = 4-3 = 4-(11 - 4 * 2) = 4 * 3 - 11

ie 3 is an inverse of 4 mod 11

[olive dragon]

Honestly, thats how we did it in class and working backwards gets me confused all the time.

[opal crescent]

well i used to be confused also lel

so yeah it's not that quicker than just going through the multiples with 4 mod 11

but god it's so much easier for the other one

[olive dragon]

Yes, this is the best method. I will try to learn "working backwards" part

Thank you very much though

[opal crescent]

well actually the multiples way is faster in this case also

cause instead of recalculating the multiple each time like you did

you could just add 10 to the result from the previous multiple

reduce mod 17

but yeah for bigger numbers it becomes long also

[olive dragon]

Yes, if theres a big number, I don't want to be doing all that

[opal crescent]

exam: find an inverse of 101 mod 257

[olive dragon]

[olive dragon]

I'm trying to work this out with inputs from (b) a=10, m=17
Answer should be 12 but I don't get it

17 = 10x1+7
10 = 1x7+3

Are you still here @opal crescent ?

[opal crescent]

why 2x5

you should divide by 7

[olive dragon]

10 = 10x1+0

[errant bear]

1x7 + 3?

[olive dragon]

wow

okay now where to go from here:
17 = 10x1+7
10 = 7x1+3
to get to 12

[opal crescent]

need some sleep?

[olive dragon]

definitely

[errant bear]

change 17s division

[opal crescent]

well you didn't finish your euclidean algo

gotta go until your remainder is 1

[olive dragon]

now.. am I dividing 1 or 7?

[opal crescent]

7 by 3

if you have a = bq+r, you get that gcd(a,b) = gcd(b,r)

that's the basis of euclidean algo

[olive dragon]

a = 10, m = 17

17 = 10x1+7
10 = 7x1+3
7 = 3x2+1

Work backwards with remainders:
r1 = ((1)7-2(3))
r3 = ((1)10-1(7))
r7 = ((1)17-1(10))

1 = 1(7)-2(r3) = -2(10)+3(7)
1 = -2(10)+3(r7) = 3(17)-5(10)
1 = 3(17)-5(10) = 0 + (-5(10))
if # in 1=3(#) match mod, stop and evaluate.
3(17) = 0
-5(10) #10 is = a from the start and -5 is the inverse
or add mod 17 to get positive inverse of 12

1 = 1(7)-2(1(10)-1(7))=-2(10)+3(7)
1 = -2(10)+3(1(17)-1(10)) = 3(17)-5(10)
1 = 3(17)-5(10) = 0 + (-5(10))
-5 is the inverse or if +mod17, the inverse is 12!

@opal crescent thank you

[errant bear]

when going from line 2 to 3, why b only distributed to the last term, b^k

shouldnt there be 2 sums

or is it just not listed out

[obtuse lance]

not sure how you're thinking in your mind, but there are only 2 "overflow" terms, a^k+1 and b^k+1

the rest pair up

[errant bear]

dont we have uh

let me write it

[obtuse lance]

https://prnt.sc/q81s2c

maybe this helps to see

what's being grouped together

the resulting a^k b term comes from a^k and a^{k-1}b

depending on if you give it b or a

[errant bear]

oh wait

yeah i was ignoring the distribution

is this right?

[obtuse lance]

,rotate

[obtuse lance]

idk what's your doubt?

write some indices in there for starters

[errant bear]

oh yeah one sec

[obtuse lance]

too vague and sheisty to say otherwise

[errant bear]

k to n

give me a bit

[obtuse lance]

about to cook dinner, so you have more than a bit I'm afraid lol

[errant bear]

ok thx lol

[errant bear]

fairly messy, sorry

this finishes the proof, right

@obtuse lance

[obtuse lance]

I feel like it would be easier for me to type up the solution myself and you check that it's the same as what I wrote lol

nevermind I started typing it and realized that's also not fun

ok that looks good

[errant bear]

lmao ok thanks

[errant bear]

what does showing a function is continuous prove

injectivity not surj right

[wooden spear]

Neither

[errant bear]

uh

how so

[wooden spear]

Are you talking about functions from $\bR$ to $\bR$?

[vital dew]

Icy001:

[errant bear]

yea

[ivory badge]

x^2 is neither injective nor surjective

[wooden spear]

hm so $x\mapsto x^2$ is continuous but is neither injective or surjective

dammit

[vital dew]

Icy001:

[ivory badge]

s n i p e d

get fucked kiddo

[errant bear]

F

[wooden spear]

[errant bear]

wait

he used the deriv to show something though

our prof

[wooden spear]

I have an idea what he might have shown

$f'(x)>0\cndall x\in\bR\implies f$ is injective

[vital dew]

Icy001:

[errant bear]

oh yeah, increasing deriv + ivt implies injectivity

right?

[wooden spear]

I don't think you need ivt

[errant bear]

hmm ok but thanks

[wooden spear]

I just thought of the proof and it does use the mean value theorem but then again I can't think of a counterexample on a space that isn't connected... oh wait

Ok you do need ivt

Let $X=\bR^-\cup\bR^+$ and consider a function $\func f X \bR$ defined separately to be increasing on the two parts

there's no reason it has to be injective

[vital dew]

Icy001:

[errant bear]

ok makes sense

so to prove surjectivity here, i would need to show that any y in R can be expressed from a single x in -1 to 1

i dont know how to do that though..

[wooden spear]

I think you can take a shortcut as follows

look at the limits as x approaches -1 and 1

and then use the intermediate value theorem

Wait...

wait a minute

This is not bijective at all

I don't think 2 can be represented

If $f(x)=2$ then $x\geq 0$ because the $x<0$ portion is clearly all negative

[vital dew]

Icy001:

[wooden spear]

Meanwhile, $0<\frac{x^2}{1+x^2}<1\cndall x\in\bR^+$

[vital dew]

Icy001:

[wooden spear]

You can fix this by replacing 1+x^2 with 1-x^2

in both parts

Then I confirmed it is bijective

[errant bear]

the domain of the original function is also -1 to 1 right

[wooden spear]

ya

[errant bear]

aka the same as the image

[wooden spear]

Well no

the function was defined as having codomain $\bR$

[vital dew]

Icy001:

[wooden spear]

so to be bijective, its range has to be $\bR$

[vital dew]

Icy001:

[errant bear]

right

[wooden spear]

Ah yes the other way to fix it is to change the codomain to $(-1,1)$

[vital dew]

Icy001:

[errant bear]

i get that mixed up

[wooden spear]

Then it will go back to being bijective I think

[errant bear]

so if i do that, or switch the + with a -, then i can take the limits and use that and ivt to show that there will exist a unique x in (-1,1) that gets mapped?

[wooden spear]

Not necessarily unique

[errant bear]

right

[wooden spear]

but uniqueness was proved by your proof that it's injective

[errant bear]

uniqueness comes from injectivity

[wooden spear]

yes

[errant bear]

ok got it

[wooden spear]

Surjectivity: $#f^{-1}(x)\geq 1\cndall x$

Injectivity: $#f^{-1}(x)\leq 1 \cndall x$

[vital dew]

Icy001:

[errant bear]

what does pound sign mean

[wooden spear]

size of a set

[errant bear]

oh cardinality

[wooden spear]

yep

I like how that formula unites the concepts of surjectivity and injectivity, whose definitions look so different from each other

[errant bear]

i had this in my notes

where u use inject and surj to get bijec cardinality

[wooden spear]

The difference between your notes and my formulas are that the implications in your notes only go one way

but mine are equivalences

for example injective implies $|A|\leq|B|$ but $|A|\leq |B|$ isn't enough to tell you that $f$ is injective

[vital dew]

Icy001:

[errant bear]

that makes sense

uh last question as i go over earlier reviews

i need to find functions h, k st neither are constant but h • k and k • h are contant

i was thinking the characteristic function might work but it doesnt

and same with inverses

[wooden spear]

an idea is to make them constant over certain ranges but not others and then have the image of each of them not land in the range where the other is non-constant

[errant bear]

hmm

[wooden spear]

so in fact your characteristic function can work

but you just have to add a constant to one of them

[errant bear]

hmm alright give me a bit

yeah the characteristic would work but i didnt realize what was going on, or what i needed to do in that making the outputs of each function fall into only 1 catagory of the other

also i was initially trying to make them equal

[fossil otter]

i have seen those inj/surj equations before, those are extremely nice

[dusky silo]

hey, struggling with this proof

after the induction step i got:
6 + [ (k+1)^2+4(k+1)+6 / 2^(k+1) ] + [ (k+1)^2 / 2^(k+1) ] = 6

so i guess according to me everything after 6 + and before = should all = 0?? but that doesnt make sense, so any idea where im going wrong?

[opal crescent]

well you don't have a sum with the n^2+..../2^n that's quite the problem

what are you trying to show ? @dusky silo

[dusky silo]

okay so for subbing in k for n, we assume all of that = 6 right?

i assumed after that you just sub in (k+1) everywhere there was an n and showed that that too would = 6 oops

[opal crescent]

well you assume $$\frac{k^2+4k+6}{2^k} + \sum_{j=1}^k \frac{j^2}{2^j} = 6$$ for some $k$ yeah

[vital dew]

emeric75:

[opal crescent]

and wanna show this holds for k+1

ie

$$\frac{(k+1)^2 + 4(k+1) + 6}{2^{k+1}} + \sum_{j=1}^{k+1} \frac{j^2}{2^j} = 6$$

[vital dew]

emeric75:

[opal crescent]

what you did is like saying $$\frac{(k+1)^2 + 4(k+1) + 6}{2^{k+1}} = \frac{(k+1)^2 + 4(k+1) + 6}{2^{k+1}} + \frac{k^2+4k+6}{2^k}$$

[vital dew]

emeric75:

[opal crescent]

you treated that thing as if it was being summed over

but it's not

so now yeah

how could we go from that to (k²+4k+6)/2^k

[dusky silo]

wait what do you mean by 'that' :p

the red circled bit?

[opal crescent]

(the thing i circled in red)

[dusky silo]

idek i expanded it and got k^2 + 6k + 8

for the numberator, i thought youd be dividing everything by 2 or something but numerator / 2 doesnt result in (k²+4k+6)

[opal crescent]

wait you mean k^2+6k+11

anyway yeah if you expand you'll get $$\frac{k^2+6k+11}{2^{k+1}}$$

[vital dew]

emeric75:

[opal crescent]

which is just $$\frac{(k^2+4k+6) + (2k+5)}{2^{k+1}}$$

[vital dew]

emeric75:

[opal crescent]

right?

[dusky silo]

yepyep

[opal crescent]

now let's put things together a bit $$\frac{(k+1)^2 + 4(k+1) + 6}{2^{k+1}} + \sum_{j=1}^{k+1} \frac{j^2}{2^j} = \frac{(k^2+4k+6) + (2k+5)}{2^{k+1}} + \sum_{k=1}^n \frac{j^2}{2^j} + \frac{(n+1)^2}{2^{n+1}}$$

[vital dew]

emeric75:

[dusky silo]

okAY i actually got it but man that was way above my paygrade

[opal crescent]

ok noice

[dusky silo]

thank you for the help haha idek how ill do that in like ~5 minutes but eh

[opal crescent]

was drinking coffee at the same time lel

[dusky silo]

^^

[opal crescent]

👌

[errant bear]

alright

only q on the final i wasnt feeling good about

so we were asked to find how many possible binary strings of length 10 exist such that each string starts and ends with 1, and has exactly three 0's in between

isnt the part about the endpoints irrelevent and the answer 8C3

[obtuse lance]

yup you got it

[sleek swallow]

It’s not irrelevant lol. If that condition wasn’t there, the answer wouldn’t be 8C3.

[obtuse lance]

well if the ends had been other stuff it wouldn't matter in that sense

like if it started with 11 and ended in 00 and was of length 12, etc etc same answer

[sleek swallow]

Yea

[errant bear]

i mean if it was like has atleast one end char is a 1

then the ans would be 3 x that

but alright, ty

Fuck me

one of the qs was asking to define countably infinite

i originally put that a set is countably infinite if it is equipotent to N

then crossed that out and put a countable union of subsets

cuz i thought that that definition is circular

[orchid jasper]

How do I show that the maximum number of elements in a matching is

If

G is a bipartite graph with bipartition (A, B)

$$|A| - \max_{C \subseteq A} (|C| - |N(C)|)$$

[vital dew]

ratsella:

[wooden lotus]

ok 95% both of these are not bipartite. Can someone just check for me? I feel like I am dumb because I feel like hw would have at least one be bipartite.

[pale epoch]

you are right

but you should justify your answer, so why do you doubt yourself

[wooden lotus]

just because usually homework likes to test proficiency

so you would expect at least one answer to be true

[pale epoch]

hm, i wouldnt

[wooden lotus]

I did justify, but sometimes I just worry about really dumb mistakes

aight cool

[dusky silo]

two questions about this:

1. why are the only sums you can make starting from a1 ? couldnt you start a sum from a2?
   and 2. why are there (n-1) distinct remainders possible with the sums they listed?

[obtuse lance]

it doesn't really matter what order you make the sum in

there are n-1 distinct remainders because you're imagining the worst case scenario

where none of the sums are divisible by n

if one of them is, then the thing you're trying to prove is true

but even when none of those sums are divisible by n, you still get the result that there's a sum divisible by n

[dusky silo]

okay following up until the last line, not sure what that bit means though like

if none of S1, S2,... Sn are divisible by n then one of them is divisible by n? wat

[jagged grove]

im having trouble proving this one

[obtuse lance]

no, if none of them are divisible by n then you have two of those sums with the same remainder when divided by n. So you subtract the smaller sum from the larger sum, since it contains all of its terms. @dusky silo

@jagged grove show your best attempt at it

[jagged grove]

ok gonna get pen and paper

brb

[dusky silo]

OHH dude that took me a minute to wrap my head around, tysm ! @obtuse lance

[obtuse lance]

yeah it's weird lol

[jagged grove]

there

@obtuse lance

[obtuse lance]

sec lemme see

base case looks good lol

[jagged grove]

im probably not representing the sum correctly

its what i think

[obtuse lance]

kind of hard to follow but I sort of see what you're doing

$1^3+2^3+\cdots+n^3 = (1+2+\cdots+n)^2$

[vital dew]

Merosity:

[obtuse lance]

you assumed that was true right

[jagged grove]

yes

[obtuse lance]

hmm would it be cheating if I just show how I'd do it?

[jagged grove]

its not a homework

[rigid oriole]

try n = 2???

[jagged grove]

im just doing it cause i want to refresh stuff

[obtuse lance]

$(1+2+\cdots+n+(n+1))^2$

oh ok good

[vital dew]

Merosity:

[rigid oriole]

oh wait 🤔

[jagged grove]

wouldnt that be

[obtuse lance]

I would look at the next term, then expand

$(1+2+\cdots+n)^2 + 2*(n+1)\frac{n(n+1)}{2} + (n+1)^2$

[vital dew]

Merosity:

[obtuse lance]

the thing on the left is what we know, the sum of cubes

[jagged grove]

yes

u want to sum

[obtuse lance]

$1^3+2^3+\cdots+n^3 + n*(n+1)^2 + (n+1)^2$

[vital dew]

Merosity:

[obtuse lance]

simplifying step

again factor out (n+1)^2 to get (n+1) and

done

$1^3+2^3+\cdots+n^3+(n+1)^3$

[vital dew]

Merosity:

[jagged grove]

where did u get

?

[obtuse lance]

I expanded the binomial

$((1+2+\cdots+n) + (n+1))^2$

[jagged grove]

$2*(n+1)\frac{n(n+1)}{2}$

[vital dew]

Merosity:

dandida:

[obtuse lance]

that's the middle term

$(a+b)^2 = a^2+2ab+b^2$

[vital dew]

Merosity:

[obtuse lance]

$$a=1+2+\cdots+n$$ $$b=(n+1)$$

[vital dew]

Merosity:

[obtuse lance]

$a^2 = 1^3+2^3+\cdots+n^3$ is what we assumed for induction

[vital dew]

Merosity:

[jagged grove]

yes

[obtuse lance]

$2ab = 2*(1+2+\cdots+n)*(n+1)$

[vital dew]

Merosity:

[obtuse lance]

$1+2+\cdots + n= \frac{n(n+1)}{2}$

[vital dew]

Merosity:

[obtuse lance]

I maybe assumed you knew this formula but maybe I assumed too much

[jagged grove]

the book did hint at that in the answers

i just didnt knew where it came from

[obtuse lance]

quick way to derive it is

write the sum below itself but backwards

$$1+2+3+4$$$$4+3+2+1$$

[vital dew]

Merosity:

[obtuse lance]

like that

[jagged grove]

ohh

[obtuse lance]

so you have 1+4=5, 2+3=5

etc

so you have 5*4

[jagged grove]

thats neat

[obtuse lance]

but we have done it twice so

5*4/2

in general that's the n(n+1)/2 formula yup

[jagged grove]

well if i said something like it is known that $1+2+\cdots + n= \frac{n(n+1)}{2}$

[vital dew]

dandida:

[jagged grove]

in a test i would have to prove

$1+2+\cdots + n= \frac{n(n+1)}{2}$

[vital dew]

dandida:

[jagged grove]

and then prove the first induction

right?

[obtuse lance]

beats me, I'm not your teacher

I would prove it by induction if I felt like I had to thought

[jagged grove]

i have done that proof before

its literally on my last exam lol

i guess teacher was lazy

rofl

i mean $1+2+\cdots + n= \frac{n(n+1)}{2}$

[vital dew]

dandida:

[obtuse lance]

idk, do what you gotta do for your teacher, I feel like it's not too crazy to use that as a formula

if you have time leftover at the end of your test then prove that by induction too to cover your bases I guess

[jagged grove]

i just want to learn so i can take a real analysis text book

[obtuse lance]

I'd rather just derive the identity for sum of cubes directly

[jagged grove]

and learn analysis

by myself

[obtuse lance]

and then equate them

[jagged grove]

the identity for the sum of cubes?

[obtuse lance]

yeah, well in general you can derive the sum of nth powers iteratively from smaller sums of powers

at least, that's more interesting imo than confirming identities someone else gives me by induction

[jagged grove]

i took those topics in a math for software engineers major

so i bet they just wanted to cover induction

[obtuse lance]

you seem like you're ready to read a real analysis book and learn by yourself

I say just go for it, read a little bit every day and just don't let yourself get discouraged when you get overhwelmed and do a little the next day etc

[jagged grove]

ill just keep doing excersises and come here every now and then

like once each day

i guess that will put me up to speed

[lethal sequoia]

Hey can someone help me with this question: “how many different k cycles (cycles of k length) are there in Sn?” (Only count two k cycles as different if they define different elements in Sn)

I’m not sure how to approach this

I guess I should try different Sn cases and then see whether there’s a pattern?

[fossil otter]

well, how would you construct a k-cycle naively?

[lethal sequoia]

What do you mean naively?

[lean creek]

@lethal sequoia I don't have a solution in mind off the top of my head, but I've been doing similar proofs in my class as well so I have some ideas to help you brainstorm strategies

Check out Menger's theorem for identifying vertex disjoint paths

and you can partition a cycle into two "arcs" which you can obtain via menger's

and then rejoin the arcs to form a cycle

[pale epoch]

pretty sure this question is about cyclic permutations in the group S_n, not cycles in a graph?

[lean creek]

oop my bad

I've been so focused on graph theory recently I'm just primed to see it everywhere haha

[fossil otter]

its a lot simpler than graph cycles

i dont really know how to help with the question without just giving the answer

i can do an example with S3 i guess

consider 2 cycles in S3

lets list all "naive" 2 cycles

(12),(13),(21),(23),(31),(32)

but we have double counted, since the cycle (12) = (21)

so we have to divide by 2

@lethal sequoia

we can use similar reasoning for 3 cycles

(123),(132),(213),(231),(312),(321)

in this case we triple counted (123)=(231)=(312)

so we divide by 3

given these cases, think about how many cycles are double counted, and how many "naive" cycles there are

and it should be easy to generalize

[lethal sequoia]

Ah okay, I think I have an idea now. I’ll try something and let you know if I got the answer

Thanks!

[weary tiger]

@jagged grove its quicker to prove the sum of natural numbers formula the gauss way than by induction

[jagged grove]

@weary tiger the exercise explicitly states that u want to use induction

though ill try proving it the gauss way next time

[weary tiger]

have to or want to?

[jagged grove]

https://cdn.discordapp.com/attachments/496785905474994186/653722998821617709/problem_1.52.png

does this answer ur question?

[weary tiger]

oh well i have this exact problem written out funnily enough

[jagged grove]

as i told the guy who helped me with this

just refreshing concepts until to read a analysis book

to read*

[weary tiger]

fk sideways pic

i evaluated the right side directly with the gauss method then used induction to show they are equal

faster than doing induction twice

[jagged grove]

u used the fact the gauss formula is equal to replatinate the problem?

rephrase*

english is not my main language u se

[weary tiger]

yea i just rewrote the sum of naturals squared in another form

and then showed the sum of cubes was equal to that

and to get it into another form i used the gauss method to show what the the sum of naturals was equal to then squared the result

[open glacier]

I am really confused about transitivity

How is this transitive if when i pair up (1,2) and (3,3) i don't have (1,3) ?

wait no

[random basin]

You can't pair up (1,2) and (3,3)

[open glacier]

yeah just clicked that

[random basin]

It has to be (a,b) and (b,c) and (a,c) follows

[open glacier]

thats it - makes sense now

[random basin]

👌

[open glacier]

Word of advice: don't answer questions so fast - people might figure it out in the next 5 seconds themselves ^^ :p

[random basin]

Haha it happens very rarely that I even can answer a question, this was such an occasion.

[open glacier]

How do i form bijection between [4,inf) and (2,10)
Task is to prove equivalence by forming bijection between those sets

[pale epoch]

hint: the composition of bijections is bijective

[open glacier]

composition of bijections
so you're saying that [4,inf) is a bijection
and (2,10) is bijection

[pale epoch]

do you know what a bijection is?

[open glacier]

injective, syrjective

[pale epoch]

so what is "[4,inf) is a bijection" supposed to mean?

[open glacier]

im just confused of what u meant by "bijections"

[pale epoch]

you used the term bijection as well

i mean bijective functions

[open glacier]

sorry english is not my native tongue

[pallid raptor]

Can someone help me with partial orderings :d

pm if this interrupts here

i just need bit of help

[open glacier]

well i have no idea how to go forward

[pallid raptor]

but are those intervals?

[open glacier]

the task says they are sets

[pallid raptor]

but if you combine you just get (2, inf) like number line and that is one to one and goes trough all numbers but idk i have not dealt with this before so retard answer prob

someone pls help me with partial ordering task on my exam that i dont understand even after reading solution

Let Z be the whole numbers, and N the natural numbers, og let for each i element in N, the set iZ given by.

a) Show that the set C is a partial ordered set under inclusion

[stray reef]

do you know the definition of a partial order

[pallid raptor]

yeah

[stray reef]

then check it

you don't even need to know the specifics of C. inclusion is always a partial order.

[pallid raptor]

well i dont see how i have the whole (a, b) (b, a) situation

[stray reef]

A subset of B & B subset of A => A=B. it's a basic fact from set theory.

[pallid raptor]

i am not 100% what inclusion is

[stray reef]

$\subseteq$

[vital dew]

Ann:

[pallid raptor]

i am not sure what inclusion is

is what i try to say

[stray reef]

...

[pallid raptor]

i have like an idea

[stray reef]

do you know what the word "subset" means

[pallid raptor]

yeah

is it all subsets

right?

[stray reef]

h

no

[pallid raptor]

ahh :d

[stray reef]

"inclusion" is just another name for the subset relation

you're asked to show that $\subseteq$ meets all the requirements for a partial order

[vital dew]

Ann:

[stray reef]

which frankly should be almost obvious as they boil down to properties that are easily verified for it

[pallid raptor]

I feel like i have the most problem with understanding the question

but like if something is a subset of a

and that is subset of b and so on

i understand how that is a partial ordering

but i dont understand what the question is doing

with all the iZ and C and things

and what is the set C

is it C that is the partial ordering under inclusion idk

[stray reef]

,,,,

[weary tiger]

I understand how to see if it is one to one

however, how do I check if it is onto?

[glossy star]

check if all integers are hit by it

[pale epoch]

take an arbitrary element and find a preimage or show that there is an element with no preimage

[weary tiger]

so set the function equal to an arbitrary element?

[pale epoch]

essentially

[weary tiger]

so say I set it equal to one, then what do I do

[pale epoch]

solve it

well, in this case you can also look at 3662x^3+9102x first

and try to simplify it

[weary tiger]

I seeee

ty

I got another

"prove 4-c theorem for planar graph without using 3-cycles"

What exactly does this even mean

4 color

theorem

[lean creek]

that question has a wiki page lol

[weary tiger]

thank god

[pale epoch]

yeah, you are not going to prove the 4 color theorem on a homework set

[weary tiger]

it's going to be on the exam

[lean creek]

hilarious

[weary tiger]

omg I can't replicate this

[lean creek]

you must be trolling

[weary tiger]

I'm not

[pale epoch]

there is not even a proof of that theorem that can reasonably be presented in class

[lean creek]

is it open laptop with proof-assist

[weary tiger]

Whatever this means

[lean creek]

kek

[weary tiger]

It's easier right?

[pale epoch]

ahh

ok

[weary tiger]

Ok so that doesn't mean 4 color

[pale epoch]

well, it's a weaker version i guess

[weary tiger]

Gotcha

[lean creek]

yeah so you have 3 forbidden minors it seems

K5, K3, K3,3

[pale epoch]

this can be done using eulers polyhedron formula

which for regular planar graphs still shows 6-colorability

and produces one of the best proofs in all of mathematics, bcs you can prove it imagining a polyhedron in a bath tub that is slowly filled with water

[weary tiger]

i gotcha

[lean creek]

not really sure of a good way to attack this

there's a result by Chvátal (it uses min degree, but chromatic + clique numbers can be related to min degree):

but it only gives subgraphs, not induced

[open glacier]

How do i form bijection between [4,inf) and (2,10)
Task is to prove equivalence by forming bijection between those sets

[gusty bay]

"When a planar graph is drawn in the plane, one can distinguish, besides its vertices and edges, its faces
(more precisely, these are faces of the drawing, not of the graph itself). The faces are the regions into which
the graph subdivides the plane. One of them is infinite, and the others are finite."

Can someone explain this to me?

I'm not really seeing the whole "subdivides the plane" visually

[faint narwhal]

if you draw a graph in paint

and use the bucket tool to fill regions in

those are your faces

[gusty bay]

But graphs can be seen in a 3d way, right

That's why something like a square with 2 diagonals running through it is still planar?

[faint narwhal]

No

Like they say

"When a planar graph is drawn in the plane"

[gusty bay]

Kind of like this @faint narwhal ?

[faint narwhal]

yes

[gusty bay]

Can you explain what the terminology "subdivides the plane" means?

[faint narwhal]

Look at your picture

Look at the different colors

[gusty bay]

I can see how we got f = 4

I just want to know in a technical sense

what that term means

[faint narwhal]

How many different colors you have

[gusty bay]

4

[faint narwhal]

thats it

[gusty bay]

that doesnt help LOL

i'm no longer interested in our calculations

i want an actual definition

4 is not a definition

of faces is not a definition

[faint narwhal]

"How many different colors you have"

[gusty bay]

what do the colors represent

[faint narwhal]

The faces

[gusty bay]

thats a circular definition

faces = subdivides the plane = colors = faces

its ok i think i see it now its fine

so we consider graphs in graph theory to be 2d?

[faint narwhal]

Basically

[gusty bay]

"If the graph is not a tree, it must have a cycle. Take any cycle and delete any edge of the cycle. This
amounts to reducing both e and f by one, without changing v. By induction, the formula is true in the
smaller graph, and so it must be true in the original one as well."

I'm not sure I understand this paragraph?

Why are we deleting an edge of a cycle

Also, if it's true on a smaller graph, why must it be true in the original?

[faint narwhal]

What does drawing back the edge do to the formula

[gusty bay]

In induction we try to prove n+1, why are we just deleting an edge and going to n again?

[faint narwhal]

We're not going to n again

[gusty bay]

We're doing induction on e though

So deleting an edge goes back to n edges?

[faint narwhal]

Yes where we can use our inductive hypothesis

To prove the case for n+1

[gusty bay]

I guess I'm not seeing the logical jump here:

Take any cycle and delete any edge of the cycle. This
amounts to reducing both e and f by one, without changing v. By induction, the formula is true in the
smaller graph, and so it must be true in the original one as well.

[faint narwhal]

What does drawing back the edge do to the formula

[gusty bay]

increases e and f by 1

[faint narwhal]

So why, if its true on the smaller graph, then its also true in the larger graph?

[lethal sequoia]

Guys I need to compute these permutations as a product of disjoint cycles.
(2346)(3425)(54) and (123)(234)(461)

Is my answer correct?
For the first: (1)(2536)(4)
And second: (13462)(5)

I know I should ignore the (1) and (4) in the first. And also the (5) in the second. Just wanted to check if I had the right thinking

[dapper rose]

yes

[lethal sequoia]

Thanks!

I put it in wolfram but it is giving a different answer so I thought it was wrong

[dapper rose]

,w (2346)(3425)(54)

[vital dew]

Display results online and refine query

Requested by EpicGuy4227#1118

[dapper rose]

did you get something like this? because WA treats it as multiplication

[gusty bay]

Is any complete graph with 5 or more vertices guaranteed to be non-planar?

Since it would contain K5?

[wooden spear]

Yes

[gusty bay]

Is there an easy way to know if a graph contains $K_{3,3} or K_5$?

[vital dew]

Momo:

[weary tiger]

can anyone help me with this one?