discrete-math

[distant osprey]

back to the first question so ive wrote out all the sets

do i just weite how theyre reflexive bc the other pairs are in the set

[weary tiger]

the way to answer the question is by presenting a set of ordered pairs that represent the whole relation

a relation is simply a set of ordered pairs. you got some already, but it is also known that it is an equivalence relation

which has these properties

[distant osprey]

ohh okok

[wispy wagon]

How many non-isomorphic simple graphs with 5 vertices that has a cycle with 5 edges are there?

[weary tiger]

There is only one non-isomorphic simple graph with 5 vertices that has a cycle with 5 edges. This is known as a pentagon.

1---2
|   |
5---4
|   |
3---5

[stray reef]

"This is known as a pentagon" [proceeds to draw an ascii picture of definitely not a pentagon]

[sand bay]

I'm trying to perform a reduction from Vertex Cover to Independent Set. I had a quick question about vertex cover though. By definition, vertex cover is the set of vertices such that all the edges are accounted for basically. So for a graph like this that is mostly disconnected, would just the set {7} be a valid vertex cover?

[last sigil]

Yea

[white grove]

Hi guys, I'm struggling with modular exponential. Basically, I'm trying to solve the function 667^937 mod 2436 while applying modular exponential but it seems can't solve the function. Here is my draft, did I do anything wrong?

[crystal oyster]

Given a0 = 2, and an+1 = 3 · an + 4, show that for every n we have
2 + an = 4 · 3n

can anyone discuss how to do this by proof of induction?

[weary tiger]

can you confirm if by "a0", "an" and "an+1" you mean $a_0$, $a_n$ and $a__{n+1}$?
i have asked you this before

[vital dew]

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

[crystal oyster]

@weary tiger yes, it did not copy right on to discord

[weary tiger]

alright

first you need to find the closed formula for the recurrence relation.

a general term An that is not defined in terms of itself

an example of this:
$$\begin{array}{cl}
b_0 = 1 \
b_{n+1} &= 2b_n \
\Rightarrow b_{n} &= 2b_{n-1} \
&= 2(2b_{n-2}) \
&= 2(2(...(2b_{n-n})...) \
&= 2(2(...(2b_{0})...) \
&= 2^nb_{0} \
&= 2^n
\end{array}$$

[vital dew]

arthur-caruso

[quartz patio]

Is there some good site/source available online where I can practice doing proofs? I understand most of the rules I learned during discrete-math, I just struggle a lot with writing actual proofs and finding the correct steps

[wide sinew]

so, here's a question from my 200 level discrete mathematics class that I took last year. It's one of those things where I don't know how I ever answered something incorrectly. Anyone wanna inform me?

[sudden minnow]

the question seems ill posed unless there is additional context, but the
n = dq + r
is meant to indicate that you are dividing n by d (divisor)

and q is the quotient

and r is the remainder

[sudden minnow]

so in that context, this isn't possible since the remainder cannot be greater than or equal to the divisor

[wide sinew]

wow

[sudden minnow]

since the qn says "is THIS scenario possible" I assume there was a previous question where this context was given?

[wide sinew]

not that it says, no. thats the entire thing there

[sudden minnow]

then it's a terrible question, I assume it was copied down from somewhere else

and context taken away

[wide sinew]

talk about a trick question in that case

[sudden minnow]

it is not a trick question it is just faulty

[queen willow]

How do loops interact with an independent set? I assume they can be in the input graph, but will never be in an independent set

[proper forge]

Can someone give me some guidance on how I'd go about this?

I imagine only the third one is an equivalence relation, but I'm not sure what the formal reasoning is

[haughty garden]

Check if each relation is reflexive, symmetric, and transitive

Note that the second one is not an equivalence relation because 3 -> 4 and 4 -> 2 but 3 !-> 2

[proper forge]

Aye. Just to be clear, the first one isn't transitive as well?

[haughty garden]

What breaks transitivity in the first one?

[proper forge]

I don't know. I just saw only 2 and 4 connects, but that doesn't imply anything when I think about it a second time

So in that case, I suppose the first is equivalent as well

[haughty garden]

Transitivity is that, if a -> b and b -> c, then a -> c

[proper forge]

Right

But C doesn't have a relation with B

So transitivity can't happen

Which doesn't mean it's broken yes?

[haughty garden]

Yep

If there isn't any relationship between a and b, then you can't really say anything about it to begin with

[proper forge]

Ok cool ty for helping me realise

An unrelated question along with that: Regarding bijections, I understand I can verify a function is injective by manipulating so X_1 = X_2, but I can't think of anything "formally" similar besides "looking at it." Might you have any ideas?

[haughty garden]

what do you mean by that? Like how to prove that a function is an injection formally?

[proper forge]

I'm sorry I meant I know how to "formally" prove injection. What I meant to say is I don't have anything as nice for surjection.

All I can think of for that is just inspecting and drawing conclusions, which is nice, but I'd imagine someone would want more

[haughty garden]

For surjection, you require that every element in your codomain be mapped by some element in the domain via your function mapping. Say that $f : X \to Y$ is a mapping from $X$ to $Y$. Arbitrarily fix some $y \in Y$. You then want to find a corresponding $x \in X$ such that $f(x) = y$, and because this works for an arbitrary $y$, you effectively show that all elements of $Y$ can be mapped by an element in $X$

[proper forge]

I understand. I suppose I just don't know how I can prove there is an X for every Y besides proof by cases for, as you say, any Y there is a unique X? I'm not sure

[haughty garden]

The typical method is to compute the preimage of f. For example, consider the function f : R -> R such that f(x) = x + 1. Fix some y in R. Then you want to find a suitable x in R such that y = x + 1. Therefore, choose x = y - 1 which is in R

Obviously, with more complicated functions, it can get a bit uglier but that's the usual method for showing surjection

[distant osprey]

any help with D1 iii-vi and D2

[turbid swallow]

How to solve the problem:
There are 4 candidates A, B, C, D in an election and their probabilities of winning are A=0.4, B=0.3, C=0.2 and D=0.1. Just before the election, C withdrew. Now what is the probability of A, B, D winning?

I tried to distribute C's probability among the remaining 3, so A= (0.4*0.2) +0.4 = 0.48 but it doesn't match the answer given.

How should this problem be approached?

[halcyon slate]

I don't see how the expression is true when p, q, and r have the same truth value

I simplified the expression to $(p \land \neg{p}) \lor (q \land \neg{q}) \lor (r \land \neg{r})$

[vital dew]

Thom Yorke

[halcyon slate]

taking the fact the and operator take precedence over the or operator

but if p, q and r are all true or false then each of these three parts within parenthesis is gonna evaluate as false

thus rendering the whole expression false

oh shoot

that's p or \neg p

🤦‍♂️

okay but the second part of the question doesn't make sense

how is it false otherwise?

<@&286206848099549185>

$p \lor \neg{p}$ is a tautology

[vital dew]

Thom Yorke

[halcyon slate]

so the whole expression should always come out to be true, right?

[sudden minnow]

your simplifications are just false then

[halcyon slate]

wdym

if either of the three terms is true then the whole thing is true

[sudden minnow]

you checked with the original expression?

[halcyon slate]

no the simplified one

aren't they both the same?

[sudden minnow]

check whether your theory holds for the original, if not then you made a mistake

all I am saying

[halcyon slate]

oh okay

[proper forge]

So is there being an inverse enough to prove its surjective?

[sudden minnow]

if the function has an inverse, it is bijective by default

so also surjective

[main elbow]

i have a similar issue. #books has a couple books on getting into proofs, but I was wondering if anyone had any idea how to get practice with proofs outside of a classroom?

[past wyvern]

I'm reading Discrete Mathematics with Applications. Around page 434 it presents the following around the rationals being enumerable/countable infinite and then the decimal representation of numbers between 0 and 1 for an uncountable infinite. The choice of using specific representations of the numbers and formulating the arguments being presented... just feels like a way to guarantee the contradiction with the diagonal argument etc

It states no countably infinite set can have an uncountably infinite set and shows the integers are countably infinite. I threw this together quickly using a similar proof format as above to show we can obtain a similar contradiction with the integers by being able to define how we represent them to begin with ... similar to choosing an "infinitely many decimal representation"

[sudden minnow]

the issue of your informal conjecture is that a prime expansion for an integer is necessarily finite, and your f would have to map to an infinite integer

so, it is not an integer

I guess I should mention here that

it is true that you can identify any real number between 0 and 1 uniquely through an infinite sequence

this infinite sequence is its binary representation (though can be other bases too ofc)

similarly, you can uniquely identify any positive integer through an infinite sequence

this infinite sequence is its prime power representation

the big difference between these two sequences is that the latter sequence has to be finitely supported

given any sequence, it has to be all zeros after a certain term

and yes, this is the big difference, because one can easily show the set of all finite sequences is countable

while the set of all sequences is uncountable

so if you wanted to adapt the proof for the real case to the positive integer case, you are guaranteed to fail for the finite part

[past wyvern]

Clarification - is the eventually all of the terms being 0 part here not "actually" the number zero but the multiplicative identity that does nothing to the final product so it's as useless as tacking on more 0s to a decimal expansion? (tacking on more prime powers of p^0?)

[sudden minnow]

yes, you can think in terms of the a_{i,k} in which case it literally is about all 0's

think of representing a (positive) integer by a sequence
(a_0, a_1, a_2, ...)

where a_0 tells you the power of 2 in the expansion, etc

this sequence must necessarily have only zeros after a certain term

[past wyvern]

That makes sense. What if we use p-adic valuation.. so the set of all rationals is $\frac{\nu_2(n)}{\nu_3(n)}$. If we define a one-to-one/injective mapping to $\mathbb{Q^+}$ with that - we still have infinitely many primes from Euclid available to map to an even bigger sets than that?

[vital dew]

CalicoJackRackham

[past wyvern]

i from the complex plane could be $i^{\nu_5(n)}$ etc? Because prime factorizations guarantee uniqueness, how can everything not be mapped to it?

[vital dew]

CalicoJackRackham

[sudden minnow]

I don't know any p-adic stuff, so you'd have to ask someone else for that, but I can tell you that whatever attempt you take rationals will be countable and reals will not, and the diagonal argument works

it is however impressive that you managed to take the fake proof this far, and I agree that many issues around cardinality are weakly formulated pedagogically

an instructor should emphasize is that what makes the diagonal argument work is the nature of the real numbers that allow them to be identified with infinite sequences

[past wyvern]

That makes sense. Thanks for walking through it with me. So is this a good counterexample to the fake proof? "In number theory, an Euler product is an expansion of a Dirichlet series into an infinite product indexed by prime numbers. " If I'm basing my fake proof on primes, then the Eulet product already iterates over them all and that's just 1 of these infinitely many infinite sequences?

[sudden minnow]

tbh I got no clue how you are relating this to number theory concepts, and my number theory knowledge is very limited but I don't think this and that are related

[past wyvern]

Yeah sorry. CS engineer for last 20 years and do number theory offhours - so as I learn more mathematical concepts - I tend to draw inferences/ frame of reference to number theory, recursion, or CS. I was looking at Donald Knuth's up-arrow notation as a possible way to get infinitely nested representations while still being in the realm of positive integers. The fact that numbers can have commom factors to indicate all possible relationships. Molecular formulae can be mapped to prime factorization without loss of generality $H_2O = 2^23^1$. It is an interesting thought experiment - but I can see mathematically, it probably strays from convention and standard notation and definitions

[sudden minnow]

yeah the issue is that the more you try to inject number theory into a problem like this the more you are going to confuse yourself, if done beyond a thought experiment that is

a logic/set theory formulation of this problem is extremely simple, and we've known the answers for a long time

[halcyon slate]

Is the assertion "This statement is false" a proposition?

I am a bit stumped by this question

From what I gather the statement "This statement is false" would imply that the statement "This statement is false" is false which would imply that "This statement is true" which contradicts the original statement.

should I conclude that this is not a proposition?

[pale epoch]

yes

[grave field]

Hey guys, could you help me with this problem, please. I have almost no idea how to solve this.

[grim skiff]

hi guys, i dont know if this question is for discrete-math

why is this equal ?

b is delta impulse

[reef dirge]

how do i find the inverse

of f

[brave rock]

f does not have an inverse. The notation f^-1(X) for some set X refers to the preimage, i.e., the set of all y s.t. f(y) is in X

[stone ridge]

This is in discrete math course so I'm asking my question here.
I don't quite understand the part circled in blue. What is the meaning that there is a function (notated in phi in the image) connecting set of strings (left set) and set of function f:[6]->[36] (right set)
My question:

1. How a function take some strings as domain and functions as co domain?
2. What does the mathematical notation f:[6]->[36] means mathematically?
3. How to come out the relation is between strings and functions?

[sudden minnow]

you can very easily enumerate your characters,

say the digits 0,...9 are numbered 1 to 10

then a is 11, b is 12... z is 36

then say you are given a string of 6 characters

(a b 1 5 z 2)

using our enumeration, this is

(11 12 2 6 36 3)

and to finish our bijection, we ifentify this with the function such that
f(1) = 11, f(2) = 12,... f(6) = 3

so we would explicitly have

$$\phi(ab15z2) = f$$

where f is the function described above

[vital dew]

lems

[sudden minnow]

as for notation, I am assuming [6] means the set {1, ..., 6}

[desert spear]

I am trying to understand that formula,

F φ ≡ φ ∨ X(F φ)

I just don't get it my interpretation about that is something like that, Eventually phi is equivalent to phi at present position or there will be phi some point in future, and its next element will be phi. But I can not be correct right?

[pearl hull]

Question what does _ means?
A

[haughty garden]

It’s basically trying to say that either phi is satisfied at the current time or phi must eventually be satisfied sometime in a future state, which is to say there will be some state where phi holds on the next state.

[desert spear]

I think I got it, Thanks 🙂

[drifting hawk]

How would do the latter? (set a one-to-one correspondence to prove theorem 4)

[desert spear]

I wonder how can I interpreted that (p U ¬q) R r formula? I thought that p will there all along until there is ~q. But how about the r? I mean the release (temporal logic operator), I mean we will keep getting r, until(p U ~q)becomes true. But how can I understand that (p U ~q) has became true in some point?

[drifting hawk]

How would you do 29? Here's my logic so far -- I'm assuming 2 0 bits following each 1 bit means immediately following
So if the lead bit is 1, then that fixes the first 3 positions
The last 2 bits of the 16 must be 0s

Then you have 11 spots to choose the 2nd one from, or C(11,1)
This fixes the next two positions after the 1 as 0s

8 spots to choose the 3rd one from and 5 spots to choose the 4th 1 from, and 3! ways to arrange the 3 free 1's, so 11*8*5/3! strings

[haughty garden]

If p U ~q is true, one of two things must happen: either p is true in the current state (in which case ~q can either be true or false) or ~q has to remain true until p is true. Therefore, r must hold until (and including the state) either p holds or ~q remains true until p holds. Note that p must eventually become true

[desert spear]

Well, what I understood about the until operator that p has to hold until ~q becomes true. I thought that if ~q becomes true then p will be false. Furthermore, I thought that p and ~q cannot be true at the same time. (I guess I thought wrong in that case). We can have bothp and ~q true at the same point if it were a release operator, I could be wrong.

[haughty garden]

Wait I did it the wrong way around: either ~q holds in the current state or p has to hold until ~q has to remain true until p is true

[modern monolith]

hey guys can someone help me
i have a final take home exam for my precalculus class and i am failing this class
this test is my last chance to pass the class
can someone help me please

[haughty garden]

There’s no requirement that both can’t hold at the same time

[modern monolith]

can someone pls help me

[haughty garden]

What about it?

[desert spear]

It said at least in the until operator.

[haughty garden]

Yeah that doesn’t negate what I said

You just require that p has to remain true at least until ~q is true

There’s no condition that specifies that p and ~q can’t hold simultaneously

In particular, once ~q is true, it makes the result of p redundant

[desert spear]

Well, I think I got it. At the end, I can conclude that until will become true when ~q becomes true in that case. Therefore, if I try to visualize that formula in the graph. would it be something like that?```

---> * ----> --->* --->* ---->
p,r p,r p,r p,r ~q,r

[haughty garden]

Yes that works

[desert spear]

Thanks for the help

[haughty garden]

This is almost correct, except you would have overcounted by fixing two zeros after choosing the position of the second 1 bit. Since you specify that two 0 bits get fixed after choosing the 1 bit, what happens if you place the second 1 bit in the 14th position?

Instead, consider fixing the group of three bits “100” and work out how many possible positions this group of bits can go in

[outer kayak]

is this an appropriate proof ?

same question here.

thanks in advance

[haughty garden]

(4a^2 + 1)/(2a + 1) having a nonzero remainder does not imply that their gcd is 1. For example, 100/80 has a nonzero remainder but you can deduce that their gcd is not 1. Instead, suppose that d = gcd(2a + 1, 4a^2 + 1) which means that d | (2a + 1) and d | (4a^2 + 1) and see if you can show that d = 1

[chrome fossil]

You didn’t do the second part of the problem, to prove it’s the only pair

[outer kayak]

ok thank you guys

[outer kayak]

better ?

[haughty garden]

Uhh that only shows that 1 | d

d | (2a + 1) and d | (4a^2 + 1)
=> d must divide a linear combination

In particular, d | 2a(2a + 1) - (4a^2 + 1) = 2a - 1. But then d | (2a + 1) - (2a - 1) = 2. This implies that d is either 1 or 2. But d divides an odd number, so d must be 1

[drifting hawk]

Er, how would I do this?

[haughty garden]

Ignore the first three positions of your string since they are indeed fixed. Imagine your string as the following:
X 100 X 100 X 100 X
Here, X can be thought of as placing some number of indistinguishable zero bits into distinguishable positions

The question now is: how many zeros do you have left to place, and how many positions are there? You can then use stars and bars to finish the rest

[drifting hawk]

Ahh makes sense, thanks

[weary tiger]

i wish i was this smort

[wet flame]

Is the answer to this just 10C2 ?

10 because 3 cards that are hearts have been picked and 13 cards in the heart suit so 13 - 3 = 10, then we want 2 out of the 10 so 10 choose 2 ?

so 45 combinations

Similiarly the total amount of combinations for picking 2 jacks will be 3 choose 2 = 3, as one jack has been already taken. same number of combinations for picking two 9 numbered cards aswell

Not sure how many combinations their are where the opponent wins can anyone help me with this? is this just 45 + 3 + 3 ?

[haughty garden]

Yes, note that each of these events are disjoint so the number of ways the opponent can win is just the sum of these events

[wet flame]

i see

so it would just be 51

assuming 45, 3, 3 is correct

interesting that this is one less than 52

[reef dirge]

is
f^-1(C) = {-1, -1}
right?

[weary tiger]

i need help

holy shit

[brittle laurel]

On my HW my prof put a problem on inverse modulo and we haven't gone over that at all so I'm really confused. I know that you can use the extended euclidean algorithm and write the gcd as a linear combination: ax + ny = 1, where x is the inverse modulo n of a. However, I get confused with reducing this expression. We (mod n) the equation and I keep seeing the result is ax = 1 (mod n). I don't understand the format. Isn't the (mod n) distributed to both sides of the equation? I thought it would be ax (mod n) = 1 (mod n) which is equivalent to ax (mod n) = 1. But I keep seeing the expression ax = 1 (mod n)...

[unreal stump]

Both are the same thing

Well actually x mod n = y mod n doesn't make sense

[brittle laurel]

But if we have ax + ny = 1 and apply mod n wouldn't we get (ax + ny) mod n = 1 (mod n)? And then we could get to ax (mod n) = 1 mod n? Or am I completely misunderstanding?

[unreal stump]

a = b mod n so that reduces to
ax+ny= 1 mod n

Because n divides 0 clearly

[brittle laurel]

Ok, thank you. I have to compute the inverse modulo 15 of 7, so I computed gcd(15, 7) to make sure it is 1 (it is). So then linear combination was 15(1) + (-2)(7). I'm a little stuck after this. I think after applying mod 15 I would have (-2)(7) mod 15 = 1 mod 15, so then x would be -2? But shouldn't x be positive? Sorry for all the questions, I have been unable to contact my professor at all

[unreal stump]

Well -2 = 5 mod 7

So you can substitute 5 instead of -2 and it will still be a modular inverse

[brittle laurel]

Ok thank you!

[stone ridge]

Oh I get it now. Thanks a lot

[stone ridge]

What is the use of phi here? As we already know the left set is already combination of password strings? Why we need phi of f here?

[dry raven]

does anyone here understand/ could explain what an elliptic curve is and how it could be used in cryptographic functions?

[sudden minnow]

because bijections preserve cardinalities, and the cardinality of "the set of all functions from [6] to [36]" is very easy to compute

[blazing rose]

if this is not not A

[blazing rose]

what is this??

is this the writers mistake? or does it have a meaning

[desert spear]

Would it be correct if I do that in such a way 😊

[reef dirge]

is
f^-1(C) = {-1, -1}
right?

Or should also 0 be included

[last sigil]

So what is f^-1(C)? I'm asking for a definition from you

@reef dirge

[reef dirge]

The inverse image

[last sigil]

Yep and what does that mean

What is contained in the inverse image

[reef dirge]

-1 ,0, 1?

[last sigil]

Why -1

[drifting hawk]

Where am I overcounting here? This is effectively counting the number of ways to arrange 10 chars, 2 of each kind, with a restriction
2 cases: d1 is site x, in which case there are 8*8! / 2^5 ways to arrange the letters and d2 is site x (or d1 is not site x) in which case there are 9!/2^5 ways to arrange the letters
There are C(5,1) ways to pick site x, so (8*8! + 9!)/2^5 *C(5,1) ways

[reef dirge]

-1 is in Z and f(-1) gives 2

[last sigil]

yes

[last sigil]

yes

[reef dirge]

So what’s the answer then

[last sigil]

This

[outer kayak]

i dont quite follow

i guess im still not sure whats wrong here

[vale cairn]

Somehow you went from the fact 1 divides both numbers to their gcd being 1, which is false (1 divides any number)

you seeing to be treating a as some variable so that "2a +1 cannot be factored"

Because it can be factored for most choices of a

[sudden minnow]

you got banned from the discord and immediately made an alt to post the same question?

rip bozo

oh he didnt get banned just deleted his post because he got discovered

[ember obsidian]

nah he gone

[sudden minnow]

nice

[muted palm]

your casework doesn't make sense

what about cases where neither d1 or d2 is site X? (e.g. d4, d7)

[urban girder]

Can someone help me with the approach I should take here?

[hallow zodiac]

Can anyone provide me with a course on solving homogeneous recurrence relations with constant coefficients in linear algebra?

[elfin mortar]

how does one go from the bottom figure to the top figure in this image? I don't seem to understand how the flow f(e) is determined from the capacity k(e)

this is on the augmenting flow algorithm (ford-fulkerson?)

[dire stag]

I'm taking discrete math next semester. I just finished college algebra. How fucked am I?

I was told to take discrete math, but there is another level of college algebra (precalculus)

should I take that first?

[jaunty spade]

yes

[sudden minnow]

probably

[radiant garden]

Why did he get banned for asking a question

[sudden minnow]

he didnt get banned for asking the question

he got banned for "challenging" people to solve his question in discussion

baiting ppl to help him basically

in #discussion where that isnt allowed, and he did that for 30 minutes or so

hate those ppl

[radiant garden]

Oh wait so he was like oh I bet u can't solve it

Hoping people would solve it

Reverse psychology 😂

[sudden minnow]

yeah he literally said that, I have posted the hardest discrete math problem in #discrete-math bet none of u can solve it

[drifting hawk]

I understand how to do this problem (going backwards) but what's wrong with this logic:
Suppose you have a_n ways to pay $n
To get to a_(n+5) you can either append $5 to $n, which means there's only 1 way to pay $a_(n+5) or you can pay $5 from $1 coins and bills, which has 2^5 ways
So a_(n+5) = a_n + 32a_n; or a_n = a_(n-5) + 32a_(n-5)

[spice wagon]

because you aren't counting the cases where you first get to a_(n-1) then add a $5 bill then a 1 for example

you're only counting the ways to get to a_(n+5) knowing that you pass by a_n, which is not necessarily true

to get to $10 dollars for example, I don't necessarily have to pass by $5, I could do $1 + $1 + $5 + $1 + $1 + $1

[drifting hawk]

Ah makes sense, thanks

Is this effectively: find the number of ways to pay $n given bills of $1,2,..n and depositing a $1 bill at the start

[radiant garden]

.

[outer kayak]

can someone help me here ? im very stuck

i believe this has something to do with the handshaking lemma

[weary tiger]

In how many ways can we select three students from a group of five students to stand in line for a picture?

Am I crazy or should the answer be C(5,3), not 5!/2! ?

If the question were to ask "in how many ways can three students out of five stand in line for a picture" then the answer would be 5!/2!

[unreal stump]

I guess C(5,3) for selection and 3! for arrangement should be fine

But ig they imply no of arrangements here?

[weary tiger]

The thing is, I don't see how the second part of the problem is relevant

The question is how to select three students

What they do is irrelevant since there are no restrictions i.e. (such that at least 2 are guys or something)

[unreal stump]

For choosing 3 students it should be C(5,3)

[weary tiger]

Yeah exactly

[unreal stump]

For no of lines,it should C(5,3) * 3!

[weary tiger]

Yes but we aren't asked about the number of lines..

[unreal stump]

Well ask your prof

[weary tiger]

It is from a book

[unreal stump]

This is a language problem

[weary tiger]

I agree @unreal stump

That's why I am asking

[unreal stump]

I think your approach is correct

[weary tiger]

So you think it should C(5,3) as well?

[unreal stump]

Yea

[weary tiger]

Alright good to know I'm not crazy

I understand the problem they tried to go for

But the wording makes it a different problem :/

[weary tiger]

hellow can you help me for this please thanks : Show that if n ≥ 3 then the number n!+3 is not prime ****

thanks but i dont see how i do

you have to factor it and it gives 5(n +1)

you have to factor again but this i don't know how i do

it's not prime for this

because we can divided 9 by 3

for this it's not in my ability

sorry i don't know how i do

we must to transforme this in an factor of 3

i have an idea it's ( 3 * 4 * 5*,,,,,, * n) but it's a factor of 3 and 3 three it will always be a factor of 3

(3 * 4 * 5 * 6 * 7 * 8*''''' * n ) it's a factor of 3 and add 3 it will always be a factor of 3

thanks for you help

[warm flower]

I think this is right, you know n! is divisible by 3 for all n > 3, so n! + 3 will also be, therefore not prime

[slender crest]

Hello! I'm not sure exactly if I should be answer part a) with a hypothesis/conclusion format or simply a formalized format.. Also for part b) I am totally lost on how to prove this

I think for part b) it's because: 1. P has to be TRUE, notS has to be TRUE, therefore R has to be FALSE, therefore T is False so notT is True

Thanks yea makes sense now. Part a) is a bit unclear still but feeling better!

[warm flower]

I think you can get to not T in 23 lines including the premises

[slender crest]

The only way I can think of showing this is by using Venn Diagrams. Is that the best option?

[ember obsidian]

by now you probably shouldve been taught a formal way to prove subset relations and set equalities

[slender crest]

You're not wrong. It's not something i've come across yet though

[quaint maple]

can someone explain to me what this means in words, R is an equivalence relation on A.

[sudden minnow]

we have the set A

R the equiv relation

A/R should be the set of equivalence classes i.e. partitions

so it is saying every equivalence relation is the union of the cartesian products of the partitions it induces

I guess

[desert spear]

I want to verify if I have done correctly the Shannon expansion for the if and else normal form, The given problem is ~p -> (q -> ~r) ```
A = ~p -> (q -> ~r).
A = {p/F} = T -> (q -> ~r).
A = {p/T} = F -> (q -> ~r) = T.

A can be written as A = p ? T ; T -> (q -> ~r).

Now let's assume A^1 = T -> (q -> ~r).

A^1 = {q/T} = T ->(T -> ~r).
A^1 = {q/F} = T -> (F -> ~r) = T.

A^1 can be written as A^1= q ? T ->(T -> ~r) ; T.
A can be written as = p ? T ; (q -> T ->(T -> ~r) ; T).

Now let's assume A^2 = T ->(T -> ~r).

A^2 = {r/ T} = T -> (T -> F) = F.
A^2 = {r / F} = T -> (T -> T ) = T.

now A can be written as, A = p ? T ; ( q ? (r ? F ; T) ; T). would it be correct if it's the final form of that Shannon expansion?```

[lost pelican]

I need help with discrete

this is the question

How many hexadecimal numbers have 5 digits and have F as the 3rd digit?

i got 16^4

wondering if that is right

[coral raven]

yes

[lost pelican]

ok

so i got 16x16x1x16x16

so was wondering if in that siutation 1 is 0

is it still 16^4

[weary tiger]

Edited: Solved

[warm flower]

Tf is a degree sequence

Oh it's just the set of degrees for this graph

@weary tiger you got any theorems that kick in when you've got all the degrees of vertices in a graph?

[weary tiger]

I can't think of any

Nevermind!

[warm flower]

🤝

[loud steeple]

did I organize the DFA correctly?

[mighty flame]

I have a question: "how many surjections are there from a set with 4 elements to a set with 3 elemnts"

I said 78 since I did 3^4 - 3

(each element has 3 possible mappings) minus the three cases where they all point to the same element

is this correct?

[coral raven]

no

what if you have, ok so

set with four elements, {1, 2, 3, 4}

set with three elements, {a, b, c}

what if f(1) = a, f(2) = a, f(3) = b, f(4) = b?

many more examples

[mighty flame]

ok thanks

[weary tiger]

yo, An Eulerian circuit is a traversal of all the edges of a simple graph once and only once. If every vertex in a eulerian circuit has an even degree, is it possible to have any cut edges?

[warm flower]

Well if there's a cut edge, then you're left with 2 vertices of odd degree

That gives you a eulerian tour

So from there, check if a eulerian tour is always connected, and if not is that case possible with what you know

[weary tiger]

If we want to build a committee of 5 people out of 7 men and 9 women, where we must have at least 1 woman, why can't we do C(9,1) * C(15,4)?

I know this overcounts, but what does it overcount?

We are first picking a woman so that we are guaranteed at least one, then 4 more people out of anyone left.

[weary tiger]

<@&286206848099549185>

[haughty garden]

You shouldn’t distinguish between choosing the woman first and then second. You first choose the woman (say A) and then the remaining people. But this is counted differently to choosing one other woman, and then A with the remaining 4 people. So you overcount the same combination of people this way

[rancid loom]

Suppose it selects women A in C(9,1) and suppose like women B in C(15,4)
In another combination it can select Women B in C(9,1) and Women A in C(15,4)
Above two are overlapping combinations

[weary tiger]

That would imply we should divide by 2, but that doesn't give us the right answer

Or.. maybe.. we should divide by 2 only in cases where a woman is selected in C(15,4)?

[rancid loom]

Umm it was a rough sketch, more men or women may be selected more than once

[haughty garden]

You don’t know how many women were chosen

All you know is that at least one is chosen

[weary tiger]

I don't think I understand this explanation

[warm flower]

So for any committee with n women, we're counting that n times

[weary tiger]

Specifically the part where you say it's counted differently onwards

[warm flower]

Because for any of those women, they could be the one you chose to be the required one, but we don't care about that

[covert bolt]

Hi I dont understand the solution for 4a and b. In particular, I cannot seem to understand the graph suggested in 4a, along with ig the whole reasoning in 4b

[warm flower]

So it's the product from i = 0 to 4 of:
9C(4 - i) x 6Ci/(i + 1)

I think

[warm flower]

4a is just K3 with a random vertex floating in space

[muted palm]

obvious any selection of 5 women satisfies the criteria

then let 5 random women be labelled with integers 1,2,3,4,5, any of the 5 of them could be "the first woman you choose"

so for all valid arrangement of 5 people you count each distinct combination w times, where w represents the number of women in that combination

[haughty garden]

The moral of the story is that what you’ve done is you’ve singled out a woman to be chosen first and this affects how the rest of your group is chosen. By counting the number of ways of choosing the remaining committee, you’ve placed an inherent ordering on the way that you’ve selected the committee (one woman first, the remaining group later). So, if the woman were to be chosen later, this acts differently to if they were chosen first

[covert bolt]

the whole thing still counts as a simple graph?

[warm flower]

Yea simple just means no loops or parallel edges

[covert bolt]

o wait it didnt say it has to be connected

ooo

[haughty garden]

So effectively, A | B, C, D, E is different to B | A, C, D, E when they really are the same committee

[covert bolt]

ok then I think I can understand 4b

[weary tiger]

Alright thanks everyone I got it now 🙂

[warm flower]

4b is just catching edge cases in your induction I think, but the 4a example maybe makes it easier to spot

[muted palm]

connected* :p

[covert bolt]

I dont really understand the first part of the solution for 5

[covert bolt]

oops

[muted palm]

starting with the claim "there exists a girl A rated worst by at most n-2 boys"

proof by contradiction: suppose the claim is false. i.e. "no girls are rated worst by at most n-2 boys", equivalently "every girl is rated worst by more than n-2 boys", equivalently "every girl is rated worst by at least (n-2)+1 = n-1 boys"

then since every boy can only rate a girl as their lowest preference, there exists at least (n-1) * n boys

however, (n-1) * n = n^2-n > n when n > 2, so we need more boys than we have for this to be feasible, contradiction.

therefore our claim "there exists a girl A rated worst by at most n-2 boys" is true

[covert bolt]

idk the n * (n-1) doe

[muted palm]

you have n girls each rated worst by at least n-1 boys

so you need at least n * (n-1) boys

[covert bolt]

I still dont really get it

[muted palm]

imo the hard part is coming up with the argument

the proof itself you should read through a few times and eventually figure out why it holds

it's kinda hard to figure out which part you're stuck on if you can't clarify

[covert bolt]

"then since every boy can only rate a girl as their lowest preference, there exists at least (n-1) * n boys" in particular

I dont really understand how it results in n * (n-1) boys

[muted palm]

ok, so in the supposition you have n girls, each rated lowest by n-1 boys

and any individual boy can only rate 1 girl as the lowest

so for girl A you have at least n-1 boys rated as the lowest, girl B you have at least n-1 boys rated as the lowest, ...

by the condition that any boy can only rate 1 girl as the lowest, the sets {boys who voted girl A as the lowest} and {boys who voted girl B as the lowest} are distinct, because if a boy voted girl A as their lowest preference, they cannot also vote B as their lowest preference

that is, the at least n-1 + n-1 = 2(n-1) lowest ratings girl A and girl B received must be from at least 2(n-1) different boys

this extends to all n girls, so the least possible amount of (n-1) + (n-1) + ... [n times] = n * (n-1) lowest ratings all the girls received must be from at least n * (n-1) different boys

so you must have at least n * (n-1) different boys

[covert bolt]

OH

omg

bruhh

ty

then n-2 was used because the smallest n to consider was 3

right

[muted palm]

eh, coming up with that argument doesn't seem easy
idk how long i would have to try random ideas before testing "most lowest ratings everybody can receive"

then again this proof is the first time i ever looked at dating preferences mathematically so maybe it's easier for you if you're familiar with the material ¯_(ツ)_/¯

[covert bolt]

uh Im also not 💀

thats why Im here

Im doing opencourseware by MIT

[weary tiger]

I am not following

[warm flower]

Is a eulerian tour always connected

[solemn zephyr]

Anyone has a clue

On how to prove this

https://media.discordapp.net/attachments/1037437095008030782/1047249326457495612/unknown.png

[warm flower]

Ik (j k)(n - j k) is a thing but I'm forgetting what it is rn

Oh they're equal, yea

[solemn zephyr]

@warm flower so do you know

[warm flower]

I'd need to sit down and work through it

[mighty flame]

So i read this answer on math overflow

but I was wondering

since there are only 1 of each rank/kind

why isn't it 13C1 * 12C1 * 11C1

when it comes to selecting the values

since you want y and z to have different ranks/kinds

[coral parcel]

That would be right if you care about which order the two singles appear in.

But 5-5-5-9-7 is the same hand as 5-5-5-7-9, so you don't want to count it twice.

[mighty flame]

🤦🏿‍♂️

thank you so much

clears it up a lot LOL

[weary tiger]

Yes'

A eulerian tour will always be connected, and each vertex will have an even number of edges

or an even degree #'

[warm flower]

A tour is with a G where exactly 2 vertices have odd degree, right

[weary tiger]

Oh what

I was taught euler tour = euler circuit

"Euler tour, in an undirected graph is a cycle that uses each edge exactly once."

[warm flower]

Well there's two possible G that can do that

Where |v c V: deg(v) is odd| c {0, 2}

[weary tiger]

Feel like this a bit over my head, I don't know what you just wrote

[weary tiger]

can you explain this like I am 5 years old

[warm flower]

2 types of graphs that have eulerian tours - One with no odd-degree vertices, and one with exactly 2

When you remove an edge from the former, you should get the latter

[weary tiger]

So a eulerian tour is not the exact same thing as a eulerian circuit?

I may have been misinformed or misunderstood information that was presented to me if so

From my courses, an undirected graph with two odd degree vertices is a eulerian path

[coral parcel]

The terminology is not completely fixed. Some speak about Eulerian "circuits" and "trails", others about Eulerian "cycles" and "path". It doesn't seem to be unambiguous whether "tour" ought to mean the closed or two-ended kind; I would avoid that word.

[weary tiger]

Euler paths don't need to return back to the original vertex @warm flower. If we cut an edge in a euler circuit we will get a euler path, but we will not get back a euler circuit... but that doesn't say much about whether or not a cut edge can exist in a euler circuit

[warm flower]

Well if the euler path is connected, then there's no cut edge in the circuit, right?

[weary tiger]

That is true yeah. Alright, solved! Thank you so much @warm flower

[indigo nebula]

I have an encryption function defined as, $$f(x) = { \ y \ : \ |7x - 4| \equiv y \ (mod \ 26) $$ How can I obtain its decryption function in such an explicit way if I can?

[vital dew]

Hamnom Gerpthood

[coral parcel]

That's a pretty strange function -- are you sure those absolute-value signs are supposed to be there? What is the domain? What does the variable y in the set builder range over?

[mighty flame]

ik a euler circuit has to use every edge exactly once

but does it have to use every vertex at least once?

[coral parcel]

I don't think that's usually required, but it only makes a difference if the graph has one or more isolated vertices anyway.

[mighty flame]

ok thanks

[void crypt]

anyone here familiar with hamiltonian decomposition?

[lapis mulch]

do you guys have any worksheets for relations and functions? (university-level)

[indigo nebula]

My mistake. I did not mean a set builder notation. Yes, it is in absolute value. You pick a value for x and put it in the absolute value term and find its modular equivalence as output.

[coral parcel]

Still, what is the domain?

The absolute-value signs only make a difference if x can be zero or negative. But if it can, then 0 and 16 both encrypt to 4, so there'd be no sure way to decrypt that.

[indigo nebula]

It is positive integers where each letter is designated by a number.

[indigo nebula]

Yeah, I agree.

[frigid wave]

hey guys

can someone help me with some homework?

i have to do it for tomorrow, but i cant manage to do it

its quite important so if someone could help please

[warm flower]

I can't read 3 but I presume 2 is "Is R an equivalence relation, and if it is what are the classes?"

[frigid wave]

yes

i translate now 3

in the second i have to demostrate that when you choose n+1 numbers there is at least 2 numbers that the difference is less than or equal to 2

[warm flower]

Okay

Well 2 is easy, 3 I'd probably need to think about

[frigid wave]

take your time mate

[warm flower]

For 2, what do you need for an equivalence relation?

[frigid wave]

like demostrate that its simetric, transitive and reflexive

i think i have 3, so dw about it

just try to get the second one

[sudden minnow]

fairly difficult question

[sudden minnow]

think about when this relation is satisfied

when x = y is obvious, but if x =/= y then we can divide both sides by x-y

[frigid wave]

yeah

but when we arrive to x=1-y we cant do mroe

[sudden minnow]

nop we can

!

so our relation is

xRy if and only if x=y or x+y = 1

@frigid wave you cool so far?

[frigid wave]

so we demostrate that they arent

cause if x=1-y -> x != y

right?

[sudden minnow]

they arent what?

[frigid wave]

nothing

like

my brain just bugged xd

thanks

[sudden minnow]

so we have this

now you just check symmetry reflexivity transitivity

first 2 are easy

if x=y then y=x

if x+y = 1 then y+x =1

either way we have it

[frigid wave]

okey

[sudden minnow]

we clearly have reflexivity because xRx

as x=x

transitivity requires a bit more work

there are multiple possibilities

so, suppose xRy and yRz

we could have, say, x=y and y+z=1, do we have xRz in this case

yes because x+z = 1

there are other cases, I think you can fill in the rest

[frigid wave]

yeah

with thats enought

enough

thanks you a lot man

[sudden minnow]

np

[bleak steppe]

i actually dont know how to fill the rest :c

[warm flower]

We don't have symmetry, right?

[sudden minnow]

why not

[warm flower]

Nvm I'm dumb, - threw me off

[frigid wave]

el menos rallao:

[bleak steppe]

ajjaj

xD

[warm flower]

But x^2 - x = y^2 - y is a lot easier to think about

[frigid wave]

maybe

idk what can be the fastest way

but both of them are correct so thank both you

[mint raft]

I have another question. what does it means with the "finding their classes"

[frigid wave]

@sudden minnow @warm flower , i have realized the havent done the part of finding the classes

do you know how to do it?

[sudden minnow]

suppose we have some integer x

I want to know what are related to x

xRy iff x=y or x+y=1

so x is related to x

and 1-x is related to x

and nothing else can be related to x

[warm flower]

And that's how I'd probably write it because you're in Z so infinite classes

[sudden minnow]

so the equivalence class of, say, 4 will be {4, -3}

[frigid wave]

ahh

okey thanks

[sudden minnow]

np

[solemn zephyr]

How many permutations on set {1,…,2n} is there, such that no even number appears into itself?

https://media.discordapp.net/attachments/905285721886187580/1051933888026513428/tiaw.png

is this correct?

[hushed cloud]

@sudden minnow hi im just wondering if you could help me with some proofs if youre good with them

or anyone please ;-;

[sudden minnow]

please don't ping me to ask a question

ask it wherever channel is appropriate, whoever wants to/can help will help

[chrome tree]

I am really confused

what is going on here?

I have to give a formal proof, and the answer is written, but I do not understand the answer

[hushed comet]

It's written up there

[calm hearth]

i'm kind of confused. what actually happens if u input b in q1?

[frigid wave]

is this correct?

[desert spear]

would it be correct if do that to prove that following problem with help of natural deduction. ⊢ p →(q →(p ∨ r)) ```

1. p assumption 
   

2. p v r [ vi 1] 
   

3.       q assumption 
   

4. q -> ( p v r) [ -> i 3 , 2] 
   

5. p -> ( q -> ( p v r )) [ -> i 4, 1] ```

[coral parcel]

Then the machine reject no matter what else happens afterwards. Oops, sorry, missed that it was non-deterministic. Getting to state q1 with b as the next symbol simply doesn't help you to make an accepting path through the automaton -- there might be other paths where you're in a different state than q1 when you're reading that b.

[wet flame]

is this num 3?

3 or 5 hmm

does order not matter here? so it wouldnt be a permutation?

[coral parcel]

4 looks right to me.

But so does 6 and 7.

And, not to give everything away, at least one more.

[elder berry]

7 has a +, no?

[coral parcel]

Ah, well spotted. I retract 7.

[wet flame]

there is one more still?

hmm ty though i think working backwards will help

[round wadi]

hi

so i have this question The sequence ⟨𝐵, 𝐶,𝐷, 𝐴, 𝐶, 𝐸, 𝐴⟩ is a walk in a graph. Which terms apply to the walk – open, closed, trail, circuit, path, cycle? Explain. and i believe that it is a an open walk and a trail because no edge is repeated it wouldnt be a path because the vertex A,C is repeated twice am i correct?

[gray sun]

¬∀x(P(x)) -> ¬P(x)
Is this correct?

[weary tiger]

(Exists)¬P(x) = ¬∀x(P(x))

Hmm, chatgpt is telling me that given a connected undirected graph whose combined vertex degrees sum up to 100, the exact number of vertices is 51. It's stating that this must be true for trees as well

[coral raven]

chatgpt is a total fabricator

it is perfectly happy to make absolutely anything up so long as it sounds plausible

[lusty flame]

can someone help

[calm hearth]

I don't get what you mean. Can you elaborate?

My question is that for example if you input the string ab,there are two possibilities: it either remains in q0 or after processing a it moves to q1. What happens after that? Does the fact that q1 does not accept b mean the first possibility is what happens?

I guess I'm confusing non deterministic to mean something like a random process?

[haughty garden]

The string is not accepted because the “run” of the string on your NFA terminates prematurely

If you process any string on an automaton where there is no valid move, then the string is simply rejected by the automaton

The non-determinism comes from the fact that you can branch out to multiple states at once by processing one input on a state. There is no single intermediate state but rather an input-state pair can have multiple successors

[wet flame]

so for this one

'Only m of the n fisherman caught fish and recieve 1 point on the leaderboard.' this would be a combination right?

[haughty garden]

Correct

[wet flame]

so it would be a combination * permutation

[haughty garden]

Yep looks like it

[wet flame]

permutation for the second part (k of the sucessful fisherman are ranked...)

alright so that rules out 1, 3,4,5,6,7,8 and 9?

well actually maybe not be 8 and 9 and 4

with the same reasoning it could also be 6 and 4 aswell since 4, 6 and 9 are equivalent

so it could be 2,4,6,8,9,10

idk

would a correct answer be nCm * mPk?

this gives $\frac{n!}{(n-m)!(m-k)!}$

[vital dew]

yotta

[wet flame]

none of the answers are the same as this

[calm hearth]

Thanks, I get it now

[wet flame]

anyone else got a clue?

[distant glade]

my buddy eric told me the same thing, must be true

[spring elk]

what do they mean by this claim?

i can have 3 nodes connected but that doesnt mean i can partition them into strongly connected components

[unreal stump]

Well there can be connections between 2 strongly connected components

It isn't a clean partition like dividing an undirected graph into connected components

1 -> 2 <- 3

This has 3 strongly connected components

Each node is a component

[spring elk]

does strongly connected not imply if i can reach node B from node A then i can also do it vice versa?

[unreal stump]

Well it does

You can reach 2 from 1 but not 1 from 2 here

[spring elk]

then which is the strongly connected component? oh u mean separating it into just 1, 2, and 3

?

so i have 3 partitions?

[unreal stump]

Yea

The algorithm here to find the components will be slightly more complex than the undirected version

[spring elk]

ahh i see.. this makes sense now thanks!

[unreal stump]

Try to think of what the change will be.(Assuming you know the regular algo for undirected case)

[spring elk]

for undirected graphs if i had {v, w} id look at all neighbours of v (so the possible w's)

process would repeat

[unreal stump]

So BFS?

[spring elk]

that depends on the way i access the list

LIFO or FIFO. I think thats the only difference right?

[unreal stump]

So That corresponds to DFS vs BFS,right?

[spring elk]

yes

[unreal stump]

Ok so what would be the change here

[spring elk]

id look at if there exists arc (v, w)?

[spring elk]

in this case though only 1->2 would be possible if i start from 1

cz arc (2, 3) doesnt exist

[unreal stump]

So you just check if w is reachable from v?(That's sufficient in the undirected case)

[spring elk]

yes. why would it not be sufficient for directed? i can think about it for a minute actually

[unreal stump]

||What if v is not reachable from w||

[spring elk]

what would the issue be? do u mean i should only count nodes w, v if there exists a strongly connected path between them?

[unreal stump]

Yea we are dividing it into strongly connected components

[spring elk]

ahhh yeah i see.. so to find all the partitions of storngly connected components my algorithm would be sth like this.

at first i was thinking u meant which algorithm will be used to find all reachable nodes in a directed path my bad

[unreal stump]

It's ok

[spring elk]

thanks for the help!

[unreal stump]

np

[spring elk]

i actually have 1 more question

this isnt the only strongly connected partition right?

since i can just have each node separated

a partition of each node by itself

[unreal stump]

Well do you consider each node to a partition when considered partitions in undirected graphs

Do you know what quotienting by an equivalence relation is?

[spring elk]

i know what equivalence relation is, havent heard about the term quotienting by an equivalence relation

ahh nvm i see what u mean. there exists a->b so we need to find a way to reach a from b

[unreal stump]

Yea

[spring elk]

cz of symmetry property

actually.. not symmetry because symmetry says if there exists a->b there should be a b->a

[unreal stump]

So if R is a relation on A,
A/R is the set of partitions induced by R

[spring elk]

so in this case it would be [a] (or b or e), [f] (or g), [c] (or d or h)?

by this i mean

i am not sure if this is what ua re referring to though

[unreal stump]

Yea this

Just pretend I didn't say quotient,no relevancd here

So a strongly connected component is literally just a partition under the equivalence R where
aRb iff a is reachable from b and vice versa

As in you start with a node

You try to reach as many nodes as possible

[spring elk]

and in the end still be possible to return back to the same node

[unreal stump]

Yea

[spring elk]

got it

thanks again

[calm hearth]

In this proof for myhill nerode, is there some reason why the initial state is defined to be so? R_L is the relation following from distinguishing extensions

[vapid notch]

i have a qusetion
The product of a rational number and an irrational number is:
the answer should be irrational number
but if 0 and the roof of 2 it gives me 0

[tight hound]

The product of a rational number and an irrational number is not always irrational, as demonstrated by the counterexample you produced.

If x is rational and y is irrational then xy is irrational if and only if x=/=0

[lusty fern]

when talking about cliques

in graph theory

how does a clique of size 1 make sense?

since a clique is a set where any 2 nodes is adjacent, but there's no node for the 1 node to be adjacent to

[haughty garden]

All vertices are cliques of size 1

You can think of each vertex as its own complete graph

So you can tell that any graph will have cliques of size 1 (it is rather boring to talk about such cliques)

[lusty fern]

doesn't it go against the actual definition though?

"any 2 are adjacent"

maybe it's just a boring base case?

[haughty garden]

The equivalent definition is that it is a complete subgraph of G, and any singleton vertex certainly fits that description

It is a subgraph that is also connected to any other vertex in the subgraph (namely itself)

[vital dew]

Fate

[solemn zephyr]

can anyone see if it is correct?

[chrome tree]

I need help with this guys

[desert spear]

Would it be correct if I do so for the following linear temporal logic. 🙂

[woeful idol]

Can someone elaborate this?

https://cdn.discordapp.com/attachments/1016392191616237580/1053022718607491154/image.png

[woeful idol]

Nvm this only applies to 1 to 1 functions and x^2 is not 1-1

[weary tiger]

How many ways are there to assign three jobs to five employees if each employee can be given more than one job?

What does 3^5 overcount in this case?

[rugged patrol]

do the case where you give each job to a different employee, then give 2 jobs to one employee and 1 job to another employee, and do the case where you give all the jobs to one employee, and then sum all

[weary tiger]

What?

The jobs can repeat

[rugged patrol]

imagine you have 2 jobs and two employees

you can give each one of them 1 job (2 ways)

or you can give one of them the two jobs (2 ways)

so in total you have 4 ways to assign the jobs

[weary tiger]

Or you could look at it this way: you have 2 choices for each job: employee 1 and employee 2

And 2 jobs, so 2^2

[rugged patrol]

yes that also works

[weary tiger]

Yeah, but it doesn't work for the above case.

Because 3^5

Is overcounting it

[rugged patrol]

in your example it should be 5^3

[weary tiger]

Yeah, but what is 3^5 counting then?

[rugged patrol]

the case where you have 3 employees and 5 jobs

[weary tiger]

Why can't you think of it as a tuple of the set of jobs for each employee?

To get 3^5

[elder berry]

It's totally fine to think of it as a tuple, but remember you are assigning 5 jobs to 3 employees, so you have the following tuple
(_, _, _) and each blank can be filled with one of the 5 jobs

[weary tiger]

No we aren't

[elder berry]

Five jobs for the first employee, multiplied by five jobs for the second employee, etc, is 5*5*5 = 5^3

[elder berry]

Huh?

[weary tiger]

We're assigning 3 jobs to 5 employees.

[elder berry]

Oh, reread the question again, an employee can have more than 1 job.
For some reason I'd think that 3^5 would undercount

[weary tiger]

What do you think the answer to the original question is?

[rugged patrol]

5^3

[weary tiger]

But 3^5 > 5^3, you know that right 😄

[rugged patrol]

it would be 5^3 if the jobs are distinct if there is no distinction in the jobs you can't do it this way

[weary tiger]

The jobs are distinct, but I'm asking why is 3^5 the wrong answer?

[elder berry]

Just to clarify, the question is how many ways to take (for example) the first job and give it to an employee, and then take the second job and again give it to one employee, and same for the third?

[weary tiger]

The question is as follows

[elder berry]

because the question can be interpreted many ways, I feel like this flows most naturally

[weary tiger]

How many ways are there to assign three jobs to five employees if each employee can be given more than one job?

(there is no additional information given)

[elder berry]

Alright, each job will have one of the five employees working on it, and the jobs are independent, meaning that you can take any of the five employees for the first one (5), any of the five for the second one (5), and five again for the last task.

Can you motivate your idea why 3^5 should work?

[gray swift]

can someone help me with matlab wor

[elder berry]

3^5 is the same as saying 3*3*3*3*3 which would translate (in the context of this problem) take each employee and give them one of the jobs

[weary tiger]

Yes, so for each employee, they have 3 choices: job 1 or job 2 or job 3

And there are 5 employees, so 3^5

[elder berry]

multiple employees mustn't have the same job

[weary tiger]

popping into ask - given a connected undirected graph with a combined vertex degree of 100, the minimum number of vertices is 50, the maximum is 51?

[weary tiger]

What? That's not true

50 in the case of a cycle, 51 for an acyclic graph

[elder berry]

That is how I am interpreting the question.
You want to assign three jobs, as in, take a singular employee that will do the job.

for example, for three distinct jobs J1, J2, J3; and five distinct employees E1, E2, E3, E4, E5; it is ok to place the employees like this
J1 : E1
J2: E4
J3: E4
(job 1 is done by employee 1, etc)
and not
J1 : E1, E2
J2: E2
J3: E5
(since we assigned the same job (J1) to multiple employees)

[weary tiger]

If that were true, wouldn't your 5^3 be incorrect...?

[elder berry]

Nope, because I am assigning a singular employee to a designated task (the 5^3 answer)
while the 3^5 answer is assigning a singular job for each employee

[weary tiger]

I'm not sure if I follow, a designated task could be all 3 jobs then?

[elder berry]

task = job
I want to assign one of the employees for the first job (I can choose any of the five)
I want to assign one of the employees for the second job (I can again choose any of the five since a singular employee can work multiple jobs)
same for third

yup, so each J1 and J2 can both be worked by E1 for example

[weary tiger]

Then why do you say "and not" here?

[elder berry]

it is not ok to place two employees for a singular job if we want to assign one job to one employee

[elder berry]

combined vertex degree = sum of degrees of all vertices?

[weary tiger]

yea

[weary tiger]

We said one employee can have more than one job..

[elder berry]

consider putting 101 vertices in a line

[weary tiger]

100 edges

[elder berry]

and? one employee can also not have any job, it's all about the wording

[weary tiger]

99*2 degrees + 2 ends= Degree of 200 for a connected tree with 101 vertices.

[weary tiger]

I'm so confused, you said we can't have that, and then you said we can

[elder berry]

Hmm, to summarize what I meant, is to put E1, E2, E3, E4, E5 in the tuple (_, _, _). (Repetition is ok)
The tuple (_, _, _) signifies
(name of employee who will do job 1, name of employee who will do job 2, name of employee who will do job 3)
and some valid tuples are
(E1, E2, E3) (E1, E1, E1) (E2, E5, E5) but an invalid tuple (E1 and E2, E3, E4)

[weary tiger]

Oh ok, so basically two people can't be working the same job, we can only pick a single person for that job

[elder berry]

Yup!

[elder berry]

mbad, had a brain fart, let me try it again

[weary tiger]

Trying to look at complete graphs

[elder berry]

How'd you get 51 as a maximum?

oh 2*49 + 1 + 1

but I feel like the minimum should be waaay down

[weary tiger]

So 3^5 will count the number of ways we choose to give a job to five employees employee

[elder berry]

precisely that, yes

[weary tiger]

Yeah complete graphs might show me the minimum should be much less

Instead of the number of ways we can choose each of the 5 employees for each of the three jobs

Alright thanks I got it I think, not sure why that was so difficult

[elder berry]

No worries

[elder berry]

Look at K8

[haughty garden]

Note that a complete graph has n(n - 1)/2 edges and you can invoke the handshaking lemma

[weary tiger]

Yeah I was just writing that

So the complete graph would probably point me towards the minimum

A star graph would be the maximum? I.e One vertex in the center, 50 vertices sorrounding and connected to the central vertex

central vertex = degree 50.... 50 radial vertices = degree 1

= 51 vertices

[haughty garden]

Well, if your degree sum is 100, then you have exactly 50 edges via the handshaking lemma. You can imagine that each edge pairs up two vertices so you could probably count that way

[elder berry]

Oh the degree sum is 100 right, so to obtain the minimum would be looking at the complete graph ||K11|| and removing the required number of edges as a simple construction

[weary tiger]

I was thinking K8, (handshaking lemma=100 degree-> 50 edges.) = n(n-1) edges= K8 = 56 edges

[haughty garden]

Ah my construction doesn’t work because I forgot that you require the graph to be connected

I was considering 2-cycle partitions of the graph

[elder berry]

n(n-1)/2 *

[haughty garden]

51 is right for the maximum

[weary tiger]

Oh I see right

[haughty garden]

Just draw a line graph

You require at most 51 vertices to connect 50 edges

For the minimum, note that 10 vertices give you a maximum degree sum of 90 (in a complete graph). So you can connect one more vertex to 5 vertices

Should be 11?

[elder berry]

yup

from K11 remove 5 edges

[haughty garden]

Oh wait not degree sum

But you get what I mean

Take K_{10} and add one more vertex

[shadow tusk]

Hey, could anyone help with graphs and their parameters, I have Kn properties correctly, I think, but I have trouble with Ks,t:

[fallen prawn]

can anyone comfirm if this is right?

[solemn zephyr]

There is a class c, such that every teen hates it

negation is

switching symbols

no

incorrect

incorrect

VcEt

VcEt: -(the predicate)

For every class there exists a teen such that teenager doesnt hate the class

I think

let's ask someone else that, as far as I'm concerned, I'm right but maybe i made a mistake

[haughty garden]

Try drawing a few examples up. Keep in mind that these are complete and bipartite; how many (minimally) colours would you require so that no two adjacent vertices share the same colour? This gives you the chromatic number

[fallen prawn]

so you think it's supposed to be VcEt? i thought so too but i wasn't sure which one

[solemn zephyr]

yes

[gloomy mesa]

Hey guys, can someone please help me with a catalan numbers path problem? I need to find the number of paths of 12 steps from (0,0) to (6,6) (going only up or right - total of 6 in each direction) that don't go above y = x and touch y = x at least once.

I know that without the "and" it's just the catalan number of 6, but don't know how to calculate the paths that touch y = x 😦

[solemn zephyr]

@gloomy mesaTo find the number of paths of 12 steps from (0,0) to (6,6) (going only up or right, a total of 6 in each direction) that don't go above the line y = x and touch y = x at least once, we can use Catalan numbers. Catalan numbers are defined using the recursion C(n) = (4n - 2) C(n-1) / (n + 1). The first few Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, etc.

To count the number of paths from (0,0) to (6,6) below the line y = x, we can use C(6) = 132. However, this count includes paths that never cross the line y = x. We want to count only paths that cross the line y = x at least once.

Therefore, we can subtract the number of paths that stay below the line y = x for the entire journey. These paths are counted using C(5) = 14. So, the paths that stay below the line y = x but cross it at least once are given by the difference C(6) - C(5) = 132 - 14 = 118.

Therefore, the number of paths from (0,0) to (6,6) that stay below the line y = x and cross it at least once is 118.

[gloomy mesa]

The thing I don't understand is - why C(5)? Isn't the definition of C(5) the number of all paths from (0,0) to (5,5) that don't go above y = x - including those who touch y = x?

[solemn zephyr]

wait no

I tried it myself, do you have the correct result anywhere?

[gloomy mesa]

yeah it's 90, but using C(5) = 42

so it does work, I just don't understand why

[crystal oyster]

• A function h : A → B I will call funny if the following statement is true: ∀a1, a2 ∈
A if f(a1) = f(a2) then a1 = a2
• A function h : A → B I will call hungry if the following statement is true ∀b ∈
B, ∃a ∈ A, f(a) = b

Prove that if f : X → Y and g : Y → Z are both hungry then so is g ◦ f

Im lost on where to start here

anyone know what to do?

[solemn zephyr]

What the hell

Is hungry

Give me a definition

Of function being hungry

[sudden minnow]

it is literally given in his question?

[haughty garden]

It seems like a hungry function is also the same as a surjective function by that definition

So it just amounts to showing that a composition of surjective functions is surjective

[solemn zephyr]

Prove by contradiction

[haughty garden]

Let f : X -> Y and g : Y -> Z be hungry functions. By the hungry-ness of f, any y in Y can be mapped by some x in X; that is, f(x) = y. And similarly, any z in Z can be mapped by some f(x) which is an element of Y. Therefore, any z in Z has a corresponding element f(x), which has a corresponding element x in X. Thus, the composition of hungry functions is also hungry

[weary tiger]

A computer system produces a randomly created PIN number of length 4 digits, where each
digit is selected randomly from 0, 1, 2, ..., 9. Repeated digits in the PIN number are allowed.
What is the expected number of 0’s in the PIN number? Answer(4/10) [Is this correct?]
If students stand in line to receive their PIN numbers, how many students do we expect to serve before
handing out a PIN number that starts with a 00? Answer: 100 students.

4/10 because 1/10 for each slot in the 4 pin numbers -> linearity of expectation is 1/10*4, right?

[lament niche]

I posted this under math help and forgor it was for pre-university questions oops.
How/why were these cases chosen? to prove an inequality

[proud needle]

@lament niche im p sure x < -1 was chosen cuz it was looking at the cases where the values inside both absolute values will be negative

and if x < -1, |x - 1| = -(x-1) cuz both will be positive

|x + 1| < 0 as well right, cuz -1 isn't included in x < -1. so |x+1| = -(x+1)

for the second case, they were looking at cases where x-1 is negative but x+1 is positive

choose any x in the interval of -1<=x<=1. 2 >= x+1 >= 0 and -2 <= x -1 <= 0 right, so based on this, we know that |x+1| = x+1 and |x-1| = -(x-1)

for the third case

x-1 and x+1 will always be positive

and then its best to double check that all cases include the domain of R

and it does!

[lament niche]

ahhh makes sense, thanks!!!

[proud needle]

Yepp

[gloomy mesa]

@solemn zephyr thanks for trying to help me mate🙏 I appreciate the effort 🙂

I'll wait till the official solution will be published...

[weary tiger]

What is this formula called?
P(Error Detected) = P(Error detected | No error) * P(No error) + P(Error detected | Error) * P(Error).

[fair widget]

law of total probability

[proud needle]

anyone want to read "Graph Theory With Applications by Bondy Murty" with me

[weary tiger]

So much text sorry

[haughty garden]

Diestel’s text is op for graph theory

[weary tiger]

Can I get some pointers on how I would do this problem?

[haughty garden]

It’s a bit advanced though

[proud needle]

Do you think it is good for beginners? I am tryna learn atleast introductory graph theory in 3 months

[proud needle]

Oh okay, what topics are included in it?

[haughty garden]

Let me check, I have it lying around my bookshelf

Matching, covering and packing, connectivity, planarity, colouring, flow network, extremal graph theory, infinite graphs, Ramseyan graph theory, Hamiltonian cycles, random graphs, graph minors

Those are all the chapters to the book

So a first course discrete-esque graph theory course would cover a subset of those topics I think

[proud needle]

For your example, why isn't a dollar given for 1R and 4B

[fair widget]

1R was drawn after 1B

[proud needle]

i don't have any formal introduction to discrete, i just know how to prove a few things here and there and I know a bit abt set theory and combinatorics, is it completely necessary for graph theory

[proud needle]

bruh i can't read lmao

[haughty garden]

It might be worthwhile to pull out the course outline for either the upcoming or previous semester of the course, and see what topics are taught

[proud needle]

graph theory course or discrete math course

[haughty garden]

Graph theory

[proud needle]

im not in uni so is there like a outline i can look at

for a course

[haughty garden]

Oh are you self-studying?

[proud needle]

yeah

[weary tiger]

this is a tough one for me, maybe easy for yall haha

[haughty garden]

Diestel’s text is good for you then imo, the later topics are a bit more geared towards graduate students but with some combinatorics at your disposal, you should be able to follow through with most of the topics

You might have touched some Ramsey theory in combinatorics, you’ll most likely see it again in graph theory

[proud needle]

what combinatorics do you think is necessary? All i know are permutations, combinations, PIE, derangements

[haughty garden]

None officially, you can get away with not having done any combinatorics and still understand graph theory

But it would benefit you to have had some exposure to stuff like Ramsey theory for graph colouring / extremal graph theory

[proud needle]

where do you think i can learn all of that

[haughty garden]

In saying that, you’ll learn it from scratch in Diestel’s text so don’t worry too much if you haven’t had any exposure

[proud needle]

oh okay

thanks!

[haughty garden]

Once you finish Diestel, I highly recommend reading Juknas’ extremal combinatorics text for a more mature understanding of combinatorics

Covers more than just basic counting. You’ll start learning about set systems, graphs (again!), and really cool results such as Erdos-Ko-Rado, Erdos-Szekeres, and some Ramsey theory (again!) in the form of Van Der Waerden’s theorem

[proud needle]

okay tysm

[weary tiger]

Can someone explain to me how "k+1" relates to this if k is red balls

[weary tiger]

Ugh I hate probability

[dry raven]

Anyone got a idea of an online course or something I could look into for discrete? I took it through uni 2 semesters ago but already forgot it all and have to take my operating systems class this next semester so I wanna refresh

[queen zenith]

Hey folks, I'm in need of some help with the Fourier transform and the DFT. Let's say I have a 'n' data points that span over time time length T. I can use the FFT (fast fourier transform) to convert these data points into the frequency domain. However, what I want to do is get the analytical continuous approximation for my original signal x(t). How can I do that given I have the complex FFT data points?

[whole sapphire]

I am stuck with a practice question for Discrete Mathematics. I have figured out I need to use the Ford Fulkerson Algorithm, which I have used before. But somehow on this graph I am stuck.

The capacity on every arc is 1. The flow on the red arcs is 1 and on the green arcs is 0. And I have to use an algorithm (which I assume is the Ford Fulkerson) a few times starting with the given flow. The goal is to find the max-flow and min-cut of D.

I get don't know how to begin with the given flow, usually I begin with all the flows at 0. Can anyone explain how I need to proceed? Thank you so much!

Graph D (weighted and directed): https://imgur.com/a/K3J4Tlg

[rose widget]

I’m not a fan of discrete maths

I tryed to convince my teacher to switch it for the further pure course

So much better I think

Discrete math is like maths for journalists or computer programmers

But we just finished the planarity algorithm in graph therory so not sure if we are behind or not

[haughty garden]

Since green arcs do not contribute to the overall flow of the network, the algorithm will attempt to go through as many red arcs as possible. There will be flow along s->a, s->b, s->e. So now the vertices a, b, and e all have a flow value of 1. If you continue along the red paths, you’ll find that the maximum flow is 3 and this should not be surprising. This tells you that the corresponding minimum cut also has value 3 by the max flow-min cut theorem

[whole sapphire]

Thank you! I will give this a go!

[whole sapphire]

@haughty garden I have indeed followed those paths and i can clearly see the max cut and min value. But now I have the idea I have not used the algorithm properly, because I could do this all in one graph. Am I forgetting something?

[haughty garden]

Ford-Fulkerson finds the maximum flow by choosing an arbitrary path to take, and backtracks to find any other possible paths. In other words, as long as there are still paths available, we will send flow to those paths

[whole sapphire]

@haughty garden Thank you so much! I am 100% sure i understand it correctly now.

[solid quartz]

Hey, i was trying to prove the Erdős–Szekeres theorem using pigeon hole. The book I'm referring to, is using Proof by contradiction and then pigeon hole principle.
here's the statement
Theorem

 Every sequence of n
2 + 1 distinct real numbers contains a subsequence
of length n + 1 that is either strictly increasing, or strictly decreasing

Proof (part of it)

Let a1, a2, . . . , an2+1 be the distinct numbers in the sequence. With term ak
associate the pair (ik, dk) where ik is the length of the longest increasing subsequence
starting at ak, and dk is the length of the longest decreasing sequence starting at
ak.
ASSUME there are no decreasing or increasing subsequences of length n+ 1 (we
give a proof by contradiction). Then ik and dk are both positive integers ≤ n, for
k = 1, 2, . . . , n2 + 1. So there are (by the Product Rule) n
2 possible ordered pairs
(ik, dk). By the Pigeonhole Principle, two of these pairs must be equal

My confusion is By the Pigeonhole Principle, two of these pairs must be equal, how can we say both increasing and decreasing sequence length is same using Pigeon hole principle ?

https://faculty.etsu.edu/gardnerr/2710/notes/4-2.pdf
here's the complete stuff I'm referring

[haughty garden]

You have n^2 + 1 pairs since k is indexed from 1 to n^2 + 1, and each i_k, d_k <= n; therefore, maximally there must be n^2 many ordered pairs (each i_k and d_k have n options independently). But, if there are n^2 + 1 pairs, then two pairs must be identical. This is precisely the pigeonhole principle at play. In other words, there exist indices s, t between 1 and n^2 + 1 such that i_s = i_t and d_s = d_t

[glacial flame]

When calculating choosing behavior, will you always be guaranteed to have an integer at every step if you alternate between multiplying and dividing like this (for nCr): n/1*(n-1)/2*(n-2)/3*...? I feel like you will because when you hit 2, you have multiplied by 2 consecutive numbers, which means one of them must be divisible by 2, when you hit 3 you have multiplied by 3 consecutive numbers, which means one of them must be divisible by 3, etc. It's kind of like a modulo behavior (and/or looking at remainders/divisibility), right?

Basically, for a given divisor d, you have d consecutive numbers multiplied together and mod d has d possible remainders, so one of them MUST be divisible by d, right?

[glacial flame]

There's also the fact that because the largest factor of a number (other than itself) can't be more than it divided by 2, any factor division will "replenish itself by the time you need to divide (for example, dividing by 3 will be replenished by the next 3 numbers before dividing by 6)

[solid quartz]

thank you, i was interpretting it as all pairs will have same increasing and decreasing length like for a1 (k1,k1) etc.. thanks for correcting my thought process :)

[covert bolt]

I dont understand the proof in b

[sonic grail]

is the picture not given?

a cycle of the type they want seems pretty easy to imagine

[whole sapphire]

I am stuck with a practice question for Discrete Mathematics. I have figured out I need to use the Ford Fulkerson Algorithm, which I have used. But somehow I am stuck.

The capacity on every arc is 1. The flow on the red arcs is 1 and on the green arcs is 0. And I have to use an algorithm (which I assume is the Ford Fulkerson) a few times starting with the given flow. The goal is to find the max-flow and min-cut of D. The answer to both should be 5. I managed to 3 for both.

Can anyone explain where I went wrong? Thank you so much!

Graph D (weighted and directed): https://imgur.com/a/K3J4Tlg

My working:
https://imgur.com/a/b3gvX9S

[sonic grail]

exactly so

can you not generalize this for N even and M > 1?

[glacial flame]

It's valid to have nested induction, correct? Like if you have a statement that you want to verify is true $\forall n,m \in \mathbb{N}$, you can apply induction of $m$ inside each step of induction for $n$?

[vital dew]

JJCUBER

[last sigil]

Yeah, sure, but it might be easier to think of fixing one of the variables and inducing on the other

Then vice versa

https://math.stackexchange.com/questions/2891651/proof-by-induction-involving-two-variables

[glacial flame]

I'm having trouble figuring out how I would use that technique for this (assuming it is even applicable/possible); this is a question I made up that I know is true with some informal reasoning (involving cases, modulo/remainder, etc.), but I wanted to try and prove it formally

(this calculates n choose k btw)

I basically wanted to prove that doing a sequential multiply divide pattern for calculating choose will always stay an integer, thus allowing the calculations to be done with integers instead of floating point, etc.

[brave rock]

Hint: this is equivalent to showing that $\prod_{i=1}^k (n+1-i)$ is divisible by a certain number. Can you see what number it might be, and try proving it?

[vital dew]

Boytjie

[glacial flame]

this was my "informal" logic, though I don't know if this is what you're getting at

[glacial flame]

k! ?

[desert spear]

let's assume there is a set of clauses in CNF form. { ~q v r v ~p, p v q, ~p, r} ```

1. ~q v r v ~p premise
2. p v q premise
3. r
   can I get direct r by using resolution line 1 and 2? or I have to eliminate one by one?```

[glacial flame]

p=T q=F r=F makes the conclusion false but the premises true

So you can’t really derive 3.

[desert spear]

well, I am trying to use the resolution?

[glacial flame]

Oh sorry I’m not sure what that is

[desert spear]

nvm

[coral parcel]

Resolution requires that there is exactly one connecting variable -- JJCuber explained why it doesn't work with two, as you're proposing to do.

[covert bolt]

I dont really understand what a tangled graph is

[coral parcel]

First off it's not a standard concept but an ad-hoc definition just for that problem.

What is your problem with the definition in your screenshot?

For every set A of vertices, if |A| <= ceil(n/3), there must be an edge from a vertex in A to a vertex not in A.

[covert bolt]

honestly I still cant visualise it

[coral parcel]

Which part of the definition do you have problems understanding?

[covert bolt]

if there is an edge leaving every set of ceil(n/3) or fewer vertices

[coral parcel]

That's what I paraphrased here.

Which part of that definition (or my praraphrase) do you have problems understanding?

[covert bolt]

does it mean for every arbitrary A the graph changes

[desert spear]

That means I ca not eliminate two variables at a time by using resolution?:)

[coral parcel]

Correct.

[coral parcel]

No, the graph is the same all the time. A is just an arbitrary subset of its vertices.

[muted palm]

might be easier to visualize than you think if you think differently about the restriction, but i wonder if that's one of the questions :p

what's the maximum number of components a tangled graph can have?

[covert bolt]

4?

I dont really know tbh

[covert bolt]

would A be unique

[covert bolt]

nope, not part of the qn

[muted palm]

consider the maximum size of the smallest component then relate to the constraint that every set of vertices of at most size ceil(n/3) must have an edge connecting between a vertex within the set to a vertex outside the set

[coral parcel]

The graph is only called "tangled" if the requirement of the definition is true for all subsets A of the appropriate size.

[covert bolt]

yea but can a vertex in a variation of set A be repeated in another set A?

[coral parcel]

Uhm, sure? If the graph has vertices {1,2,3,4,5,6,7,8,9}, then both of {1,2,3} and {1,2,4} are 3-elements subsets, so there has to be an edge out of {1,2,3} and there has to be an edge out of {1,2,4}.

[covert bolt]

oh

actually what does it mean by "an edge leaving from the set of vertices"

like only 1 edge coming from the set of vertices

[muted palm]

for a graph with n vertices you have to check the condition holds for every valid selection of A

i.e. every possible subset of size up to ceil(n/3)

so there are nC1+nC2+...+nC(ceil(n/3)) subsets for which the restriction holds corresponding to having 1, 2, ...., ceil(n/3) vertices in a valid subset A

[coral parcel]

There must be at least one edge that goes from a vertex in A to a vertex not in A.

[covert bolt]

ohh

[coral parcel]

(I'm not sure if your graphs are directed or not.)

[covert bolt]

undirected

[desert spear]

what would be the result of the resolution if the given clauses are { ~p v t , ~q v r v p}

would it be ~q v r v t

[haughty garden]

Yes

Resolution rule asserts that $\alpha \lor \beta$ and $\lnot \beta \lor \gamma$ resolves to $\alpha \lor \gamma$

[desert spear]

then what would be the result if I perform the resolution those given clauses ( ~p v s v t ), (~p v ~s v ~t). That is how I thought about it, ( ~p v s v t v ~p v ~s v ~t ) since we can resolve only one literal at a time. as we can see that we can resolve s and ~s form those clauses. thus, the result would be = ( ~p v t v ~p v ~t ) = ( ~p v t v ~t). similarly, (~p v ~s v t v ~p v s v ~t ) = ( ~p v t v ~p v ~t ) = ( ~p v t v ~t). thus, we can conclude that by doing the resolution we will get that following result. In that case ( ~p v t v ~t). But I wonder what if we want to remove t instead of s?

[haughty garden]

It won’t matter whether you remove t or s

If you resolve s, you do obtain ~p v t v ~t but this is always valid since any assignment for t makes this statement true

If you resolve t, you obtain ~p v s v ~s which again is always valid

[desert spear]

But as you can see that I have used two steps to get the result. If the first step I resolve s, and the second step I resolve t, then the end result will not be the same. I mean one clause will have t and other clause will not have the s and vice versa

[haughty garden]

When you perform a resolution, you obtain a new clause in CNF which is the result of resolving one literal from two (or more) clauses

While the clauses you obtain are not syntactically the same (one contains s while the other contains t), they have exactly the same semantic definition

[desert spear]

that mean I have to be consistent with the literal I am resolving in that case right?

[haughty garden]

Yes, as long as you’re consistent, you should obtain the same results regardless of which literal you resolve

[desert spear]

yes, I think I got the idea. Thanks for the help. Tomorrow is the exam I almost got the wrong idea about the resolution. thanks for the help. It is literally life saving 🙂

[desert spear]

sorry to interrupt again, if I perform resolution to those clauses ( ~q v p ), (p v ~q v q) the result would be ( ~q, v p ) right?

[glacial flame]

Yes, though without the comma. You can also take note that the second clause is a tautology, so you just get the first clause as your result.

[wheat elbow]

can anyone help me with a graph theory question regarding the handshaking lemma?

[desert spear]

It was there unintentionally, how about this one?s v t , ~s v ~t = t v ~t would it be correct then?

[glacial flame]

It wouldn’t be =/equiv, but it would be a strong implication

Also, you effectively derived a tautology which usually isn’t that helpful

[desert spear]

that means I cann't use the resolution in that case?

[glacial flame]

No you can use resolution, but this is a strong implication behavior, never an equivalency

For resolutions in general

Resolution is a kind of rule of inference, not a law of logic

[desert spear]

but the result wouldn't be correct right? since the result is tautology

[glacial flame]

The result is “correct” but unhelpful

Deriving a tautology when using rules of inference doesn’t really help

It’s like saying any_statement_you_can_think_of => T

[desert spear]

I think so, I thought wrong, I wanted to use the result t v ~t. but t , t v ~t gives t v ~t. it's not helpful at all.

[signal rose]

How do I solve this using Generating functions?

[stray reef]

presumably a good first step would be to rewrite the recurrence relation you have there in terms of the generating function \sum a_n x^n

[whole sapphire]

Can someone check some Graph Theory proofs for me?

[haughty garden]

Might be better to just directly post your question than to ask