discrete-math

[rapid mural]

dont ask to ask just ask

[plucky void]

p - w ~ 23 - t

[cinder burrow]

can anyone help me with one problem

im stuck

Consider a relation S on the set of integers Z, defined as follow:
x S y ⇔ x≡ymod5 for all x, y∈Z.
Verify whether S is equivalence relation or not.

[sudden minnow]

what is the definition of an equivalence relation

[umbral blade]

If Satisfiability is proven not to be in P, then factoring is not in P

Would the proposition be true or open?

I’m thinking open but what happens if an NP-Hard problem is proven to not be in P

[solemn zephyr]

How many numbered graphs are there on n vertices (that is, the vertices are distinguishable and we are not interested in isomorphisms) that have all degrees even and nonzero?

[sudden minnow]

I wasn't asking you mate

[cinder viper]

Am I correct with my understanding of injective/surjecive functions: Since injectivity and surjectivity are properties of functions, then all elements of the domain must map to something. It's exactly what they map to that determines whether they're injective or surjective. ie. There will be zero elements of the domain that do not map to anything

[ember obsidian]

yes

much like an even number is a special kind of integer. theres no such thing as an even number thats not an integer

[cinder viper]

Thanks, that clears up years of confusion 🙂

[haughty garden]

We already have problems that are in NP-hard but not in P; for example, the Halting Problem. This does not say much about anything because NP-hard problems need not be in NP. If X is a problem in NP-hard, then any problem Y in NP can be reduced to X in a polynomial amount of time. This does not require X to be in NP

[haughty garden]

This should be open. It is not known whether there is a reduction from SAT to factoring. There is, however, a reduction going the other way; that is, there is a reduction from factoring to SAT. So, if SAT is not in P, we can’t deduce whether factoring is too

[woeful idol]

Any resources on how to do arithmetic on reduced obdds? Tried googling but can’t find anything. For example take the conjunction of these two obdds

I hate these darn diagrams

[haughty garden]

It might help to keep track of when both OBDDs lead to 1; the conjunction isn’t too bad because you know that any other combination must become 0

For example, in the first OBDD, if y is true, then any condition on z gives a 1

Therefore, the conjunction can only point to 1 if y is true and z is false

It is easy to see that any other combination must point to 0

[tropic creek]

Can somone help me with this problem?

[haughty garden]

What problem?

[tropic creek]

A password consists of 12 characters using upper or lowercase letters and the digits 0 through 9.
What is the probability of randomly guessing this password on one attempt?

[coral parcel]

Was the password randomly chosen too?

[tropic creek]

this is all the info

[coral parcel]

If it was picked by a human, you can't assume all 62^12 possibilities are equally likely, and guessing CorrectHorse will yield a significantly better probability than guessing rs2pNNbvMYBr. But it's difficult to quantify by how much.

[true venture]

Say I have an integer composition of some number m, with n parts, and where the differences between neighboring parts is within {-1,1}.
Ex. 4 3 2 1 : m=10
And you then look at all the 2^(n-1) possible compositions of length n (for any m,with the same first part b, minimum b is n) to find all values of c. Where m = (b*n) + c, b being the first part of the composition.
Calculating these for n up to 5, the values of c are either all odd numbers from one to the n'th triangular number or all evens from 0 to the n'th triangular number. However certain values of c are repeated, I'm lost on how many times a certain value of c will appear?

[sonic grail]

isn't satisfiability also in NP tho

[haughty garden]

It is currently not known if SAT is in P, though, and this is precisely the P vs NP problem. If SAT happens to be in P, then this shows that P = NP. More generally, if any problem in class NP-complete happens to also be in class P, then P = NP

[sonic grail]

that's the point, no
sat is in np, factoring is np hard so if sat isn't in p, neither is factoring

.. wait factoring is maybe not np hard

nvm lol

[solemn zephyr]

How many numbered graphs are there on n vertices (that is, the vertices are distinguishable and we are not interested in isomorphisms) that have all degrees even and nonzero?

[woeful idol]

If we have this OBDD:

Is O prime here just the node z?

or does it also include the terminal node 0?

[weak forge]

I have a problem related to chromatic polynomials (graph theory) can anyone help me.

[muted gate]

i need some hint on how to prove de morgan's 1st law

$(A \cup B)^{c} = A^{c} \cap B^{c}$

[vital dew]

texaspb

[muted gate]

somebody please

[grand totem]

If you have the corresponding de morgan law for logic at your disposal then its just a straightforward application of that, otherwise try double inclusion

[muted gate]

i forgot to mention

I'm trying to prove this identity in a probability context

so like

for any two events E and F

$(E \cup F)^{c} = E^{c} \cap F^{c}$

[vital dew]

texaspb

[muted gate]

wdym by double inclusion

[grand totem]

Proving the left side is a subset of the right side and vice versa

[muted gate]

ha

alright!

that sounds easy, i'll try

[weak forge]

Can anyone answer my question.

I calculated Number ways to colour graph in 1 or 2 colour is 0 and in 3 colour is 12,in 4 colours is 144 and 5 colours is 720

I calculated chromatic polynomial but i am not sure about it . Can anyone help me or correct me if I am wrong somewhere.

<@&286206848099549185>

[plush pond]

!help

[lofty cloud]

Please read #❓how-to-get-help

[steep creek]

When I took discrete math I felt like the number one thing that I never really got was proof by induction. Does anyone have any good sources for me to look for to get better at ?

[honest holly]

@steep creek any discrete math textbook should have lots of problems for you to do...

Are you struggling with what induction means and why it's a legitimate way to prove things?

Or just how to apply it

Because generally, how to apply it is completely dependent on the problem you are working on

[steep creek]

No, I don't believe it's that. I can see that it's legitimate. However, I have trouble problem solving my way through these steps to verify any type of proof

[honest holly]

Can you give an example?

I'm having some trouble gleaning your difficulty with induction

[steep creek]

Here's a practice problem I had a couple months ago.

Like my problem here is I wouldn't know where to start. Like I'm only somewhat sure in starting with creating base cases

[honest holly]

Okay so what is base case here

[steep creek]

I assume 1

[honest holly]

Sure,

So now assume it holds for n>=1, show it holds for n+1

[steep creek]

So I just substitute n for n+1. Which I believe gives me $\frac{3n^2}{2} + \frac{9n}{2} + 3$

[vital dew]

Alexs

[honest holly]

Yes, that's what you want to show

You want to show the left hand side is equal to that

But you don't know a priori that the LHS is indeed equal to that

[steep creek]

So you're saying I have to prove the equation with n+1 plugged has to be proven that it is equal to the formula I just gave?

[honest holly]

Yes

Assuming the identity holds for n

[steep creek]

Ah ok, so I think this is where I might get lost at

I think I have an idea

@honest holly Would this be on the right track

[honest holly]

Yes!

However, you don't want to write the LHS is equal to the RHS in the first step

Because you don't actually know it's true yet

All you are doing is manipulating the left hand side

[steep creek]

Yeah I was thinking about that, I think I just had it up there because it was fresh from what we had

But what would I do after this

I assume I substitute the first part of step 3 with 3/2k(k+1)

[honest holly]

Well why do you have both k and n

Pick one and stick to it

[steep creek]

Sorry for being confusing with the K variables I got used to doing that from class

[honest holly]

Okay

Anyways yes you are on the right track

[steep creek]

Oh ok my problem with this is wouldn't substitution defeat the purpose of proving this?

[honest holly]

No you are assuming it holds for n and proving it holds for n+1

[steep creek]

Ahh it's because the purpose of induction is by proving with n+1

Right

@honest holly I think I messed up on my algebra here

I'm not sure

Nevermind

Thank you for the help @honest holly !

I had the math right

[reef dirge]

how do i find questions with answers to practice Naive set theory

[royal reef]

What graph theory books related to the Zarankiewicz problem should I read?

[proud needle]

I'm reading Diestel's Graph Theory and I was wondering what exactly this is:

$\mathbb{Z}/n\mathbb{Z}$

[vital dew]

sxbuto

[proud needle]

What exactly is it? I am confused on how the elements are defined.

Also what does it mean as regarding $\mathbb{Z}_2 = {0, 1}$ as a field mean?

[vital dew]

sxbuto

[proud needle]

What does nZ mean in the definition?

Also, what does this section mean:

[high carbon]

nZ refers to the integer multiples of n. Hence, 2Z={..., -4, -2, 0, 2, 4, ...} for example.

As for the second question, this is a sequence of definitions, so I'm not sure how to clarify it any further without more specific questions about it.

@proud needle

[proud needle]

Thanks, I will clarify my questions.

[high carbon]

[proud needle]

So what is the set Z/nZ

[high carbon]

Ah, yes, taking what I said about nZ a bit further, we get the quotient set.

Strictly speaking, this Z/nZ is something a bit gross: we collapse everything that differs from a multiple of n by an integer 0,1,...,n-1 into the same equivalence class.

Now this definition is a bit obtuse, and this definition does not make any mention of a simplification.

[proud needle]

Okay, that makes sense.

[high carbon]

However, it is isomorphic to the set of integers modulo n:

Yup!

[proud needle]

Okay!

[high carbon]

And then the set of integers modulo n is exactly that set of representatives.

We then sort of inherit the ring operations from Z on this new ring, Z/nZ.

Namely, we work modulo n. Does that ring a bell?

Modular arithmetic is a common name.

[proud needle]

Yeah. I'm not familiar with any abstract algebra concepts.

I understand mod arithmetic though.

[high carbon]

Oh, okay! Then considering this is the discrete math channel, I may not have needed to say any of that. 💀

But okay, that's still good!

[proud needle]

I don't understand how the "refined partition" is defined.

A partition is just splitting up the set into k subsets s.t. all subsets in the partition are disjoint right? Ex. {1,2,3,4,5} partition = {{1}, {2,3,4}, {5}}.

[high carbon]

Correct.

Now for the refined bit from me... Just looking at it, I don't know that I've ever worked with it, so I can't give you much more than is already there. I can tell you that it still needs to be a partition, and so we call it a refinement because there are (in general) going to be more sets in the refined partition.

That's a generic term for something larger in a way that is more useful in math.

(In my experience.)

[proud needle]

Okay, thanks! You've been a lifesaver lol!

[high carbon]

Aww, you're welcome; thank you!

[high carbon]

You think you could give an example of a refinement of this partition? :3c

[muted gate]

guys

how can we generalize this following property

$A_{1} \cup A_{2} = A_{1} \cup (A_{2} \setminus (A_{1} \cap A_{2}))$?

[vital dew]

texaspb

[muted gate]

make the union of ttwo sets be the same as the union of disjoint sets

🥴

the expressions start to get sorta complicated when n>=3

[vale cairn]

Yeah you can do it by induction

Let B1 = A1 and then B_n = A_n \ (B1 cup ... cup B_{n-1})

[muted gate]

yeah ive see nthis formula before

but like

shouldn't it be an intersection after the set minus

[vale cairn]

Why

I'm taking away everything which we've already written down

And leaving everything else in

[muted gate]

why do we need an intersection here then?

is what i don't get

i guess for the case n=2 it's easily seen in a venn diagram

OOOH

omg

NOW i get it

lol

after about 6 mins of intensive thinking

[vale cairn]

I mean tbf, usually I would just write that as A1 cup A2\A1

which lines up with what I gave ^

[muted gate]

so this is equivalent to A1 cup A2\A1 right

[vale cairn]

Yes

[muted gate]

nice

that helps a lot with my problem

thanks

[vale cairn]

np!

[muted gate]

alright

hm

well i have encountered another problem

I need to extend that to an infinite amount of sets

lol

taking n -> \infty

[vale cairn]

these are defined recursively

so it's fine

[muted gate]

oh true

perfect

[proud needle]

Lol I can't find it in the book and I can't find it on the internet. I think refinement is a broad word.

[high carbon]

Aaaah, fair enough! Well, I see four options.

That set with three elements can be broken up further if we want.

I see one option is {{1}, {2,3}, {4}, {5}}. This satisfies the definition of a refinement. Can you see why? @proud needle

[proud needle]

That makes perfect sense!

what's the difference between homomorphism and isomorphism for graphs?
is it that for isomorphism the graphs are "equal" but for homomorphism a graph is a "subgraph" of another?

[quaint elm]

somebody talking about powerset???

anyway subsets are great

[quaint elm]

isomorphism is a to-way mapping

[proud needle]

ohh

and homomorphism is only one way?

[quaint elm]

yup

[proud needle]

would the top be isomorphic because its bijective, but the bottom is injective, so its just homomorphic

[quaint elm]

yup

but how does that relate to edges and stuff?

https://youtu.be/RatkBWHUSqo

[proud needle]

oooh thanks!

[quaint elm]

I got stumped by the notation here, but seems this is hitting at what I'm looking for

[quaint elm]

I'm trying to figure out graphs as well

[proud needle]

i think picturing homomorphism as "subgraph" is fairly accurate

[coral parcel]

Beware that there are two possible concepts of graph homomorphism. Either you require that "a and b are neighbors => f(a) and f(b) are neighbors", or you require that "a and b are neighbors <=> f(a) and f(b) are neighbors".
Claims that are true about one of these concepts may be nonsense if understood to be about the other.
But they give rise to the same concept of "isomorphism", which is the more important concept.

[proud needle]

Claims that are true about one of these concepts may be nonsense if understood to be about the other.
Wdym?

[coral parcel]

Well, perhaps not "nonsense" but "blatantly false".

[ember obsidian]

some claims are true under one def but false under the other

[ember obsidian]

so the video uses the 1st def of homomorphism that tropo mentioned

[coral parcel]

Topologists tend to favor that definition. Logicians may find the other one more natural/useful.

[proud needle]

i mean the second def is just isomorphism, is it not?

[coral parcel]

No, because the mapping on vertices is not required to be bijective.

[sudden minnow]

sometimes the 2nd definition of homomorphism is referred to as strong homomorphism

[proud needle]

a and b are neighbors <=> f(a) and f(b) are neighbors

wait how is this not isomorphism?

[coral parcel]

Because f is not required to be bijective.

[proud needle]

ohhh

mb

in the context of graphs, f would always be bijective if |V(A)| = |V(B)| right?

[coral parcel]

So we can say, for example, that a bipartite graph is any graph that has a homomorphism into the complete graph K_2, but all bipartite graphs are certainly not isomorphic to K_2.

[coral parcel]

No. Counterxample: if you have a 4-cycle with vetices {0,1,2,3} and edges {0,1}, {1,2}, {2,3}, {3,0}, then defining f(0)=f(2)=0 and f(1)=f(3)=1 gives a strong homomorphism from that graph to itself that is not an isomorphism.

[proud needle]

Graph G
   A--------E
  /          \
 B --- C ---- D

Graph F
  a-----b
 /
c

mapping:

M: V(G) -> V(F)
A = C = a
B = D = c
E = b

A and B are neighbors, a and c are neighbors.
A and E are neighbors, a and b are neighbors
This means that Graph G and Graph F are homomorphic right?

[coral parcel]

Okay, first off, do not make the mapping itself invisible. Saying A=C is nonsense.

[proud needle]

Wdym "invisible"

[coral parcel]

What you most likely meant to write was M(A) = M(C) = a etc -- but you left out the M, producing the nonsense claim that A = C = a.

[proud needle]

ohhh yeah thats what i meant

[coral parcel]

The = sign means "is the same thing as". It does not mean "and the thing we get is then".

[proud needle]

👍

[coral parcel]

That is not a homomorphism under either of the definitions, because E and D are neighbors in G, but M(E) and M(D) are not neighbors in F.

[proud needle]

would it be a homomorphism under the first definition if i did the mapping from F to G

wait no nvm that wouldn’t be a function

[quaint elm]

Yes, the notation was an absolute disgrace and utterly inelegant, such abuse of notation should be left to peasants only. That is if you don't intend to become one, dear sir

Nah, man play around with notation, until it feels like you own it for yourself

you'll adopt the common notation after a while

that's how it usually goes for me

[proud needle]

ok thx 🙏

[quaint elm]

btw there is a thing called equivalence classes

and equivalence relation

[proud needle]

yeah i heard of them

[quaint elm]

when you equip that relation, you count them as equal

[quaint elm]

cool, cool I am just getting comfortable with partitions

but after that I think my grasp of them will be solid

[proud needle]

equivalence relations are things like congruence, =, similarity, etc... right?

[quaint elm]

yeah, and it's quite arbitrary sometimes

if you have a clock 24 kind of = 12

elements in {-24, -12, 0, 12, 24, 36, 48, ...} all have that congruence or whatever with each other

[proud needle]

The definition of a homomorphism in the textbook im using is the following:

[rapid mural]

There's a definition of equivalence relation

[quaint elm]

symmetry, reflexivity and transitivity

[proud needle]

Let $G = (V, E)$ and $G' = (V', E')$ be two graphs. A map $\psi: V \rightarrow V'$ is a homomorphism from $G$ to $G'$ if it preserves the adjacency of vertices, that is, if ${\psi(x), \psi(y)} \in E'$ whenever ${x, y} \in E$.

[vital dew]

sxbuto

[quaint elm]

nice the arrow cleaned it up a notch

[proud needle]

Lol yeah.

[quaint elm]

so...

how would a graph like that look like

the connections are the same?

or does the neighbors vary?

[proud needle]

Yeah i was thinking of that still. But by that definition, G to G' can be a homomorphism even if G' is smaller than G.

One sec, lemme draw it rq.

[quaint elm]

I think of it as overlapping nodes of the edge

so you have an edge who's end vertex you overlap with another edge which could stand on its own and then be counted, but when they overlap in the same "space" whatever space means in this topology... it is only counted once

[proud needle]

yeah i think so as well

[quaint elm]

I usually like to say topology is the neighborhood properties of a thing

[proud needle]

i thought topology was more of a folding geometry thing

[quaint elm]

well, if you have people standing in a circle

three people in a cycle

each of them have two neighbours

and it might look more like a triangle than a circle

[proud needle]

OHH I GET THE LINK BETWEEN HOMOMORPHISM AND ISOMORPHISM NOW.

[quaint elm]

WHAT??

GIVE ME THE INSIGHT NOW

[proud needle]

if the inverse mapping is bijective and the inverse mapping is also an homomorphism its an isomorphism

basically you see my example? inverse psi would not be homomorphism so graph A and graph B aren't isomorphic

[quaint elm]

yeah, but how is the mapping thing only surjective? Edges seem so intrinsic to a graph, isn't that all a graph is? Is it an artifact of what we call the edges??

how they need nodes to be distinct??

I'm confused if you can't tell

[proud needle]

wdym "Edges seem so intrinsic to a graph, isn't that all a graph is? Is it an artifact of what we call the edges??"

lemme show an example of isomorphism

[quaint elm]

btw you used phi, phi stands for f in greek mate

fi

[proud needle]

shoot my bad

i get mixed up by thes like crazy

[quaint elm]

yeah, well math people use greek as an extra font, f in greek is just phi so it stands out as a function name

[sudden minnow]

to have an inverse you need to be bijective in the first place

but yes an isomorphism is a bijective homomorphism where the inverse is also a homomorphism

[quaint elm]

me too btw, but you'll get used to it and the symbol will look more special then

[quaint elm]

yup

[sudden minnow]

^this is true for every mathematical structure where there is a notion of a homomorphism

[quaint elm]

or you loose information about what it was before

[proud needle]

Does this mean a 4-cycle graph isn't isomorphic with itself as the mapping isn't bijective?

Oh thats only for that specific mapping.

[coral parcel]

Everything is always isomorphic to itself. But that doesn't mean that every mapping to itself is an isomorphism.

[proud needle]

Okay yeah that makes sense.

Isomorphism and homomorphism being a characteristic of the mapping and not the whole mathematical structure sometimes throws me off.

[coral parcel]

Yeah.

[quaint elm]

you speaking facts

[coral parcel]

We talk about objects being "isomorphic" to each other because merely knowing that some isomorphism exists is often interesting information in itself. But it is very rare to speak about "homomorphic objects", because there's usually no interesting conclusions to draw from that without knowing more about the homomorphism.

[proud needle]

Ohh okay. Typically, we tend to focus more on isomorphisms right? rather than homomorphisms

[coral parcel]

Definitely so in graph theory.

The weighting is less lopsided in most of abstract algebra.

[quaint elm]

examples of something being true for the supercase -> subcases

[proud needle]

So in context of graphs, a mapping f: A -> B is an homomorphism from A to B if A is "contained" within B?

[quaint elm]

contained in an edge that contains/has B?

[coral parcel]

That's a much vaguer intuition than the actual definition, but sure, it will serve you in some cases.

[proud needle]

okay, i'm getting a better picture

[coral parcel]

The "contained in" intuition is really better captured by looking at injective homomorphisms only.

Then the two notions of homomorphism correspond to talking about either subgraphs or induced subgraphs.

[quaint elm]

I mixed up A and B as vertices and not Graphs mate

and that didn't make sense so I made a small superset

an edge

[proud needle]

A and B are sets of vertices, i made an error I mean f: V(A) -> V(B)

[proud needle]

do surjective homomorphisms exist?

[coral parcel]

Sure.

For one things, isomorphisms are bijective, so in particular surjective.
But we can also look at

G:   1---2---3     H: 4---5

and then say f(1)=f(3)=4 and f(2)=5. That's a surjective but not injective homomorphism.

[proud needle]

Oh that makes sense

[quaint elm]

what is A, B? The inputs. I don't understand, relations flying left and right

[proud needle]

Is there a "method" for finding a certain mapping?

[proud needle]

A and B are graphs. V(A) are the vertices of A, V(B) are the vertices of B.

[quaint elm]

Ok, thanks

[coral parcel]

There's not a good general method. It's a famous unsolved problem whether there is a polynomial-time algorithm for determining whether two graphs even have an isomorphism between them. So in practice for exercises, just winging it by ad-hoc reasoning is what you do.

[proud needle]

Oh okay.

Does that problem fall into the P vs NP stuff?

Is there a polynomial time algo for verifying a mapping is an isomorphism?

Oh wait there is

[coral parcel]

Yes, just check the condition for all pairs (a,b).

[proud needle]

yeah

[coral parcel]

This means that deciding graph isomorphism is in NP. It is one of the few "natural" problems that are known to be in NP, but neither known to be in P too, nor known to be NP-complete.

[proud needle]

Cool.

[proud needle]

i think the induced subgraphs better fit the characteristic of "containment"

[coral parcel]

It depends on what your application is, really.

[quaint elm]

This NP or P thing needs a Gödel's theorem thing, cuz it just seems like a consequence of something being impossible

[fervent raven]

quick question, a set cannot be a proper subset of itself right?

[haughty garden]

Correct

[serene mural]

. 1296
|
16 648
| |
8 324
| |
4 162
\ /
2

For this hasse diagram, do i need to connect every number in range 4 - 16 to every number in range 324 - 1296?

[stray reef]

what's the original problem?

[serene mural]

R = {1,2,3,4,6,8,9,12,16,18,24,27,36,4854,72,81,108,144,162,216,324,432,648,1296}
xRy↔ x|y.

this is my current answer

[stray reef]

ah, so it's that set ordered by divisibility

yeah, 4 should be joined to 324 and 8 to 648 and 16 to 1296

[serene mural]

i see, thanks

[quaint maple]

J contains all real numbers between 0 and 1, R contains all positive real numbers, how do i prove that |J|=|R|?

[coral parcel]

Find a bijection between them.

[muted gate]

the real numbers are so fascinating

[coral parcel]

Note that this requires you to first have decided on one particular function that you claim is a bijection.

[rapid mural]

Might be easier to find a bijection from $\bR$ to $(0, 1)$ actually. This is equivalent to finding a bijection $f: (0, 1) \to \bR$

[vital dew]

DerpZ

[haughty garden]

Another way is to invoke the Schroder-Bernstein theorem (if you've been taught that) and find two injections. One injection is quite straightforward because of subset inclusion, the other injection is a little less straightforward

[rapid mural]

machine learning moment

[glacial flame]

So in my discrete class, I learned of onto and one-to-one meaning the same as surjective and injective, respectively. Additionally, I learned that these are properties that non-function relations can have. These are both incorrect, right (particularly the onto part and lack of function requirement part)?

[cerulean wind]

yes

[glacial flame]

I love getting taught incorrect information 🙃

[grand totem]

it's not incorrect, but quite uncommon (outside of set theory at least)

[glacial flame]

onto has an additional requirement alongside surjective, to my knowledge

Oh shoot maybe I’m talking about one-to-one and injective

[grand totem]

how i interpreted the question was whether the notion of injectivity or surjectivity may also be applied to general relation (and not just functions)

[glacial flame]

??

Ah okay

As opposed to?

I don’t know what you mean by “actual” 👀

[grand totem]

anyway, you may call a relation R injective if (x, y) ∈ R and (x', y) ∈ R implies x = x', i.e. every y is related to at most one x (this is equivalent to the inverse relation R^{-1} being functional). If R is actually a function then you can prove that R is injective (in the sense we just described) iff R(x) = R(x') implies x = x' (which is the usual definition for functions)

similar thing with surjectivity - but again, no one really does that

[glacial flame]

Yea we learned it the first way

Similar deal with onto; every co-domain value is related to at least once

[grand totem]

Nothing wrong with that, just saying that it isn't that common (hence why people might assume it's incorrect)

yea, R is surjective onto a set Y if Y is a subset of the range of R

[glacial flame]

Ah here it is; this is what I was meaning to refer to which differs from what I was taught

[grand totem]

What is the definition given in your class?

[glacial flame]

One-to-one $\equiv$ injective

[vital dew]

JJCUBER

[glacial flame]

Aka it can be applied to any domain+codomain even if not functional

Which changes the answer to counting problems on relations

[grand totem]

My guess is that they're (implicitly) only talking about functions (= functional relations), in which case you're back to the definition above

[glacial flame]

Nope, the first relations we learned were onto and one-to-one and they were for any sets even when non-functional

Functional relations were the last thing we learned about

In our problems, counting problems about one-to-one had a different answer than functional + one-to-one

Also, we just learned the terms onto and one-to-one; later in class, our prof said surjective and injective were synonyms

Towards the end of the semester, I showed him what I found about one-to-one having an additional constraint of being functional. I think I recall him saying he wasn’t aware of that and would change it for future semesters.

[grand totem]

that wikipedia definition isn't set in stone and considering how rarely one speaks of injective relations (that aren't also functions) it is far from being standard terminology

so just use your profs definitions if they're consistent

[glacial flame]

Yea I continued to use his definition throughout the course; now that it is over, I’m just trying to get closure on what is “common”/“proper”/“correct” elsewhere in the math community

And it sounds like the wiki definition is what’s most common, correct?

Or wait are you saying injective is typically functional implicitly/by definition?

[grand totem]

lets just say that without context if you were to ask what one-to-one means, people would most likely immediately assume that you're asking about functions and then the only distinction is usually whether you only mean injectivity (in which case it's usually just called a one-to-one function) or if it should also be surjective onto a given codomain (in which case it's sometimes referred to as a one-to-one correspondence)

[glacial flame]

So typically all of these relations are in the context of functions

And a one-to-one correspondence means bijective?

[grand totem]

yes

[glacial flame]

Interesting, thanks!

[grand totem]

injectivity (of functions) is usually stated in the f(x) = f(x') => x = x' fashion because it doesn't fully commit to the materialistic set theory view of a function as a special set of ordered pairs. so in other foundations (where functions are taken as a primitive concept instead of being defined in terms of sets) it still makes sense (and one might argue that it is much closer to general mathematical practice)

[glacial flame]

Yea our class was… interesting

It was very formal in many ways, but I think it diverged a bit in some places

[glacial flame]

I mean I have a YouTube… I’m not a fan of myself that’s for sure.

[covert bolt]

also dumb qn but what does min mean

[muted gate]

the minimum element in that set

so in that case it's the minimum value between 2^i and 2^n-i

[covert bolt]

wait why is it when 2^i=2^(n-i)

[muted gate]

that's the maximum

"The maximum value is achieved when 2^i and 2^(n -i) are as equal as possible"

[covert bolt]

yea but idg why

[muted gate]

but idk the big picture

i was just answering about the meaning of min

[covert bolt]

ooo

o wait I get it now thancc

[modest swan]

can someone help me with a basic question, in propositional logic, whats the difference between a logical formula and a function

[muted gate]

a formula is a sequence of terms

a function is a n-ary predicate which is always preceded by n terms

I think that's the principal difference

so a function attributes property to each term

[last flower]

Hello, can someone help me with this question :
let f and g two continuous functions on [a;b] and ∀x ∈ [a, b], f(x) < g(x)
Show that ∃m>0 / ∀x ∈ [a, b], f(x) + m < g(x).

tbh i don't know how to start this problem

[coral parcel]

That's definitely not discrete math. #real-complex-analysis or #calculus would be better. (Hint: consider the function g(x)-f(x) and hopefully you know something about the range of a continuous function on a closed interval).

[dull blade]

Of course it's not discrete it's right there in plain sight

Most original math joke

[young rover]

Can somebody help me out with 3rd question ?

[muted gate]

,rotate

[proud needle]

I need some help trying to understand a proof.

Proposition: The number of vertices of odd degree in a graph is always even.

[coral parcel]

How many ends of edges does the graph contain?

[proud needle]

2 times the number of edges right?

[coral parcel]

Yes.

And the number of ends of edges is the sum of all the node degrees.

[proud needle]

The proof is as follows:
As $|E| = \frac{1}{2}\sum_{v \in V}d(v)$ is an integer, $\sum_{v \in V}d(v)$ is even.

[vital dew]

sxbuto

[proud needle]

Yes, but we are considering the number of odd-degree vertices right?

[coral parcel]

$$ \sum_{v\in V} d(v) = \sum_{d(v)\text{ odd}} d(v) + \sum_{d(v)\text{ even}} d(v)$$
The last sum is even, since the LHS is even too, the middle sum must also be even.

[vital dew]

Troposphere

[coral parcel]

But the sum of an odd number of odd numbers can't be even. Since the terms are definitely odd, there cannot be an odd number of them.

[proud needle]

Oh thanks that makes perfect sense.

[proud needle]

$\epsilon$ is a function referring to half the graph's average degree. Why is there a colon ($:$) next to it? Is it a notation meaning something?

[vital dew]

sxbuto

[vale cairn]

It looks like the normal (non-mathematical) usage of :

[proud needle]

oh lol it is

[analog hound]

Isn't this false if we select 1 eleven times?

[rigid oriole]

rip

different is likely intended

[analog hound]

Oh yeah I thought they meant integers between 1 and 29 but that's a better fix

[coral parcel]

It makes sense, you can select 10 different numbers less than 29 without reusing a prime factor (1, 2, 3, 5, 7, 11, 13, 17, 19, 23) but then the 11th needs to reuse one.

[haughty garden]

I immediately think of using the prime counting function

Oh beaten to it

There are 10 primes <= 29 so choosing the 11th integer must share a common prime divisor

[rapid mural]

yup so

you let x be in A cap C arbitrarily

this is correct

because recall what the subset is saying here

[proud needle]

What does $V := {0, 1}^d$ where $d \in \mathbb{N}$ mean? The book says that $V$ is the set of all $0$-$1$ sequences of length $d$.

[vital dew]

sxbuto

[sudden minnow]

cartesian product d times

[proud needle]

thx

[analog hound]

Yes

[analog hound]

I was having trouble making my proof this concise, thanks

[proud needle]

2. \textbf{Let $d \in \mathbb{N}$ and $V := {0, 1}^d$; thus, $V$ is the
   set of all $0$-$1$ sequences of length $d$. The graph on $V$ in which
   two such sequences form an edge if and only if they differ in exactly one position
   is called the \emph{$d$-dimensional cube}. Determine the average degree, number of
   edges, diameter, girth, and circumference of this graph.}

Is the girth always 4? If so, how would I prove that?

[vital dew]

sxbuto

[stray reef]

the girth is the length of the shortest cycle, yes?

@proud needle do you still need help w/ this

[proud needle]

Yes

[proud needle]

Yep, it is.

[stray reef]

right

the girth of any graph is then at least 3

show that your graph cannot have a cycle of length 3 (or indeed any odd length)

oh also theres an edge case (pun not intended): for d=1 you will have a graph consisting of a single edge

[vital dew]

Arnab Pal

[stray reef]

wrong channel, by a long shot.

did you mean #calculus?

your ramblings seem more calculus-adjacent than discrete math.

there's also #discussion, or #math-discussion, or maybe even #chill.

[violet rose]

Oh

[stray reef]

integration is still calculus. it is not discrete math.

[violet rose]

Yeah sorry

[unkempt fiber]

I ask graph theory here or?

I'll just post my question as well then:

I don't understand why size of minimum vertex cover of a graph ≥ V(G). I think it should be ≤ V(G)

I believe minimum vertex cover of a graph is the set of all vertices of the graph that have an edge on them, so basically covering all possible edges with the minimum number of vertices

how is that ≥ V(G) ?

[hybrid bolt]

where are you seeing it should consist of at least as many vertices as the graph already has? your intuition sounds right if it corresponds with the definition I'm familiar with, that the size of a minimal vertex cover has to be less than or equal to the size of V(G) because the former is a subset of the latter, unless there's a definition or idea here I'm totally missing

[unkempt fiber]

My notes say:

A vertex cover is a subset of V(G) duch that complete subgraph on V(G)\S is empty.
then, it writes: Let L(G): the size of minimum vertex cover, then-
Proposition: v(G) ≤ L(G) ≤ 2v(G)

am I mistaking v(G) and V(G) here? is v(G) something else perhaps?

[haughty garden]

It seems like they define V(G) to be the vertex set of graph G, meaning that v(G) is something completely different. They should define that notation somewhere in your lecture notes

[unkempt fiber]

the proof has the following line about v(G)

If M is a maximum matching of size v(G). Let M = {e_1, ..., e_v(G)}. Let e_i = {x_i, y_i}. Then any vertex cover S must contain one element from {x_i, y_i} for all i.
=> |S| ≥ v(G) s.t. x_i, y_i are all distinct
=> L(G) = min |S| ≥ v(G)

[ionic field]

Hi , can i ask where can found inclusion exclusion principle problems?

[unkempt fiber]

no worries got it: it's the size of maximum matching in G

[ionic field]

I didn't find

i found it thank u , i hope u give me more

I'm looking for exams or like that i found just application

[weary tiger]

What's the best source for learning discrete structures if you're trying to self teach?

[coral parcel]

What do you mean by "discrete structures"?

[weary tiger]

sorry i meant discrete math

[coral parcel]

"Discrete math" is not really a unified thing -- is more a catch-all category that means vaguely different things at different institutions that have courses by that name. Often it might simply mean "all the bits of math that we insist CS students need to learn".

[unkempt fiber]

Let G be a graph. Let W be the set of vertices of a matching. Then prove that there exists a maximum matching whose vertices contain W.
How do I go about proving this?

[coral parcel]

Have you learned about augmenting paths?

[unkempt fiber]

no

[coral parcel]

Alternating paths? Berge's theorem/lemma?

[unkempt fiber]

Wait a bit.. I'll go through my notes once again.

nope

[unkempt fiber]

so, a disconnected graph is when deleting an edge isolates even if just a point on the graph?

[coral parcel]

A disconnected graph is when there are two nodes that don't have a chain of edges connecting them.

[unkempt fiber]

T.p. If $(X_1, Y_1)$ and $(X_2, Y_2)$ are minimum cuts in a transportation network, then prove that $(X_1\cup X_2, Y_1\cap Y_2)$ is also a minimum cut.

[vital dew]

Arya

[unkempt fiber]

I don't understand the question itself. Is it possible to put it in simpler terms, explaining what a min. cut is in the first place

[haughty garden]

I’m assuming a transportation network is nothing more than a flow network. A cut partitions the flow network into two disjoint sets of vertices. The value of the cut is the sum of the edge weights that are used to partition the vertices (ie form the cut). Therefore, you want to find the cut that minimises the sum of edge weights which is called the minimum cut of the flow network

[unkempt fiber]

hmm got that one!!

[civic shoal]

Suppose u got a function that maps from N X N to N, would you say that the cardinality of N X N is larger than cardinality of N even though they're both technically infinite?

[modest swan]

If I try to prove a statement by contradiction but end up not arriving at any contradiction in the end, am I disproving it?

[tight hound]

The two sets have equal cardinality.

[tight hound]

If you aren't able to arrive at a contradiction in this case, then you aren't proving anything.

[last flower]

oh, my bad

[leaden pulsar]

Hi guys anybody know of a super pedantic, in depth, and rigorous book on algo analysis

[weary tiger]

CLRS

[leaden pulsar]

Oh yes that's true

I guess the reason I haven't read it thoroughly is it's dry as dust 🤣

Thank u

[weary tiger]

that is true

best of luck!

also there’s another

[leaden pulsar]

But it's a very good book
Tyty!!

[weary tiger]

it’s not pedantic like clrs check out “jeffe cs illinois” (google it) and check out the chapter pdfs of his algo book

wordy but very clear and less dry imo

[unreal stump]

I guess depends on your purpose.

I have no clue what audience Sisper is targeted at,may be exactly what you are looking for.

But from an application pov, I think Skiena is good

[weary tiger]

Sipser is more of a course on computation theory, finite automata

Less about Big O and actual complexity analysis I believe.

[leaden pulsar]

Yeah I guess my question was mostly into complexity

But complexity foundations I guess are horrible, Turing machine lemmas iirc

[unreal stump]

Sisper does complexity analysis in the 3rd part of the book

I guess it all depends on what you are learning complexity theory for

[leaden pulsar]

You could I guess reformalize complexity by taking the length of a trace of an automaton but like, 😟

No reason other than to get over my deep discomfort with some of the tools

[unreal stump]

Is this for an algorithm analysis class?

[leaden pulsar]

Ive already taken and passed a PhD algos analysis class

I'm done with it

I just want to know how you'd do it systematically and not hackjob like we did

[unreal stump]

Well I guess Sisper is good then

[weary tiger]

dang nice man

Do you find that stuff helping with leetcode or too theoretical for it

[leaden pulsar]

Oh it was incredibly helpful for leetcode

I began trying to do 1hard leetcode a day, thinking it would help with algo

It in fact did not at all

But, afterwards I could do roughly 20 LC problems in 1 day

[unreal stump]

What do you mean by "hackjob" exactly

[weary tiger]

Any strategies for getting good at hards? I can do most mediums and some hards

[leaden pulsar]

We just pulled tons of bounds without proving them

[unreal stump]

So what categories do you struggle with. hard, medium, etc don't matter as much as category

[leaden pulsar]

What really helped for me was doing klienberg and tardos questions from the textbook, then doing all the coding in batches by hand

[weary tiger]

Hmm Array ones cause it’s not really one category but often some manipulation

[leaden pulsar]

So instead of pressing the "run" button, I'd print tons of questions, then work them all out by hand, then code

[unreal stump]

array is the worst category ever. Because literally anything can come within it

[weary tiger]

exactly

[unreal stump]

Also there are only like 15 tricks you need to know

[leaden pulsar]

I'd already had a lot of experience with algo, and my problem wasn't the datastructures, it was I realized the critical thinking and design

[weary tiger]

I probably just need tod o more questions and stay at it llonger without solution peeking

[unreal stump]

And everything else is a repetition of this 15 things

[weary tiger]

the grokking patterns

[leaden pulsar]

It really helped too to prove all of the basic strategies in the abstract

Like prove Dijkstra, prove bellman Ford, prove trie runtime

[unreal stump]

What about the more obscure stuff

[weary tiger]

Prove the runtimes or the general algorithm?

[unreal stump]

I thought you did all the weird over the top stuff no one cares about in a PhD algo class

Like some crazy variant of Fibonacci heap

[leaden pulsar]

Usually the general algo but not runtime

[leaden pulsar]

We did indeed do this

And like discrete fourier transform etc

Max flow min cut

And lots of randomized algo

It helped though
Once you see it in the extreme cases it's easier to recognize in the easier ones

[unreal stump]

So randomisation doesn't change the time complexity right? Like it reduces the constant,but the complexity remains the same

[leaden pulsar]

Well there's two kinds

One is whp find the answer. One is whp expected runtime

Both are basically negligible probability, usually, of failure

The trick is to get the probability of failure to decrease exponentially with the number of repititions

Check like, contention resolution in klienberg tardos

I think you'll see what I mean

[unreal stump]

That seems like a very interesting book

[weary tiger]

Yeah that book seems good

[leaden pulsar]

very well written and ive never felt happier in my life about such a dull subject

[weary tiger]

I wonder how it compare to CLRS but the sections seem very clear

CLRS very dense

[leaden pulsar]

BUT how they come up with the bounds is like,

CLRS is much more readable

for Klienberg and tardos it took good time and deep concentration

[weary tiger]

is that book a graduate level

[leaden pulsar]

CLRS i could process slowly over time

yes

beginner graduate

[weary tiger]

Gotcha

CLRS seems for all levels

probably mostly UG

[unreal stump]

Ok,I thought I was the only one who thought algorithm analysis was boring

[weary tiger]

Same

[unreal stump]

mb algorithm design is very interesting, I meant analysis

[leaden pulsar]

My roomate on the other hand seems to have worked in detail a very large portion of Knuth

He's absolutely nuts

🤣🤣

The things I've seen him do with TCS don't seem mortal 🤣

[unreal stump]

I don't know if I should trust hackernews but apparently Knuth isn't that bad

[leaden pulsar]

1. You shouldn't, a lot of those guys are just big n or California hackers telling war stories from ugrad/masters
2. I think it's more due to my roomate being personally mentored by a prominent discrete mathematician for four years

But the crazy things I'm talking about are like, coming up with a new publishable algorithm for computing eigenvectors / eigenvalues on gpu in like a weekend

[unreal stump]

Damn

[weary tiger]

dang wtf

[leaden pulsar]

That's the most recent one

[unreal stump]

I guess when you do a PhD, you meet some insanely smart people

[weary tiger]

Wow

Companies must be running after these people

[unreal stump]

I mean most companies don't have roles that need PhDs

[weary tiger]

Oh i thought this was graduate in general

Quant companies but even then most roles don’t need PhD like you said

[leaden pulsar]

He'd not make a higher salary than web page people if he joined a CS company

And similarly with quant

[weary tiger]

Are they interested in academia more so?

[leaden pulsar]

They need ppl to do their job

Yea

[unreal stump]

I mean you can always go for FAANG,right?

[leaden pulsar]

Yup yup

[weary tiger]

True

[leaden pulsar]

But I have friends from ugrad making 180k out of ugrad in faang

[weary tiger]

I’m sure some faang would love to fill research scientist

[unreal stump]

Not sure how hot R & D is

[leaden pulsar]

And then some guys who graduated this PhD program make the exact same salary

[weary tiger]

Yep and it’s growing even higher. FB pays 250 ish for return interns going FT

[leaden pulsar]

R&D doesn't make huge huge salaries unless you're management

[weary tiger]

I think it’s more of the “intellectual fulfillment” at that point

[leaden pulsar]

At Amazon, their highest management people in my subfield pull in almost 1mil.

But the peons doing research cap out at like 230k

Which is good but like...

[unreal stump]

I mean 180k per year is still insane

[leaden pulsar]

Not worth 5 years of PhD suffering unless you enjoy the suffering 🤣

[weary tiger]

I wonder how reliable is https://aipaygrad.es/ then

[leaden pulsar]

I'm in formal methods not ai

ai is better

[weary tiger]

Oh right sorry complete brain lapse

[leaden pulsar]

More applied

[unreal stump]

So you do like verification?

[leaden pulsar]

Yes 😎

[weary tiger]

But interesting data points never the less

[tight hound]

Jane Street pays 500k per year fresh out of undergrad right?

Or so I've heard...

[weary tiger]

More

575 ng offer it seems with more for performance.

Citadel, HRT seem similar if not a bit lower while companies like Radix are higher

[tight hound]

Oh ok

[unreal stump]

Ok,so like what's your main object of study? Formally verifying programs in complex langs like Java don't seem very feasible

[weary tiger]

Not much really known universally in quant other than first year offers, since it’s mostly performance based (more so for trading but also for swe, idk about research but I assume similar).

[tight hound]

Right

[weary tiger]

What’s the general idea behind verification? Not familiar.

[unreal stump]

Well you prove a program is correct formally,I guess

Instead of "this code looks good to me"

[weary tiger]

Ah I see, yeah I will probably understand better after taking a. computational theory course

[leaden pulsar]

Look up Jahob 😄 and featherweight Java. But no

My main object of study is constraints

Quadratic arithmetic constraints 😄

For interactive proofs

Even more jokingly I study very restricted excel spreadsheets

[unreal stump]

I think they mean they study some kind of relational data

Well think SQL

[leaden pulsar]

Oh oki it's not quite sql, it's more like, the problem instance size has to be bounded by a constant

And the quadratic arithmetic constraints look like
(linear combination * linear combination) = linear combination

So if you want to try something out, you might write some c++ code that does little more than an excel spreadsheet

Of course, trying something out will take you a few days, proving it works might take much longer

[unreal stump]

Can you suggest some introductory papers on what you are doing?

[leaden pulsar]

• less is more, refinement proofs for probabilistic proofs, jiang et all
• efficient ram and control flow in outsourced computation

Those are both systems papers

But I'm helping out on the not systems side

Proofs arguments and zero knowlege by thaler is introductory

[unreal stump]

I guess I will be more interested in the system side of things. Thank you

[leaden pulsar]

The theory is still a mess outside of the computational complexity part of the theory which is more established

The theory ig meaning what's the most efficient way to represent X in Y is still a mess

Most efficient way to represent ram lookup for example

There could be some sort of theoretical limit, like the dynamic optimality conjecture...

(for splay tree)

[unreal stump]

By ram lookup, you mean the whole memory hierarchy thing?

[weary tiger]

very interesting stuff, thank you for sharing!

[unreal stump]

Because splay makes me think of cache

[weary tiger]

I felt like i’ve seen that yeah

[leaden pulsar]

I actually don't mean memory hierarchy thing

I mean the following: there are curently a few zero knowledge proof ways of representing ram:

1. Specify a hash function in r1cs. Use this hash function to create a merkle tree, so that you can gaurentee whp that your loads and stores are consistent with the string of hashes from the merkle tree.

2. (currently the preferred approach)
   Model the program as an automaton, with the transition relation given by the program, and time increasing at each transition.

From some of these states, chose time, along with kind of access, address, and value from the state. use an arithmetization of an as-waksman network to permute them into sorted order by time then address, and separately enforce sorted order. Seperately enforce also that each load is equal to the previous store in the sorted order.

its a little of a mess of a construction but the net effect is that you get RAM and you get transition relation of an automaton

3. Hash your additions to the state and exponent an agreed-upon prime to the hashed value. now the hardness of discrete log makes it hard to lie about the consistency of the state...

[granite atlas]

Hey all! I'm trying to get a head start to my next semester, where I'll be taking discrete math. Does anyone have any recommended resources for self teaching discrete math? As of now I've got Concrete Mathematics on the recommendation of /r/learnmath, but any other resources that were helpful for those of you who have already taken this course would be very helpful in giving me direction on where to get my start on this!

[leaden pulsar]

😄 are you in a computer science program

if so I suggest "how to prove it"

oh hm concrete mathematics is more advanced than how to prove it

[coral parcel]

Beware that courses named "discrete math" can vary significantly in content from institution to institution, so take anything you read with a grain of salt.

On the other hand, probably the luckiest outcome is that whatever you self-learn isn't what's in the course. That way you won't be bored when the semester starts and you'll have learned something you wouldn't have occasion to learn otherwise.

[granite atlas]

lol, yeah. I'm currently in my second year of community college in a program to transfer me to my state university once I've finished up my gen eds and transfer requirements. I have two semesters left before transfer 😛

I've finished all my other math necessary for me degree - which in my case is up to calc 2 - but I'm most likely going to be taking a minor in data science so if that's the case I still have linear algebra and calc 3 on my horizon at least

[granite atlas]

For me, I have plans to be overseas for a friends wedding toward the end of my next semester, so what I'm most concerned with is getting a good background foundation so that I can get ahead in that class early and free myself up to focus on my time with friends toward the end of the semester without it negatively impacting my grade 🤞

Other than the textbook I've found a few youtube video resources - namely a discrete math series playlist from TrevTutor and a couple of playlists of entire course lectures online

It sounds like I may want to reach out to my teacher in advance to get an idea for exactly what we'll be covering in the course, though, to be safe

[leaden pulsar]

One cute thing my discrete math class didn't teach was how to do induction proofs by contradiction to minimality

Like in e. g. the proof of bezouts theorem *

[granite atlas]

I'm still pretty unfamiliar with discrete math outside of the basics - I know it's a class that'll be going over a lot of proofs and setting the foundation for how computers "think" and operate under the hood, hence why it's useful for compsci students. I really enjoy math classes that are focusing on concepts and underlying logic rather than rote memorization, so I think I'll like the class a lot and am generally all for learning all that I can about it regardless of whether it'll be required for my particular class.

[rigid tartan]

Do you want to hear something funny

[leaden pulsar]

Yes

[rigid tartan]

I once read a paper that pointed out since, by default, cells in excel only depend on expressions in other cells, you can regard excel as a kind of stateless programming language. In particular it's basically a functional programming language. And arguably it is the world's most popular functional programming language! So the paper was basically like, let's take some of the most popular ideas in functional programming over the past 20 years and incorporate them into an excel plugin so that users can take advantage of these ideas.

This started as an academic paper in a CS journal and slowly escalated into like a legit plugin for excel that dramatically increases its power w support from microsoft

https://www.inapps.net/microsoft-excel-becomes-a-proper-programming-language-inapps-technology-2022/

To roll their own custom functions, users had to use Microsoft’s other macro-based programming language, Visual Basic for Applications. (Or, starting in 2018, JavaScript — and of course, Microsoft’s JavaScript-superset TypeScript.)

In a video appearance at POPL 2021, long-time Microsoft researcher Simon Peyton Jones noted that Excel’s end users were implementing functions using JavaScript, reiterated in a Microsoft Research blog post by a senior principal researcher and a senior principal research manager. “Excel formulas are written by more users than all the C, C++, C#, Java, and Python programmers combined.”

[leaden pulsar]

Oh wow popl 21

I was there but I didn't attend this demo

What a crazy coincidence

[rigid tartan]

https://www.slideshare.net/kfrdbs/peyton-jones

here's a slideshow

i can't find the paper

[leaden pulsar]

Thank u 😀

[rigid tartan]

imo "how computers think under the hood" is different than the proofs taught in discrete math. To understand how computers think under the hood you just need to understand true, false, AND, OR, NOT, IMPLIES. The usefulness of discrete math is more to teach you how to reason through algorithms and convince yourself and others that they're correct when you need to write a sorting algorithm

but you really don't need to know how a computer thinks under the hood to write a sorting algorithm

[leaden pulsar]

Oh wow that's wild when he said discrete math I was imagining like, types of binary relations and de bruijn graphs

[coral parcel]

I don't think IMPLIES is all that important for digital logic or bit fiddling. 😆

[granite atlas]

Good to know - appreciate you sharing that bit of clarification!

I'm sure there's a lot of misconceptions I currently have - hopefully they'll be cleared up as the class progresses 😛 I'm new to the server, but I may end up using this chat a lot in the coming months!

Do you guys ever get in any of the voice chats, or do you usually handle things via text chat in here?

[rigid tartan]

I don't personally use the voice but I see people in there.

[rigid tartan]

Why stop with tossing out that one? None of them are except for NAND

[coral parcel]

I'm not sure I would toss it out without further, but I would consider replacing it by XOR.

[unreal stump]

Well practically speaking for bit twiddling, you use AND,OR,XOR and maybe some NOT.

NAND and NOR are very useful for describing latches,flip flops and probably other mechanisms as well ig.

Never heard of IMPLIES as a digital logic thing

[weary tiger]

if 2-2=0 they why dosent 2-0=0?

[vital radish]

How do I find the number of solutions to $\sum_{i=1}^n a_i = N$ where $a_i < k$? Basically just stars-and-bars with an upper bound.

[vital dew]

kappa

[vital radish]

I don’t know if this is the right place to post this but I was redirected here.

[rapid mural]

number of solutions to what specifically

each a_i?

[wild cove]

hi! im not sure whether this topic belongs here...
this is found on the wikipedia page and we are trying to derive stirling's approximation

when we set m to be 1, the summation should become 0 and O(1/n^m) should become O(1/n)
so after taking exponential of both sides, i get n! = e^y √n (n/e)^n e^O(1/n)

however, written on the wiki page is 1 + O(1/n) instead of e^O(1/n), and i cant figure out why...

moreover, this inequality is mentioned earlier in the page, and it indeed suggests that e^O(1/n) is correct and O(1/n) looks like a function "between" 1/(12n + 1) and 1/12n

if e^O(1/n) is correct, why is it equal to 1 + O(1/n)?

https://en.wikipedia.org/wiki/Stirling's_approximation

[inland gale]

1 + 1/n are the first two terms of the taylor series for e^(1/n)

[wild cove]

ohhhh i seee

thanks!

[proud needle]

has anyone here read “graph theory” by diestel? what do you think are the prerequisites to the book?

[weary tiger]

from looking at the exercises / table of contents, good background in proof techniques seems pretty helpful

maybe some basic combinatorics knowledge

[proud needle]

okay thank you! do you think i can get more experience in writing proofs while doing the exercises in the book or should i do something easier

[weary tiger]

I haven't done something in depth in graphs like this, I'd say be familiar with induction, maybe proof by contradiction / existence / uniqueness proofs

You can learn those in book of proof by hammack, how to prove it by velleman, etc

You can do both I think, depending on your comfort level

Best of luck

[vital radish]

Sorry my problem was vague. Basically how many n-tuples of non-negative integers sum to N (stars and bars). We can easily find this using the stars-and-bars formula, but things get trickier when we give a_i an upper bound. (eg. if we have 3 integers that sum to 5 but cannot be greater than 3, an example would be 2+2+1=5. But how do we find how many exist?)

[coral parcel]

I haven't head of a general approach for that which is feasible for large numbers. If one of the parameters (say, the bound for the terms or the number of terms) is small, you can look for some ad-hoc way to unfold it along that axis only, while keeping the other numbers symbolic. But that's more of a vague heuristic than a method.

[feral steeple]

You mean

[feral steeple]

x+y+z=5, x,y,z cant be greater than 3?

x,y,z belong to whole numbers?

If its that then find (x+y+z=5, x,y,z>=0)-(x+y+z=5, x>=4or y>=4 or z>=4)

[coral parcel]

This is a useful approach when the bound for each term is close to the desired sum, but I'm assuming 3 and 5 were just examples. Suppose you want to write 64532 as a sum of 172 naturals each less than 514 ...

[vital radish]

Yes, where all of them are nonnegative integers

[weary tiger]

PIE, principle of inclusion exclusion, like if youre given what idontsleepanymore said, but also applies if only some of them cannot be greater than k

[vital radish]

Could you elaborate a little more

[weary tiger]

Ok sure give me a few minutes

for example you want nonnegative $$x_i, x_1 + x_2 + x_3 = 5, x_1 \leq 3, x_2 \leq 2$$

[vital dew]

JOKER

[weary tiger]

then you can formulate this as #(ways for all nonnegative x_i) - #(ways such that x_1 >=4 or x_2 >= 3)

Since the second term is a union, you can use principle of inclusion exclusion to calculate that (still using stars of bars, but now it is) : #(ways such that x_1 >= 4) + #(ways such that x_2 >= 3) - #(ways such that x_1 >= 4 and x_2 >= 3)

The >= case is more natural with stars and bars since you can just subtract the number (4 in the case of x_1 >= 4) from RHS and apply the stars and bars formula

[vital radish]

Thanks!

[weary tiger]

no problem

any time you see cases that can overlap, try formulating them in a union (the second term in the first message) which will lend to PIE

and actually in this case x_1 >=4 and x_2 >= 3 cant both be true

since that means x_3 has to be negative

[vital radish]

So 0 cases for that

[weary tiger]

right

so basically both the cases with x_1 and x_2 are disjoint

so one less case to calculate overall lol (the intersection)

obviously this can be a nightmare with lots of boxes (the x_i) and lots of stars (RHS)

generating functions will likely be more useful there to try to find a formula that you can simply plug in the number of stars as n and it will get you an answer

[reef dirge]

is this transitive?

[coral parcel]

What are your thoughts?

[reef dirge]

that it is

[coral parcel]

Because?

[reef dirge]

dont know how to explain it tbh

or prove it

[coral parcel]

Make an attempt at the explanation.

Perhaps start by stating what it means for that relation to be transitive.

[reef dirge]

ik what it means and i think it is transitive but i just dk how to prove it mathematically

[coral parcel]

Can you explain it but not "mathematically"?

[reef dirge]

if a^2 = b ^2 and b^2 = c^2 then a,b,c must all be the same number or the negative i think. and because of that aRc

idk if that makes sense

[coral parcel]

That sounds fair.

But you can shorten it to: If a²=b² and b²=c², then surely a²=c² (no matter what the silly raised 'two' happens to mean). But that is the definition of "a R c".

[reef dirge]

ah i see so it is transitive

[weary tiger]

How do you do this superscript in messages on Discord?

[coral parcel]

I type the Unicode characters for superscripted 2 and 3.
(They're in the Latin-1 character set, so I have key combinations for them).

[weary tiger]

Did i get ghost pinged here?

[vital radish]

yes I think I’ve found a closed form for the formula

[weary tiger]

Nice. Generating Functions?

[vital radish]

No I’ll post it shortly

[weary tiger]

Nice

[vital dew]

kappa

[vital radish]

$a_1+a_2+a_3+\dots+a_n=N$, where $a_i<k$

[vital dew]

kappa

[vital dew]

kappa

[covert bolt]

dumb qn but are isomorphic graphs counted as distinct graphs

[tight hound]

Usually not

[weary tiger]

I need help to solve this question

[muted gate]

first find all numbers x + y that are divisors of 24

within that set A

then the relation matrix of R and R o R are pretty straightforward

[weary tiger]

I don't know how to find R o R?

[rapid mural]

write it out

[urban mantle]

How would someone like Google compute hamiltonian cycle on their big data sets?

They must have some algorithms, some heuristics. I cannot find anything practical for more than 500 nodes.

I know that's NP-complete problem so I trying to find something that gives some close enough solutions. Maybe cycle that skips 5 or 10 nodes on 5000 nodes or so.

[hollow loom]

is discrete mathematics by oscar levin good for basic discrete mathematics, or is the one by susana epp better? which do i bother with? do you have a better recc for a noob?

[hollow loom]

i think the reason i ask is because of the following:
"but the intent is not to provide a solid mathematical
foundation for computer science, unlike the majority of textbooks on the
subject."

so I guess what id add to my original question is, does susana epp's book prove to be better at satisfying that, and if not are there any books that do (?)

[weary tiger]

from looking at TOC, rosen's discrete math seems better for greater coverage for topics. I honestly dont think theres a correct choice if you want "math for computer science". tbh anything with graphs, basic combinatorics, logic should be enough for a "foundation", and other topics come with more interest / you want more in-depth math

the "math for computer science" thing i dont really think is something to worry about when choosing a discrete math book. choose something that has topics youre interested in with a few that may be useful regardless

[sudden minnow]

there are so many of these discrete math books and I'm not convinced they differ in any meaningful way

[hollow loom]

cool:)

[weary tiger]

Y

[spring elk]

should i do htis using induction?

im thinking of doing this using case 1: deg(v) = 1 for at least 1 vertice and case 2 deg(v) >= 2 for all vertices

[brave rock]

Hint: use the handshaking lemma

If you're not familiar with the handshaking lemma, it says that the sum of all degrees is 2e.

[spring elk]

hm

still cant figure out how to do this

i can see that the inequality is between min{deg(v)} < sum deg(v) / n < max{deg(v)} using that lemma

[brave rock]

I'm confident you can figure it out from this

[spring elk]

yeah ok i see. sum deg(v) should clearly be smaller than n*max(deg(v))

thanks

isnt deg(v) = 1 actually? G is a loop-free undirected graph

if deg(v) > 1 it will have a loop

[pale epoch]

why?

[spring elk]

if there exists n vertices and there is a vertex with degree > 2 it will have an edge to another vertice

whic would cause a loop

or nvm

[pale epoch]

i think you should check what loop means again

[spring elk]

"In graph theory, a loop (also called a self-loop or a buckle) is an edge that connects a vertex to itself." ok i was thinking of a cycle, so then if a vertex has degree > |v| -1 it will have a loop.

but i dont think this is helpful for this exercise anyway

[tame bone]

has anyone eperience with chomsky-algorithm?

[icy snow]

Can someone verify whether my logic behind this question is correct or not?
So given a set of 8 numbers from, how many numbers are there that have at least one uneven number or one 6
Each of those 8 numbers can be any number,
So my answer is 10^8 - 5^8 + 10^8 - 9^8 - 10^8 + 4^8,
This is in the form of |A U B| = |A| + |B| - |A ∩ B|,
With 10^8 - 5^8 being all sets with at least one uneven number,
10^8 - 9^8 being all sets with at least one specific number,
10^8 - 4^8 being all the sets with at least one uneven number and one 6

I looks correct to me

Do not look at it like a set, My fault, just look at it as a row of 8 numbers,

[weary tiger]

Hey guys is their any pre requisition for discrete math

[brave rock]

Not really

[cedar token]

is this correct? idk how to answer this question

[haughty garden]

that looks right to me

[cedar token]

okiee tyy

[cedar token]

how to do these 2 questions

[weary tiger]

The first question seems fairly basic. It is an arithmetic series, so takes the form $T_n = a + (n-1)d$

[vital dew]

ninerforce

[weary tiger]

Where Tn is the desired term, a is the first value, and d is the common difference (the amount by which each element in the series increases)

You can then use that standard formula with the values specific to your question to find the nth term

I don’t know enough to explain the second question, sorry

@cedar token

[cedar token]

thank youuu

[covert bolt]

For 1a, can I just say the largest possible subset of multiples of prime is {2,4,...,2n} which has a cardinality of n, but since n+1 numbers are chosen it is not possible for every 2 combinations of numbers in the subset to not be relatively prime, and since the other subsets of multiples of primes give a smaller cardinality it can be concluded for n+1 numbers chosen from the set, there must be a pair of numbers that are relatively prime?

[covert bolt]

Also why is there binary involved in the solution for b💀

[stray reef]

do you find the word 'binary' deathly intimidating? it is possible to rephrase this solution in a way that does not contain that word.

[covert bolt]

But the solution does use the binary number system right

Just wanna check this

Actually what is the qn even asking

Idrk tbh

[little prism]

for example if k=4 and n=10, how many solutions are there to x1+x2+x3+x4=10

one solution might be (1,1,2,6) and another is (9,1,0,0)

how many are there in total

[covert bolt]

Oh it's SLOE?

[little prism]

whatever that abbreviation is

[covert bolt]

System linear of eqn

Ooo

[little prism]

the x_i here are supposed to be non-negatives integers. so yes while the equation is indeed linear the approach to solve this question is not the same as for what you usually mean by linear systems of equations

[covert bolt]

ah

ok ty

[chrome fossil]

You can also use star and bar.

[leaden wyvern]

is reflexive relation both transitive and symmetric ?

[unreal stump]

No

[blazing plaza]

Hi guys its been a while

is this correct? can someone help me explain in different way, filling each box with how many choices we have?

[obtuse lance]

are you trying to understand it? I'd recommend drawing a venn diagram

[sage lance]

Hey folks, I recently started a project to cement an undergraduate learning and understanding of Graph Theory. I published what I am intending to do to gain some fundamental mastery in this space as well as share my plan with other would-be graph theory students here: https://jacobzelko.com/01012023000122-graph-theory-learning/#roadmap Would anyone be willing to comment on my plan? I am particularly wondering if I am missing any fundamental concepts or resources. Thanks! P.S. Could you share comments on the webpage discussion so I do not lose track of comments?

[weary tiger]

Another reference would be Bondy & Murty's Old book, the new one is err, a bit too much. I cannot comment on your plan totally not because it has been a long while since I did any gt but the content outline is not very apt on what you are going to actually cover and more importantly the system of division via topics is confusing, just godo a planner and divide everything per session. A lot of the stuff you have spanned out on on multiple slots in the table are about 1-2 classes worth of content whereas some of the topics with only one slot assigned can take 3-4 classes on their own, so i am not sure how much of what you are covering.

From the CS side of things-
There are a lot many theorem(s) like Pósa's, Dirac's, Vizing's, Turan's, Ore's, Kurtawoski's , KG's at the minimum which any standard course on gt would cover. You do have the topics listed under which these will come under btw! As of now the plan looks very bare bones, better yet get the course timeline of some degree programs of CS/math for gt and use them as a reference for what to cover when.

Side note, that dark mode makes the table text invisible for me. Also pick a better rationale maybe? A basic understanding wouldn't be much of a motivation given that you have so much of a mismash that you want to cover.

[sage lance]

This is fantastic -- thanks! Yea, I am trying my best to get a bit more lay of the land of what I need to study first and I was even confusing myself with topic layouts. I'll have to make this more clear and less confusing.

Also, ack, I did not know that about dark mode + the table @weary tiger . Thanks, I need to fix things there then.

[obtuse lance]

I agree with the picking a better rationale part too. If you're focused on CS, maybe focus on specific algorithms you want to understand and work on what you need to understand those better. One possible source is the book Introduction to Algorithms by Cormen Leiserson, Rivest and Stein, but I'm sure there are better resources out there.

main thing is if you're just learning random facts, I think it becomes much harder to remember long term or apply it since it's in a vacuum

[whole dust]

can someone explain how he went from $\binom{-3}{k}$ to $(-1)^k \cdot \binom{k+2}{2}$?

[vital dew]

TurkishNutcase

[weary tiger]

For any real $n$, $$\binom{-n}{k} = (-1)^{k}\binom{n + k - 1}{k}$$

[vital dew]

yika

[whole dust]

I see

How is this derived?

Or like what’s the meaning

[weary tiger]

Hmn take for example n = 0 in pascal's recurrence

[sudden minnow]

by definition,
$\binom{-n}{k} = \frac{(-n)(-n-1)(-n-2) \dots (-n-(k-1))}{k!}$

[vital dew]

lems

[weary tiger]

that would lead you into negative uppers

[sudden minnow]

now take all the negatives out

[weary tiger]

a better way to think would be rotate the pascal's triangle maybe

[whole dust]

Ok makes sense

thanks!

[sudden minnow]

np

[rapid mural]

It specifically has to be a partition

[leaden wyvern]

let A and B be finite sets with |A|=m and |B|=n.find how many function are possible form A to B???
m2^n ??

[sudden minnow]

what do you think?

[sudden minnow]

n^m

[leaden wyvern]

how

[sudden minnow]

you have m elements in A, each element in A can get sent to n different elements in B

n^m

seems like you already understand that not every partition works

why does {1,2,3},{4,5,6},...,{3n-2,3n-1,3n} work? because if you have 2 elements in one of the sets they necessarily differ by at most 2

yes

yeah in this case you want to prove some specific thing

[leaden wyvern]

ohh....but are all n^m function are unique??...i mean are they all n^m injective function ??

[sudden minnow]

of course they aren't necessarily injective

but they are different from each other, of course

or else they'd be the same function?

[leaden wyvern]

can we say that total number function possible is equal to the number of element in the set of Cartesian product of A and B set??

[sudden minnow]

no

,,|A \times B| = |A| \cdot |B|

[vital dew]

lems

[leaden wyvern]

ohhh

[sudden minnow]

,,|B^A| = |B|^{|A|}

[leaden wyvern]

yaaa

[vital dew]

lems

[leaden wyvern]

got it

thnkasss

[sudden minnow]

if you haven't seen this before

,,B^A

[vital dew]

lems

[sudden minnow]

it means "set of all functions from A to B"

if you've noticed, we use exponentiation notation

[sudden minnow]

precisely because of this

[leaden wyvern]

ohh..ya..got it..thanks

[haughty garden]

yep

you need to show that, regardless of which n + 1 integers you pick, there will always be two which differ by at most 2

so you aren't permitted to choose the n + 1 integers

[stone wing]

Is this proof correct and what can i do better? Can we say in case 2. the condition is vacuously true?

[stray reef]

i'd prefer to say that case 2 rules itself out -- the sum of all degrees ends up odd, which contradicts the handshake lemma

[stone wing]

ok thanks😇

[covert bolt]

hi I dont understand the solution

esp where n! came from

[obtuse lance]

Does it help to know that $\binom{a}{b}=\frac{a!}{b!(a-b)!}$?

[vital dew]

Merosity

[covert bolt]

yea I was able to simplify the expression to $\frac{(n+k-1)!}{(k-1)!}$

[vital dew]

Opify

[covert bolt]

but I still dont really get it

[obtuse lance]

It's similar to stars and bars if you're familiar with that

[covert bolt]

and I also know it can be further simplified to $n \cdot n-1 \cdot ... \cdot k$

[vital dew]

Opify

[covert bolt]

o man

I just had the same thing yesterday 💀

[obtuse lance]

imagine the stars are books and then the separators are the book shelves

we care about the order of books on a book shelf, but the dividers representing different book shelves doesn't matter

maybe it helps to think if you have 7 books and 3 book shelves, then XX|XXXX|X would be one way to represent the 7 books with 2 dividers

[covert bolt]

ok thank you

[obtuse lance]

yeah you're welcome

[covert bolt]

for j why cant I use n!

[regal gate]

To prove that Ramsey numbers R(s,l) exist, it is enough to prove that R(2,l) exists for all l and that R(l,s)<=R(l-1,s)+R(l,s-1), right?

The inequality is to be interpreted as: if R(l-1,s) and R(l,s-1) exist, then R(l,s) exists and the inequality holds.

[coral lantern]

How do we get to the consideration (green)?

[weary tiger]

it is

re write it

[leaden wyvern]

A path with n vertices has length n-1 ?? is this true??

[stray reef]

what is R_11?

[weary tiger]

Real numbers mod 11 i assume

[weary tiger]

the stuff in green is derived via eulers totient theorem

Since remainders are additive you can check $$R_{11}(2^{2016}) + R_{11}(3^{2016}) \implies R_{11}((2^{10})^{201} * 2^6) + R_{11}((3^5)^{403} * 3^1)$$

and from there its pretty trivial to find the answer

[vital dew]

Smoothie King

[sudden minnow]

looks good to me

unless order of the teams matters but if the question is posed this way I don't believe it should

np

[vital dew]

akari

[sudden minnow]

wait so

if pitches being different matters, the original answer should be correct

if they don't matter, presumably you'd divide previous answer by number of ways you can order 3 pitches around, to get an unordered answer

[weary tiger]

this is absolutely correct

if the order matters

if order doesnt then divideb y6

[vital dew]

Opify

[covert bolt]

In the even case, why isn't there $\binom{n}{\frac{n}{2}} + \binom{n}{\frac{n}{2}}$ combinations for when there are equal amounts of both republicans and democrats?

[vital dew]

Opify

[haughty garden]

To select a committee of n people of which exactly half are Democrats, you need n/2 Democrats and n/2 Republicans

C(n, n/2) + C(n, n/2) implies that you want either n/2 Democrats or n/2 Republicans, not necessarily both at the same time

[covert bolt]

Ok thank you

[coral lantern]

thankss!

[lapis mulch]

what does it mean for range to be "can mean either" here?

[rapid mural]

If f is onto then the range is Y

Else the range would be the image

[sudden minnow]

no, what it's saying is range means codomain or image depending on the person

sadly, there's no consensus but when I see range used it almost always means image

[weary tiger]

Need help in Recurrence relation

[stray reef]

please do not post the same problem in multiple channels.

[weary tiger]

Do you know the answer to this? I solved it so I want to check my answer. I can send my answer to your DMs. Thank you.

Solved as in I do not know the initial conditions here**

[obtuse lance]

you can post it here with spoilers if you want, I also know the answer and can check yours