discrete-math

[bold atlas]

can someone tell me the difference betwee nthese two symbols ?

• and link-+ ?

[brave rock]

It is impossible to know without context.

Clearly they have been defined previously.

Maybe you should read their definitions.

[umbral blade]

After getting the truth values I determined that the logical connective ? is also not associative. So this connective is not commutative and associative? Just want to make sure I looked at this right

[brave rock]

Your answer is correct

Be careful about the way you're phrasing your answer though

it is not correct to say that it is ((not commutative) and assocative) and it is incomplete to say that it is (not (commutative and associative))

[umbral blade]

Well it is not associative and not commutative. The way I phrased it sounds like it is not both but could be one right?

[bold atlas]

V1 is a abelsche group
V2 is a body

[brave rock]

this is exactly what I was going to say, yes

you could also say it is neither, nor :)

[brave rock]

We say "Abelian group" and "field" in English.

$\oplus$ and $+$ in this case are defined on entirely different sets. If $v,\ w \in V$ then it is meaningless to write $v + w$ but it is meaningful to write $v \oplus w$.

[vital dew]

Boytjie

[brave rock]

Does that make sense?

You will see later that there is a requirement that + and \oplus be 'compatible' in some way.

[bold atlas]

i dont rly get it.
Isnt it addition ?

[brave rock]

No.

A field and Abelian group alone defines what 'addition' is. Internally, this 'addition' could look very wild, and not be the addition that we think of for real numbers

[bold atlas]

how is the "addiiton in circles" called?

i think i need to read something about it to udnerstand

[brave rock]

Do you mean addition in modular arithmetic?

[bold atlas]

i mean the symbol

[brave rock]

It does not mean anything

We are saying that it is some operation – and it could be a lot of different things – such that along with V it forms an Abelian group.

Are you familiar with the concept of an Abelian group?

[bold atlas]

i know the condition of abelian group

[brave rock]

OK, so \oplus is just the operation of some Abelian group V. So you should know that it does not refer to one particular thing.

Is that clear?

I made a slight typo, I meant to write V instead of K.

[bold atlas]

i think yes

[uncut herald]

Boyt is this a way to solve the 500 integer age people problem

[brave rock]

it doesn't make sense to me I'm afraid.

Your first solution was the one I had in mind.

[uncut herald]

This is the method I saw for a similar problem but I couldn’t see how it relates to the matrix thing

I’m using the formula for compositions in the second one

[brave rock]

You find two things with the same value, rather than the value you want, then combine them in some way to get the value you want.

[uncut herald]

Saying there’s a finite amount of compositions mod 500 that aren’t 0 and we must repeat some

[cobalt tartan]

posted it in the logic and proofs channel!

idk how to discord

[umbral blade]

Is there a logical equivalence rule that i can use to simplify the inner those in parenthesis:

(¬p ∨ r) ∧ (¬q ∨ r)

what is the rule to simplify ¬p ∨ r to p --> r and ¬q ∨ r to q --> r

[inner otter]

yes, I can't remember the name though. maybe a form of DeMorgan's laws or something?

[inner otter]

"p --> r" is equivalent to "~p v r". I don't remember if it's a "rule" or is true by definition or what

[inner otter]

actually just look up distributivity

[umbral blade]

I found this online

I have to name each step during simplification

What could I name it

[worthy violet]

I’m looking for metrics that could be useful for quantifying the "connectedness" (I'm using this word informally) of graphs. I don’t know a lot about graph theory but the problem I am working on can be translated into a comparison of simple undirected graphs that can be either connected or disconnected, where the number of nodes is always the same. The only metric I've looked at so far is the total number of edges.

[inner otter]

sorry I don't remember all the names

[umbral blade]

Oh I’m just talking about the first one

If you know

[inner otter]

not sure, but see these: https://math.libretexts.org/Courses/Monroe_Community_College/MTH_220_Discrete_Math/2%3A_Logic/2.5%3A_Logical_Equivalences#Properties

[umbral blade]

I am trying to figure out how to simplify using logical equivalences: (¬p ∨ q) ^ (¬r ∨ s) is logically equivalent to (pVr)-->(qVs)

What would be the next step for simplification using logical equivlances I dont see how any of the laws I know apply to this next step

[haughty garden]

Try applying the distributive law twice

[bold atlas]

can you show an operation with oplus ?

[brave rock]

It's maybe not clear to you, so before I give you examples of Abelian groups, I will stress again that \oplus does not refer to any particular operation.

Anyway, here is an example of an Abelian group.

[vital dew]

Boytjie

[brave rock]

Here is another example.

[vital dew]

Boytjie

[brave rock]

Here is a final, general example.

[vital dew]

Boytjie

[bold atlas]

so \oplus is a placeholder for a operation that has to be defined ?

it can be anything ?

[uncut herald]

Anything commutative

[bold atlas]

and this circle with a dot ?

couldnt find it here
https://en.wikipedia.org/wiki/Glossary_of_mathematical_symbols

[brave rock]

In latex it is \odot

It is, again, not referring to anything specific.

https://detexify.kirelabs.org/classify.html

[uncut herald]

This seems like abstract algebra not discrete math ngl

Lol

[quiet tendon]

is it possible to ask question about graph theory here?

[inner otter]

yes, look at the channel description

[brave rock]

Just ask. If you end up posting in the wrong channel, people will just tell you where to post.

[quiet tendon]

I was wondering how do I know the first two are isomorphic

I know hte definition but I meant like how do I see it so fast

[little prism]

seeing whether two graphs are isomorphic is hard

[quiet tendon]

ahh but my teacher saw it

I guess he knew the answer beforehand

[brave rock]

It is not at all easy to see which of these are isomorphic

As Dena suggests, it's very hard in general

[little prism]

NP-complete iirc

[quiet tendon]

what is np-complete

[little prism]

"hard problem"

[brave rock]

I just looked it up and wikipedia at least says it's unkown whether or not it's np-complete

But I think it's still fair to say: it's very hard

[little prism]

ok then I'm misremembering. but yeah, hard problem

[quiet tendon]

I have another question I have to draw every non isomporphic graphs with 4 points

but isn't that alot of graphs?

[brave rock]

Not too many

[quiet tendon]

these are the ones I came up with

but how do I know if I am missing one

[brave rock]

You think of a systematic way to check

[quiet tendon]

ye so u mean smth like first u do all 4 dots beside eachother then the squares?

but isn't there a formula to check the amount of possible non isomorphic graphs for a given amount of vertices

[brave rock]

There isn't one that I'm aware of.

I think you should try and come up with your reasoning independently.

[quiet tendon]

I tried I think I got all them

does anyone know what is meant by incident?

[brave rock]

"incident" means "occurs on"

it's a term borrowed from geometry

we might say that "the point x is incident on the line L"

Here they give three synonyms for the terminology, so it should be clear what they mean.

[quiet tendon]

I see thanks

[quiet tendon]

he says that the amount of edges are nC(2) or (n * (n-1)) / 2 I understand the second one but I don't see how u can come up with nC(2)

the picture was just an example

[brave rock]

An edge is uniquely determined by the vertices it connects, so an edge corresponds to a choice of two vertices

[coral parcel]

You're in desperate need of some parentheses there.

[quiet tendon]

ahh I see so there are n vertices and every vertice has 2 connection so nC(2) gives the amount of edges?

[coral parcel]

No, but every edge has two ends, and every choice of two (different) ends gives you an edge because the graph is specified to be complete.

[quiet tendon]

oh ye I said it wrong but I see it now

[umbral blade]

since there are four terms in (¬p ∨ q) ^ (¬r ∨ s). Would I make r = (¬r ∨ s) so i can do the distrubutive law

[haughty garden]

Yep

[frozen rune]

yes^

[umbral blade]

I am attempting to prove this formula to be a tautology using logical equivalences: [ (p-->q)^(r-->s) ] -->[ (pVr)-->(qVs) ]

So far I have gotten this in steps for my proof:
[ (p-->q)^(r-->s) ] -->[ (pVr)-->(qVs) ]

x = (p-->q)^(r-->s)

y = (pVr)-->(qVs)

x -> y

~x V y. Conditional rule. Substitute back in

~ ((p-->q)^(r-->s)) V (pVr)-->(qVs)). De Morgan's Law

((p ^ ~q) V (r ^ ~s)) V (pVr)-->(qVs))

z = (r ^ ~s) Substitution

(p ^ ~q) ^ z V (pVr)-->(qVs) Distribution

I am wondering if I am on the right track at all and if my steps make sense

[inner otter]

It would make more sense if you used different letters instead of reusing p and q

[umbral blade]

What about now? I edited it.

[snow junco]

You messed up here

Why is it still ^ between the two larger parentheses groups? (ignore everything outside the red circle)

[plain valve]

why is the height of the tree N/2?

@ me if you understand why

[unreal stump]

<@&268886789983436800> sus link

[umbral blade]

Believe I fixed it now

When proving a tautology we’re looking to simplify to the point where we can use the negation law right?

[snow junco]

until we get r V ~r for instance to get T or r ^ ~r to get F etc… until our result is static

[snow junco]

Simplify until it’s just T in this case

[uncut herald]

Imagine the sequence of the tree at each layer is 1, 2, 3, 4 ... n. Then it's clear that it has height n. If the sequence is 2, 4, 6, 8 ... n there are half as many entries, so n/2. Adding a 0 does nothing to overall time complexity as it's a constant for any n

[glass spade]

Stuck on part a)

[tight hound]

Each 5 element subset of {0,1,...,9} corresponds to a unique strictly increasing function, and each strictly increasing function corresponds to a unique 5 element subset.

[glass spade]

True

Oh now it makes sense

[cunning mason]

How to intuitively think about composition of relations?

Some examples:

Then what is:
$S\circ R$

[vital dew]

MyFavoriteAccount

[cunning mason]

maybe something like:
coordinates where the first coordinate is the first coordinate of a coordinate in R, and the second coordinate is the second coordinate in a coordinate in S, AND the second coordinate in R, and the first coordinate in S are both in the same set

[brave rock]

Here's an illustrative example

Imagine you're looking at a set of points, some of which are connected by lines. We will write a R b if points a and b are connected by a line.

a R b iff a, b are one line apart

a (R o R) b iff a, b are two lines apart

a (R o R o R) b iff a, b are three lines apart

Savvy?

[cunning mason]

so R o R means that there is something connecting them

for example here the 8 in C connects the coordinates

[reef needle]

guys can i discuss graph theory in here?

[coral parcel]

Yes, see the channel description.

[glossy kayak]

a = a + b .. what is a?

not 0?

a is 0

it's actually solvable i think, if you try to solve for a with b

a = b * infinity^2

a = a + b sole for a + b

((((a + b) + b) + b) + b) + b ... (b * infinity) + a

(b * infinity) + ((((a + b) + b) + b) + b...) = (b * infinity) + ((b * infinity) + a)

C = C + M

[glossy kayak]

or rather E = E + M

[willow ingot]

Hey, I found these resources...seem very useful!

https://www.studypool.com/services/27394055

https://www.studypool.com/services/27396442

https://www.studypool.com/services/27454687

on discrete math 👆🏻

[reef needle]

guys

1. G is a Tree (every 2 vertices are connected with exactly 1 way)
2. G is a cohesive graph without circles
3. If you take away any Edge G breaks into 2
4. There is always 1 vertice(n) more than edges(m). n = m + 1

does this look familiar to you

why is this channel so empty

why does graph theory not have it's own channel

isn't it an important topic?

@coral parcel

[coral parcel]

The channel selection is not intended to encode which topics are "important", but more (though very roughly and approximately) which topics have lots of conversation about them.

[little prism]

'zusammenhängend' is connected.

[inner marsh]

I am given the recursive equation $a_n = 4a_{n-1} - 3a_{n-2}$ and that $a_1 = 2$ and $a_2 = 5$. how am I to find a general formula for $a_n$?

[vital dew]

MaiTheLord

[brave rock]

You may want to look into generating functions

[inner marsh]

I am sorry but I can't understand how it helps me here

[brave rock]

Generating functions are one way of finding closed forms for recurrence relations.

Here is a guide https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_(Morris)/02%3A_Enumeration/08%3A_Generating_Functions_and_Recursion/8.03%3A_Using_Generating_Functions_to_Solve_Recursively-Defined_Sequences

[inner marsh]

I don't really get what this is representing

[brave rock]

You could spend a while worrying about what exactly that represents, or you could just use the technique.

To be frank I don't think that even experts in generating functions know what they 'represent' directly

[inner marsh]

well I don't even understand why we represent this sequence (a_n = 3a_{n-1} - 1) like that... I'd have no idea how to actually apply the technique to my problem

[brave rock]

Example 8.3.2 is almost exactly your problem.

This webpage explains things in fair detail. Perhaps you could spend some time with it

[sacred fern]

generating functions are overkill for this no?

advancement operator is simpler?

[unreal stump]

egfs are perfect for this

[sacred fern]

A^2 - 4A + 3 = 0 gives a solution to this almost instantly

[unreal stump]

Well egfs are all about advancement operators smh

[sacred fern]

yeah but they are scary looking ngl

[glass spade]

i havent heard about egfs and advancement operator

but in the textbook im reading they call it characteristic equation

$a_n=\frac123^n+\frac12$

[vital dew]

play

[inner marsh]

how do you actually get to that point?

[quick tusk]

how can i do this. I got this but idk where to go from here

[little prism]

now you have to show that the thing in the brackets is divisible by 2 and 3

you can go through the options of n odd/even and n congruent to 0,1,2 mod 3

[quick tusk]

oh

yeah i tried the n odd/even path. I havent been taught the congruent part. My term hasnt started yet

can i do this without the congruent part because idk what that is

[quick tusk]

for this question, is this the correct reasoning why (p+1) is divisible by 6. Because in every 2 consecutive numbers, one must be divisible by 2 and in every 3 consecutive numbers, one must be divisible by 3

[sacred fern]

so the first thing is that their sum is even, why is that?

[little prism]

the congruent part means that every number has one of the forms 3k, 3k+1 or 3k+2

[little prism]

so you can use that instead

[quick tusk]

oh

why do we choose those forms and not something like 2k, 2k+1

[quick tusk]

i added p and p + 2 and factorise 2 out

[little prism]

2k, 2k+1 corresponds to even/odd

3k, 3k+1, 3k+2 is the "3-version" of being even/odd which is based on divisibility by 2

[quick tusk]

so the idea is to use 2k, 2k + 1 to show that (2n^3 + 3n^2 + n) is divisible by 2. And then use 3k, 3k+1, 3k+2 to show that it is divisble by 3?

[little prism]

yes

[quick tusk]

oh

that's a lot of work lol

i got this from 3k

so theres no easy way of showing that the bracket part is divisible by 2?

[little prism]

the whole modulo framework speeds up the work

well you can use stuff like odd*odd=odd and even*anything=even. but the proofs of these things are also based on 2k, 2k+1

[quick tusk]

im guessing modulo stuff is extension for the 3k, 3k+1, 3k+2 thing that you are talking about

[little prism]

yes

[quick tusk]

ok thx for showing me this former stuff first. Should make it easier for me when i learn modulo

[little prism]

you will notice that the parts that the 3k goes into dont really matter for the argument except that they include a factor of 3

which means you don't really have to calculate everything perfectly as long as you know whether it includes a factor of 3 or not. and when you formalize that you end up with modulo

[quick tusk]

yeah i couldve just done that, i see and just mindlessly expand. Cant really do that for 3k+1 tho

[little prism]

even for the 3k+1. track explicitly in which of the final terms it appears. and then see that for none of them you care about the explicit form, just that they include a factor of 3

[quick tusk]

damn ok. Yeah i will need a lot of algebraic practice to have insight such as yours, but i see what you mean. thx

[little prism]

this isn't stuff that you see before doing it

it's stuff that you see after and wonder why it is. and whether you can exploit it to reduce future work

which, as mentioned, leads to modulo stuff

[quick tusk]

in some way it is insight, like how after figuring that 3k part is divisible by 3, then you can kind of see that you only need to focus on the expansion from the '1' in 3k+1, since you already know 3k has factor 3. probably

[little prism]

exactly

[quick tusk]

modulo is the remainder stuff, right

[little prism]

exactly this. only the remainder 1 matters. the 3k doesn't matter

[quick tusk]

ok i'll get this eventually LMAO

[native dragon]

Would someone here be willing to help me with a graph theory problem 🫠

[meager prawn]

just ask

[inner marsh]

I am given $\frac{1}{(1-x^2-x^3+x^5)^n}$, and I need to find the coefficient of $x^{13}$.
Let me know if I did this correctly: I'll start by factoring the denominator to $(1-x^2)^n(1-x^3)^n$. now, I'll use the binomial theorem to represent the factors:
$(1-x^2)^n = \binom{n}{0} - \binom{n}{1}x^2 + \binom{n}{2}x^4 -\binom{n}{3}x^6 + ...$ and
$(1-x^3)^n = \binom{n}{0} - \binom{n}{1}x^3 + \binom{n}{2}x^6 -\binom{n}{3}x^9 + ...$
Now, I'll find the products which equal $x^{13}$. these are $x^4x^9$ and $x^{10}x^3$. so we have $\binom{n}{2}x^4(-\binom{n}{3}x^9) + (-\binom{n}{5}x^{10}(-\binom{n}{1}x^3))$, and the coefficient of $x^{13}$ is $\binom{n}{5}\binom{n}{1} - \binom{n}{2}\binom{n}{3}$. is that right?

[vital dew]

MaiTheLord

[sacred fern]

Feels like a pigeonhole principle problem ngl

[native dragon]

I'm trying to solve it probabilistically but I have no idea what variable I need to randomly choose

I thought of randomly choosing an edge but that didn't get me far

[sacred fern]

What if you did contradiction?

Take a graph on n vertices with less than 8n - 36 vertices

[native dragon]

yeah that's what I tried 😭

[sacred fern]

And maybe show that the number of complete subgraphs stays the same

[native dragon]

I tried randomly choosing an edge but that didn't get me very far

mostly since someone who hates you can choose the graph so you have no idea of what it might look like

[sacred fern]

Randomly choosing an edge is tricky

[native dragon]

yeah but idk what else I can randomly vary

[sacred fern]

How many vertices would be need if every vertex was part of a K3 subgraph?

Cuz if we can find that the we may be able to use this somehow

[native dragon]

no idea, technically this doesn't even mean that 8n-36 is enough

[sacred fern]

Yeah no but we get some sort of lower bound

[native dragon]

I could try but 8n-36 is a lower bound on "enough" edges not the actual cutoff value

I thought of randomly attaching a label to each vertex but I have no idea how I could use that either

[sacred fern]

The reason I ask this is cuz it’s most likely to make a new K3

[native dragon]

True, but for a K3 I'm still running into the issue of what to probabilistically vary

[sacred fern]

I think direct counting is better

[native dragon]

wdym direct counting

[sacred fern]

Actually idk

[true venture]

So given the sequence $1,1,0,0,1,0,0,1,0,1,1,0,2...$
Starting at n=0,1,2,3...

with generationg function $\frac{1}{G(0)}$

with $G(k) = 1- \frac{q^{k+1}}{1+\frac{q^{k+1}}{G(k+1)}}$

Expands into $G(0) = 1-\frac{q^1}{1+\frac{q^1}{1-\frac{q^2}{1+\frac{q^2}{...}}}}$

Then using the generalized continued fraction formula I get

$x_0 = 1$

$x_1 = 1 - q^1$

$x_2 = \frac{1}{1+q^1}$

$x_3 = \frac{1-q^2}{1+q^1-q^2}$

$x_4 = \frac{1}{1+q^1+q^3}$

$x_5 = \frac{1-q^3+q^5}{1+q^1-q^4+q^5}$

$x_6 = \frac{1+q^5}{1+q^1+q^3-q^5+q^6}$

[vital dew]

jo_fish

[true venture]

As you continue to expand the fraction and find x_6,7,8...the terms of the sequence should be the coefficients of q in the denominator of x right?

[inner marsh]

How does $\frac{1}{(1-x^2)^n(1-x^3)^n}$ expand to $\newline (x^0 + x^2 + x^4 + ...)^n(x^0 + x^3 + x^6 + ...)^n$?

[vital dew]

MaiTheLord

[jolly ledge]

That's the neat part: it doesn't

[inner marsh]

wdym by "it doesn't"?

my book says it does because of

$\frac{1}{(1-x)^n} = (1+x+x^2+...)^n$

[vital dew]

MaiTheLord

[inner marsh]

but I don't get why this is true either

[jolly ledge]

Because it isn't?

What book is that

[inner marsh]

Some discrete math combinatorics book

are you sure it's not true

[jolly ledge]

Absolutely.... u can check it on a computer. Heck, 2nd one ain't even convergent

What kinda book is that ngl...

Hopefully that's a type

Typo

[inner marsh]

How do you check that

[jolly ledge]

We can rewrite the sum on the 2nd part as $(\sum^i_{k=0} x^k)^n$

[vital dew]

Kiameimon | Welt Rene (glomed)

[jolly ledge]

And... this clearly is not the same as the LHS. Try plotting it on desmos for any n

Unless n = 0, this isn't true

What book is that BTW? I'd srsly recommend switching books if that ain't a typo 💀

[inner marsh]

It's one of the books of the course I am taking...

[jolly ledge]

Any context to this?

Like the only way this is true is if x = 0

[inner marsh]

it's just mentioned as a fact in some point, I might've missed its explanation

[jolly ledge]

💀it's very obviously not a fact unless x = 0, bruh that book 💀

[inner marsh]

I've tried to google it and found this

https://www.quora.com/What-is-the-proof-that-1-1-x-1+x+x-2+x-3

I am so confused

[jolly ledge]

Ah.....

Ok

[jolly ledge]

So basically what this is trying to say is that the geometric sum converges to provided all terms in the sum is < 1 (that being said, it isn't equivalent to your expression? Since yours is raised to the power of n)

Yknow the geometric series formula?

$a + ar + ar^2 + ar^3 \dots ar^n = a \cdot \frac{1-r^n}{1-r}$

[vital dew]

Kiameimon | Welt Rene (glomed)

[inner marsh]

not sure

[jolly ledge]

You should look up a proof on that tbh. It allows u to compute the n-th term of any series that follows this pattern

For example 1 + 2 + 4 + 8 ....

In this case a = 1, r = 2

So plug in the values into the formula and boom, gives u the suk

Sum

Now, the thing is that if the common ratio (r) is less than 1, we can determine where it'll converge to by taking a limit

(Try evaluating it yourself @inner marsh)

Just take the formula I gave above and take the limit as it approaches infty assuming |r| < 1

(Note that we must assume |r| <1, else as the sum approaches infinity our series will not converge)

[inner marsh]

how does the proof work then if x must be less than 1?

[jolly ledge]

That's the thing, it doesn't.

This is similar to the argument 1+2+3.... = -1/12

It's false as the sum doesn't converge

[jolly ledge]

Heard of it?

[inner marsh]

no

[jolly ledge]

It goes around the lines of

[inner marsh]

but this seems to work always (except x = 1)

[jolly ledge]

... tbh its a really hard thing to explain in 1 message. Most videos on it that I find are like 30 mins long

https://youtu.be/jcKRGpMiVTw

Have a look at it at your own time

[inner marsh]

alright

[true venture]

Is this being used in the context of generating functions? If so it is often assumed x<1. And whenever or not it converges is ignored.

[inner marsh]

ok

[inner marsh]

I get this, obviously the first assumption that 1-1+1-1+... = 1/2 is wrong.

however

[inner marsh]

this seems to make sense

[jolly ledge]

It doesn't converge. You cannot apply these recursive arguments to non-convergent series

[jolly ledge]

Hm, never knew that

Conventions brr

[inner marsh]

wdym? what wrong manipulation is there in the proof?

[jolly ledge]

If the sum doesn't converge, you cannot manipulate it as such. It is not equivalent.

[inner marsh]

so saying $1 + x + x^2 + ... = x(1 + x + x^2 + ...)$ is illegal

[vital dew]

MaiTheLord

[true venture]

There is a book, generatingfunctionology I recommend looking at chap 2. It explains the assumptions of using series in this way.

[jolly ledge]

If x >= 1 yes

[true venture]

You can find the pdf

[jolly ledge]

Oh, I've heard thst book before. What prerequisites do they assume?

Doesn't it cover stuff abt recursive functions and counting?

was considering having a look at it

[true venture]

Not sure, it's pretty accessible.

[inner marsh]

how do I get rid of the exponents in $(x^0+x^2+x^4+⋯)^n (x^0+x^3+x^6+⋯)^n$ to find the coefficient of $x^{13}$?

[vital dew]

MaiTheLord

[quiet tendon]

is E(X^2) the same as X bar ^2

[inner otter]

no, the latter is the average of X squared, I assume

[quiet tendon]

and the first one?

btw I meant X^2 bar

I found online the answer that X^2bar is basically the estimator of E(X^2) and that means that X^2 bar is quite accurate if the sample size is big but it's not exactly the same unless the sample size is as big as the population size

idk if this is correct

[mystic depot]

What's the best way to self study discrete math type of problems? I want to take this course at my university: https://cs170.org/ but I want to self-study before since people tend to have much more discrete math experience than I do.

[orchid idol]

yo ik you’ve taken this class then how do you prove a stable pairing exists if we allow unmatched entities

[haughty garden]

If you want to get up to speed specifically to be comfortable with studying algorithms, my recommendation is to familiarise yourself with basic set theory (mostly for notation purposes; you just need to be comfortable with the notation that is often used in naive set theory) and proofs (you’ll come across a lot of proofs, especially when proving the correctness of greedy algorithms). Then it’s just a matter of applying and practice; break down the problem into smaller portions that are much more manageable and then combine your insights together to form a cohesive argument/solution

[haughty garden]

Is this in the context of Gale-Shapley? You don’t require every entity to be matched

Just that, if two entities prefer each other, they should not match with other entities

[orchid idol]

yes it is

how do i show that it’s stable tho?

the hint says to use imaginary entities that match w a job/candidate if they prefer to be unmatched

[mystic depot]

I guess my question is how do I practice proofs? In my experience they're not like computational type of problems where there is a definitive and concise answer.

[viral crown]

basic calc

[quick tusk]

would using this property be a good strategy to solving this question

[unreal stump]

Yes, it is

[jolly ledge]

[quick tusk]

i have this so far. I equate the equation to 1 or 0 so i could find gcd easily. Idk how to simplify the x, but its an integer when i compute it. Is gcd = 1 correct from my working

[jolly ledge]

probably the most efficient GCD algorithm

[quick tusk]

yeah it's a cool property

[jolly ledge]

also

yes GCD is 1

(i.e they are coprime to one another)

[quick tusk]

yeah

side question, how do i simplify that expression

you can just tell me what tools i need, and i'll give it a try

[jolly ledge]

what do you want to simplify?

[quick tusk]

the x i found here

[worldly hollow]

Any book recommendation to learn lobster graph?

[frank dome]

I'm having problems with generatingfunctionology chapter 1 exercise 10g, pastebin: https://mathb.in/75444. I got the required pgf $\frac {t^n(1-t^m)^n} {m^n(1-t)^{n+1}}$ but I'm not sure how to expand it to get the jth coefficient, to get the CDF

[vital dew]

bostock

[ripe mulch]

if i have a hash function that has uniformity. if i mod the output of the hash function will it still be uniform?

[pale epoch]

depends on uniform in what

[scenic dove]

Can someone explain how these two quantifiers are different?

aren't they both the same quantifier?

"For all n E N"

oh

what are the two quantifiers in that example?

[brave rock]

They are both forall

[ripe mulch]

what do you mean by this?

[pale epoch]

uniform in what set

if the cardinality of the range isnt evenly divisible by n, it cant possibly be uniform mod n

[reef needle]

could help me with this by any chance?

so far i have only done simple induction examples with sums

this is the first one with a real problem

[pale epoch]

unsure why this question suggests to use induction

there is a simple direct solution and induction is just rewriting

anyways, just look at the first few examples

there is only one of those trees of height h

and the "rule" to go from height h to h+1 is not hard to figure out

[reef needle]

yeah it's just n number of leaves multiplied by 3 for h+1

[pale epoch]

sure

i dont see why this requires induction

its just unnecessary phrasing

[glass spade]

stuck on part f and g

I know that 1/(1-x) = 1 + x + x^2 + ...

1/(1-x)^2 = 1 + 2x + 3x^2 + ...

[stray reef]

what would the generating function be for the sequence in f without the zeros

[glass spade]

1/(1-5x) = 1 + 5x + 25x^2 + 125x^3 + ...

1/(1-x^2) = 1 + x^2 + x^4 + ...

i think it's starting to make sense to me after staring at the author's solution

i do 1 / (1 - (√5 * x )^2 ) and then the sequence work

and then for g i use 1/(1-x)^2 = 1 + 2x + 3x^2 + ... and replace x->x^3 and then multiply by x to shift right

[green iron]

I'm looking for free discrete math exercise with answer sheet if anyone know where to get those please let me know.

[glass spade]

https://discrete.openmathbooks.org/dmoi3.html

i skipped all the exercises without the solutions

[green iron]

thanks a lot!

[latent cloud]

Do I need to understand logic and set theory in order to understand graph theory. I have knowledge in linear algebra but wanna learn graph theory since it seems useful. Atleast more useful than set theory and basic logic since I’m programming a lot and I don’t feel like I need more knowledge in those areas atm.

[honest holly]

What is logic and set theory?

If you learned linear algebra, the logic and set theory you know would be enough

[latent cloud]

Those are two areas within discrete maths

I’m pretty sure we didn’t touch either of those areas in my linear algebra course.

[plucky marsh]

There are some basics with it that should be known to understand most undergraduate math

[plucky marsh]

So if you multiply a function by x^n, it shifts each number in the sequence down. If you replace f(x) with f(x^n), it puts zeros In between numbers in the sequence

[latent cloud]

What are those basics?

Proofs?

[plucky marsh]

The basics are like what the symbols mean so that you can read math.

[latent cloud]

Ok thanks 👍🏻

[late whale]

is the cardinality of the subset of a power set always equal to 1?

[tight hound]

What do you mean by 'the' subset? Also, power set of what?

[honest holly]

To be clear, set theory refers to something which most people do not do

Same with logic

If you are referring to the introduction to sets and logic which is found in so called discrete math classes (a better name would probably be introduction to proof), then yes you would need to know it to learn anything in mathematics

[next vault]

Yeah I think this is accurate, lots of very serious individuals in math who would be hard pressed to express all the axioms of ZFC let alone tell you about forcing, the most seminal technique of modern set theory

[chilly hemlock]

Does anyone know how to find the combinations of playing computer games?

Rule is that you cannot play two days in a row. You have 9 days of gaming and want to distribute it in 31 days.

[coral parcel]

Divide 32 days into some combination of 9 × "game followed by non-game" and 14 "non-game", then discard the last day (which is always a non-game day).

[chilly hemlock]

$${32 - 9 \choose 9} $$

[vital dew]

Jonathan!

[chilly hemlock]

?

[coral parcel]

Yes.

[swift gyro]

Hey does anyone have practice questions for sets , functions n relations , logic??

[safe cloud]

How many four-digit codes with the digits 1, 2, 3, 4 exist in which at least one digit is not repeated?

[tight hound]

Try counting the codes in which all digits that appear are repeated.

[lyric quartz]

hm didnt know latex has infix operators

[fathom harbor]

Hey, I was trying to understand How The following Cn coeficient was obtained. Someone could explain me? Thanks for listen

[fathom harbor]

I've an Analysis book for such questions, It is from a Brazilian writer Elon Lages Lima. I don't know if its interest you

[swift gyro]

Its alright. I will take anything at this point

[zealous elbow]

im on iii
and my first path f
was
6,1 then along 3,2 then along 5,5 then along 4,0
which gave a flow value of 2
so i added that to the flows of the path i used
and now i cant find a possible way to get f'
like its actually just impossible?

[coral parcel]

The infix \choose comes from plain TeX; there's also an infix \over for factions. LaTeX strongly discourages them in favor of its own \binom and \frac, which take their arguments in the same way as macros do.

[stuck compass]

you did it. here's your f', with a flow value of 7 vs the original 5

[mint basalt]

what is the difference between arrangement and permtation?

[reef needle]

@coral parcelare you German by any chance?

i really need a German to check this

this example or something similar has a high probability to come in my exam tomorrow

[long cape]

hello

could anyone explain me what does B^A mean?
as i understood that its the elements that belong to a and b
A,B are sets

[meager prawn]

He only knows some. I have yet to identify his country.

[versed perch]

Hello i have a alot of questions to ask

Where am i going wrong?

Its a pretty basic question

Is c the correct option?

[meager prawn]

Notice they're both equal to the product of all the entries in the matrix

[safe cloud]

How many are there six-digits numbers with the digits {1, 2, 3, 4} where every digit appear at least 2 times?

I tried counting:

[ripe mulch]

Since there are no multiples of a positive integer between 0 and n, we know that n cannot be a divisor of any integer between 0 and n. This means that when hunting for the positive proper divisors of a positive integer m, we must only test the integers between 0 and m. What exactly does this mean?

[analog tinsel]

sieht für mich vernünftig aus looks reasonable

[worldly hollow]

Any web recommedation to learn graceful coloring (graph theory)?

[fossil mural]

it's saying that, for example, 11 can't be a divisor of 8, because it's larger than 8

all of the divisors of a number must be smaller than that number

so if we want to find the divisors, we only have to check up to the number we're finding the divisors of, since there won't be any above that

[slender hawk]

Greetings Discrete, I am currently working on finding sources for applications of Graph Theory and Combinatorics in particle physics, quantum mechanics, or any other related engineering concept. This has proven to be difficult so far. Please, @ me if you have any general information or good ideas for sourced information. All is welcome.

Best,

[hexed falcon]

Can someone please provide a step-by-step explanation for the answer? I would really appreciate it.

[jolly ledge]

!show

[lofty cloud]

Show your work, and if possible, explain where you are stuck.

[chilly hemlock]

does anyone know what they mean by components?

this is what i've come up with so far:

[vital hedge]

is this a graph?

[brave rock]

No. Edges must have endpoints.

[vital hedge]

but it said edge has either one or two endpoints

[brave rock]

The reason they say "one or two" is that an edge may connect a vertex to itself.

[vital hedge]

i see

thanks a lot

[brave rock]

If you would like to see it set-theoretically...

There is a map from the set of edges to the power set of the set of vertices

and we require everything this map outputs to have at least one and at most two elements

This is complicated though. It's easier if we require directed graphs

[vital hedge]

true XD

[brave rock]

Then we have a set $V$ of vertices and $E$ of edges, together with two functions $E \to V$ which define the source and target

[vital dew]

Boytjie (never-to-be-glomed)

[brave rock]

Now if you want to force this to be non-directed you have to think a bit, so I'll just point this out and leave it at that.

[timber barn]

To find f(n) when n = 3^k, given f(n) = 2f(n/3) + 4 and f(1) = 1, let's evaluate f(n) assuming f is an increasing function.

anyone knows the solution and explanation?

[brave rock]

Hint: we can also say f(3n)=2f(n) +4.

[timber barn]

Ok

I saw that

but what next

[true shore]

is the written part a good explanation or does it not make sense?

S = {n E Z | n = (-1)^k, for some intger k}.

S, consists of all integers (n) such that there exists an integer for which the expression n = (-1)^k holds true.

[vale cairn]

Well you should mention an integer k

[exotic whale]

Hi does anyone have any good resources to learn discrete? I swear I have no clue whats going on in my homework

[inland raft]

scheinerman

[glass spade]

i really like this problem

[viral crown]

is this right

i like that problem too

i think it's vv cute

[glass spade]

There's two C

[viral crown]

||top right is supposed to be F||

oops

[glass spade]

||I believe it's correct ✅ ||

[urban berry]

hey i had a question about ordered fields

can we ever say that the subset of elements is equal to the field of elements?

from this definition it sounds like all elements of F are in a subset (lets call it A) except 0

since the three conditions are 'or' based

[vale cairn]

No because then 1 and -1 are in that subset and then 0 is

[pale epoch]

im not sure this definition suffices to get ordered fields?

[vale cairn]

I think it works if you define x < y iff y - x is in that subset right

That second paragraph is in bad english

[fossil mural]

i think you'd also need to require that 0 isn't in the subset

[vale cairn]

Yeah you need that "or" to be a trichotomy

[ivory badge]

x \leq y iff y-x is “positive” is fine though

[ivory badge]

The subset closed under addition and multiplication guarantees the thing’s compatibly partially ordered, and if you make it where P u -P covers the whole thing you should get a total order, since either x-y or y-x is in there. (You want P n -P disjoint except maybe 0 tho)

[pale epoch]

sure, if they are disjoint

you can also force -1 to be negative

and/or squares to be positive

then 1 is positive and ...

[ivory badge]

Well forcing squares positive and such gives a more restrictive notion ofc

Idk how well behaved those ones area, but lattice ordered rings and f-rings have some structure theorems proven about them

(f-rings being a more “nice” looking one that doesn’t have silly pathological behavior, like 1 not positive despite being square)

[regal ice]

Guys does anybody know a regular grammar for this language L={w:|w| mod 3=0} over {a,b}

[quick jungle]

Is it possible to construct a junction tree from a 4 node clique?

[vital dew]

pikachupikachu

[inland raft]

is this a valid "combinatorial proof" of the binomial theorem?

[viral crown]

ngl something about this proof gives off weird vibes

[regal gate]

why its so long

[viral crown]

^

[inland raft]

[viral crown]

i think you have a working proof here

[inland raft]

i thought this was the more sane way of doing it, i actually am working on a more crazy soln lmao

[regal gate]

actually

[inland raft]

what's off or weird about it?

[regal gate]

suppose x and y dont commute

then what is (x+y)^n

you cannot group terms

so for example (x+y)(x+y)=x^2+xy+yx+y^2

[viral crown]

its just the same proof i've seen but it gives bad vibes

i think it's correct

you can simplify it a lot

[viral crown]

we're assuming you can

[vital dew]

pikachupikachu

[regal gate]

yeah

[vital dew]

pikachupikachu

[viral crown]

i think it's already corrdct

just assume it commutes

[regal gate]

i mean you got the idea I sps, but its very wordy

[viral crown]

as far as assumptions go that might be the smallest one

it's a lil wordy

[inland raft]

so i can remove the filler "from the alphabet {x,y}"

[viral crown]

yes

[inland raft]

i can also remove the line "to prove the theorem" because the proof wouldn't change without that

[viral crown]

ehhhhhhhhhh

tbh

leave it be

you got the idea

that's all that matters

go work on the new crazy soln and show it to meee

[vital dew]

pikachupikachu

[viral crown]

looks correct enough to me

[inland raft]

how about now?

[regal gate]

yeah guess its good

maybe I overexaggerated the wordiness, like if you want to make it rigorous, you have to write words lol

[viral crown]

no need to make it rigorous

it's more than rigorous enough

[regal gate]

I meant that this is already rigorous

[regal gate]

have you done this one? its in Bona too

this is a fun one, and not difficult (here you are supposed to give a combi proof ofc)

[inland raft]

haven't will work on it later fs

[vital dew]

pikachupikachu

pikachupikachu

[inland raft]

don't even know if the lemma holds tho

[jolly ledge]

Hm, I see similarities between it and whatever is shown on wiki had to resort to wiki cuz I prefer induction proofs

[jolly ledge]

hmmm

well it's doable by induction but ig the challenging part is by combi

[jolly ledge]

I think it's quite literally reiterating what a power set is + then getting you to show that binom expansion is equivalent to no. of elements

it definitely does, since the number of elements in the power set is 2^n (each element in the original set is either in a subset (which as a result makes it part of the power set), or is not)

but as to showing a direct correlation between binom and this? Hm.... The numbers add up, but showing this "combinatorically" may be a challenge

[molten bane]

isnt this statement just purely false?

for any a in Q, there exists m and n that are integers where they have no common factors in the form a = m/n

but integers are a subset of Q

and all integers must share common factors in the form a = m/n

am i misunderstanding this?

[inland raft]

it's false because n cannot just be any integer, it must be nonzero

[molten bane]

that as well

[inland raft]

if there are any common factors you just cancel them

[molten bane]

then it becomes an integer

and any integer will have a common factor

in the form m/n

[inland raft]

what? 4/6=2/3 is 2/3 an integer?

[molten bane]

do we just assume 1 doesnt count as a common factor?

im genuinely asking lmao

[inland raft]

if you assume that it does then you're practically saying any given pair of numbers have a common factor. is that even a meaningful thing anymore?

[molten bane]

thats my question

im asking the validity of whether its well defined or not

and yes my premise should have been since all pairs of numbers share a lcf of 1, can we state that the statement is false

[inland raft]

1 divides every integer, if you wanna be more precise just say m and n have no common factor except 1

[molten bane]

cool, thanks!

[inland raft]

"it's quite literally reiterating what a power set is" isn't helping me go anywhere. if you're simply stating the fact that for a set of n elements there are 2^n subsets then that can be shown simply by observing that to each subset there corresponds a unique n-binary string and there are 2^n such strings, about how you go from this elementary fact to saying that the claim i maid in said lemma holds is i think jumping through hoops

[inland raft]

first proof i presented was supposed to be the typical way of doing it so unsurprisingly wiki has the same idea

[jolly ledge]

it is, but well, numerically it does add up it's gonna be hard to establish a direct combinatorial correlation though, as I mentioned.

Hm.

[vital hedge]

are these graphs isomorphic or not ? plz help me

[inland raft]

isomorphic graphs need to have same |V| and same |E|

[iron marsh]

@vital hedge you still working on this?

[iron marsh]

I figured it out, and this one is actually kind of tricky

I'll just give you a hint until you get back. Pick any vertex in the first graph (the graph is symmetric, so it doesn't matter which one you pick), and pay attention to how its neighbors connect with each other. Now do it with the 2nd graph.
How might this idea be useful?

[vital hedge]

what's the next?

is your idea to find a mapping function? QQ

[inland raft]

don't mind anything i have written here, i didn't even notice they had the same no of edges lol mb

[iron marsh]

Well, first, let's assume we choose the vertex u_1. Then in has neighbors {u2,u4,u5,u6,u8}.
Now which of these vertices connects to u2? u4? Do this all the way up to u8.

[iron marsh]

If only it was that easy 😛

[inland raft]

haha, the one on the left look more cluttered so i just assumed along

[iron marsh]

For a more visual representation. Draw a graph that only has the vertices of u1's neighbors: u2, u4,u5,u6,u9. The edges for the graph are the same edges in the original graph.
This is known as the linked graph for u1.

Now try to convince yourself that for the left graph to be isomorphic to another, the linked graphs must be isomorphic to each other.

Note: this is not enough to say it is isomorphic, but it is a consequence of graph isomorphisms.

[iron marsh]

Based on the last thing I said, you should be able to deduce whether this thing I want you to do will show if there is a graph isomorphism or not.

If you're having a hard time understanding the linked graphs, this should help.

I made a random graph and I put the linked graph for each vertex in purple next to them. Hopefully this will help

[vital hedge]

yes i understand linked graphs now

[iron marsh]

Good, I'm glad this was useful.
Now, find the linked graph for one of the vertices in the first graph and do the same for the second.

Again, the linked graph is the same for every vertex in each graph here, so it doesnt matter which one you choose

[vital hedge]

yes

but how can I find a mapping function or something to prove

[iron marsh]

finding corresponding linked graphs for each graph is not sufficient to show two graphs are isomorphic, but it is a necessary condition if they are isomorphic.

So if what we are doing is not enough to prove they are isomorphic, then why would I be asking you to do this?

[vital hedge]

I have no idea XD

[iron marsh]

If a graph is isomorphic, we need to construct a function that preserves vertices and its corresponding edges, correct?

[vital hedge]

yeah

[iron marsh]

This function is called a graph isomorphism. However, if the linked graphs do not match, no graph isomorphism exists, because it is absolutely necessary that they do for two graphs to be isomorphic.

If you do not believe me, try to convince yourself as to why this is true

[vital hedge]

so, your idea is to list all linked graphs of G1 and G2, and each one will have eight

[iron marsh]

So draw the linked graph for u1 and v1. Are they the same (isomorphic to each other)

[vital hedge]

and match them ?

there will be 64 possibilities

[iron marsh]

You only need to look at an individual vertex here since all linked graphs in each graph will be the same in this case

[vital hedge]

yes

[iron marsh]

What on earth are you talking about

[vital hedge]

wwwwwwwww

[iron marsh]

Can you draw the linked graph for u1 and v1 please?

Send a picture once you finish

[iron marsh]

No, that is not what a linked graph is

A linked graph of u1 only has the vertices that connect to u1. It does not contain u1 itself

[vital hedge]

oh~~

[iron marsh]

In this example: the middle vertex is connected to the upper left, upper right, and bottom right. Those 3 vertices are the vertices in our linked graph for the middle vertex.

Since the top left and top right connect to each other in the original graph, we connect them in the linked graph.

Notice that the bottom right vertex connects to neither of them, so it has no connections.

I've highlighted the neighbors and their connections for the middle vertex in red

The purple graph next to the middle vertex is the same as that. that is the linked graph for the middle vertex

[iron marsh]

That's more like it!

Now do the linked graph for v1

[iron marsh]

Perfect! Now, they look a little different. Are these graphs isomorphic to each other (this is a much easier problem to solve)

[vital hedge]

no

[iron marsh]

why is that?

[vital hedge]

right has C4

left only has C3?

[iron marsh]

That's not a bad observation. I didn't think about that.

[vital hedge]

oh~ so they are not isomorphic

[iron marsh]

The thing I noticed was that one of the vertices in the first graph, u5, connects to all the neighbors. But there is no such vertex that does that in the 2nd linked graph

The linked graphs are not isomorphic, so what does that tell us about the original graphs?

[vital hedge]

I have no idea ww

[iron marsh]

Remember, graph isomorphisms must preserve linked graphs (up to isomorphisms), but the linked graphs are not isomorphic.

So what conclusion can we draw?

[vital hedge]

oh I don't know this

[iron marsh]

I think I said it like 3 times at this point 😛

[vital hedge]

G1 and G2 are not isomorphic

[iron marsh]

Precisely!

[vital hedge]

sorry

[iron marsh]

All good. You're learning a new topic, so things like that can be easy to miss

Now, let me ask you a follow up question.

[vital hedge]

since I only know if two graphs are isomophic , then their subgraphs by removing a vertex must be isomorphic?

[iron marsh]

We were in a very special case where the linked graphs for every single vertex is the same in each graph. But, that won't always happen (and we see that in my example).
If we were trying to show two graphs aren't isomorphic by looking at their linked graphs, how would we do that?

[iron marsh]

we removed more than just a vertex. Remember we only looked at the neighbors of a vertex.

[vital hedge]

ok

[vital hedge]

by observing their vertex with same degree?

and it is the largest

[iron marsh]

the largest? How do you mean?

[vital hedge]

nothing ......

so can you teach me a procedure to determine

[iron marsh]

The same degree is important, but many regular graphs (all vertices have same degree) can have different linked graphs in each vertex.

[vital hedge]

yes

so we can check linked graphs only when they are all the same?

[iron marsh]

It's relatively simple: draw the linked graph for each vertex in both graphs, and see if you can find isomorphisms between them.
This seems like an undertaking, but what you may have noticed is that linked graphs are a lot simpler than the original graphs, so finding isomorphisms between linked graphs shouldnt be too terribly difficult.

It becomes a matching puzzle where you have to match linked graphs in graph 1 to linked graphs in graph 2.

[vital hedge]

oh~~~~~~

i seee~~~~~

thank u so much!!!!!

is that a theorem?

or just a method

since my teacher didn't teach me that way

[brave rock]

It should be mentioned that we don't know how difficult the graph isomorphism problem is exactly, but we have not found any polynomial time algorithms for it. This is just to say that it's a hard problem in general, and you're going to have to be creative.

[iron marsh]

Consider two graphs X and Y that are isomorphic to each other:
Then there is an isomorphism f that sends vertices in X to vertices in Y. For f(x)=y, prove that the linked graphs of x and y are isomorphic.

Finding graph isomorphisms is not particularly easy, and it's even harder to show that there is no such function. You have to find some special property between two graphs that should be preserved in an isomorphism (but isnt).

[vital hedge]

oh it's not enough to prove

[iron marsh]

It is not sufficient to prove it they are isomorphic, but it is a consequence of isomorphisms. So if it doesn't hold, we know the graphs are not isomorphic.

[vital hedge]

ok

pardon me

so how will u check this

if u have time

[brave rock]

Have you tried anything yet?

[vital hedge]

QQ

yes

[brave rock]

You should try and be creative on your own first.

[vital hedge]

but my method sycks

sucks

so there's no particular way to do this

?

the last question

or any technique ?

[iron marsh]

Hint: turns out what we did last time will help a lot

[tight hound]

You could try the method of linked graphs again.

[vital hedge]

oh~~

ok

I am going to sleep

thanks a lot

it's 1:09 at Taiwan

[iron marsh]

Actually, this is actually where it gets tricky. The Petersen graph on the left has linked graphs that are completely disconnected

[vital hedge]

hmm....

[iron marsh]

I said that wrong. It is edited now

Same thing for the 2nd, so all the linked graphs are the same

[vital hedge]

then how do u write the mapping function

[iron marsh]

First, you definitely shouldn't assume there is one.

[vital hedge]

ok

[iron marsh]

So the petersen graph on the left has diameter of 2 (largest distance between vertices) and girth of 5 (smallest possible cycle)

This properties should be preserved in an isomorphism.

Looks like they do. Although there are no guarantees, there is some potential on it being isomorphic.

Yep, I got it

@vital hedge you said you are going to bed, so I'll leave you with this for when you wake up.
I saw v1->v2->v3->v7->v6 makes a cycle of 5, so I decided to let that be the boundary of our graph, and then shove all the points inside. Mess around with the interior a bit, and you will get exactly what you need.

[weary tiger]

hi, I am confused a little here

https://intranet.missouriwestern.edu/cas/wp-content/uploads/sites/17/2020/05/Hamilton-Paths-and-Hamilton-Circuits-1.pdf

it says:

A Hamilton Path is a path that goes through every Vertex of a graph exactly once.
A Hamilton Circuit is a Hamilton Path that begins and ends at the same vertex.

I understand hamilton path, but the hamilton circuit its weird because now u will visit the starting vertex twice ?

and also I am not sure why the example of Hamilton path is not a hamilton circuit I think I can start from the node at center and end at it

I have an exam tommorow

I think it can have both ?

right hamilton path and circuit

[elder berry]

The definition of a Hamiltonian circuit is a bit bad. A Hamiltonian circuit is a circuit that goes through each vertex exactly once (of course starting and ending at the same one).

A graph can have:

• no hamiltonian path and no hamiltonian circuit
• a hamiltonian path but no hamiltonian circuit
• a hamiltonian path and a hamiltonian circuit

[weary tiger]

@elder berry thank u

[worldly hollow]

I'm trying to find chromatic number using graceful, i still don't know how to conclude the number from the step 'i've done.

[iron marsh]

@weary tiger what is graceful?

[worldly hollow]

One of algorithm used to find chromatic number i think

[iron marsh]

Oh, I'm not familiar with the algorithm, but finding the chromatic number is pretty easy in this example

[vital hedge]

I have a question , is there only a isomorphism of G1 and G2 when they are isomorphic?

[tight hound]

Yes

Two graphs are defined to be isomorphic if there exists an isomorphism between them.

[vital hedge]

thanks a lot

[jolly ledge]

don't ask to ask, just ask

[hushed comet]

or just nohello.net

[raven yarrow]

if you have two sets A and B, and you know there exists an injection from A to B, and you know there exists a surjection from A to B, is that enough to guarantee there exists a bijection from A to B?

specifically there’s no guarantee that the injection and the surjection are the same function

[little prism]

using axiom of choice, from the surjection you can get an injection B->A and then you can use schröder bernstein. no clue what happens without AoC

[raven yarrow]

ah excellent, schroder bernstein was what i was looking for

thank you!

[dapper coral]

Hi any1 knows how is this true?

[iron marsh]

Took me a while, but I have an answer to this

Consider the unit circle and R.
There is an obvious surjection x-> (sin(x),cos(x)), and if you are familiar with the projection map from the sphere to the reals, that is injective (but it misses a point on the sphere).
However, there is no bijection from the reals to the unit circle

[fossil mural]

...wait what

[iron marsh]

At least I'm pretty sure

[fossil mural]

aren't they both the cardinality of the continuum

[iron marsh]

I'm sorry, but I dont know what that means

[fossil mural]

hmm
the unit circle is basically [0,1] right? so the question is whether there's a bijection between [0,1] and R

oh wait there is

if you take a number in (0,1] and take its reciprocal, you can get any real number > 1

so get two copies of [0,1], leave one of them as it is, and take the reciprocal of the other, now you have all positive real numbers

ok so we actually want four copies of it to get the negatives as well

and then to show that having four copies of [0,1] is the same as having one, join them together into [0,4] and divide by 4

[iron marsh]

No, because if we think of it as an interval, the ends connect at the same place.

[fossil mural]

alright well [0,1) then?

[iron marsh]

But thinking it as [0,1) would be fine

Or, just [0,2pi) to make life easier

Okay, maybe there is one 🤔

[fossil mural]

adding one thing to an interval of real numbers doesn't matter
you can take a list of all the rational numbers in the interval, shift them all "forwards" in the list by 1, and put the extra point in the empty space at the start of the list you just freed

[ivory badge]

circle bijection [0, 1)

gg

[iron marsh]

No continuous bijection, but that's not the question we care about

Is there a bijection from [0,1) to the reals?

[fossil mural]

yes

[iron marsh]

Really? How does it deal with 0? 🤔

[fossil mural]

a single point is pretty irrelevant when you're dealing with infinite quantities

[iron marsh]

Okay, so this wasnt actually a counter to the problem. Damn

[fossil mural]

if you can find a copy of the natural numbers inside a set, then adding an extra element to the set doesn't change its size

[iron marsh]

Fair point

[fossil mural]

you can map that element to 0, 0 to 1, 1 to 2, 2 to 3, etc.

[iron marsh]

So really we can just shift the naturals by 1 and keep everything else in R the same

[fossil mural]

yep

[iron marsh]

Do you have an idea for this problem bee? I'm honestly not sure.

[fossil mural]

or you could shift the reciprocals of the natural numbers, since there are countably many of those too

[viral crown]

didnt sm1 already answer it 😭

[viral crown]

here

im a big fan of AoC tbh

[iron marsh]

I guess I dont wht Schroder Bernstein is to realize it was an answer :p

[viral crown]

dackid im not young like that anymore im not caught up w the slang

js got out of hs and already feeling old fr

[iron marsh]

That was me forgetting to put the a in what.

[fossil mural]

...i'm 3 and i don't get it either so i think you're fine

[ivory badge]

there's a homeomorphism from (0,1) to R

[iron marsh]

I feel like this was a bit, but you also genuinely looked it up so I'm not sure

[viral crown]

not a bit i was so confused 😭

[ivory badge]

there is no counterexample constructible, since choice says it's enough

[viral crown]

schroder bernstein is the thm which says "if u have injection a --> b and b --> a then |a| = |b|

[iron marsh]

Yea, I've pieced together that I was wrong here

[iron marsh]

Really? Woah!

[viral crown]

the proofs are surprisingly complicated for what seems like such a simple statement

[iron marsh]

That is definitely not an obvious claim

[viral crown]

really?? i thought it felt obvious and then i tried to work it out and failed miserably

that was my first intro to somewhat srs math

it was awful

[ivory badge]

Well, it kinda falls out from the idea where |X| <= |Y| iff injection X->Y

so depending on your definition this might be trivial

[iron marsh]

Does the 2nd part mean there exists an injection that sends x to y?

[ivory badge]

injection between sets

yes

[iron marsh]

Ohhh, so |X| is referring to the order of the set

[ivory badge]

|X| is cardinality

[iron marsh]

Yeah, I gotcha now

[viral crown]

the reason i thought it was obvious was bc if there's one to one for a-->b then you're mapping each element of a onto an element of b, and if there's one b-->a then you're mapping each element of b onto an element of a, and i couldn't see how it would be true if |a| wasn't equal to |b|

[ivory badge]

|X| = |im X| <= |Y|

[viral crown]

fwiw i could never have figured this out a year ago

[ivory badge]

the injection + surjection claim implying existence of a bijection might very much so depend on choice though

[raven yarrow]

? yea there is

[iron marsh]

It's already been addressed

[raven yarrow]

ah alright

[jolly ledge]

[unique dove]

I've started learning discrete math and ran across this statement that the set of rational numbers is in fact countable but doesn't elaborate at least not here and I was wondering the proof for that statement

[viral crown]

unfold the line

alternatively

https://math.stackexchange.com/a/659332/1012550

[unique dove]

Thanks

[vapid drift]

hello

is chat gpt correct

P: ¬(a ∧ c) → (b ⊕ a)

Let's construct a truth table for P:

a b c (a ∧ c) ¬(a ∧ c) b ⊕ a ¬(a ∧ c) → (b ⊕ a)
T T T T F F T
T T F F T T T
T F T T F T T
T F F F T F F
F T T F T T T
F T F F T T T
F F T F T F F
F F F F T F F
Therefore, P is a contingency.

Moving on to Q: c → ((a ∧ b) ↔ c)

a b c a ∧ b (a ∧ b) ↔ c c → ((a ∧ b) ↔ c)
T T T T T T
T T F T F T
T F T F T T
T F F F T T
F T T F T T
F T F F T T
F F T F T T
F F F F T T
Therefore, Q is a tautology.

Based on the analysis, the correct answer is:

A. P and Q are both tautologies

is this correct

[jolly ledge]

rules.

[vapid drift]

im not breaking any rules i believe please tell me the rules im breaking

[jolly ledge]

posting GPT messages

[vapid drift]

responses as in answers from chat gpt to questions askeb by users. Im asking if chat gpt is wrong here

<@&268886789983436800> am i wrong for this?

[jolly ledge]

also, GPT is wrong ._.

[hazy pine]

posting "is GPT wrong" isn't explicitly against the rules, no

though we discourage phrasing it like that

we'd rather you just ask a specific question about what's confusing you

(as in, not post GPT at all)

[vapid drift]

Is it the truth table thats wrong?

[jolly ledge]

oh he was referring to his GPT message above

[jolly ledge]

here

[hazy pine]

that isnt a response

[jolly ledge]

oh wait

[hazy pine]

so it isnt against the rules

[jolly ledge]

ah

I get what u mean

[jolly ledge]

yes

[hazy pine]

its just very hard to respond to it in a useful way

[jolly ledge]

yeah

tbh you shouldn't be asking GPT if you're stuck

chances are it will give you a wrong response

and if it does you may not be able to identify it's mistake

and build wrong concepts

• you should try the qn yourself if you haven't

[vapid drift]

I have

but i dont think im doing it correctly either

[jolly ledge]

what was your anser?

u could send it here

[vapid drift]

i dont have an answer i just have truth tables

[jolly ledge]

ah, then show it

[vapid drift]

wait i think if i ask you what wach one means i might be able to do it better

[jolly ledge]

hm?

btw this is the truth table for the 2nd proposition

[vapid drift]

(a ∧ c): and and c are the same. ¬(a ∧ c) not and c. b ⊕ a b and a are the same?

[jolly ledge]

ah, I see what you're trying to do. Sure, let's do it that way (personally I prefer this method of evaluating such expressions too)

[jolly ledge]

that circle with crosses inside... it's xor (or, but not both)... right?

[vapid drift]

yes

[jolly ledge]

or is it nand?

ah

then b xor a is true if b or a is true, but is not if both a and b are true

well, perhaps it's easier to break down these expressions

before evaluating their truth values with reasoning?

let's break down teh first one

[vapid drift]

ok

[jolly ledge]

$\neg (a \wedge c) \implies (b \oplus a)$

[vital dew]

Kiameimon | Welt Rene (glomed)

[jolly ledge]

so how can I simplify it? Are you familiar with this: $P \implies Q \equiv \neg P \vee Q$

[vital dew]

Kiameimon | Welt Rene (glomed)

[jolly ledge]

wait

I got it flipped

but yes

lemme fix it

[vapid drift]

what are the three lines again?

[jolly ledge]

it just means to say that they're loigically equivalent

[vapid drift]

oh ok

i get it

[jolly ledge]

P implies Q is the same as not P or Q

so we can use that to simplfy the first expression

[vapid drift]

is this right?

[jolly ledge]

$\neg (a \wedge c) \implies (b \oplus a) \equiv (a \wedge c) \vee ((b \vee a) \wedge \neg (a \wedge b))$

[vital dew]

Kiameimon | Welt Rene (glomed)

[jolly ledge]

notice that all I did expand the conditional

and translate the meaning of xor

into more elementary expressions

(b or a, but not both a and b)

following so far?

[vapid drift]

wait why did you include c in the expansion

[jolly ledge]

?

okok

[jolly ledge]

look here

now, just take P to be not(a and c)

and Q to be (b xor a)

[vapid drift]

i see

[jolly ledge]

from here, it's quite clear that this isn't a tautology. This statement is false if A and B are both true, and C is false

since not (a and b) will evaluate to false

and (a or c) will also be false

but at the same time, it is clearly not a contradiction

can you find some truth values for a, b and C to prov that?

am I going too fast for u? let me know

[vapid drift]

yeah sorry about the slow responses on my end just tryna comprehend some stuff

[jolly ledge]

ot

it's fine, let me know what is troubling you

[jolly ledge]

I'll do my best to explain my thought process

,rotate

[jolly ledge]

let's see what you've got here...

yep, looking great

quite frankly though, why do a truth table for it?

[vapid drift]

is there a way to think about it that wouldnt need a truth table?

[jolly ledge]

how I'd do it is see if I can eyeball some truth values for A, B and C which will make it false (that is to say, intentionally make our statement false)

[vapid drift]

for the a+b part only

[jolly ledge]

and then eyeball to see if we can pick some values of A B and C where it is true

if I can find such values then I can conclude that it's neither a tautology nor a contradiction, but if I can't, only then would I resort to a truthg table

as for the a + b part

this is clearly true when a or b is true, but not when they are both true

so, if a and b are both false, this is false

if a is true, b is false, this is true, same for if b is true, a is false

but if a and b = true, then our statement is false

[jolly ledge]

lemme tell you how I usually look through these kinda propositions to find this

so, basically, we know that a proposition $P \wedge Q$ is definitely false so long as one of them are false

bruh

latex

[vital dew]

Kiameimon | Welt Rene (glomed)

[jolly ledge]

right?

since P and Q can only be satisfied if both P and Q are true

[vapid drift]

right

[jolly ledge]

so looking at $((b \vee a) \wedge \neg (a \wedge b))$ specifically, I notice that if a and b are both false, or if a and b are both true, then we have this statement to be false

[vital dew]

Kiameimon | Welt Rene (glomed)

[jolly ledge]

now, what about the (a and c) part?

for this entire proposition to be false, I need that to be false too

[vapid drift]

b or a is true but both of them cannot be true just look at the values

i get it

[jolly ledge]

so if I were to assert that a and b are both true, or a and b are both false (so that the 2nd part is definitely false. Remember, I'm trying to test if this is a tautology or not, so I'm seeing if there is a case where our expression here can be false), is there a way which I can make (a and c) false too, so that I can conclude that the entire statement is false?

[vapid drift]

tautaulgy must mean that the final column everything is true correct?

[jolly ledge]

yep

so thing is

if I can find just 1 value where it is false

I can be certain that it is not a tautology

[vapid drift]

i get it I luv u

[jolly ledge]

so that's what I'm doing, intentionally doing all I can to make this propositon false

and if I can't, then it is a tautology either that, or I may have overlooked something XD

oh, by teh way

https://stanford.edu/class/cs103/tools/truth-table-tool/

this helps you generate truth tables