discrete-math

[glacial turret]

Sry, $F(P) = min{deg(P_i)|o\leq i\leq n}$

[vital dew]

VY (Logic_VY)

[lethal linden]

I mean, you could say something like $$\max({n \in \mathbb{N} : x^n \mid P})$$

[vital dew]

Cufflink

[lethal linden]

i.e., the largest natural number n such that x^n divides the polynomial

[glacial turret]

That's definitely a possibility but I was just curious if there were any specialized notation

Thanks

[severe gust]

someone help me with this

[fierce nova]

when q then p

[severe gust]

so d?

wait no c

[fierce nova]

pretty sure its b

q - > p is the same as ~q -> ~p

contrapositive

i like that question, it didnt just have q-> p in it

testing a few skills at once

https://cdn.discordapp.com/attachments/853325130175348776/1306458359012266074/image.png?ex=6736bda9&is=67356c29&hm=edee63f7e70d8aa10a8929d597f99688b6677cc70019505d803d1e839e3989f8&

now who can help me with 52

i think its just if the inverse is still equiv?

B x A = D x C, if that is true, then we can conclude that a = c and b = d?

nvm that wouldnt be a good way

they have to be non-empty

since cartesian product is just multiplying the cardinality of both

even if u did B x A = D x C, it would still be the same as A x B = C x D

but if one on both side is empty
then you would get {} = {}

[severe gust]

guys the answer to this is gonna be A right?

cuz every element in the first function is mapped to an element in the other function right?

[oblique pelican]

correct

[severe gust]

k thx

[weary tiger]

guys what is 1+1?

[fossil mural]

2

[sand pelican]

so 3^2 \equiv 3^{4-2} \equiv 3^{-2} \equiv 1 (mod 8). I wonder how 1/9 \equiv 1 (mod 8)

[oblique pelican]

Negative exponents work differently in modular arithmetic. 3^-1 = 3 mod 8 since 3*3=1 mod 8. (Its similar to how 3*1/3 = 1 so we define 3^-1=1/3). So 3^-2 = 9 = 1 mod 8. Not all integers have inverses mod 8 (meaning that it doesnt make sense to take a negative power). The condition for an integer n having an inverse mod 8 is that n and 8 have no common factors other than 1. 3 and 8 have no common factors other than 1 so 3^-1 exists and it also happens to be 3.

[lethal linden]

Don't think of 1/9 as the decimal 0.111.... Think of 9^{-1} as a label for the number a such that 9 * a = 1.

So what 9^{-1} "means" depends on what * and = mean, which can vary.

You have

9*9 = 1   (mod 8)
```so

9^{-1} = 9 = 1 (mod 8)

If we're talking about rational numbers then the number a such that 9*a = 1 is indeed a = 0.111...

If we're talking about the integers modulo m then what a is depends on m.

[glossy orchid]

ive just started computer science at uni level, and im struggling with discreet math is there any pointers to how i should approach learning it or any helpful resources?

ive just done 4 weeks on proofs with quantifier/ predicate formal proofs and now being introduced into set theory, relations and functions

[snow cedar]

Can someone help me out with b / c?

I think to find the number of red (or any colour) edges, you have to notice that each vertex has 1 red edge, but since each red edge is shared by two vertices so we're double counting. so we can get Red E = V/2

[lethal linden]

How many red edges are there in terms of the number of vertexes?

[snow cedar]

v/2

[lethal linden]

Yep. Then the faces put other restrictions on how many RBY edges there are.

You get a bunch of linear equations for edges of each color, faces of different sorts, etc.

Since those have to be natural numbers, there's a smallest V which satisfies them.

(There won't be a unique solution because any graph which satisfies it can be combined with a disjoint copy of itself and still satisfy it.)

[still bloom]

To determing if the graph is planar im using eulers formula but the face part is kinda confusing me

Can someone dm me and get in a call to help please

[snow cedar]

Oh I thought the question is asking for a unique solution

I got this linear equation:

3F{6-length} + 2F{4-length#1} + 2F{4-length#2} = 4 + V
and
F{6-length} + F{4-length#1} + F{4-length#2} = 2 + V/2

I can see I can get F{6-length} by multiplying the bottom eqn by 2 which says it is = V/2 - 4

But I'm having trouble solving for F{4-length#1} and F{4-length#2}

[lethal linden]

What is F?

[snow cedar]

F is the total number of faces but the F{...} that I'm describing is counting the number of faces of each type

There is only 1 face type that's a 6 cycle, and 2 types that are a 4 cycle so i differentiate them with #1 and # 2

[fresh hull]

How do I prove part b

[cerulean plover]

For card hand problems in discrete probability, I'm confused on whether or not I'm supposed to use combinations or permutations.
The amount of ways to get a full house is the amount of ways to choose 2 kinds * the amount of ways to choose 2 cards of different suits * the amount of ways to choose 3 cards of different suits. I'm getting this as C(4, 2) * C(4, 3) * C(13, 2). Kimberly Brehm on youtube is using permutations for that last term, making it C(4, 2) * C(4, 3) * P(13, 2). I sort of understand it, as the order of the kinds does differ the hand (the first two cards being of kind A and the last 3 being of kind B vs the first 2 of kind B and the last 2 being of kindA). My issue is that my textbook contradicts this, using combinations as the term for the amount of ways to choose the kind.

Which one is it?

why is, in one case, it permutations, and in the other, combinations?

nevermind, i got it. 2 pairs would be combinations because 2 aces and 2 kings = 2 kings and 2 aces

mb

[grand totem]

Hint: From a * a = b we get that a * (a * b) = b * b. Try showing that a * (a * b) = b by considering two cases (one for each possible value of a * b).

[fresh hull]

Oh got it, thank you!!

[kind needle]

Hi all,
I'm trying to solve a problem and I don't know which solution to use.
I want to find all cycles in a graph up to a limited depth (to avoid exponential complexity). I thought of simply doing depth first search, would this solution suffice if i don't mind it taking some time to run?
My idea is to store all cycles and then simply use them later on, I'd want to find all negative cycles therefore I'd loop over them and sum their weight edges to check if they're negative or not (directed graph so in both directions example A -> B -> C -> A and A -> C -> B -> A).

Because I want to chose only a few starting and ending points in the graph (such as A in the example above), I'm thinking there's no need for me to find all cycles, just all cycles starting/ending with the nodes I chose.

Is there a general/better solution for this problem?

[merry merlin]

Problem in basic Graph Theory and Matchings, can I get some help?

[solar marsh]

consider this graph

[agile magnet]

Yea yea this is 3 days later but I have an answer!

The notation I've seen is $f^{\mathrm{in}}$. So if $f(x) = 3x^8 + 5x^4 + 3x^2$ then $f^{\mathrm{in}}(x) = 3x^2$.

[vital dew]

Spamakin🎷

[agile magnet]

I've also seen in(f) as similar notation

If you're curious, this comes ip in a field called algebraic geometry, which is the study of the geometry defined by the zero sets of polynomials (so as an example, x^2 + y^2 - 1 = 0 describes the unit circle in 2D space)

[vivid osprey]

Under what condition does it hold that $$\bigcup _1^{\infty }U_j\cup \bigcup _1^{\infty }V_j=\bigcup _1^{\infty \ }\left(U_j\cup V_j\right)?$$

[vital dew]

psie

[agile magnet]

what do you think?

[vivid osprey]

well, I think the left hand side is really equal to $$\bigcup_j\bigcup_i (U_j\cup V_i).$$

[vital dew]

psie

[agile magnet]

yes it is

but I claim that this is also equal to the right hand side

[vivid osprey]

🤯

[agile magnet]

and you should try to work out the proof

it's quite straightfoward

just applying definitions, no trickery

[abstract whale]

Hey guys! I know you are not supposed to ask if you can ask questions, but I am about to embark on a fool's errand that is reading a book with little to no worked solutions. You might be wondering why I am doing this, and the reason is because this book seems way too cool/interesting that honestly makes me just want to dive into it. So my question is: Is it cool if I spam this discord server with questions whenever I get stuck, or whenever I need somebody to verify if my proof/program is correct? This is the book, for anybody that's curious/interested: https://cs.wheaton.edu/~tvandrun/dmfp/

[agile magnet]

yea that's fine lol

but whatever questions you do ask, make a good solid effort of trying it yourself before asking

you'll learn more that way

[abstract whale]

Cool, thanks man

[inland zenith]

are you going to do it in SML?

it does seem like a cool book by the way!

[abstract whale]

Yes sir! SML seems like a nice gateway into other functional languages like Haskell and Ocaml later on.

Yeah, I really think the lack of exposure/solutions hurt this book's reach, because it really seems like a hidden gem

[inland zenith]

Well... sure, SML is a great language, no doubt, but the tooling is honestly quite terrible, just be aware of that if you plan on spending any amount of time writing SML code, it is not terribly uncommon for people to work through SML books in OCaml (which I have done) but I fully admit that it is extra work and may be confusing if you don't know OCaml

But I'm not trying to dissuade you at all

[inland zenith]

let us know if it lives up to your expectations! 🙂

[abstract whale]

Yeah, running SML seems like a pain in the ass, not gonna lie, but I should be okay. Once I am done with this book, I am planning to never touch it again lol

[abstract whale]

For sure, you will hear from me a lot, don't worry lol

[inland zenith]

Hmm, okay. I think if the book doesn't have any large scale projects you should be okay, that's one of the more annoying parts, managing projects with dependencies and multiple files

all that really sucks for SML

[abstract whale]

Man, that's the worst part on any language, can't even begin to imagine how terrible it is for SML. Sheesh lol

[inland zenith]

And not a whole lot of editor support but it still exists, so it's definitely not terrible

[abstract whale]

Yeah, I think SML was just chosen as a "vanilla" choice for a functional paradigm programming language. I guess it's easier to learn the SML syntax than learning Haskell and Ocaml syntax for a "small" book.

[inland zenith]

For sure, it's a very nice choice for this type of book, it is a small language, similar to R5RS Scheme, but statically typed

definitely a large minority of books and research projects that use it

I appreciate SML a lot because its semantics are fully formalized, which is very rare

[abstract whale]

Sounds like you have worked with lots of functional programming languages. Seems like you have worked on some seriously interesting projects.

Living up to your username, I see lol

[inland zenith]

yeah I love functional programming, but no I haven't really worked on interesting projects, well, nothing that is of interest to anybody other than myself anyway, just for fun

[inland zenith]

😅 it's a reference to the Thief video games, I'm not so egotistical haha

[abstract whale]

Would love to see your github one of these days, if you are comfortable with sharing it lol

[abstract whale]

I could swear I have that game in my steam account. I should play it one of these days

[snow cedar]

Kinda stuck with organizing this:

I'm going to call each type of face F1, F2, F3 respectively.

Since each edge is shared by exactly two faces, I get that
6F1 + 4F2 + 4F3 = 2E
And so E = 3F1 + 2F2 + 2F3

And i tried using eulers formula to solve for F, which gives me F = 2 + {V}/2

[inland zenith]

sure, not really much to see https://github.com/BridgeTheMasterBuilder

[inland zenith]

which one? the newest one from 2014?

[true iris]

hey someone can help me ton find the nature of this series

[inland zenith]

wdym nature? the sum, or whether it's convergent/divergent?

and maybe better to ask it in #real-complex-analysis ?

[kind needle]

to find all simple cycles starting/ending at source node s for an undirected graph, doing a depth first search starting from node s, and checking if we end up back at s is sufficient?

[inland zenith]

yes, in principle, but of course you must watch out for other cycles or your algorithm might not terminate

[kind needle]

how so?

why wouldn't it terminate?

with dfs we only go to a vertex once with the visited array no?

[inland zenith]

depends on how you implement it, if you want to enumerate all possible cycles you need a more sophisticated approach

[inland zenith]

actually I'm not 100% sure about this anymore, but intuitively it seems like it would make sense that you can find all the cycles this way

[kind needle]

i only want all possible cycles starting and ending from source node s that I chose though

otherwise i could just use johnsons algo if i wanted all cycles no?

[inland zenith]

yes I understand, but after you find one cycle, how will you find other cycles that also visit the same nodes?

[kind needle]

I was wondering about that
what if I increment an array with visited nodes when im going down the graph, if i find a cycle add it to a global list
then when I go back up the graph simply delete the child node from the array

and continue the process

something like that, is what I wrote is clear?

[inland zenith]

not to me, sorry, I don't quite understand what you mean

but I think I understand the rough idea

would probably work

[kind needle]

ok thanks, will try it out it'll make it clearer for me too ^^

[inland zenith]

good luck!

[snow cedar]

I got F1 = V/2 - 4 and F2 + F3 = 6, however shouldn't I find a way to isolate F1 and F2 by themselves too?

[abstract whale]

That's the one, I think. Is the 2014 as good as the OG one?

[inland zenith]

I don't know, I haven't played it. I think it's good

[abstract whale]

Dope! I should have expected that you liked Rust lol

[inland zenith]

it seems to take from Dishonored, which is ironic since Dishonored owes its existence to Thief, so it's kind of weird for a Thief game to then take inspiration from Dishonored, not that that's a bad thing, the Dishonored series is very good

But the first two Thief games are incredible, highly recommend playing

3 is also not bad at all

[abstract whale]

Bet. Imma try to hunt down the OGs to get the genuine thief experience instead of a dishonored reboot lol

[muted pumice]

What is the inequalities in terms of intervals for -3 ≤ 1/x < 1?

[inland zenith]

Nice, hope you like them. Be patient, those games can be pretty brutal, in a good way, it's honestly almost like if you wanted to be a thief in real life

the level design is not there to help you at all

[abstract whale]

That's actually dope. So you have to actually be stealthy instead of just killing everything in sight to be a "successful thief". Definitely gonna play those games.

[inland zenith]

yeah you are not gonna be killing many people, you will get destroyed

[abstract whale]

Hopefully the development team cuts you a check after this promo, cuz damn lol

[inland zenith]

haha

[vocal grove]

Quick question, does anyone know how to graph this exactly?
I'm trying to draw this out but it looked wrong.

[inland zenith]

this is what came out of graphviz

[vocal grove]

Oh my

The way I did it was like a spider web.

[inland zenith]

this can't be right, where are all the edges incident to 2 for example?

am I understanding the format correctly?

[vocal grove]

No, I think mine's likely wrong.

[inland zenith]

2 -- 4, 6, ... means there's a 24 edge and a 26 edge, right?

etc

[inland zenith]

by the way, the computer just made a choice as to how to lay it out, you can also go for a more weblike layout

e.g.

sorry couldn't be bothered to fix the conflict there

[vestal bronze]

https://csacademy.com/app/graph_editor/

[vocal grove]

Oh this site is very very useful.

Thank you so much.

[vocal grove]

It's fine, I don' think this is a big deal.

[patent pilot]

So Im doing
Consider the following second-order homogeneous linear recurrence relation with constant coefficients: 𝑎_n = 6𝑎_n-1 − 9𝑎_n-2, 𝑛 ≥ 2 with 𝑎_0 = 2, 𝑎_1 = 5
Solve the recurrence relation to find an explicit formula for 𝑎_n

https://media.discordapp.net/attachments/1282168382879301664/1307549138963005470/PXL_20241117_033301517.jpg?ex=673ab587&is=67396407&hm=2d1a0f7db7a15cab0c583372c50609c5329accd13810b50584697bb4a4beaa31&=&format=webp&width=471&height=837
What am I doing wrong here, rather how do I find the a_n=r^n ?

Do I need to use this formula instead ?

[patent pilot]

So I think I got a^n = 5^n

and I can repost how I got there

[strong moat]

if p , then q

[glossy orchid]

https://tenor.com/view/omori-omori-sunny-math-algebra-logic-gif-23535542

[sharp rose]

Omori reference

👀

[snow cedar]

I thought we can use euler formula for this, but now I think we cant because the question says the graph is not connected. In this case, what can we do?

[lethal linden]

For a general planar graph, the Euler characteristic is 1+k where k is number of connected components.

[snow cedar]

On second thought I reread it again, doesn't the hint make it sound like the graph IS connected?

The "outside" is counted as a face too

[lethal linden]

Every planar graph has an "outer face", which is why the Euler characteristic of a connected planar graph is 2 and not 1

Like, consider K_3. It has 3 vertices and 3 edges.

[snow cedar]

Yeah but what if you had a graph that had 2 disconnected K_3, by this setup, would the hint that every face contains a cycle just be talking about one of the K_3?

[lethal linden]

In that case, the outer face has two cycles.

If it helps, you can imagine embedding the two graphs so that one is a smaller triangle fully contained in the other. Then there's the region inside both, the region inside one but not the other, and the region outside both

[snow cedar]

The thing is I haven't heard about euler characteristic before, so I think there's another way to solve this problem. I saw a theorem that said for a planar graph with at least 3 vertices that m <= 3n - 6

[lethal linden]

Well, Euler's formula just is the statement that a connected planar graph has Euler characteristic 2

Look at the proof and induct on the number of connected components k

Euler's formula is the base case; the induction by comparison is much, much easier

Euler's formula holds for each connected component of a planar graph

There's only one face that's common to every connected component, namely the outer face.

If you sum up V_i - E_i + F_i = 2 for each connected component, you count the outer face k times

So you get V - E + F + (k-1) = 2k by summing up all k instances of Euler's formula

You don't even really need induction unless you're being extra formal tbh, the above is 99% of the proof

[snow cedar]

How did we get the (k-1) on the Left hand side?

[lethal linden]

F is the number of faces overall. We counted the outer face k times and all the other faces exactly once. One of those k times contributes to F, and the other k-1 are over-counting.

[snow cedar]

Got it

So then using this, we still need to show the bound of m <= g/(g-2) * (n - 2)

[lethal linden]

I didn't think deeply about the specific problem, but yes, it should be enough. Every face has a boundary containing at least g vertices.

If you add up all of he boundaries and bound how much you can over-count edges or vertices, you'll get some expression bounding F in terms of g and the number of edges or vertices or something

And I suspect n-2 becomes n-k-1 or something

[snow cedar]

right so I got a bound of $fg \leq 2m$

[vital dew]

clementine

[snow cedar]

Then I think I think I can isolate F in this equation here

So F = 2k - k + 1 + E - V

So F = k + 1 + E - V

Then
$(k + 1 + E - V)g \leq 2m$

[vital dew]

clementine

[snow cedar]

actually ill just use V = n and E = m lol

So $(k + 1 + m - n)g \leq 2m$

[vital dew]

clementine

[snow cedar]

gk + g +gm -gn <= 2m

gm - 2m <= gn - g - gk

m(g-2) <= g(n - 1 - k)

m <= g(n - 1 - k)/(g-2)

[snow cedar]

Seems like it. So then the next step is to show g(n - 1 - k)/(g-2) <= g(n - 2)/(g-2)

I think we just cancel out soem terms and get

n - 1 - k <= n - 2

Which tells us that 1 <= k

Is that sufficient? Or am I supposed to word it differently

[lethal linden]

k is the number of connected components, so it's always >=1

Which means n-k-1 <= n-2

[snow cedar]

Ah I was trying to show it by going deeper: It explicitly says it holds when k >= 1 which is what our original constraint was

[lethal linden]

But k >= 1 for every graph no matter what.

Every graph has at least one connected component.

So, spelling it out like that makes it seem like you aren't sure what k represents.

g/(g-2) * (n - A) <= g/(g-2) * (n - B) if A >= B >= 0

Which is just a statement about inequalities.

And n - (k+1) <= n - 2 because k >= 1

k >= 1 is a fact you use, not something you conclude.

[snow cedar]

Ohhh

Wording it like this makes sense

Thank you 😄

[lethal linden]

[snow cedar]

I had another question, I'm trying to prove this direction: "If no connected component of G is a k-regular graph then G is (k - 1)-degenerate."

k-regular means that every vertex has degree k.. But since no connected component is k regular there has to be a vertex with degree < k. Are we supposed to use this idea to "list" a vertices in a conveninet way?

[misty iris]

A player of a video game is confronted with a series of opponents and has an 80%
probability of defeating each one. Success with any opponent is independent of
previous encounters. The player continues to contest opponents until defeated.
(a) What is the probability mass function of the number of opponents contested in a
game?

i already know the answer but am confused

so the answer is (0.2)(0.8)^x-1

The probability of successes it is defected by opponent is 0.2

how tho shouldn't it be 0.8?

[gusty swallow]

No, probability the player defeats an opponent is .8, so the probably the player loses to an opponent is 1 - .8 = .2

[misty iris]

Yeah but the formula used here shows 0.8 as the opposite of defeating an opponent no?

[heavy trench]

Can anyone share some interesting resources for Discrete maths OR Probability OR Combinatorics related riddles or puzzles that require deep logical thinking?
One example can be the problem known as the "Sleeping Beauty Paradox", though it was quite easy in my opinion, but I liked the way it was structured that makes it look like a paradox.

[fossil mural]

ok now i'm curious what you think the "quite easy" answer actually is

[heavy trench]

I just want some good brain workout, so any problem that require deep logical thinking will do

[heavy trench]

Will have to go back to the problem to recall the answer, give me few minutes, be right back..

1/3 @fossil mural

Can explain logically if you want me to..

[vestal bronze]

i also think 1/3 is hard to argue with

[heavy trench]

There's no valid argument to that imo, try if you have one, I'll try to address it

[vestal bronze]

i don't like how you said "it makes it look like a paradox"

as if you can think of 3 examples that are "truely paradoxical" unlike this one

they all seem the same to me

[inland zenith]

wrt/ that problem I think the only "paradox" is how the problem is framed, it's one of those cases where the source of contradiction is just that your understanding of the question is incorrect, similar to the drinker's paradox

[vestal bronze]

same question, when is that not true

there's a paradox where your understanding of the quesiton is not the problem?

and you're saying it's not just one, but there's multiple

[inland zenith]

hmm, I suppose it's a matter of degree, when the reason for the misunderstanding is trivial I wouldn't say it's a paradox, but I don't know

[inland zenith]

what do you mean?

[vestal bronze]

i mean like if you name one paradox where i agree that it's something special

that only proves there's one paradox, but we would expect like 3

otherwise why have a name for these things at all

if we figure out that we can find only one paradox, at all, that just means we misunderstand what's a paradox

it seems that a paradox is a lesson, a counterexample that shows you that you're thinking wrong, and you need to resolve it one way or another

so if you can distinguish between "true paradoxes" and "misunderstandings" you can name a bunch of things that are "open problems" that can't be understood

that sounds like you're just dividing into "i know this one" and "i don't know this one", something personal

[heavy trench]

It's not a paradox imo, just that it's famously known by that name is why I said that.

[heavy trench]

it's one of those cases where the source of contradiction is just that your understanding of the question is incorrect
Can't agree more

[vestal bronze]

i'm saying i don't understand

is it like you can't verbalise what's a paradox it's just things that make you feel a particular way?

we need to find an example where we both agree it's not a misunderstanding to discuss it further i guess

i can't think of any but i'm prepared to agree with your choice

[heavy trench]

So a paradox is like when you start from same point and give two sets of valid arguments and reach two different points, one from each set and these points are pretty obviously contradictory to each other.

Hence my statement that the "Sleeping Beauty Problem" is not a paradox..

[vestal bronze]

ok, so what's an example where that happens

i think i see what you mean, like you need to dismiss the question to resolve

but that sounds more like "stupid question"

[heavy trench]

Well examples for this will be mostly theoretical I guess..
Say time travel becomes doable for us one day and you go back in the past and kill your past self. If you past self died, how can your future exist? If your future doesn't exist, how can it go back to kill your past self?
Very very hypothetical example, I know but to understand what paradoxes are like, it should do..

One better example from google:
THIS STATEMENT IS FALSE!

Now if the statement is false, that means it's true. If the statement is true that means it's false.

[vestal bronze]

um ok

[heavy trench]

@fossil mural what do you think?
Regardless, if you have any resources that I asked for, please do share 🥺 .

[vestal bronze]

yeah so it has to be stupid and unresolvable

i understand now

[fossil mural]

i mean i think both of those resolve in about the same way that the sleeping beauty problem does: "if you define what the words mean then the answer becomes obvious, it's only hard if your intuitive concept doesn't quite make sense"

[heavy trench]

"What the words mean" as in?

[fossil mural]

well like, what's "time travel"

any full description of a universe that contains time travel includes an answer to the grandfather paradox

[heavy trench]

No I mean in the problem it's pretty clear that the sleeping beauty is awaken and asked what is the probability that the coin came up heads and the context for "the coin" is - the coin using which they decided when to wake her up.

[fossil mural]

well then what's "probability"

[vestal bronze]

i agree, there is a distinct type of paradoxes that are particularly dumb, they often don't have cool names, nobody talks about them much

it's consistent to call them true paradoxes and call "resolvable" ones not true paradoxes

thanks

[fossil mural]

i mean considering that in fact logic works, there aren't going to be any "real" paradoxes above a certain threshold of realness

i think the most reasonable thing to call a "paradox" is something that deduces a contradiction from an intuitive concept (or a mathematical theory, in the case of Russell's paradox), so that there's not really any "resolution" other than "yeah ok i guess that intuition just doesn't actually mean anything"

[inland zenith]

one possible definition of "true paradox" in this context would be type error, if something can't be assigned a type it's a paradox, that covers Russell's paradox and "This statement is false" and everything involving self-reference and negation

stuff which can't be reconciled

I think some types of legitimate math which makes perfect sense but not until you learn it could be called paradoxes too, like infinite series, which are very counterintuitive and people tend to reject them if they are not familiar

stuff involving infinity in general

[analog tinsel]

when I have a set S and I say , let ${a,b,c,d} \subseteq S$ be a subset of S. Is it guaranteed that this subset has cardinality 4 ?

I have seen people say that this set could very well just contain a four times and therefore have cardinality 1. But to me, this doesnt make sense since a set by definition cannot contain duplicates of an element, implying that this set has to be of cardinality 4.

I am confused, does someone have an explanation?

[vital dew]

barış

[inland zenith]

I would say you are correct

[analog tinsel]

here for example they use a set that contains duplicates but then they just talk about the cardinality. This would tell me that a set can contain duplicates, but the cardinality is defined to count only one instance of each element

[inland zenith]

a set with four a's is another idea, called a bag or multiset

[analog tinsel]

right, thats what I thought too

[inland zenith]

but if you say just set, that rules out {a,a,a,a}

[analog tinsel]

alright thank you !

[little prism]

well a,b,c,d are presumably variables and you havent said anything about which values they are and whether those are equal

thats whats important

it could be that a=1, b=2, c=2, d=3, then {a,b,c,d} has 3 elements

if you want to say that the set has four elements then you need to say something like "a,b,c,d pairwise distinct"

[fossil mural]

...i wouldn't exactly say that sets "can't contain duplicates"?

it's more that it's just not meaningful, to say that a set contains duplicates

[analog tinsel]

ok that makes sense

[fossil mural]

the only property that a set has is its membership relation, which you can kind of think of as basically just, a function that takes a thing and outputs either "yes" (it is in the set) or "no" (it isn't in the set)

[analog tinsel]

so to repeat youre point : whenever, a,b,c,d are variables and not concrete elements, there is no guarantee that these variables are all pw. distinct, correct?

[little prism]

yes

[analog tinsel]

appreciate it, thanks!

[little prism]

if we are talking about the set {a,b,c,d} of actually the letters a,b,c,d then that set has four elements

[analog tinsel]

yes that is clear

[fossil mural]

${a,b,c,d}$ just means the set ${x : x = a \lor x = b \lor x = c \lor x = d}$, so if for instance $a = b = c = d$, \ then this set just ends up being ${x : x = a \lor x = a \lor x = a \lor x = a} = {x : x = a} = {a}$

[vital dew]

bee [it/its]

[analog tinsel]

ok that makes a lot of sense

[analog tinsel]

this is what confused me

initially

some sources say a set cant contain an element multiple times

but I thought it can

its just not counted

in the cardinality

[fossil mural]

well it's not counted in anything, if you had a set that "contains x twice" (and doesn't contain anything else) then that would be equal to the set that "contains x once" (and doesn't contain anything else)

because both of these sets satisfy $y \in \text{the set}$ iff $y = x$, and there's no other way to distinguish them

[vital dew]

bee [it/its]

[fossil mural]

(the axiom of extensionality is what formalises this idea that the membership relation determines what the set is like this)

[analog tinsel]

alright thanks a lot

I think I understand

[analog tinsel]

I will look into it

unfortunately I havent been introduced to the basics of set theory, all these axioms and stuff

in computer science we just start right in the middle

its like "here, this is a set, now use it"

or maybe Im just slow lmao

[little prism]

frankly you dont need any of those axioms anyway

for most stuff

naive set theory is good enough

[analog tinsel]

yes thats true

[misty iris]

i got the answer which was
(0.2)(0.8)^x-1 but why, isnt the formula P(X=x) = (q^x-1)*p where q is the probability of an event failing, how is 0.8 failing?

[glossy orchid]

hi all, i have a question about set cardinality of 2 unknown sets, so what we know is X,Y are sets, and |X| < |Y|, so the cardinality of:
|(X U Y)x(Y \ X)| >= (|X| + |Y|) x |Y|
am i correct?

[placid yoke]

Could anyone help with these 2 problems? I have put my attempt in the pdf and the feedback that I got, but I still don't know how to do it.

[obsidian cove]

I need help for this

How is 1+1 defined here , for example

[fossil mural]

to be honest i'm not clear on what exactly they're asking you to show here

[fossil mural]

but anyway i'm guessing 1 + 1 = -1

[obsidian cove]

How though

Also what type of addition or multiplication are you assuming

[fossil mural]

well what else would it be

[obsidian cove]

Idk

U right then I guess

[fossil mural]

if 1 + 1 = 0 then there's no point listing -1 separately because 1 = -1
if it's something with x in it then the whole thing collapses into just being numbers

[obsidian cove]

So what's (x + 1 ) + x

[fossil mural]

2x+1

and 2 = -1 so that's in this list as 1 - x

[obsidian cove]

Ohj

That makes sense

I know you're a math undergrad which is how you were quick to find out 1+1 is -1 but how could I find out stuff like that

It seems like just knowing that one fact let's you do the rest of the question

[fossil mural]

(i'm not actually lol, the roles are more about level of knowledge, but anyway)

[fossil mural]

well i think kind of just this?

i kind of had to guess about what the context is, but given the guess that they expect this to be a field

what you get if you just keep adding 1 to itself, in any finite field, is that eventually you get back to 0, and it acts like the integers mod n for some integer n

(in fact n has to be prime for it to be a field, but that isn't actually necessary knowledge for this particular thing)

so given that what we're given here is 0, 1, -1

...well thinking about it it is somewhat more complicated in the general case

but in this case it's just, if you go off the top of the integers it "wraps around"

(if it didn't do something like that then, as you observed, it doesn't really make any sense)

[fossil mural]

or actually what you can do in general is count how many numbers there are

if i tell you that there's a reasonable way to make {-7, 0, 1, 9, 17} into a field, then you can tell just by counting that these are 0, 1, 2, 3, 4, and so everything is going to be mod 5

and then if you want to know what 9 + 9 is, you look for the number in here that's equal to 18 mod 5, which is -7

[fossil mural]

because 4 + 1 has to be something, and if it's 1 or 2 or 3 or 4, then 4 is equal to (respectively) 0 or 1 or 2 or 3, which it shouldn't be, but if 4 + 1 = 0, that's fine

[misty iris]

how do i find pmf

[oak drift]

Hello everyone I have to find the value of 1 mod 7 + 2 mod 7 + 3 mod 7 ... + 100 mod 7

but I genuinely have no idea where to start

does anyone have a hint/idea where I could start (not the whole answer ofc)

[inland raft]

what properties of mod do you know

[oak drift]

sadly pretty much none

Well ik a congruent to b (mod m) can be written as a = b * km

[lethal linden]

The "nice" thing about modular arithmetic is that every algebra maneuvers you're familiar with still works, but you have some extra maneuvers at your disposal.

So 1 mod 7 + 2 mod 7 + 3 mod 7 ... + 100 mod 7 is the same as 1 + 2 + 3 + ... + 100 (mod 7).

Do you know how to calculate 1 + 2 + 3 + ... + 100?

[oak drift]

oh I didnt know that

[lethal linden]

It was probably proven for you, but the proofs don't usually make it clear what it really means.

These would be proofs that addition and multiplication are "well-defined mod n", i.e., if a = b (mod n) and x = y (mod n) then a + x = b + y (mod n) and ax = by (mod n).

[inland raft]

you sure about that?

[lethal linden]

(And, yeah, a = b (mod m) doesn't mean that a = b * km.)

[oak drift]

I saw this in a video maybe I interpreted it wrong?

[oblique pelican]

a - b = kn
(a and b differ by a multiple of n)

[oak drift]

so the video is wrong?

[inland raft]

read what you wrote and see how it compares to whats in the video

[oak drift]

oops you're right

I did the same mistake in a previous exercise

[glossy orchid]

What's the meaning of this c dot

Is it just *2

[inland raft]

So much to critique about this mess

[glossy orchid]

i acc despise of this server i didnt ask your opinion i asked what that means

half the answers i get are just comments on irrelevant stuff

[inland raft]

noone here wrote it dawg why do you expect us to know whether a 2 or 1 was intended

[vestal bronze]

usually i'm like "what do you expect from discord" but this is "what do you expect from internet"

[glossy orchid]

dawg read the question

definetly a 2 👍

im certain

im asking about the c dot

[inland raft]

did you write that by yourself? you should know what you intended by the . notation

[glossy orchid]

no its from my practice questions

and ive just had a change if prof. and he does stuff differently

[inland raft]

it would be easy to guess if the context wasnt this confused

why is mathbbR this set??? Like what?

one would normally guess it's simply the set {(2m, m) where m in N}

but the whole thing is confused, it's choked.

and it's not a discrete math problem

[neon harbor]

You seriously think he wrote it himself and then came here to ask what it means? And "so much to critique about this mess" and your only critique is that the R is written in boldface? I feel like you're being intentionally antagonistic

I think its pretty clear it means {(2m, m) where m in N}

[glossy orchid]

im taking compsci last i remember and this module is called discreet math

[inland raft]

what do you think

[glossy orchid]

thank you 🙏

i think its just my bad knowledge in math and notations because i havnt touched maths for over 3 years and came into uni with high school level maths experience

and a lot of ppl here are so fussy with how i write things or questions i ask

[inland raft]

maybe you should work on that then?

[muted pumice]

how to filter ‘my_df’ (name) to show only the rows where “Age” is greater than 30 in Rstudio?

[thorn tusk]

maybe just try some cases like 1 2 and 3 and see if a pattern emerges and then check if that pattern makes sense and see if you can derive it?

wait is PMF just the function for calculating the probability of something happening?

because i think the formula for calculating the probability of two consecutive heads or two consecutive tails ocurring in exactly n flips is just

for n $\ge 2, f(n) = 1/2^{n-1}$

[vital dew]

Indian Jones

[thorn tusk]

i think

because before the first flip that begins your sequence of two heads, you have to alternate flips so that you dont create a sequence of two in a row before the intended number of flips right

or you could just prove this by induction or smth

you can prove that f(n) = 2 by casework

and then assuming that $f(n) = 1/2^{n-1}, f(n+1) = (1-f(n+1)) * 1/2 = 1/2^n = 1/2^{(n+1)-1}$, so then $f(n) \implies f(n+1)$

[vital dew]

Indian Jones

[thorn tusk]

i think i did this correctly?

[thorn tusk]

???

[quasi mantle]

is this always correct?

[agile magnet]

I assume f is a function f: A -> B?

If so, have you tried to prove this yourself?

[covert anvil]

what does v<w mean?

for vectors

[oblique pelican]

Probably supposed to be |v| <= |w|

Unless there's some other ordering they mentioned, but it's probably just that

A > 0 could mean a lot of things though

[lament kayak]

idk wtf v > w means but A > 0 usually means A is positive definite

[oblique pelican]

also why would they say "0 <= v <= w with v != w" instead of just "0 <= v < w"

or wait im dumb

they can have the same magnitude but be different

[little prism]

it could also mean <= in each coordinate

the notation should be explained somewhere previously in the book

[fresh hull]

In this question, ive shown that a left and right identity exists, now how do I show they are equal?

[cerulean radish]

Consider their product

[quasi mantle]

Let G be a 3-regular graph with 100 vertices each side... is there such e in G that G/{e} has a match with 99e?

[muted pumice]

How to use the formal definition of x^c to determine dx^c/dx?

[inland zenith]

G is bipartite?

[quasi mantle]

Yes

[covert anvil]

Theorem: If a Cauchy sequence has a convergent subsequence, then both the sequence and its subsequence converge to the same limit.

[inland zenith]

#real-complex-analysis

[covert anvil]

I don't think this is advanced level. I found it in a book written for university beginners.

[inland zenith]

I don't think that channel is just for advanced real analysis, but it's definitely not discrete math in any case

maybe #calculus then

[covert anvil]

I don't know what the hell discrete math is XD. I just remember there were some sequences, but I don't know.
so you are probably more familiar than me. I will try other channles.

[inland zenith]

let's just say discrete math is pretty much the opposite of real analysis

to be fair, sequences are not totally out of place here but still, it's something that's studied in analysis

@covert anvil but to answer your question since it doesn't matter that much, what have you tried?

it's pretty easy to show using an epsilon delta approach

well, "easy", it's not that hard, it takes a little bit of work

[covert anvil]

yeah book was a real analysis book.

intruduction at least

[inland zenith]

do you know the epsilon delta definition of a limit?

[covert anvil]

I did something and I checked the given proof my proof was correct but later, later when I needed to go back since this theorem mentioned next chapters, I just confused with the proof. I was looking for another approach.

[covert anvil]

yes I know.

[inland zenith]

and you know the definition of Cauchy sequence?

[covert anvil]

yes

[night stream]

can someone explain how to do 2a please

[inland zenith]

ok, just mix that together, let's say the sequence b_n has a subsequence a_n which converges to some value L, i.e. the difference between a_n and L is smaller than some epsilon past a certain n which is larger than some value delta or N or whatever, then you must show that there exists some delta' (or N') such that the difference between b_n and a_n is smaller than some other epsilon for sufficiently large n, and after you prove that, you can easily show that the b_n converges to L by using this result

it was a bit lazily stated on my part but that's the rough idea

if a_n gets arbitrarly close to L and b_n gets arbitrarily close to a_n then b_n also gets arbitrarily close to L too

[covert anvil]

Actually, that was what I did, and I am questioning what made me confused. Right now, it seems pretty clear.

[covert anvil]

thank you!

[inland zenith]

yw 🙂

[inland zenith]

oh right it was given that it was a Cauchy sequence so you don't even need to show the second part, can also assume that, so it's just combining them

[covert anvil]

yeah yeah

I got the point.

[inland zenith]

alright ^^

[inland zenith]

sorry also does G/{e} mean G with e removed?

[quasi mantle]

Yes

[inland zenith]

have you proven that a regular bipartite graph has a perfect matching?

[quasi mantle]

Yep

Halls problem

[inland zenith]

well isn't G-e 2-regular so you can just apply that? unless I'm thinking about it wrong

[quasi mantle]

Nope g well be 3 regular with 2 vertices that have deg 2

[inland zenith]

yes but then it's also 2 regular, or it has a 2 regular subgraph if you prefer

[quasi mantle]

And if we didnt prove that reuglar graphs have perfect march

This feels roo simple

[inland zenith]

yeah, I dunno

[quasi mantle]

This isnt true.. iff only work one way
(-1)^n doesnt converge but subesequence converge

The other way is just instant ....

Same epsilon same n0...

[quasi mantle]

Thanks anyways... ill try to ask in other place

[inland zenith]

please let me know if you solve it, good luck

[inland zenith]

actually, it is true, given that the sequence is Cauchy

otherwise you are correct

[quasi mantle]

Oh right. Cauchy sequence <-> converges

[inland zenith]

mhm

[hard hazel]

Can anyone give me a hint as to how to create the exponential generating function that generates the sequence 0!, 1!, 2!, 3!, . . .

?

It feels straight forward but I dont wanna jump the gun

[quasi mantle]

There is a trick with gamma function and e^x and intehral but that might be an ovsrkill

[hard hazel]

Definitely overkill for my class

[polar geode]

Hey would it be correct to say R union R?

[oblique pelican]

Did they define what it means to add relations?

[lyric quartz]

composition?

oh that was 8 hours ago....

[weary tiger]

Can anyone give me some guidance on this question? I'm not sure how to extract information about closure as the only information given about $*$ is a relation but that gives no information about whether an element is in $R$

[vital dew]

Cloudy

[weary tiger]

Maybe I've misinterpreted the question somewhere?

[glad quest]

As a disclaimer, abstract algebra is not my strong suite. Nevertheless, here's what I thought of. Thanks to $\sim$ being an equivalence, you can use the first two equations on $R$ with $$ instead of $\circ$. As a result you get $$ab\sim ac\leftrightarrow b\sim c.$$ Since $R$ has exactly 1 representative of each class, $b$ must equal $c$ and in turn $ab$ must equal $ac.$ You can do the same for the first position. This then gives you that $x=ab$ is in relation only with itself and no other elements in $R$, and therefore it must be an element of $R.$

I hope I didn't make any leaps. It's been a while since I did algebra.

[chrome nexus]

hi i have a question regarding this:
How many ways are there to seat four of a group of ten people around a circular table where two seatings are considered the same when everyone has the same immediate left and immediate right neighbor?

my original thought was to do (n-1)! so 3! would be my answer.
but i wanted to ask if i was correct in doing so, if not why?
(we havent been introduced to permuations or combinations yet just the counting rule principles )

[vital dew]

valekral

[glad quest]

First, let's get all the seatings without worrying about the ones that are the same. To fill the first chair, you have 10 options of who to pick. For the second chair, since you've already seated 1 person, you have only 9 people. For the third and fourth chair you have 8 and 7 people respectively. So the total amount of seatings is 10×9×8×7= 5040. Equals seatings are the same when everyone has the same immediate left and right neighbours. This basically means that you "rotate" everyone (counter)clockwise. Since we're seating 4 people, there are 4 different rotations. This reduces the amount of our seatings to 5040/4=1260. That should be the final answer.

[marble tree]

This is a practice final from my class. I am sorta stuck on how to prove this? Any help is appreciated, Thanks!!!

[chrome nexus]

tysm :DDD

[thorn tusk]

is Kruskal's just Prim's but the edge you select in any given step doesnt need to be connected the the edges you have already select?

[thorn tusk]

idk maybe draw a graph?

or just bash it

oh nvm its already been done

[novel escarp]

Is there any place on the internet where I can find solutions to the "Exercises in Graph Theory" by O. Melnikov
It doesn't seem to be efficient to look for the solutions and making people solve them for me multiple times, it would be more efficient if there was a single place with all of the solutions
Can I (let's say) just host a GitHub repo myself, store my solutions there and let people view/edit them

[thorn hedge]

Look at a maximal matching and count the number of edges between matched vertices and the other vertices

[grand totem]

* is already a binary operation on R, i.e. * : R x R -> R if that's what you're asking. So the only thing you need to prove in order to show that (R, *) is a semigroup is that * is associative.

[weary tiger]

How do you know it’s closed in R? I can see by the relation that it’s at least closed under S

[grand totem]

Like I said above, the problem explicitly tells you that * is already a binary operation on R.

[polar geode]

Can someone tell me if I approached this correctly ? It’s part (d)

[spare gulch]

what is a "tower"

[little prism]

context?

[spare gulch]

I saw this somewhere and I was curious what a tower is

I don't know what book it's from though

[agile magnet]

Yea you're gonna need to find more context lol

[lethal linden]

1. Don't use | for "such that" outside of set builder notation. It's confusing and hard to read. If you really have to abbreviate, write "s.t."
2. Are you trying to do a proof by contradiction? If so, say something like "Assume for contradiction..." and clearly state what's being contradicted when the moment arrives.
3. Your manipulations are incorrect as you've written them
4. Your conclusions don't contradict anything. Assume your second calculation is correct, so you can correctly conclude |a-c| <= 0. If that's the case then surely |a-c| < 1, which is stronger than what you want to show.
5. You shouldn't expect to find an issue for arbitrary a,b,c because there are some values of a,b,c which do have a transitive relationship. So the general case couldn't possibly lead to a contradiction.
6. Write down precisely what it means for the relation in (d) to not be transitive.

[polar geode]

Thank you so much !!

[analog tinsel]

I want to define a set S the following way:

For a given (simple) graph G = (V,E) let S be a set that contains a k-independent set X of G, if G contains such a set X, and is empty otherwise.

Now I was told that S is not well-defined, since its not clear which k-independent set should be chosen.
Also it is not generally known how the vertices of G are labelled.

Usually in the context of computers I could always assume that the graph is encoded in binary representation and therefore I can just say something like "S contains the lexicographically first k-independent set", which is unique.
However it is totally unclear to me whether something like this can be done here in the context of "pure" math.

Is there a way to have S well-defined?

[fossil mural]

...well it depends on what exactly you want that for, i think, because i'm not really sure why being able to define a specific one would be useful?

because like

let S be a set that contains a k-independent set X of G, if G contains such a set X, and is empty otherwise.
this is valid

it's not a definition, but if you're like, trying to prove some property of G that doesn't contain the variable S, and one of the steps in the proof is to assign a variable S like this, that's fine

the thing that would be somewhat more of a problem but which it's also unclear why you would want, is if you wanted to do something like define "the" function that takes a graph G and outputs the set S

[patent pilot]

https://media.discordapp.net/attachments/1282173083783921804/1309656939915120650/image0.jpg?ex=67426092&is=67410f12&hm=bc94d3c4b2dbb1ce402beba9ac9db7447737617cb098e92723d72e3fe9ba9ac4&=&format=webp&width=449&height=840
https://media.discordapp.net/attachments/1282168382879301664/1309662372062826537/rn_image_picker_lib_temp_f2dd5dd3-a0c1-4a3e-a973-4d9060d569ff.jpg?ex=674265a1&is=67411421&hm=035614d3de17bf76ed58c1e28b966281d6f07fbe29df89505026d349a5cc6f21&format=webp&width=472&height=839&
Am I doing this right?

[analog tinsel]

yes thats exactly the problem here. I want to construct a logical formula based on S.
I want a propositonal logic formula that is defined like satisfiable if and only if G contains a k-independent set.
Or really just if any object O has any (finite) property P. I just took graph and k-independent set as an example

So the formula would be this:

$\varphi_G \coloneqq \bigvee_{Y \in S} \top$

[vital dew]

barış

[analog tinsel]

So idk how standardized propositional logic syntax and semantics is but here the big V is a logical or over each element in S and the T is a tautology

so yeah, this formula is not well defined if S is not

[fossil mural]

ok i have no idea how that relates to the question you originally asked and also honestly i'm confused about what you're saying but if the question is just "how do you write a formula that's true if G contains a k-independent set" then

$\exists S \subseteq V (S\text{ is }k\text{-independent})$

[vital dew]

bee [it/its]

[fossil mural]

(where the stuff inside can be replaced with whatever the actual definition of k-independence is)

(i'm assuming here that a k-independent set in a graph is a set of vertices, but if that's not true you can replace V with something else)

[analog tinsel]

so what you wrote is essentailly what I wrote, just in another syntax

in our course we have a definition with an alphabet and semantics

and a grammar

for a formal language

that is our boolean logic

it should be some standard thing but as I said I am not too sure how commonly used this is

[analog tinsel]

or wait, hm I meant S contains one of G's k-independent sets (as in Maximum Independent Set of vertices) if G contains such a set, and is empty otherwise

Im not sure you meant the same thing

[analog tinsel]

sorry ok overlooked this message

[fossil mural]

i mean i think "using some kind of propositional logic" is fairly common, but there are various minor variants in how you define it (that turn out to not matter much in the sense that they all define essentially the same system) so possibly the specific collection of choices that your course is using isn't very common

but yeah to the extent that it's not standard i'm mostly guessing it's nonstandard in a way that doesn't matter much

(well unless they made any decisions that are just weird)

[fossil mural]

well what this means is "G contains a k-independent set"

[analog tinsel]

should be alright, we also teach stuff like np completeness of boolean sat in that context

well anyways

[fossil mural]

i guess the way i'd write this is $(\exists T \subseteq V (T\text{ is }k\text{-independent} \land T \subseteq S)) \lor (\neg\exists T \subseteq V (T\text{ is }k\text{-independent}) \land S = \varnothing)$

[vital dew]

bee [it/its]

[analog tinsel]

so my problem is this.
I want a formula based on S, but if S is not well defined, the formula isnt

[fossil mural]

"either there is a k-independent set in G that is a subset of S, or there is no k-independent set in G and S is empty"

[fossil mural]

well the formula i originally said is well-defined

[fossil mural]

(this one)

if you're trying to do it in a language that doesn't contain $\exists$ then i honestly have no idea how you'd talk about graphs at all in that language, or why you would want to

[vital dew]

bee [it/its]

[analog tinsel]

ohh

now I think I get it

what in the brackets is "such that S is k-independent"

ok give me a sec

[fossil mural]

well i don't know what a k-independent set is

but for instance if a set is k-independent if it's not empty then $S\text{ is }k\text{-independent}$'' should be replaced with $S \neq \varnothing$''

[vital dew]

bee [it/its]

[fossil mural]

(i assume that's not the definition lol)

[analog tinsel]

oh sorry

what I meant is just an independent set of vertices, which has cardinality k

so no two vertices are joint by an edge

and there are exaclty k vertices in that set

ok so the think is

what I am trying to do is find a sneaky way around actually solving the exercise

[fossil mural]

alright so, $\exists S \subseteq V (|S| = k \land \forall u,v \in S : {u,v} \not\in E)$, or something like that

[analog tinsel]

because usually people would construct nicely formed fomulas

[vital dew]

bee [it/its]

[analog tinsel]

that acutally make sense

but since we can just make the formula dependent on any set we can define

this weirdly allows for a lot of tricks

and I am trying to test the boundaries

and I thought you could solve every single exercise by such an approach

the one you gave would again require some more details in our logic

which I wanted to avoid

[analog tinsel]

yes exactly that

so I mean nice formulas like these

this formula would be satisfiable if and only if there exists a k-hitting set for given M, S, k

where M is a set, S a subset of M's powerset and k some natural number

and what you could always do if the question is only existence of a solution, is say

"Let S be the set of all solutions ( so here of all k-hitting sets, for given M,S, k) "

and then have

$\varphi_{M,S,k} \coloneqq \bigvee_{Y \in S} \top$

[vital dew]

barış

[analog tinsel]

then if S is empty, the disjunction evaluates to an unsatisfiable formula $\bot$

[vital dew]

barış

[analog tinsel]

otherwise we have a disjunction with a tautology $\top$ inside

[vital dew]

barış

[analog tinsel]

but then usually the follow up question is "explain how you can translate a satisfying truth assignement to the variables into a solution"
which would obviously be impossible here

anyways I feel like I am harrassing you with this

xD

I appreciate your help!

[calm cedar]

hey guys, i have a question that needs some clarification (in regards of graph theory), lets say we have G = (V, E) be an undirected graph where V is the set of vertices (node 1, node 2, node 3 for example) and E be the set of edges

lets say the visual representation of the graph is as followed:

 1

/
2 3

what would the incident edge be exactly? (from my understanding its just the link between the nodes, node 1 has an incident edge from node 1 to node 2 and node 1 to node 3)

in other words, is an incident edge just a synonym to a link?

[lethal linden]

Incident means two things are touching.

An edge is incident to the vertexes it's connected to.

You might talk about two edges being incident to each other if they share a common vertex.

[rose flume]

Would like to learn if there's a different outcome.

[vestal bronze]

different outcome?

[rose flume]

What outcome would it be if you apply the "AND" logic to the Base-3.

[vestal bronze]

if there's an obvious correct way i can't think of it

┌──┬─────┐
│  │0 1 2│
├──┼─────┤
│0 │0 0 0│
│1 │0 1 2│
│2 │0 2 2│
└──┴─────┘
```maybe like this

[rose flume]

(Revised by adding different outcome)

[rose flume]

I don't see A, B, and A^B for your decisive outcome.

[vestal bronze]

i like mine

[rose flume]

I guess you land on arbitrary.

[vestal bronze]

your last one is waht i did

just 1 and 2 are reversed

[rose flume]

Do your flip trick froggy.

[vestal bronze]

so it's the last one

[rose flume]

I guess it's the hand in the air for the time being.

[warped gull]

I'm having a problem proving with contradiction that if (a * b) != c * k (k some integer) then a != c * p (p some integer)
in other words : if c doesn't divide (a*b) then c doesn't divide a

[dim trout]

,tex a \cdot b \ne c \cdot k \rightarrow a \ne c \cdot p

[vital dew]

captindfru
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[glad quest]

Does it have to be through contradiction?

[warped gull]

If you have another way I would be happy to hear it, I just didn't think of any

[glad quest]

Instead of proving $$a\cdot b\neq c\cdot k\implies a\neq c\cdot p$$ try proving the contrapositive: $$a=c\cdot p\implies a\cdot b=c\cdot k.$$

[vital dew]

valekral

[glad quest]

If I'm not missing sth, this should be a valid proof.

[warped gull]

I tried it and I get to
(c * p) * b = c * k
p * b = k

which leads me to a dead end or am I missing sth?

[glad quest]

You want to prove that if there exists such integer $p$ for which $$a=c\cdot p,$$ then there also exists such integer $k$ for which $$a\cdot b=c\cdot k.$$ What you got is what $k$ must equal for the equations to hold, and since we know what both $p$ and $b$ are, you've proved that such a $k$ indeed exists.

[vital dew]

valekral

[glad quest]

(sorry for the late response, i was cooking pasta)

$$a=c\cdot p\ |\ \cdot b,$$ $$a\cdot b=c\cdot p\cdot b\ |\ \text{let}\ k=p\cdot b,$$ $$a\cdot b=c\cdot k.$$

[vital dew]

valekral

[spark surge]

hello. I have no idea if im in the right channel or not but im looking for someone to explain strong induction for me on a specific problem. I have no clue what's going on and i have to submit an assignment on it soon..

[lethal linden]

Ask the question

[spark surge]

this is the question. i get the general concept of strong induction but i have no idea how to apply it

[lethal linden]

First, you need to have a statement to prove. What's the answer?

[spark surge]

im not really sure, how do i get the statement?

[lethal linden]

Well, call it a conjecture, if you'd like. What are some possible total amounts, what are some impossible total amounts? Is there a pattern?

[spark surge]

i guess anything less than 25 would be impossible? and some possible amounts would be any combination of the two? so 25x+40y?

[lethal linden]

Yep. The set of possible total amounts is $$T = \left{25n + 25m ,:, (n,m) \in \mathbb{N}^2\right}$$ where $$\mathbb{N} = \left{0,1,2,3,4,\ldots\right}$$

[vital dew]

Cufflink

[lethal linden]

Show the statement you've been given for strong induction. There are many equivalent ways to state it, at various levels of generality.

[spark surge]

can you elaborate on that please?

[lethal linden]

Your book or whatever gave you a defition of strong induction. What is it, verbatim?

[spark surge]

Discrete Mathematics and Its Applications (7th Edition)

[lethal linden]

Ok. Could you prove this with induction if the only denomination was $25 and the only possible values were of the form 25n for natural number n?

[spark surge]

what am i trying to prove exactly?

[lethal linden]

That if the only gift card denomination is 25 then the possible values are of the form 25n, for any natural number n.

(Solve the simplified one first, to work out any confusions you have w/ induction.)

[spark surge]

alright let me try it one second

[lethal linden]

Share what you have so far; it shouldn't take this long unless you're confused.

[spark surge]

im not really sure if this is correct or not

[lethal linden]

I see. Think of it like this. Let T: ℕ → ℕ be the function where T(n) is the total value of your $25 gift cards if you have n of them.

Our proposition P(n) is that T(n) = 25n.

So...

1. P(0) is the proposition that T(0) = 25*0 = 0
2. P(1) is the proposition that T(1) = 25*1 = 25
3. P(87) is the proposition that T(87) = 25*87 = 2175
4. etc.

It doesn't make sense to say "P(1) is true for n=0". P(1) is whatever the proposition is when n=1. What you've proven in you base case is P(0).

Your book excludes 0 from the natural numbers, so induction starts at n=1. But it doesn't matter. You can start induction at n=0 or n=1.

[fossil mural]

(that should be 2175, not 2,75)

[lethal linden]

woops

[spark surge]

thats a mistake on my part, i meant to write p(0)

[lethal linden]

I sliced off the tip of my left index finger the other day and it's wrapped in a thick bandage + stitches. I'm very typo-prone right now. Haha.

Anyways, P(n) is the statement that T(n) = 25n.

If T(n) = 25n can you prove that T(n+1) = 25(n+1)?

Well, T(n+1) = T(n) + 25. It's whatever my total value is with n cards plus 25 for the extra card.

Therefore```
T(n+1) = T(n) + 25
= 25n + 25 (by inductive hypothesis)
= 25(n+1)

which is `P(n+1)`. So if we assume the inductive hypothesis `P(n)`, we can conclude `P(n+1)`.

[spark surge]

yes i understand that.

[lethal linden]

Ok.

What does n represent, here? Like, in plain English?

[spark surge]

the number of cards i assume?

[lethal linden]

Yes, that's correct.

You might say we're "inducting over the total number of gift cards"

In the case where you have two denominations, i.e., n gift cards worth $25 and m gift cards worth $40, what is the total number of gift cards?

[spark surge]

n+m?

[lethal linden]

Is that a question?

[spark surge]

no, the ? implies that im not sure lol

[lethal linden]

You're telling me that if I gave you 6472 $20 gift cards and 12 $14 gift cards, you wouldn't be sure how many gift cards you had overall, regardless of denomination?

[spark surge]

if n is 6472 and m is 12 then the total would be n + m

[lethal linden]

Seems like you're sure! 🙂

Anyhow, what would inducting over the total number of cards in the two-denomination case look like?

[spark surge]

can you explain that a little more? not sure i follow

[lethal linden]

Ok. You had no issue setting up the induction when it was one denomination. What's the induction for the case where there are two denominations?

[spark surge]

25n+40m

[lethal linden]

That's just an expression. Induction means you have a proposition parameterized by a single natural number and you're aiming to prove it's true for every natural number.

What's your proposition in the two-denomination case? What's P(n)?

[spark surge]

is it P(n) = 5n ? since 25 and 40 are both multiples of 5 so the only numbers i can produce using them are also multiples of 5

[lethal linden]

P(n) is a proposition.

It's something that could be true or false.

5n is not something that could be true or false, it's just some number.

In the one-denomination case P(n) is the proposition "If I have n $25 gift cards then their total value is 25n."

[spark surge]

p(n) is " 5n dollars can be made from 25 and 40 dollar cards"

[lethal linden]

We're trying to prove: "If I have k $25 gift cards and j $40 gift cards then my total value is 25k + 40j."

The issue is that there are two natural numbers involved now. That proposition, as written, isn't parameterized by one natural number, but two natural numbers.

You could say the proposition P(k,j) is "If I have k $25 gift cards and j $40 gift cards then my total value is 25k + 40j."

But we don't know how to prove something like P(k,j) by induction, if that's even possible.

We want a proposition P(n) parameterized by a single natural number. Part of the challenge is figuring out what that number should represent.

It can't represent only the number of $20 cards, or only the number of $40 cards.

Well, by analogy to the one-denomination case, maybe we can have n represent the total number of cards regardless of how many of each denomination we have.

[spark surge]

so n would represent k + j?

[lethal linden]

That's one way to do it.

Another way to do it is thinking about the range of values of 25k + 40j. There's some smallest value the expression can have, then a second-smallest, then a third-smallest, etc.

Then P(n) would be the statement "The n-th smallest value of the expression 25k + 40j is _____", where ______ is some expression that depends on n.

Or...

[lethal linden]

Actually, reflecting on the question again, I think it might be aiming at something else, namely that you can get all multiples of 5 larger than a certain amount.

[spark surge]

that amount would be 25, correct? since the smallest value would be if k = 1 and j = 0

[fossil mural]

well if you can get all multiples of 25 above 25, how do you get 30?

[spark surge]

did not think of that. youre correct

[lethal linden]

This question isn't great because there are many ways you could express the total possible value.

Some folks might just say it's obvious that the total possible values look like 25k + 40j, even if formally, technically that's something which needs proving.

Then there are other, less obvious expressions, which also warrant proving.

The reason I suspect the latter is because you don't realllllly need strong induction to prove that if you have n cards then the total looks like 25k + 40j for some k,j with k + j = n.

I don't know your professor/graders. This is the kind of question where, if you prove they all look like 25k + 40j by induction, would you get points off because you didn't prove the "actual" thing you were meant to prove, despite the fact it wasn't explicitly given?

[spark surge]

i have no clue. our professor did one problem on strong induction and went on to the next topic

[lethal linden]

On the other hand, I hesitate because proving you get all multiples of 5 larger than a certain amount requires you prove a bunch of individual cases below the threshold.

Like....I'm pretty sure you get every multiple of 5 starting at 140. Below 140, you're missing a bunch of multiples of 5.

Anyways, the "professional" thing to do would be to spell out this ambiguity and prove both versions.

[spark surge]

thank you

[snow cedar]

Hi everyone, I'm unsure about how to start with showing the => direction. By the definition I know that P_G(R) means # of proper r-colorings of G using r-colours.

[lethal linden]

What's theorems or lemmas about trees and/or chromatic polynomials do you have at your disposal?

[snow cedar]

These are the ones I could find:

[lethal linden]

What about trees? What characterization of a tree are you using?

There are many equivalent ones.

But from the chromatic polynomial, you can determine how many connected components a graph has and how many edges it has.

And a connected graph is a tree if and only if |E| = |V| - 1

[snow cedar]

I think we have |E| = |V| - 1

[lethal linden]

Sorry yes

[snow cedar]

Don't think this was given as a theorem to us so we might need to prove it from scratch

[lethal linden]

A graph is connected if and only if x^2 doesn't divide its chromatic polynomial

It's not hard to see if you think about coloring the graph BFS-wise, and realize a graph's chromatic polynomial is the product of the chromatic polynomials of its connected components.

[snow cedar]

Hm ok Ill experiment a bit

[lethal linden]

Pick a starting vertex v. If you have k colors then you can pick any of those k colors, but every vertex after that in the same connected component has to be colored using fewer than k colors.

[snow cedar]

Yes this makes sense to me. If there was a cycle i'd expect a - 2 term somewhere

Actually nevermind i dont think that is true

[final forum]

Could someone help me with notation for game theory? I'm trying to same something like "player 2 can modify their strategy for another position such that it performs just as well" but I'm not sure how to make it precise

so far I have this but the notation just seems really bad

[snow cedar]

Oh yeah@lethal linden , I realize I omitted some information, I think we are supposed to use the theorem in a) to help out with b).

If we're doing the => directin for b by contradiction, supposing its not a tree then there are two cases:

1. It's not connected. Then do using part a maybe we can do something with P_{G1}(x)P_{G2}(x) = x(x-1)^{n-1}
2. There are not v - 1 edges (Maybe a counting argument where each factor of the formula implies how many edges there are in the graph?)

[lone ice]

It says “To find the shortest path from node A to node B using a pruning Algorithm

[sharp crypt]

How to prove this combinatorically?

[lethal linden]

$$\binom{a-1}{b} + \binom{a-1}{b-1} = \binom{a}{b}$$

[vital dew]

Cufflink

[sharp crypt]

yeah but that would be algebraically

using that

[lethal linden]

Ok, then stars and bars

[sharp crypt]

the right side is choosing k+1 elements from set of n+1 elements, how to make the left side seem similiar?

[lethal linden]

How much of a hint do you want?

[sharp crypt]

lets start from slight

i did some similiar proofs but the less complicated they are the harder for me is to make a good proof

[lethal linden]

Hint: every subset of the natural numbers is well-ordered

[sharp crypt]

We have a group of n + 1 people. All of them are ordered (like natural numbers, from 0) We want to make a team which consist of randomly chosen, k+1 people.

On the right side we are choosing k +1 people to the team out of n + 1 people.

On the left side, we first assume what if only people up to some number k <= m <= n* want to be in the team (This way we consider what if people after number k dont want to play, what if people after k+1 dont want to play etc until everybody wants to play).
Firstly, we get the largest numbered person who wants to play and then choose the rest (then we end up with binomial(m, k) no matter how many people want to play, since we always take the person with biggest number to the team)

In general, on both sides we count how many possibilities we have to choose a team of k + 1 people within given set of people

* up to n, because there are n + 1 people and we start counting from 0. This way if people up to k want to play, we have people up to number k - 1 and assuming we order from 0 we have exactly k people which wanna be in the team.

idk if i used the hint but would it pass as an okay explanation? @lethal linden

[lethal linden]

It's pretty muddy. You're picking a set of k+1 numbers. How many ways are there to pick the smallest number in the set? Once the smallest is picked, how many ways are there to pick the rest of the set?

[sharp crypt]

its the largest number in the set

but for natural numbers there is always one way to pick largest/smallest number in given set, then after we pick it we can pick the rest of set in binomial ( power of set which we started from - 1, k) ways

thats why i assumed we pick the "biggest" person. If we picked the "smallest" we would end up in always picking 0

if we pick the biggest person I believe we still can achieve all possibilities of teammates chosen

[sharp crypt]

we can always pick only one of those "special" elements because natural numbers are well ordered i think

When we have a set of (0, 1] we cannot really pick the smallest one because reals are not well ordered

am i thinking right?

because then always picking a "Special" person we get rid of the +1 in k+1 on the bottom of binomial

[twilit matrix]

do you guys have any idea about this?

[dire lance]

this is kind of an elementary question, but this feels like I need to be triple-quadruple checked on this

Let's say we have two functions A, B: M --> M which are surjective on some (infinite) set M. We take B* to mean the inverse image.

Letting x be an element of M, is B* ∘ A only a function iff B is also injective?

[dire lance]

Try f: Z --> Z/6Z where f(x) = 3x

[twilit matrix]

but fx=3x doesn't satisfy f(xy)=f(x)f(y)

[dire lance]

In 6Z it should? f(xy) = 3xy = 9xy = 3x * 3y = f(x)f(y)

[twilit matrix]

sorry could you explain what do yuo mean by Z

[dire lance]

Z meaning integers, Z/6Z meaning integers mod 6

[twilit matrix]

ooh

one moment

so is f Z/6Z and 3x as well?

or is it f(x)->(3x)mod6

i think i got it thanks a lott<333

[inland zenith]

I have a question about something puzzling I read in a graph theory textbook. In a proof of one implication of a characterization of trees (if a simple graph T on n vertices is connected and each edge is a bridge, then between every pair of distinct vertices in T there is exactly one path), there is this argument, paraphrased a bit: "assume there are two paths p1 and p2 with p1 of shortest possible length. since p1 is of shortest possible length, the sequence of edges constituting the path p2 cannot be a rearrangement of those in p1, since if that were the case, we could use these common edges of p1 and p2 to form a path strictly shorter than p1, [...]"
my question is, given vertices u and v and a path between them, how can there possibly be many paths between them consisting of the same edges? I mean, they are arguing that is impossible, but why do you need this argument to rule that out, it seems impossible just by definition of a path, you can't permute the edges at all

right?

[sand thorn]

Can I get a hint on this, I spent wayyy too long trying to figure it out on my own and looking back at notes

This is an assignment so no full answer

I know that (n-1)/k kind of gives you the number of splits

that's the only thing I could figure out that sounds useful

[fossil mural]

what's the sum of the degrees of the vertices in G?

[sand thorn]

oh right i can do that and substract it with n

or not

wait

[sand thorn]

The sum of the degrees would give you n for internal vertices but the issue is we dont know the internal vertices to be able to get the leaves

the sum of the degrees for all vertices is the number of edges though times two

hmm let me see

right so I get:
sum of deg = 2*(n-1) = k + (k+1) × (number of internal vertices) + 1 × (number of leaves)

= 2 * (n-1) - k = k * (number of internal vertices) + 1*n

= 2 * (n-1) - k - n = k * (number of internal vertices)

(number of internal vertices) = (2 * (n-1) - k - n) / k

n - (number of internal vertices) = leaves

thank you

i forgot to exclude the first vertex

the formula becomes

which is still incorrect

Here are my steps ^

Or wait i think the first vertex is meant to be 1 more branch than the other vertex so that it can have the same degree as per the question

nvm

ok I solved it differently

basically i assumed "n" to represent internal vertices then found a formula to have it express the number of leaves were there to be "one more level" and then once I had that next iteration's number of leaves, I just divide it by the degrees (excluding the one degree attaching to above vertices)

This for those curious

[sand thorn]

Also, for some reason I'm missing 1 other answer here. I couldn't figure out the mistake after many attempts...

[split oasis]

and this is Multinomial distribution?
so it wouldbe
n!/(i! * j! * k!) * P^i * P^j * P^k ?

for C) is just using the pdf func
and get 0.0945
d) is Binomial distribution with n=8 and pAdele=0.5 right? 0.21875
e) Given XAdele=3 , the remaining n′=5 votes are distributed between Lizzo and Taylor. The conditional probs are

p lizza = 0.3/0.5 = 0.6
p taylor = 0.2/0.5 = 0.4

then P(XLizzo​=3,XTaylor​=2∣XAdele​=3)=5!/(3!2!)​×(0.6)^3×(0.4)^2 = 0.3456?

[tidal mesa]

Anyo recommendated book/guide for Recurrent
Sequences?

[slim wagon]

Can someone please confirm if this (somewhat informal) proof is correct?

[abstract hare]

woah all of this looks so advances

[sinful owl]

It looks fun

Imma take it next year tho

[quasi mantle]

This might be hard to read , but it was hard for me to translate aswell lol.
Let x(n) be the size of A where A f:[10] -> [N] functions s.t for every F,G f([10]) intersection with g([10])= 0
You need to prove x(n) value and its the upper bound

[quasi mantle]

@ashen bane

[ashen bane]

?

[snow cedar]

Do I need any complicated theorems about chromatic polynomial, or is there a more intuitive way to solve this?

[fossil mural]

this should be doable as just combinatorics without needing to know anything in particular about chromatic polynomials, i think?

...the method i'm imagining is kind of tedious if there isn't a trick i'm missing, but it's not something stupid like "enumerate all the colourings"

[lethal linden]

If p is the chromatic polynomial, what does p(k) represent?

[snow cedar]

I think the thing with chromatic polynomial is that you're not necessarily using ALL of the colours (Some of the amount you're counting can be for using k - 1 colours for example), so we'd need something different

P(r) means the # of proper r-colorings of G w/ r = # of available colours

[lethal linden]

Hmm

[lethal linden]

HMM

(Subtract out the colorings you don't want.)

[snow cedar]

Right I found something

Like maybe I thought to use this

[lethal linden]

You don't need to find anything — you just need to understand what the chromatic polynomial represents!

And use inclusion exclusion

[snow cedar]

Don't I need to find the value of P_g(4)?

Also f_G(1) = 0
f_G(2) = 0 (Because cycle is not bipartite)
f_G(3) = ?

[lethal linden]

For each size-3 subset of S, your set of colors, there are p(3) colorings which use that subset or any subset.

There are C(4,3)=4 such subsets.

p(4) - 4*p(3) subtracts too many subsets.

Inclusion exclusion

[snow cedar]

I want to remove the amount of colorings that use a subset of Size 0, Size 1, Size 2, Size 3

When you write 4*p(3), the p(3) could be using a subset of size 3, size 2, size 1, size 0, is that what you mean by itt subtracts too many?

[snow cedar]

Nvm I got it

[snow cedar]

How are we supposed to break this problem down to justify the smallest value for the Ramsay number?

Like n - 1 makes no sense because then there wont be a chance for a blue K_n to exist so probably the Ramsay number has to be bigger. But is there a more formal way to talk about this?

[lethal linden]

For the upper bound, find a K_n which has appropriate monochromatic cliques regardless of coloring.

For lower bound, find a coloring of K_{n-1} that doesn't have a monochromatic clique of either size.

For this exercise, think about what a monochromatic clique size 2 is, and what it would mean to not have one.

[vapid depot]

https://theoremoftheweek.wordpress.com/2010/05/02/theorem-25-erdoss-lower-bound-for-the-ramsey-numbers/
Really simple proof but I found it pretty neat. My first time seeing the probabilistic method.

[lethal linden]

Here's an old combinatorics midterm of mine, some fun and related exercises:

[snow cedar]

Can I say I think it's just n, because n - 1 might not even work (Because for example when K_{n-1} is has all blue edges, there is no opportunity to find a red K_2 or blue K_n).
When we colour K_n, if the colouring has a red edge then its easy to see the Red K_2. if the entire graph has edge coloured blue then your Blue K_n is already given
Is that it? Or is there a certain way to phrase this idea

[lethal linden]

That's it. A blue 2-clique exists if there's even a single blue edge.

If there's no blue 2-click then the remaining vertexes must all be red

[snow cedar]

Oh when you see R(2, n) you were thinking K_2 is blue and K_n is red

[lethal linden]

Whatever the colors are

[snow cedar]

Same idea though if you switch them around I guess haha

[lethal linden]

Purple and mauve

Periwinkle and forest green

Anyhow, that's the idea. K_{n-1} colored with all red has neither clique

So that proves it's greater than n-1

And if K_n has no 2-clique then all edges are red, so the whole graph is the n-clique

That proves it's no larger than n

This is the base case for a useful inequality proven by induction btw

[snow cedar]

Thanks! I also had a question about this, my idea was like this but it got stuck:
Let R(10, 10) = x. I claim K_x is a subgraph of K_n. Therefore any orientation of K_n will result in an orientation of K_x. Now I'm wondering how to get the result we need. Maybe I set forward edges = red, backward edges = blue for the sake of our orientation?

But this would just tell me that Kx contains a red or blue K_10 which doesn't seem to help because it just says "all the edges here are forward or all the edges here are backward", but my goal is to say something like "these 10 vertices are acyclic", so I think I was supposed to do something else. Is there a different observation we can make?

[lethal linden]

Well, think about coloring that corresponds to the orientation

Like, orient one way color it red

Other way color it blue

[snow cedar]

Right, looks like I got that so far

[lethal linden]

Imagine putting the vertexes in a line

What does a 10-clique look like, colored that way?

Like label vertexes {1,2,...,n} and put them in a line

So red goes right to left, blue goes left to right

Or whatever

[snow cedar]

So for me I'd have 10 vertices in sequential order, red edges will go from left to right and blue edges will go from right to left

Oh wait

So if we think of it this way

You can never trace a sequence of red edges and repeat a vertex?

[lethal linden]

Or say smaller-to-larger and larger-to-smaller

[snow cedar]

Okay what if we had like, a monochromatic K_3 with all red edges (idk if i am even allowed to bring up this example)

You'd put 1, 2, 3 on a line and since red = forward edge, we'd draw some arrows like 1->2->3 (and also an arrow from 1 to 3)

But when you look at the drawing isn't that cyclic?

Ah wait! I see my problem

[lethal linden]

No...? Every red edge goes from smaller to larger. How could there be a cycle?

[snow cedar]

I was thinking about in terms of drawing the arrows first, then I assumed the orientation. I falsely thought a clockwise triangle meant all edges are "forward"

[lethal linden]

Ah

That's why I changed to saying smaller-to-larger and larger-to-smaller

If you have 10 edges all pointing smaller to larger, it'll be an acyclic subgraph.

[snow cedar]

Right

Yeah I think the idea about projecting the vertices into a line helped

[snow cedar]

by the way i was wondering about what the minimum values of r and s are here, our notes doesn't even say them. I think that having either of them as 0 or 1 is problematic

Because I don't think K_(-1) or K_0 are defined

[quasi mantle]

?

[crimson hemlock]

How would you prove/disprove it?
Assuming A,B,C are sets

[lethal linden]

Well, if it's true for every set C then it'll be true for any *particular * set C of your choosing.

[crimson hemlock]

I chose the empty set an it came out true
But if A = {1}, B = {2}
And we choose C = {1,2}
The union is correct, but A≠B
So it's false

@lethal linden

[lethal linden]

No. You're being asked to disprove whether

∀C(A∪C = B∪C)

implies

A = B

For A={1}, B={2} the antecedent is false, which means the entire implication is true since P→Q is equivalent to ~P ∨ Q.

Choosing C to be the empty set shows it's true.

Because if it's true for any C then it's true for C = {} in particular.

[crimson hemlock]

Ahhhh I get it

Thanks!!!

[snow cedar]

For this question about hyper-graph ramsey theory, would I follow a derivation similar to the example on the top?

Lol this stuff looks crazy

I am also having trouble with understanding b and applying it to our situation, it sounds like we need k >= 4 points for this

[lethal linden]

That's always a safe bet. Try it and see what happens.

[snow cedar]

The thing is, we're working with R^4, but the example is working with R^3., so I'm unsure of how to say if a Quadruple is convex or not.

Couldn't we do this question using strictly the facts from A and B?

The question gives us a sequence (1, x1), (2, x2), ..., (n, xn) and no three of those lie on a line

And I think we would need n >= 10 otherwise we might have a "no clique"

[lethal linden]

Worry less about whether it follows the exact form and just try stuff. What have you tried?

[snow cedar]

I tried something that didn't involve the example,
Since n >= 10, if we repeatedly apply Fact A after choosing 5 points randomly, we will eventually run out of random selections so it means that every 4 points form a convex quadrilateral. Then I apply fact B to get that the n points are the vertices of a convex n-gon . From these n points we can get 10 points, and apply fact B again to get what we want?

[lethal linden]

This doesn't make sense. It would seem to imply that this is true in any set of at least 10 points, which is trivially untrue.

[lethal linden]

Say you want to look at 4-triples because we're using R^(4). What are some properties relevant to the exercise that would could use to decide what to color? Just list some.

[snow cedar]

So we would have i < j < k < l
There's a line segment i-k, and a line segment j-l. Maybe we can have j be below the line segment i-k and have k be below the line segment j-l to colour it convex?

[lethal linden]

Maybe. That's one property. Name some other properties 4 points on the plane may or may not have, mentioned in the text.

Just get a bunch of properties out in front of you first and then decide which are most promising.

[snow cedar]

Another thing I think is that 4 points on a plane are either convex or concave depending on how you place them

[lethal linden]

What does it mean for 4 point points to be convex?

Regions can be convex or not, but isolated points themselves aren't.

[snow cedar]

Oh I meant 4 points on a plane could either form a convex or concave polygon

Yeah regions

[lethal linden]

There's really just convex and non-convex, but yes.

Given 4 points, color the 4-hyperedge blue if they are the vertexes of a convex polygon. Color it red otherwise.

Or maybe color blue if they don't

Then you either have: a set of 5 vertexes, no 4 of which (something something), or a set of 10 vertexes, any 4 of which (something something).

[snow cedar]

The reason for this bringing this up is because you're using the definition of the Ramsay number right?

Since $n = R^{(4)}(5, 10)$, this means that if the edges of $K_{n}^{(4)}$ are colored red or blue, then it will contain a red $K^{(4)}{5}$ or a blue $K^{(4)}{10}$.

[lethal linden]

Uh huh. You have R^4(5,10) points in the plane.

[vital dew]

clementine

[snow cedar]

Ok and my understanding is if we say that the blue edges indicate the 4 vertices form a convex quadrilaterial, then we can use fact B on K^(4)_10

[cursive nymph]

is the real line good intuition for «linear orderings»?

or maybe it doesn't capture some cases

[brave rock]

The real line has a lot of structure that a typical linear ordering does not, so I would say no.

[lethal linden]

What? No.

[cursive nymph]

subsets of R?

[brave rock]

There are infinitely many linear orderings that cannot be subsets of R, so no.

But I suppose for intuition...

Yeah, for intuition I think it works well enough

[snow cedar]

Ah sorry, It seems like I have a misunderstanding then. Putting the meaning of red and blue aside (because you can just switch their roles without loss of generality), why were we saying "Given 4 points, color the 4-hyperedge blue if they are the vertexes of a convex polygon. Color it red otherwise." ?

[lethal linden]

It's clear from the text of the problem that you would like to use (b) with k=10

Assign colors to guarantee that happens

[honest rock]

"10. Since 0
is a possibility for oranges and for apples but not for both. we have
(9 + 1)(6 + 1)- 1 ways" Is the solution as described in the answer key, can anyone explain this to me please?

[lethal linden]

All the ways you can choose 0 or more of either, minus the one way where you choose 0 of both

But I kind of object to the framing of that as a "way of picking", because to me "way of picking" means a choice of order.

Like AAO and AOA are two different ways of picking three pieces of fruits

This question is more like "How many different baskets of fruit can you end up with, assuming the basket contains at least one piece of fruit?"

[honest rock]

thank you! this made it clear to me

[honest rock]

This is written in the answer key. As I have no previous experience in combinatorics, I don't know if this is relevant

[lethal linden]

I mean, it's just a matter of what they mean. That's why I never like word problems like this. They rely on conventionalized interpretations of ambiguous English words

Like folks who say "or" means inclusive or unless you say "either x or y"

[snow cedar]

Okay how about like this.
\

Let $n =R^{(4)}(5, 10).$ This means in any red / blue coloring of the 4-edges of $K^{(4)}n$, it must either contain a red $K^{(4)}{5}$ or a blue $K^{(4)}_{10}$.
\

Now we need to assign meanings to the colours.

\

Attempt #1: Coloring an edge red if the 4 points inside form a convex quadrilateral. Coloring an edge blue if the 4 points do not form a convex quadrilateral. This isn't valid because suppose we got a blue $K^{(4)}{10}$. This implies that there are no 4 points out of the 10 points form a convex quadrilateral. But Fact A says for any 5 points, no three of which lie on a line, 4 of them must form a convex quadrilateral. This is contradiction so we cannot have a blue $K^{(4)}{10}$.
\

Attempt #2: Coloring an edge red if the 4 points inside do not form a convex quadrilateral and red otherwise. We can't have a red $K^{(4)}{5}$ because we can find a contradiction in Part A. So we must have a blue $K^{(4)}{10}$ .From here we apply fact B

[vital dew]

clementine
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[honest rock]

@snow cedar what book are you using?

[snow cedar]

The book I check out is called "Intro to Graph Theory" by Douglas West

[lethal linden]

You've got the idea, but there's no contradiction involved. You have $n = R^{(4)}(5,10)$ points in the plane. Color a $4$-edge blue if its points don't form a convex quadrilateral, color red if they do.

\\

There's either a blue $5$-clique or a red $10$-clique. A blue $5$-clique is a set of $5$ vertexes no $4$ of which form a convex quadrilateral. That's impossible by (a).

\\

Therefore there must be a red $10$-clique. A red $10$-click is a set of $10$ vertexes where any $4$ form a convex quadrilateral. By (b) that means they form the vertexes of a convex $10$-gon.

[vital dew]

Cufflink
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

[snow cedar]

Oh I see

Yeah that's more concise

Thanks Cuff!

[jade plover]

Hey, they've asked me to prove that
[a]+[b] = [a+b] and that [a]·[b]=[a·b] are both well defined in modular arithmetic.
But I don't know where to start

I mean, my first idea was to chose a generic element for both equivalence classes, but I don't think that's the way to proceed

[little prism]

choose two elements for each equivalence class and show that the resulting equivalence class is the same in both cases

[a]+[b] and [a']+[b']

[jade plover]

I mean, it seems obvious for me that it is the same, but the thing is that I don't know how to express it on paper, cause I'd say sth like: "it is obvious that..." but it isn't, and i don't know how to express it

[little prism]

you have to use that [a] and [a'] are the same equivalence class

which gives you an equation for a and a'

then plug that in

same for the b's

[jade plover]

can I affirm, by definition, that if [a1] = [a2] then a2 = a1 + kn, for k belonging to Z?

[brave rock]

That is precisely what it means for [a1] = [a2], yes.

[jade plover]

right, cause I was confused with having [a2] and a2

but now I think is clear

ty

[fierce cedar]

I got this right, but I'm a bit confused on how we map our function in the second part of the question. Do we look for similar isomorphic invariants between vertices in V(G) and V(G')?

[lethal linden]

Each picture depicts a bijection between V(G) and V(G'), but they're not all isomorphisms. Pick the ones that depict an isomorphism, if any.

For g to be an isomorphism it has to be a bijection between vertex sets which preserves edges, i.e., a~b in G if and only if g(a)~g(b) in G'.

Preserving adjacency also preserves many higher-level properties, like degree, but at the lowest level either it preserves adjacency or it doesn't. The graphs are small enough you can manually check for each edge.

Like, if v1 is sent to w3 then the neighbors of v1 have to be sent to the neighbors of w3.

[fierce cedar]

I noticed that v1 -> w1 because it preserves the edge with v4/w4, v2 -> w3 because it preserves the edge with v1/v4, etc. are we looking for that kind of pattern?

[lethal linden]

Just check that the property holds.

Say g is like the second picture, where g(v1) = w3 The neighbors of v1 are v4 and v2, so g(v4) and g(v2) have to be neighbors of w3. That means g(v4) must be one of w2 or w1, and g(v2) must be the other. But g(v4) = w4, so it can't be an isomorphism.

In computer science, the problem of determining whether two graphs are isomorphic is called the "Graph Isomorphism Problem" and we don't know any efficient algorithms for general graphs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem

You can imagine doing this kind of "chase the edges" work for graphs with even a few more vertexes would get very cumbersome, very fast.

So, it's often quicker in practice to just look for properties preserved by isomorphisms that are present in one graph but not the other. That proves they're not isomorphic.

[lethal linden]

You also didn't show the rest of the page, so I don't know if you're meant to pick exactly one image or whether more than picture could possibly depict an isomorphism.

If you can only pick one then the answer is the first picture.

One way to see this is by realizing that graphs don't have to live on the 2d plane. If you imagine the graph is just four rings tied together with pieces of string, then any rearrangement of those rings + strings that don't alter the connections will be a picture of the same graph.

So if you think of the two criss-crossy edges as two pieces of string, one laying on the other, you could hold w1 and w2 down on the table and flip the other two horizontally to un-cross the strings and get a graph that looks exactly like the one on the left.

That gives you one isomorphism: send v1 to w1, v4 to w4, and then swap the other two vertexes.

And that's the function depicted in the first picture.

But there can be many isomorphisms between two graphs and without more meta-information I can't rule out the possibility that the other pictures also depict isomorphisms. I'd have to check.

[fierce cedar]

Just those, but I get it now thanks for the explanation

[snow cedar]

I'm trying to get the intuition for this hint about Ramsey Number,

Firstly in general I think that if n = R(x,y), then any coloring of K_{n + 1} will contain a red K_x and blue K_y (Because colouring K_{n+1} will colour the K_n anyway).

I think what's tripping me up is the nested values in the R on the right hand side, because I'm not seeing why creating a 2-edge-coloring is helping us

[sullen vapor]

hello, guys! Nice to meet y'all. I am a first-year computer science student in the second semester. Starting from this semester, I have been taught some discrete math. I have been struggling with it quite a bit since teacher of our math class isn't good at explaining concepts of discrete math and she rushes too much. She focuses on completing the lecture slides rather than giving out lectures carefully to students. For those reasons, I have been self studying discrete math since the start of this semester. I have been watching discrete math videos and self learning some concepts. If there is anyone who can relate to me or can navigate me the right path, can you please tell me what should I do next to do well in exam and for the good sake of Computer Science major? I truly want to delve into it. Can you please advise me whether I should use textbooks? I have downloaded some books.

[lethal linden]

Do as many exercises as you can. Aim for 10+ per week. Get feedback. Incorporate feedback. Repeat.

Godspeed: https://www.amazon.com/Invitation-Discrete-Mathematics-Jiri-Matousek/dp/0198570422

[sullen vapor]

thanks a lot for your suggestion 🙏🏻🙏🏻

[weary tiger]

I need some help with this question. I was able to solve it with a finite state acceptor but how do you solve this with a regex (Concat, Union, Kleene Star operations only)?

I would show what I've tried but I didn't really get anywhere with anything. Any tips on how to start this kind of question or certain ways I should be thinking?

Here's my working for solving it with a regular grammar (left form) and DFSA but I still have no idea how to do it with a regex. Is there a way I can convert it from one of these forms to regex form somehow?

[lethal linden]

I swear, every other book comes up with its own random-ass notation for formal grammars.

[vagrant latch]

Sorry guys if this is a stupid question but I cannot understand what the resources on the internet are trying to say:
I'm given the following task:
Let X and Y be any sets, we assume that there exists a bijection from X -> Y (and therefore we can write X ∼ Y?)
Proof that this relation is an equivalence relation.

So I do understand that an equivalence relation requires being:

• symmetric, reflexive and transitive.
  Now imagine X = {1,2} and Y = {a,b} and f = {(1,a), (2,b)}
  Then f is bijective, correct?
  But how can it be symmetric, because if we added the elements (a, 1) and (b,2) that wouldn't make any sense as those are elements of Y x X and not X x Y.
  Also how can a relation be reflexive if the domain and codomain are disjunct (or generally different like in the example)?

[cerulean radish]

It doesn't ask you to show that the bijection is an equivalence relation

[vagrant latch]

$ Let ( X ) and ( Y ) be any two sets. ( X ) is called equinumerous to ( Y ) if there exists a bijection between ( X ) and ( Y ). In this case, we write ( X \sim Y ).

Prove: This relation is an equivalence relation. $

[vital dew]

Uzumi0

$ Let \( X \) and \( Y \) be any two sets. \( X \) is called equinumerous to \( Y \) if there exists a bijection between \( X \) and \( Y \). In this case, we write \( X \sim Y \).

Prove: This relation is an equivalence relation. $
```Compilation error:```! LaTeX Error: Bad math environment delimiter.

See the LaTeX manual or LaTeX Companion for explanation.
Type  H <return>  for immediate help.
 ...                                              
                                                  
l.49 $ Let \(
              X \) and \( Y \) be any two sets. \( X \) is called equinumero...

Your command was ignored.
Type  I <command> <return>  to replace it with another command,```

[vagrant latch]

It doesn't?

[coral raven]

the relation seems to be that: X ~ Y if there is any bijection from X to Y

so for symmetry, you want to show that if there is a bijection f from X and Y, there exists a different bijection g from Y to X

[cerulean radish]

It asks you to show that the existence of a bijection between two sets is an equivalence relation, here symmetry would be equivalent to saying that there exists a bijection Y -> X if there exists a bijection X -> Y

[fossil mural]

so in this example, if X = {1, 2} and Y = {a, b} and f = {(1, a), (2, b)}, then f is a bijection which means the pair (X, Y) is in the equivalence relation defined in the question

[vagrant latch]

I think I partially understand now, thanks. So it's a question about a set of bijections.

[solar marsh]

Does anyone have a list of exercises to apply Dilworth's theorem to Posets?

[agile magnet]

You can apply Dilworth's theorem to get a fast algorithm to solve this

O(E log E) lol

[haughty garden]

i think you can get an even faster algorithm for it using some sort of reduction to LIS

but yah i liked the dilworth solution to this

[marble tree]

really stuck 🫠 🫠

[agile magnet]

You use Dilworth to get the fast LIS alg right?

[haughty garden]

yah

i think so

i don't remember the details

oh wait naive dilworth gives you something like O(m^2)

where m is |E|

but you can use dilworth with dp to get O(mlogm) via a reduction to LIS

[snow cedar]

Is the idea like this?

After we make a 2 edge-colouring for K_{n-1} based on the 3-edge colouring for K_n,
by definition the 2-edge colouring for K_{n-1} will either contain a red 2-edge colouring of K_(R^3(a,b-1)) or blue [...]

In both cases wlog, if theres a red 2-edge colouring of K_(R^3(a,b-1)), we can turn it into a 3-edge red colouring by adding back the vertex v.

[lethal linden]

Just analyze the cases carefully and remember what "red" and "blue" mean when you're 2-coloring the auxiliary graph.

If v is the vertex you remove, a blue edge {x,y} in G' means {v,x,y} is blue in the 3-hypergraph.

[snow cedar]

Yeah if {v, x, y} is blue in the 3-hypergraph doesn't that naturally suggest a blue-3-clique with this following idea: (I'm using red in this case)

Like $n - 1=R(R^{(3)}(a,b-1),R^{(3)}(a-1,b))$. Suppose the coloured $K^{(2)}{n-1}$ graph has a red $K^{(2)}{R^{(3)}(a,b-1)}$. Extending the edges in the red $K^{(2)}_{R^{(3)}(a,b-1)}$ so that they contain $v$ would form a $K^{(3)}a$ in $K^{(3)}{R^{(3)}(a,b-1) + 1}$