discrete-math

[snow cedar]

Wait so like do you mean this: If the edge value of this is 3
A ------- B

You'd turn it into
A --- X --- Y --- B
\ /
\ /
\ /
Z

Oh i did not mean to put a Z

I mean draw an edge from A all the way to B

And there should only be X in between, no Y

[sick grail]

I mean one of these two

I probably shouldn't have mentioned the difference because it's not actually more anoying to do the right one

I was just thinking of the fact you would have a -1 on the number of vertices you're introducing, and didn't realise you only really need to write that '-1' down like

twice

maybe more than twice, point being it's not actually important or annoying

[snow cedar]

Ah I see what you mean

Yeah I can see why after you transform it, G' is eulerian

Because you'd just be using up the intermediary nodes to get from A to B

and potentially the direct edge A to B

So after you get your Eulerian Circuit of G', I'm thinking you take the induced subgraph that doesn't use any of those intermediary nodes

And that subgraph is basically the original graph G?

[sick grail]

yes

not 'potentially' the direct edge because of the number of extra edges that have been introduced

you're guaranteed to use it, since the walk using each edge fe times turns into a walk that uses each of the fe different paths between A and B exactly once

[snow cedar]

Yeah this makes sense to me

That's actually really smart, changing our perspective like that

I had separate question to ask but you might be busy lol, don't want to take up too much of your time

[sick grail]

ask anyway, even if I weren't going to answer someone else could have

[snow cedar]

Okay !

So for this, I had a lemma that said Max degree of a graph G <= 2 iff G is a disjoint union of paths and cycles.

I think for this question, I can at least apply this lemma. Then, rule out the possibility of paths (Because I would argue a path would have a vertex with degree 1 which is not possible since every vertex has even degree).

But I think since this talks about disjoint union, it doesn't fully answer the question

[snow cedar]

Thank u sm for the help! ❤️

[snow cedar]

Actually, I take this back. I misread the inequality. The max degree could be way higher than 2 so I can't apply this lemma

Okay now that I think about it more, I think I can use induction on this

On the number of vertices

[sick grail]

edges works better

[snow cedar]

Actually wait, I think vertices are inconvenient because of this:

When I have n + 1 vertices, and I remove 1 vertex, its neighbours will have their degree go from even to odd. So it's not clear how to apply an induction hypothesis here

[snow cedar]

For induction on edges, is the predicate we are proving like this:
P(E): IF a graph G has an E edges then (If a graph G has every vertex of even degree, then we can partition its edge set into cycles)

In which case, the base case |E| = 1 would be vacuously true?

[sick grail]

E = 0 is minimal, and yeah its essentially vacuous

As a hint, it's better to be doing strong induction

so P(E) would be having E or fewer edges

[snow cedar]

Oo okay!

I think I am supposed to observe some structural pattern after removing an edge

When I go from |E| + 1 edges to |E| edges (by removing an edge)

[sick grail]

this also breaks the degree condition

[snow cedar]

Yeah I was thinking about that

[snow cedar]

Do we have to strategically remove edges until we "fix" the degree condition? I'm unsure how to apply the induction hypothesis

[sick grail]

there's a reasonably natural way to remove a bunch of edges without breaking the degree condition

in particular there's a way to remove either two or zero edges from each vertex

although you'd have to justify that you actually can do it

[snow cedar]

Yeah I'm going to think on that for a bit

All I am thinking is that let's say I remove one edge from A to B. Then I would need to remove an edge for B to (Something Else) and so on

[snow cedar]

my reasoning is def handwavy though lol

[sick grail]

when does that 'so on' end?

[snow cedar]

I mean, until I visually see that each vertex has an even degree but this definitely doesn't sound like a strong justification

I tried an example with K5 the connected graph (And 2 triangle graphs connected, the other one being upside down)

[sick grail]

B hastwo edges removed because it has edges to A and (somethine else) so it keeps even degree, right?

(something else) is the same because of edges to B and (so on)

what condition do you need to make sure you're removing two edges from A?

[snow cedar]

A has to be connected to something different than the vertices we mentioned earlier

[sick grail]

why something different?

what's wrong if (so on) is A?

[snow cedar]

Oh right, technically we can have a 3-length cycle

[sick grail]

or really any length

[snow cedar]

A -- B --- Something Else

And a is (so on).

Then removing these edges would disconnected these vertices

[snow cedar]

yeah, i can see this

[sick grail]

you can remove a 3-cycle from K5 just fine without disconnecting the graph though

[snow cedar]

True, I meant for 3 length cycle example I gave (which is pretty small and overly specific)

But i dont know how the graph looks like when I am doing induction

As you keep deleting edges, is the idea that you're tracing out a cycle?

[sick grail]

yep

so really all you need to do is justify that there is a cycle in the graph, remove it, and apply (strong) induction to partition the remaining edges

[snow cedar]

Yeah that makes sense

wait a second

I was thinking, since G has even degree vertices, can't I just say it has an eulerian circuit (which is a cycle)?

as a way to justify

Actually nevermind

I forgot that eulerian circuit has to visit every edge, so you can't just say you can form an outline cycle out of that

Though going back to the prior discussion, if we delete edges to trace out a cycle, are we addressing the comment in the question that says "(overlapping vertices are allowed)"?

[sick grail]

after we delete the cycle, we may have other edges going through vertices of the cycle

the inductive step will then yield other cycles going through those vertices

aka overlapping vertices

really there's no need to address the comment, it's just saying "by partition the edges we don't mean a vertex is in a single cycle"

[next sail]

Heyy guys! Is this correct?

[obtuse lance]

does the empty string have an even number of 1s

[next sail]

Hmm

I don’t think so

R u referring to Lamda?

[obtuse lance]

sure that's one way of notating it

is 0 an even or odd number

[next sail]

Even?

[obtuse lance]

aha

[next sail]

So yes?

[obtuse lance]

yep - an empty string has zero 1s

[next sail]

Ohhhh

[obtuse lance]

which is an even number

actually taking this in to account might even help you simplify your finite state machine

since you now know the starting state is your accepting state

[next sail]

Hmm

Thanks for ur help

I don’t see how I can simplify it tho

Can u explain more to me?

[obtuse lance]

try putting a starting arrow at either S_2 or S_5 and see what parts of the automaton you can remove

[next sail]

Just updated

Thanks for ur help

I have another quick question

Should S0 in this case accept lamda?

[obtuse lance]

I don't understand what you did, this is what I had in mind

[obtuse lance]

the finite automata here is perfect, checking the regex one sec

[next sail]

omg

i didnt realize this could be made using only 2 states

[obtuse lance]

main thing I'm really seeing is your two paths to S_4 have 0* at the end, but you don't really need it cause it's part of the beginning of "how to get back to S_4". I don't think it hurts you to have it though, but you could maybe even rethink it a bit to put the 0* entirely on its own either between the two or even at the very end of it too.

[obtuse lance]

yeah you're welcome!

[next sail]

okay

i think i'll not include it

i need to go to my prof's office hrs and ask him more abt when lamda is accepted/rejected

have a gn!!

[obtuse lance]

sounds good, yeah you too good night

[snow cedar]

To prove the RHS => LHS, I think I should be using a theorem that says a graph is bipartite iff every cycle is of even length.

Would the approach be to show that every induced cycle is of even length => every non-induced cycle is of even length by some sort of induction?

[dreamy thicket]

Does anyone know how to prove the second question?

[analog tinsel]

idk why I am not able to do this rn through equivalences but you could technically also use a truthtable

[gusty geode]

aaaaaaaa

[analog tinsel]

I would say that the theorem "a graph is bipartite iff every cycle it contains is even" is for left to right.

I G is bipartite then every cycle in G is even thus every induced cycle is even

You could do what you suggested for the other direction.
My first thought would be to assume that we have a bipartite graph G in which every induced cycle is even but there exists a non-induced odd cycle in G, and then find a contradiction

you probably meant left to right , instead of right to left

[rustic elk]

I wanted a huge list of sequential matrix games in game theory (preferably two players) for some research work. If you know of such list please ping me!

[snow cedar]

I mean proving this direction:

If every induced cycle is of even length, then a graph is bipartite

[magic shuttle]

an example we went over in class, im confused by why E would be wrong

next image is how im visualizing it, it ensures that there will be at least one zero, and possibilities where positions may or may not be 0, so i dont get why it's incorrect

if D can be right by handpicking each position to place it in and then leaving the rest up to the chance that out of the 10 options, the rest will be 0, doesnt this work the exact same? i dont really get why handpicking the positions the way they did in D is more correct than this

[oblique pelican]

That visualization shows that it's possible to double count certain strings if you use 4*10^3 since for example 0011 would fall into the first and second categories

D is basically removing the possibility for a 0 to show up in the spots you've already counted for

0___ -> 10^3
_0__ -> 9*10^2 since we remove the possibility of 0 being in the first spot
__0_ -> 9^2*10 same thing for the first two spots
___0 -> 9^3

[magic shuttle]

ohhhh, i understand now
thanks!

[mental plaza]

guys i have a midterm coming up for discrete and i understand most concepts taught so far but its hard for me to get the hang of the laws of equivlance

any suggestions

[inland zenith]

what do you mean by laws of equivalence?

[mental plaza]

simplifyinh expression using the laws of equivalence

[inland zenith]

not sure what you mean, do you have an example?

[mental plaza]

yeah gimme a sec

problems like these where i have to use the laws to simplify expressions

[inland zenith]

oh, okay, I get you

it's just rules you need to memorize, it will help you to do lots of exercises I think

and understand why the rules work

[mental plaza]

yeah you are right

but like i was following this video

and this dude just starts pulling stuff out of nowhere

and it gets confusing

[inland zenith]

can you link the video?

[mental plaza]

https://youtu.be/XMCW6NFLMsg?list=PLTd6ceoshprcTJdg5AI6i2D2gZR5r8_Aw

this one

the later examples i solved for them but i end up getting the wrong answers

[inland zenith]

should you be watching videos like this? boolean algebra is similar to classical propositional logic but you should probably think of them as separate

the question you shared is prop logic right?

[mental plaza]

yes, sorry i was away for a bit.

we also deal with problems like the ones in video

i can show one from my textbook

[river turtle]

cant wait to take discrete next sem

[analog tinsel]

yes, if you have a proof and want it checked feel free to share it

[snow cedar]

Assume every induced cycle has even length.

When an induced cycle is a part of a larger cycle, the rest of the larger cycle has to be divided into another induced cycle. So the length of the larger cycle is (length of first induced Cycle which is even) + (length of Second Induced Cycle which is even) - 2*SharedEdges which is also even.

So all cycles are of even length. So the graph is bipartite

[analog tinsel]

looks fine to me.
(if someone sees something I overlooked please let us know)

[analog tinsel]

idk if you proved in your course that
(a or b) and (c or d)
is equiv to
(a and c) or (a and d) or (b and c) or (b and d)

If you have this rule then you can follow it easily
(similar to (a + b) (c + d) = ac + ad + bc + bd)

did you solve it ?

[novel ore]

in b) are we assuming 0 is in N or not in N

bc a canonical function would just be n mapsto (0, |n|) if n is even and (1, |n|) if n is odd but this doesn't work if N doesn't have 0

nvm that wouldn't work lol even if it did have 0

wait i'm hella stupid what was i thinking 😂

but anyways i feel like we have to assume 0 is in N

[bronze shuttle]

cant you just spam a logic table

i might be wrong tho

2^3=8 cases isnt that bad

[snow cedar]

I think this is something that needs contradiction but I need help.

Here's what I noticed if there are supposedly two perfect matchings:

• In a matching each vertex is only incident to one edge in M1 and one edge in M2.
• If a is is matched with b in M1, a would need to be matched with another vertex in M2 call it c.
• This means in M1, c had to be paired with another vertex call it d.
• But in M2 since a is paired with c, d needs to be paired with something else.

I'm not sure how to reach the contradiction though, I just see that we need to "reassign" new pairings. Any advice?

[bronze shuttle]

it might be possible to induct

because given a root

its children have their own subtrees

[snow cedar]

I'm wondering if there's an alternative concise way to prove the statement

[bronze shuttle]

hmm

[snow cedar]

Like even if I am inducting on the size of the tree, don't I still need to justify "At most one perfect matching"? That's the hard part to me

When the tree is small, like A - B - C there is no perfect matching from what I can see . but thats just a small case

[bronze shuttle]

ok yeah

its probably not right to induct

the best idea is the idea to show contradiction if their exist two perfect matchings

oh i got it

what hapepns if you combine the edges of the perfect matchings

then each node has even degree

each node has even degree -> there must be cycle

so contradiction

[snow cedar]

hmm .. What was your motivation for this? I don't see it immediately

[bronze shuttle]

finding contradiction

you try to show that these two cant coexist

[snow cedar]

Yeah I get that part, i guess it's the next part im having trouble seeing

all i see is that Since the perfect matchings are different, at least one of the vertex will have a different edge connecting to it

[bronze shuttle]

yeah

[snow cedar]

So that vertex would have degree > 1

otherwise it could not have a different edge connecting to it

but i cant connect this to what you said about "then each node has even degree"

[bronze shuttle]

Because think about it

In a perfect matching each node has degree 1

Combine the two matching

Each has degree 2

[velvet lynx]

is a set A with the identity operation an algebraic strutcrue

[brave rock]

Sure, in the universal algebra sense. Pretty boring though.

[royal haven]

Hello, what is the cardinality of a countable infinity cartesian product countable infinite sets

I mean thats |NxNxN...| so |N^N| right?

and thats the same size as real numbers

[short grotto]

Well it is uncountable, as the positive real numbers can be put in obvious 1-1 correspondence with a subset of it

[royal haven]

So countable cartesian product of countable sets is uncountable?

[fossil mural]

yes

[short grotto]

Oh sorry i did not see, yea that is correct

At least if all the countable sets in question are infinite

[fossil mural]

or more precisely if infinitely many of them have more than one element, and none of them are empty

[short grotto]

Right yeah im sorry hehe

[royal haven]

Ok I can show N^|N| is uncountable so then my question really is if I can say |NxNxN...| countable infinity-times is the same as N^|N|

[fossil mural]

i honestly don't know how else you would have defined N^|N|

[short grotto]

Hmm, well |NxNxN...| in that sense is just the cardinality of N^N, which is all the functions from N to itself (this has to do with index sets), which is N^|N|

[royal haven]

Ohh okk ty guys idk why I had a problem with that lol

[short grotto]

Its okay :)

Infinite stuff is harddd to get your head around

You've gotta be really careful

Good on you for just asking instead of assuming

[outer rune]

so using this combinational circuit diagram i was asked to derive the boolean expressions

for T4, am i allowed to use the XOR symbol?

or do i need to expand it out

like this:

i just dont know if im allowed to use a xor symbol in the boolean expression

[bronze shuttle]

I dont see why not

[outer rune]

i dunno

idk if boolean expressions allow anything other than OR (+) and AND (*) operators

[analog tinsel]

is there someone whos experienced with big O notation?
I wanted to use something like this

$\mathcal{O}(\log^{\mathcal{O}(1)} n)$

but was told that I should rather write $\mathcal{O}(\log^c n)$ for constant $c>1$

But I see people use this notation as in the first case often in papers.
So is there actually a reason why one should not nest big O notation?

[vital dew]

barış

[cursive nymph]

is there \textit{substantial} between $f(a)=f(a)$ and

$$
a=b \implies f(a)=f(b)
$$

?

[vital dew]

Sweet Tea 🧋🥥🍍🥭

[cursive nymph]

probably too dumb of a question. didn't study formal systems

$f(a)=f(a)$ might look silly, but it's a cool assertion that turns programming junk-functions into \textit{pure} ones

[vital dew]

Sweet Tea 🧋🥥🍍🥭

[bronze shuttle]

isnt that the definition of injective

[cursive nymph]

the reverse is, no?

[bronze shuttle]

huh

$$a=b \implies f(a)=f(b)$$

[vital dew]

buboblakistoni

[bronze shuttle]

this is the definition of injective i think

or wait no

[brave rock]

No it is a consequence of the underlying logic.

[bronze shuttle]

i was thinking of $\iff$

[vital dew]

buboblakistoni

[brave rock]

But indeed, yes, maths is not programming.

Functions are actual functions.

Programmers co-opted the word.

[cursive nymph]

it becomes fun when your functions are actual functions xD (in FP say)

ofc there are the goddamn exceptions everywhere

div could've been implemented with the Maybe monad, so it'd be strict

but no, 1 div 0 gives an exception : (

[brave rock]

OK

[blazing seal]

Depending on how far away from classical maths you're willing to go, the latter statement can be consequential/non-trivial depending on how = is understood/meant/treated

[fringe bluff]

Is there any easy way to count the number of graphs that have a given coloring?

[inland zenith]

just program in Gallina or something, your soul will remain pure

[frosty blade]

Why cant remainder be negaitive?

[brave rock]

because that's the definition

[frosty blade]

but why. why is the equation for 36/5 have to be -36 = 5 * -8 + 4 and not -36 = 5 * -7 + (-1).

[oblique pelican]

Remainder would not be unique if you allowed it to be negative and positive. The definition also just makes it more general and easier to work with for proving stuff if you don't have to make exceptions for negative values. I'm sure there's many reasons why, but that's what I can think of.

[frosty blade]

ok thank you

[lapis bramble]

I guess you should be fine if it isn't specified
if we are being pedantic, xor is not considered fundamental connective in propositional calculus, the reason being the lack of symmetry with valuations for conjunction
but I don't think this matters in your case

[snow cedar]

i thought that if theres a differing edge in the matching, it implies the degree is at least 2, not exactly 2

[bronze shuttle]

but each node only has one edge in a perfect matching right

[snow cedar]

yeah its part of one edge

[bronze shuttle]

exaclty

[charred harbor]

I was proving this question and i know how to prove it using the usual routine I'm just curious if it still a formal proof if my argument is based on the conditions to where x belongs?
Basically, let x be an element of the left side then x is an element of C but not to the intersection of A and B. Thus x, can be one of the following: 1. element of C, not an element of both A and B,
2. element of C not an element of A,
3. element of C, not an element of B.
Now let x be an element of the right side, then x can be one of the following

1. element of C not an element of both A and B, 2. element of C not an element of A 3. element of C not an element of B.
   Since the left and right hand has the same possibility for where is x then they are equivalent.

[abstract tulip]

How can I solve recurrence T(n) = T(4n/7) + T(3n/7) + cn is O(n log n) for some positive constant c using recursion tree?

I've tried it by using T(n) <= 2T(4n/7) + cn

And it gives the relation

$T(n) \leq T(1)n^{\log_{7/4}2} + c n \log_{7/4} n$

[vital dew]

.choram

[abstract tulip]

Which is not O(n log n)

[shut ivy]

$\exists u \forall a [au = ua = a]$

[vital dew]

rabbits_advocate

[shut ivy]

is this quantified statement correct to express multiplicative identity?

Shouldn't the quantifiers be the other way around like $\forall u \exists a [au = ua = a]$

[vital dew]

rabbits_advocate

[shut ivy]

is it the case that both are correct ?

[ocean ocean]

When you draw the tree you have O(log n) layers and cn per layer for a total of n log n

[abstract tulip]

But how about T(1)'s ?

[ocean ocean]

T(1) is just constant by assumption usually

[abstract tulip]

yes but I saw few cases that number of T(1) influences the result

[ocean ocean]

You start from T(n) so the number of T(1)s is just n

When you split n to 4n/7 and 3n/7 the sum is still n, so you don't increase

[abstract tulip]

oh

I didn't think of that

Thank you for help!

[ocean ocean]

Np

[shadow lion]

I'm confused as to what this question is asking

I can't make heads or tails of the situation

does anybody mind explaining it to me?

e.g. what am I looking for in this example matrix?

I don't understand what they mean by "maximum number of nonzero entries with no two in the same line" and "minimum number of lines that include all nonzero entries"

[night magnet]

I assume is something like this

[shadow lion]

but what am I looking for?

[night magnet]

the number of 1 (nonzero values) should be equal to the number of rows or columns that includes that nonzero values

sorry if i made some mistake i'm not native of english

[night magnet]

There are 3 ones in the matrix and the number of columns and rows that contain that nonzero values is 3

[shadow lion]

so how about for this?

[night magnet]

It says no two on the same line, I understand that as it can't be 2 nonzero values in the same row or column, but I may be wrong

[shadow lion]

nvm, I looked this problem up and see it now

nevertheless, thank you @night magnet for the help!

[novel ore]

i'm tasked with showing that |Z| = |{0, 1} x N| - here are we asssuming that 0 is included in N?

[brave rock]

Doesn't matter

[novel ore]

huh okay

can i get a hint for a bijection between the two? I tried defining a bijection from Z to N x {0, 1} by n |-> (n mod 2, |n|) but this doesn't work

i've also tried taking all positive numbers in Z and mapping them to (1, n) if n > 0 and (0, |n|) if n < 0 but this also doesn't work

[brave rock]

Draw a picture of the two sets and compare them.

[novel ore]

ok, will do

[tacit portal]

I know this isnt the help channel but could anyone help me w an induction proof. I have been stuck on this particular one for weeks now even though it should be a short problem.

[storm prism]

a context-free language concatenated with another CFL is closed. Does this imply a CFL concatenated with a non CFL always results in a non CFL?

[lean rover]

How come the chromatic polynomial of a C4 graph is P(C4, λ) = (λ − 1)^4 + (λ − 1)
I thought that for chromatic polynomials we only cared about the minimum coloring and now how many different ways we can get minimum coloring.

why do we care about case 2?? IT is not giving us minimum amount of colors?

[spare gulch]

what's the difference between $\subset$, $\subseteq$, and $\subsetneq$

[vital dew]

sushi

[lean rover]

⊂ means that a set is proper set of another set so it is not allowed to be equal to that set. Given A = {1,2,3} then B cannot be B = {1,2,3} if you use ⊂. But if you say B ⊆ A then B=A means that A=B is also a set. I honestly don't think there is a difference between ⊊ and ⊂ cuz they are both saying the same thing and I have never seen ⊊ before today so maybe someone correct me if I am wrong

Guys I need help with something here:

Question: How many people has Sarah shaken hands with?```

Does this even have an answe?

I mean Sarah can either at maximum shake hands with 8 or none. I am confused, btw the topic is about graphs.

[odd heart]

Just as an aside, in some areas (for example, very often in analysis/measure theory/probability), ⊂ is used to mean weak inclusion, so "A ⊂ A" is a true statement, mostly because in those areas it's rare for proper/weak inclusion to be separate cases, so the "simpler" symbol is used for both.

Just like with 0 being (or not) a natural number, it's worth double-checking what convention a particular source uses.

⊆ and ⊊ have the advantage of being unambiguous, but the disadvantage of being more complex symbols.

⊂ will mean the same as one of those two, but I'd say it varies which one, mostly depending on the area of mathematics.

[lean rover]

I have understood my problem better but I'm still confused how we know for sure that Sarah and Alex are the 4 and 4 shakes couple?

Btw the answer is 4 but it could easily be 0-8?? I don't see why it has to be 4.

[neon harbor]

I "solved" it by drawing a graph, and it seems like two of the nodes must have degree 4 just so that the degrees of the other nodes add up, but I'm not sure if I can prove it. I do have a partial proof though: we know degrees 0 to 8 must appear atleast once, so by the pidgeonhole principle there are exactly two nodes with the same degree. You can easily check that the 0-degree and 8-degree cannot be duplicated, and you cannot have a duplicated node with odd degree, because that violates the handshaking lemma. So the duplicated nodes must have degree 2, 4 or 6. And Alex must be one of the duplicated nodes since he sees 9 different degrees

[lean rover]

I don't get this part: "Alex must be one of the duplicated nodes since he sees 9 different degrees". We don't know anything about Alex, we only know that he got 9 answers if I understand correctly?

Or am I missing something important?

[neon harbor]

He asks the 9 other people what their degree is, and he gets 9 different answers, ie. everyone except Alex has a different degree between 0 and 8. Alex also has degree between 0 and 8, so he shares degree with someone else

[lean rover]

yes now I follow but then still it leaves use with 2, 4, 6

Also it sorts of ruin the whole handshake relation like 0-8, 1-7, 2-6, 3-5, 4-4 etc

[neon harbor]

If you could show that the degrees of each couple must sum to 8 then you would have a proof, but I'm not sure how you could show that directly

[neon harbor]

but I think it's enough to construct this graph and argue that each step is forced (with liberal use of WLOG), since at various points you have only one node with degree 1, then only one with degree 2, etc

[lean rover]

what is the red edge supposed to be?

Btw a question about graphs, what is the point of four color theorem if theorems like six color theorem exists? Six color theorem tells us that a graph is planar if the chromatic number is at most 6 whilst four color states the same thing but with 4 instead. Isn't it useless?

Or is there a difference in the wording that I somehow don't understand.

[neon harbor]

Couples, ie. nodes that cannot share an edge

[lean rover]

I still am not sure how the correct solution is 4, I'm sorry lol.

[neon harbor]

Have you tried to draw the graph? Write down 10 nodes, divided into couples. Then pick a node which will have 8 neighbours. Which node must have 0 neighbours?

[oak drift]

can someone tell me if my reasoning is good for my proof?

this is the question

I feel like my use of C as an arbitrary case is weirdly formulated

[lean rover]

I recommend posting here #proofs-and-logic

[lean rover]

Isn't it better to do natural deduction on this tho, I assume the first 3 are the premises?

[oak drift]

You're right sorry

[oak drift]

The first three lines are equivalences

[azure smelt]

What is an improper subset and does it consist of line underneath the sign of subset? When do we use this?

Can someone help me understand the concept of subsets in Set theory? I get confused as to what counts as subset when it comes to A= {a,b,c}
I saw some solutions and it said a is a subset of A whereas some said {a} is a subset. Is there a difference when brackets are placed? What difference do they make on the cardinality?

[hard pike]

No, in your case a is not a subset of {a, b, c, d}, it is an element.

However {a} is a set (as indicated by the brackets), and all of its elements (in this case only a) also belong to A={a, b, c, d}, it is therefore a subset of A

A proper subset of a set S is a subset that is not equal to S, this word exists because S is a subset of itself

As for your last question, brackets indicate a set, if your element is not a set, it makes no sense to talk about it's cardinality

[languid jacinth]

Can someone offer a resource that offers intuition for why algebraic manipulations of functions (from and back to taylor series) works so well when dealing with generating functions? I understand that there is isomorphism between combinatorics combinations and multiplications of polynomials, but it kind of loses my intuition when we start using taylor expansions for trig and exp functions, or even geo. series. If some relation (taylor series (TS) = some function (fn)) holds in functions with real variable I guess it makes sense that isomorphism still holds (TS(fn1)*TS(fn2)=TS(fn1*fn2)) for some operation *. But It really losses my beloved combinatorial intuition. Can this isomorphism be explained, for example, from the abstract algebra point of view by doing everything in formal series ring (without substituting functions from calculus)?

[hard pike]

https://www2.math.upenn.edu/~wilf/DownldGF.html

Not sure this has what you're looking for but it might help you

[lean rover]

If G = (X ∪ Y, E) is bipartite, we say that a matching M is complete (of X) if every node in X is matched by M

Is this true?

In order for bipartite to have complete matching, do all nodes must have an edge in the matching or only all nodes in one set x in G = (X U Y, E)?

It seems to me from the theorem that only one set is required to have all nodes with edge in the mathcing.

[little prism]

well cant have a matching on both X and Y unless they have the same size. and if they do then its enough to say to have a matching on one of them

[haughty garden]

you're probably thinking about perfect matchings

[lean rover]

Guys in my book it states:

Given a family Φ = {Sᵢ | i ∈ I} if sᵢ ∈ Sᵢ and i≠j ⟹ sᵢ ≠ Sᵢ.
Such a set of distinct representatives is usually called transversal.

I have no idea what transveral.

What is a transversal of a set?

[hollow echo]

how to solve?

[lean rover]

Wait I am confused are you trying to add the fractions or is there something I am missing?

If I right, do you know about lowest common denominator?

[hollow echo]

nope

[lean rover]

wdym nope?

[hollow echo]

idk about this

[lean rover]

Lets look at the first question. Do you know what a denominator is? It is the number under the "_" so given 1/4 our denominator is 4. In order to add fractions we must make sure both have the same denominators.

[hollow echo]

2/7?

[lean rover]

no we have 1/4 and 1/2. We need to make 1/2 have the same denominator.

We want 4 as a denominator in 1/2.

(1/2)*2 = 2/4

no we can add (1/4) + (2/4)

which will be (1+2)/(4) = 3/4

[hollow echo]

oh k

[lean rover]

https://www.youtube.com/watch?v=CoCmsyFQ_Xc

check this out

[velvet lynx]

uni-level maths :p

[haughty garden]

the way i like to think about transversals of a family of sets is that it's kind of like the 'cross section' of the family; more formally, you can think of it as a set that contains exactly one element from each of the sets in the family

[lean rover]

How many different conjugacy classes are there in S5

What is the question even asking me?

[upper owl]

hello

this is not discrete ma fren

Maybe go to primary schol they wil help u

[weary tiger]

😂

[tacit portal]

would anyone be able to help me finish my I.S. for my proof. I am on the very last step of the I.S. but can't seem to figure it out.

[hollow anvil]

in your opinion..mathematics are dificult,easy or beutifull

?

[languid jacinth]

Tnx for the answer, I took a look, it looks like a good book for problemsolving skills, so I'll keep reding. I found this video (https://www.youtube.com/watch?v=GZ3saM0GwGU) which was pretty helpful, at least it directed be to think in ceratain ways

[analog tinsel]

yes

[oak drift]

hello everyone, I have a small question

This is my assignement due tomorrow so teacher wont answer me haha

for the first question, I know the answer is true, but for my proof I just want to know if you think I'm allowed to use the fact that two even numbers will end up as an even number

[analog tinsel]

it would probably be useful to translate the words into math

then its clear

[oak drift]

yeah so you think if I translate it into math I will be allowed to use that indentity or I will still need to prove that too

[analog tinsel]

depends on how you use it

if you just write "the product of two even numbers is an even number" then I guess your teacher wants a reason for why that is

I assume its a beginners course

so these things are normally required

[oak drift]

its intro to discrete math

[analog tinsel]

yeah, people usually want to see that you understand why such a statemtn is true

[oak drift]

damn okok

Ill prove both then

[analog tinsel]

well its just

math notation

makes it clear

in this case

what I mean is

there is a way you can express any even number and then also another for every odd number

[oak drift]

I just wrote a (odd) = m + 1 where m is even

is that bad

[scenic peak]

there's no need to use that fact, thinka bout what it means for a number to be even, then what does it mean for a number to be odd, can you write an expression for an odd number?

[scenic peak]

that's not very good

can you write an expression that only gives even numbers?

[oak drift]

2n?

[scenic peak]

yes

[oak drift]

cuz any number times 2 is even

[scenic peak]

can you now write an expression that only gives odd numbers

[oak drift]

2n+1

[scenic peak]

exactly

so you know that a and b are odd

a and b are not neccessarily equal

you want to prove that ab is also odd

can you write a and b using your "odd" expression?

[oak drift]

hmmm

(2n) * (2n+1)

[scenic peak]

(2n)*(2n+1) = ab

but a and b are odd

do you see the issue?

[oak drift]

wait mb

[scenic peak]

also

a = b might not be true

[oak drift]

so like 2n+1 * 2m+1

both n and m are arbitrary

[scenic peak]

yes

don't forget the parens

[oak drift]

yes ofc

[scenic peak]

(2n+1)(2m+1) = 4mn + 2n + 2m + 1

what can you say about this RHS?

[oak drift]

ohhhhh

I see it

well 2n is even

so is 2m

4mn = 2(2mn) and 2mn is even so 2*even is still even

[scenic peak]

despite the fact that you "see" it, you should still factorise it

[scenic peak]

yes

[oak drift]

actually

[scenic peak]

2(2mn + n + m) + 1

[oak drift]

okok

[scenic peak]

first part is clearly divisible by 2, which means its even

+1 makes the entire thing odd

[oak drift]

yep

well thank you it makes much more sense than what I was trying to go with

[scenic peak]

a lot of things you can just tackle by breaking them down into their definitions

and then solving those "definitions"

[oak drift]

thx

cuz my definition of odd was even + 1

so a = n+1

[scenic peak]

your definition is a bit lacking I believe

don't quote me on this but odd numbers are moreso defined in terms of the even numbers

an even number is a number n such that 2 divises n

then odd numbers are the numbers such that 2 does not divine n

consider threeven numbers

what would it then mean to be throdd?

[oak drift]

what is threeven

srry english isnt my first language

oh ok so divisible by 2?

[scenic peak]

threeven would be divisble by 3

[scenic peak]

that's the definition of even I would use yes

[oak drift]

oh so not divisble by 4

3*

[scenic peak]

2 | n means 2 divises n => n is even

if ^^ doesn't hold, then n is odd

[weary tiger]

i do not understand this at all

[blazing seal]

Which part of it is giving you the most trouble ? What do you think is going on with it ?

[weary tiger]

the b part

[blazing seal]

Well, what do you think it's asking you ? Try re-reading the first paragraph in particular

[velvet lynx]

hint: ||you don't need to change the room number by a constant amount||

[ashen bane]

b. is inclusion exclusion principle right

and c is just taking b part but using one less processor, and then multiply by k

right?

[haughty garden]

are the jobs distinct

or are they indistinguishable

[ashen bane]

as i understood they are distinct

serialized

pretty sure

[spice glen]

Can somebody provide me with a reference to help me understand "What Isomorphic Graph is" and "How to check for any graph that it is isomorphic or not?"

[spice glen]

<@&286206848099549185>

[severe stump]

Isomorphic Graph

[spice glen]

Okay, but how can we calculate that it is Isomorphic Graph or not? I know 3 conditions which is : 1) Number of Edges must be same in both the given Graph (2) Number of Vertices must be same in both the Graph (3) An Equal number of vertices with given degree. (4) Vertex Correspondence & Edge Correspondence must be valid. I have understood 3 of them, but I'm unable to understand the 4th Rule. How can we Calculate Correspondence between vertex and edge?

[severe stump]

Basically there must be a one-to-one bijection mapping between the vertices of the two graphs that preserves the edge relationships. In simpler terms, if you rename the vertices of one graph to match the other, the edges must also match correctly.

[spice glen]

Okay, got it, Can you please provide more examples, or any website where I can practice for Isomorphic Graphs?, But Thank You for the help.

[scenic peak]

two graphs are isomporhic if they are isomoprhic

there's not just 3 conditions

there are infinitely many conditions

any condition you can think of that isn't based on ordering/names for the vertices/edges is a condition that must be preserved

hamiltonian, shortest path, longest cycle, amount of cyclkes, number of edges, number of vertices

to practice it you can try and draw isomorphisms for graphs <= 5

[severe stump]

I can recommend a book "Introduction to Graph Theory" while on websites there should be some simulator to plot graphs

[spice glen]

@scenic peakOkay got it, what is your recommendations for Online References / Books/ eBooks ?

[spice glen]

Okay, Thanks for the Help.

[scenic peak]

mathlibretext usually has a few exercises and good explanations + examples

[spice glen]

Okay, is it a Website or a Book?

[scenic peak]

website

[spice glen]

Okay, Thanks for the Help.

[haughty garden]

it's worth noting that it is not known whether deciding if two graphs are isomorphic is computationally easy or hard in general

[haughty garden]

in the case where they are distinct, part (b) does indeed look like inclusion-exclusion

[onyx hull]

Hello! I want to ask for reccommendations on what materials/resources to use to study abstract geometry(specifically i can't wrap my head around the proofs of the theorems of hyperbolic geometry). send help😭. Thanks!

[fossil mural]

those first three conditions aren't part of the definition, they just follow from the actual definition of graph isomorphism, which is that there's a bijection between the vertices that preserves edges

intuitively two graphs are isomorphic if they're "the same up to relabelling", so if you want to show that two graphs aren't isomorphic, you can often do that by pointing out some property that one graph has and the other doesn't

[weary tiger]

i did not understand

[vapid token]

Let $G$ be a bipartite graph with $m$ edges. Prove $\nu(G) \ge \frac{m}{\Delta(G)}$.

[vital dew]

KirPlop

[vapid token]

not sure what to do

This did not help me

[north junco]

what does [V] convey? if V is the set of all vertices from G, then what is [V]?

[little prism]

given that F are supposed to be edges, it should be something like V^2 but maybe you also allow loops? or you have only undirected edges? the notation is a bit odd tho

[north junco]

this is quite literally the first page, the author seems to be notation dumping so i didnt really follow that much

it doesnt explicitly say it allows loops, multigraphs, etc

[little prism]

can you show the entire page?

[north junco]

a bit of an exaggeration, this is the third page technically

first page

[little prism]

ok yes

first line

[V]^2 meaning the set of 2 element subsets of V

[north junco]

this is the page the snippet was on

[north junco]

ah, i see

oh wait, isnt that just an edge

[little prism]

yes thats the point

(undirected) edges are subsets of V of size 2

directed edges would be elements of V^2, so thats why I was talking about that earlier

[north junco]

why are these 2 graphs isomorphic?

does isomorphism mean that you can move around the vertices so that you can construct from one graph into another?

[oblique pelican]

yeah basically

[north junco]

ah i see, that makes it somewhat simpler

say i have a graph like this, let V be the vertices of this graph, and U be the red vertices

the edges with green allows are the neighbors of U, but then what about the bottom 2 edges?

[vapid token]

also, thoughts on my tikz graph?

[raven ermine]

Hey, can anyone help me prove this?

Using rules of nference

[hoary cedar]

hi, can somone pls help me understand what alpha i does?

this is the principle of inclusion and exclusion btw

[lean rover]

A linear binary code C has check matrix as follows. Find a triple (a,b,c) such that the code C can correct 1 mistake.

How do I even begin?

[little prism]

if you want to correct 1 mistake you need a certain minimal distance and that tells you something about the linear dependence of the columns

[scarlet spire]

How can I exhibit a one-to-one correspondence between the set of positive integers and the set of odd negative integers?

[solar marsh]

by Konig theorem, take a minimum cover S, and use the fact that every edge incides in a vertex of S

[mental plaza]

what is a good concrete definition of a predicate? I found " A predicate is one or more variables defined on some specific domain"

but its defined differently on every website

[ivory hemlock]

Bro I had the same question in my college exams 2 days back .
i marked it as isomorphic but my friends said itsd no isomorphic and I am wrongg
Edit : Just saw its slightly different

[ivory hemlock]

Predicates in Discrete Maths and English are quite similar
In Discrete Maths we can say , Predicate is a property of the subject.

[weary tiger]

Hi all, what resources could I watch/read to learn how to do these problems:

[ivory hemlock]

What does U mean here

[weary tiger]

big union I believe

[ivory hemlock]

I think that's generalised Union

[lean rover]

I have checked the solution but don't really get it at all, can someone explain this to me.

[ancient tide]

in asymptotic analysis
is Theta(g) = O(g) intersect Omega(g)?
also i think o(g) = O(g) \ Theta(g)?
and omega(g) = Omega(g) \ Theta(g)?

[vapid token]

Let $G=(X\cup Y, E)$ be a bipartite graph. Prove that there exists $x\in X$
such that every edge incident to $x$ belongs to some maximum matching.

[vital dew]

KirPlop

[vapid token]

Which theorem should i look into

[wild lava]

currently on the struggle bus with this hw and its due in 20

[cerulean wind]

is G required to be finite?

[vapid token]

yeah hahha

Not sure this is the right direction

yeah no

[cerulean wind]

why do u say that?

[vapid token]

I'm thinking I should show there exists a vertex x in X whose removal decreases the size of the maximal matching

which is sufficient

or is it

[vapid token]

no it is not

[vapid token]

any ideas?

[vapid token]

you cookin?

[cerulean wind]

i don’t think so

i like to try my thoughts in the text box

not really sure. i liked ur proof idea

it seems like the choice of y is important tho

and we aren’t given a unique y for each x, so we can’t really make a function without making some arbitrary choices

[vapid token]

right

with our phi, we have

[cerulean wind]

but there is a function from X to the power set of Y taking x to the set of vertices y in Y for which xy is not in any maximal matching

[vapid token]

that is \phi

[cerulean wind]

no

phi is vertex valued

my function is set valued

[vapid token]

yeah

I am referring to the image

Let ( M ) be a maximum matching in ( G ), and let ( \nu(G) = |M| ) be the size of this matching. Suppose, to the contrary, that for every ( x \in X ), there exists ( y \in Y ) such that $y$ does not belong to any maximum matching. We may thus define $\phi: X \to Y$ so that for all $x\in X$, $x\phi(x)$ does not belong to a maximum matching. It follows that there is a matching $N\subseteq[X,\phi(X)]$ of size $|\phi[X]|$. Since no edge of $[X,\phi(X)]$ belongs to a maximum matching, $|\phi[X]|<\nu(G)$. $|X| - |\phi[X]| > |X| - \nu(G) \geq 0$.

[vital dew]

KirPlop

[cerulean wind]

thinking you may want to look at halls theorem

i feel like it should be used here but i’m not seeing how atm

[viral crown]

this should be provable using notions of like, factor critical graphs

[viral crown]

i don't think this would work in any direct sense

maybe there's a proof using it

[vapid token]

I haven't learned that

just hall's, konig, menger

basic matching theorems

[viral crown]

should be doable with konig too

[vapid token]

how

[viral crown]

mm seems like it will work

sorry i’m really eepy

if you’re still doing this tmr lmk and ill see if i can come up with something proper

[vapid token]

aight

I can't focus honestly

[viral crown]

but i think factor critical stuff will work i’ve shown similar things with it

[vapid token]

Homework was due 2 hours ago anyways

[viral crown]

email ur prof and ask for a quick extension

aight imma sleep

gn!

[vapid token]

gn

[acoustic sable]

is there something wrong with my solution?

<@&286206848099549185>

[hot lantern]

I'm having trouble understanding division and distribution of distinct objects

and distribution of identical objects: (i) when empty groups are not allowed, (ii) when they are allowed

Can anyone help?

[cerulean radish]

What's being applied on the 3rd equality in the proof is not distributive law

Although the equality is correct

[upbeat summit]

Does anyone have time to help me with my mathematical proofs hw. Just need help understanding the questions, don’t have to tell me the answers

[cerulean wind]

this is used to prove konigs iirc

[viral crown]

i'm quite sure there are proofs not using it too

[cerulean wind]

wikipedia confirms they are equivalent. i hadn't realized that.

[vapid token]

Did you come up with a construction?

[craggy socket]

Hi. What do the big AND symbols mean?

The book doesn't introduce this in the section

[vapid token]

It means “For all” basically

[craggy socket]

For all (~p_i V ~p_j)?

[vapid token]

With i+1 <= j <= n and 1<=i<=n-1

$\bigwedge_{i=1}^n p_i=p_1\wedge p_2\wedge\cdots\wedge p_n$

[vital dew]

KirPlop

[vapid token]

It’s this

[faint pecan]

Hello, could someone explain to me how to demonstrate an equality? I've just started discrete mathematics and I'm having trouble understanding it.

[vapid token]

Show the left hand side is a subset of the right hand side and vice versa

<@&286206848099549185> somebody good at graph theory I got a problem

Let $G=(X\cup Y, E)$ be a bipartite graph. Prove that there exists $x\in X$
such that every edge incident to $x$ belongs to some maximum matching.

[vital dew]

KirPlop

[vivid osprey]

Is it true that $$\bigcup_1^n (A_i\times B_i)=\left(\bigcup_1^n A_i\right)\times\left(\bigcup_1^n B_i\right)?$$

[vital dew]

psie

[viral crown]

@vapid token apparently wikipedia will have something showing they r equiv, you can just read it there

i feel that the proof will not be hard to understand

[vapid token]

I looked and did not find what was referenced

[viral crown]

mmmm damn

[odd heart]

It is an excellent exercise to prove it or find a counterexample.

[viral crown]

k i'll see what i can come up with

[vapid token]

Ty

Honestly it’s discouraging that I can’t seem to figure it out

I must’ve missed some trick used in class

[viral crown]

you're good, it's easy to miss things

[vapid token]

Lean towards the finding a counter example

[vivid osprey]

ok

[viral crown]

did u ever go over augmenting paths?

[snow cedar]

I'm not sure how to prove the => direction. Right now I think that if each person is matched <= 2 jobs, then since there are |A| people there are <= 2 |A| jobs that are matched. any advice?

[languid jacinth]

Ig for if direction, you can use induction, start with a set of all people and than remove the one with ≥ 2n jobs. Than keep doing this for the rest of people. That way we constructed people with at least 2n, 2n-2, 2n-4, ..., 2 Jobs.

Maybe try to construct a valid matching from this

Although I might have gotten something wrong because only if part doesn't make sense, what if we have 2 people and 4 jobs and they are both qualified for 2 jobs, without overlap

[deep vector]

this graphs are isomorphics?

[languid jacinth]

I think yes

[viral crown]

see if you can drag the vertices around to get it

[languid jacinth]

It's 2 cycles of size 5, connected node by node

[languid jacinth]

In first graph this structure is very visible, but in second, try to split it in a right way

[languid jacinth]

Can anyone check this, I might have gotten smthng wrong

[solar marsh]

I think yes

[deep vector]

oh okey thank you

[viral crown]

tsk

nosols

[vapid token]

Yes

[viral crown]

i think a contradiction based argument using them will eventually work because you'll always be able to alternate

and then maybe use other theorems to get bounds or something

[vapid token]

Hmm

You think this

[vivid osprey]

Let $X$ and $Y$ be decomposed as the union of sets ${X_n:n\in\mathbb{N}}$ and ${Y_n:n\in\mathbb{N}}$ respectively. When does $$\bigcup_{n=1}^\infty (X_n\times Y_n)=X\times Y$$hold?

[vital dew]

psie

[solar marsh]

no

[weary tiger]

Hey, I'm looking for a tutor specific for discrete math can somebody help me

[craggy socket]

Thanks, I'll try solving it later

[winter light]

Post your questions here, maybe someoene wil help

[weary tiger]

How many elements does each of these sets have where a and b are distinct elements?
(a) P({a, b, {a, b}}) (b) P({∅, a, {a}, {{a}}}) (c) P(P(∅))

Can someone explain for c

[vestal bronze]

∅ is 0

so P(∅) is 1

so P(P(∅)) is 2

you can replace ∅ with {}

[split oasis]

stuck on this not sure what to do

[ashen bane]

can someone help with C

[gentle tendon]

Recursion

[ashen bane]

It's impossible doing it using hm exclusion inclusion princple?

[ashen bane]

need help

[cerulean radish]

Let P(n) denote the probability of a random graph with n vertices being connected, try to come up with a recursive formula for P(n) and see if you can find its closed form (hint: ||P(n) = (the probability of a vertex being connected to the rest of the graph)*P(n-1)||)

[ashen bane]

Hm

[snow cedar]

I think I am supposed to apply a consequence of Mengers theorem, but I'm having trouble actually seeing how to carry out the proof. Any advice?

I thought maybe to use this somewhere

But I'm not sure how to carefully construct my paths

[snow cedar]

Like, I can't really foresee that P_i and P_j don't intersect any vertices. This theorem just tells me infomration about a single P_i only

[snow cedar]

Yep still stuck

[vapid token]

Consider a new vertex adjacent to y_1 through y_k

Apply mengers theorem on that vertex and x

[vapid token]

.

[snow cedar]

what motivated this idea?

[vapid token]

It's used to apply Menger's theorem in a few proofs

Adding a new vertex or two

[snow cedar]

Hm.. by this do we mean we introduce a new vertex z and add in some new edges z-y1,..., z-yk?

[vapid token]

yes

By the k-connectivity of G, the minimum x-z vertex cut is at least k, meaning there are at least k vertex-disjoint paths from x to z

[snow cedar]

I think my understanding is a bit different on how we concluded this, would we be relying on this?

[opaque rune]

best site for practice proof problems? proofs def my weakest area rn

[vapid token]

precisely

[snow cedar]

Okay I see, how do we relate these vertex-disjoint paths that were from x to z, to the paths from x to y_i?

vertex disjoint means these path have no node in common except for x and z from my understanding

[vapid token]

suppose one such path did not include a y_i, then there would be some other vertex connected to z for this path to traverse

which goes against our assumption that z is only adjacent to the y_i's

[snow cedar]

Oh wait I see now, this holds based on our construction

Also because our original graph is k-connected, then making a new graph with z connected to the y_i's still keep it k connected .

[vapid token]

yup

[snow cedar]

And in this part, when we said there are at least k vertex-disjoint paths from x to z, doesn't it end up that there are exactly k vertex-disjoint paths, each going through some y_i? Or does this detail not matter at the end

[vapid token]

it does not matter

[snow cedar]

Got it

[vapid token]

You might say G+z is at least k-connected

I don't know if it's obvious or true that the minimum vertex-cut remains k

But it is certainly at least k

since the degree of z is k, there are at most k vertex-disjoint paths

So there would be exactly k, yes

[snow cedar]

I also had another question,

I think an easy case for this is that when x has a neighbour y that is unmatched, we can extend it to a perfect matching by deleting the original edge from x to whatever neighbour it had, then add a new edge from x to y.

I guess the tricky case is when the neighbour is already matched, we'd have to somehow create a new matching

[vapid token]

literally what i've been trying to prove for days

[snow cedar]

Omg lol

[regal geode]

[split oasis]

now sure how to do this

i am trying to do PR[At most 50 or less show up] < 1 - p[51] - p[52]

but 51 and 52 are disjoint so not sure what to do

[vapid token]

#probability-statistics

Let $G$ be a bipartite graph with vertex sides $X,Y$, and $0 < a<1$. Suppose
that for every $S \subseteq X$ we have $|N(S)| \ge a|S|$. Show that there is a
matching in $G$ that saturates at least $a|X|$ vertices of $X$.

[vital dew]

KirPlop

[weary tiger]

Emperor Augustus heard many good things about Cleopatra, so he decided to invite
her to Rome. Cleopatra arrives with 8 of her finest advisers. Augustus, wishing for an
amicable meeting, also brings 8 of his advisers to the meeting. Cleopatra, Augustus,
and their 16 advisers sit and discuss at the round table. We’ll consider two
arrangements the same if everyone has the same left and right neighbours.
You can leave your answer as an expression such as 14! Or P(14, 14) .

3 of Augustus’ advisers need to tend to some urgent business and leave, but
3 philosophers come into the room. There are now 9 in Cleopatra’s party, 6 in
Augustus’s party, and also 3 philosophers at the round table. How many ways
are there to arrange them such that nobody sits next to someone of their own
party? Explain solution.

Pls someone help

[willow yacht]

Which is the "standard" definition for tuples of 1 element?
I understand that for more than 2 elements, the tuple's definition extended the definition of ordered pairs
(a, b) = { {a}, {a, b} }
As...
(a, b, c) = (a, (b, c)) = { {a}, {a, { {b}, {b,c} } }

So, which is the definition for 1 and 0 tuples that is coherent with the previous definition?

[pale epoch]

you wont get one

you'll have to formalize as functions

or sets of ordered pairs

or actually, just set the 0 tuple to be the empty set

and then bootstrap from there

if a is an (n-1)-tuple, you get the n-tuple (a,b) via (a, b) := {{a}, {a, b}}

@willow yacht

[willow yacht]

I'm here :D

So... which could be an option to define a single element tuple? :,v

[pale epoch]

${{\varnothing}, {\varnothing, x}}$

[vital dew]

Lochverstärker

[pale epoch]

following what i wrote above for n=1

this is the 1-tuple (x)

[willow yacht]

OkOk? And why sometimes it's represented as just the single element?

[pale epoch]

the representation doesnt matter

if you do it like you said, you have to treat 1 (and 0) tuples as special cases

if you want them all at once (the finite ones anyway), you can do what i said though

nobody worries about this in practice

[willow yacht]

Ok

[pale epoch]

i mean, this breaks down for infinite tuples anyway

so what you can also do is define 2-tuples only (which you need to define functions)

and then define an n-tuple (where n is allowed to be infinite now) as a function from an n element (ordered) set into your space

[snow cedar]

Lmk if you figure it out 😂 or if anyone can chime in to help us both out, that would be great too 🙂

[viral crown]

we will proceed by contradiction.

then each vertex x in X has an edge e that doesn't belong to any X-perfect matching. pick v in X and let u in Y be the other vertex of ev. then assume there is an edge incident to u that is in the X-perfect matching. (if there wasnt, we could remove the pair v is in already with the pair vu and get a new X-perfect matching).

there is a path v1u1v2u2... s.t vkuk is not in the X-perfect matching and ukv(k+1) is. this path will alternate between edges in the matching and edges outside of it and thus it must close. then just swap the edges and you'll get an X-perfect matching s.t at least one of the edges that "are in no such matching" are in one.

this is a contradiction and we are done

i think i'm also making an implicit assumption that it's connected here

i think that's fine in this case bc of the wording of the question

[harsh lichen]

can anyone recommend any sources for discrete math practice problems and solutions? currently doing counting and logic. thanks👍

[wise crater]

hi

[novel ore]

shouldn't this be N^N is an element of P(N x N)?

[vestal bronze]

one relation is an element

N^N is apparently all functions

[novel ore]

yeah, so it would be a set of ordered pairs and thus a subset of N x N right

hence an element of P(N x N)

[vestal bronze]

yes

one function would be

[novel ore]

oh wait

ah

i see now

thanks

[ashen bane]

yo

anyone on

An urn consists of 30 red balls and 70 green balls. What is the probability of getting exactly k red balls in a sample of size 20 if the sampling is done without replacement (repetition not allowed)?

[vestal bronze]

count outcomes

imagine balls are numbered

[ashen bane]

ok

i dont understand why is that

[vestal bronze]

i don't know what you mean

[ashen bane]

Why shall treat the balls serialized

thats what i dont understand

[vestal bronze]

i don't know

[ashen bane]

So why you suggested it

[vestal bronze]

that's the trick

[ashen bane]

I mean i want someone to explain me this

cuz this is the part i didnt understand

[vestal bronze]

i think of it as "in real life balls are always different"

[ashen bane]

It's not really a trick if you dont understand it

imo at least

[vestal bronze]

why

[ashen bane]

in balls in colors it doesnt matter if you pull (R1,R2,B1)
or (R2,R1,B1)

assuming the balls are not labeled

the formula somehow discards this multiplications

i must understand how

[vestal bronze]

they cancel

you can do the multiplications, they would just repeat in numerator and in denomnator

[ashen bane]

using the nPk thing?

ye ill try

[vestal bronze]

@ashen bane basically it's a lie, they don't mean "you get each sample with equal probability"

they mean you get samples as it would work in reall life, and ignore the difference between balls afterwards

so it doens;t change the outcome

it's about knowing this convention

it's probably super dumb i just can;t appreciate it, because i randomly intepreted it that way the first time i've seen it

[ashen bane]

oh so you can't really do wanted criteria / all possibilities?

[vestal bronze]

yes

because 1+19 would happen rarely, and 10+10 would happen more often, even ignoring the difference in 30 and 70

[ashen bane]

damn it's really fricking me rn

[vestal bronze]

you're right to be mad

[ashen bane]

dang

[vestal bronze]

also i wasn't talking about sequentially taking the balls versus at the same time

i meant like the balls are different from each other, and you take them at the same time

i'm pretty sure we're talking about differen things

idk, it's probably the same idea

[fossil mural]

it's just... probability?

the same as how the answer to "if you flip a coin 5 times and count the heads, what's the probability you get 0" is not "that's one outcome out of 6 possible so 1/6"

[fossil mural]

that only works if all of the possibilities have the same probability of occurring

[ashen bane]

Let me ask you what's bugging me

how both combinatorical questions have the same answer:

I dont understand how both have same answer you got me

for 2nd question i understand why it works

for 1st i dont

[fossil mural]

ok well if we just look at specifically drawing GGR in that order, because that's simpler than having to account for order etc

there are 4 green balls and 6 red balls, so the probability you get a green ball first is 4/9

now (assuming you took a green ball out) there are 3 green balls and 6 red balls, so the probability you get a green ball is 3/9

now there are 2 green balls and 6 red balls, so the probability you get a red ball is 6/8

[ashen bane]

this is for GGR?

[fossil mural]

yes

[ashen bane]

now same for GRG

RGG

right?

[fossil mural]

yes

[ashen bane]

Ok but why it still works

[fossil mural]

...?

[ashen bane]

the original formula?

[fossil mural]

what's "the original formula"

[fossil mural]

ok well wait

if you agree that this method works

...we can do exactly the same thing to compute the answer to the 2nd question as well

[ashen bane]

i want to understand why this formula works

hypergeometric

its same result for 1 and 2

[fossil mural]

well do you understand why it works for the second question?

[ashen bane]

It solves the general problem: for K green balls and N-K red balls, whats possibility of choosing n balls where k of them are green.

so basically the denominator is number of ways to choose k balls from K(order dont matter) * the rest choosing other serialized balls.
dividing by the totals of ways to choose n serialized balls from N the total

[vestal bronze]

that is definitely what i was explaining, balls are "the same" vs. different

[ashen bane]

it makes sense cuz the order doesnt really mater here

i didnt understand your explaination ig

[fossil mural]

...i mean i never tried to explain that formula so it makes sense that you didn't understand my explanation of that formula?

[ashen bane]

could you please

it was not you

i was talking to frown

[fossil mural]

ok wait i'm now completely lost on what it is either of you actually don't understand here

[ashen bane]

Why the formula works

thats it lol

[fossil mural]

why it works for what question

[ashen bane]

for both actually

its the same answer for both

apperantly

[fossil mural]

alright well the reason it works for 2 is... pretty much just what you said?

the number of ways we can pick 2 green balls and 1 red ball, ignoring the order in the sample, is (the number of ways to pick 2 green balls) * (the number of ways to pick 1 red ball)

[vestal bronze]

suppose if you're choosing 4 balls with replacement, and there's 5 red and 5 green balls
then RRGG happens more often than RRRG, instead of equally often

[fossil mural]

and the denominator is the total number of ways to pick 3 balls, again ignoring order

[ashen bane]

yessir

[ashen bane]

with replacement ye, but here there is no replacement\

[fossil mural]

and because with the numbers every possible outcome has the same probability, we can just divide the number of outcomes we want by the total number of outcomes

[ashen bane]

yes

ok for second problem i agree

[fossil mural]

then for question 1 the reasoning is just that it's the same as question 2

putting numbers on the balls doesn't change the probability

[ashen bane]

doesnt it change the count ?

[fossil mural]

yes, but not the probability

[ashen bane]

ah

ahhhh

ahhhhhh aa

damn

That's what i was messing around i think

omfg 😦

Is this like handshaking? or is there formal proof for this

And one last question to make sure i got it 100%, why is it ok to do not care about order in both denominator + numerator, i guess if we did care, we would get same answer, but why its ok no to care about the order?

it's again like handshaking?

[fossil mural]

...idk what you mean by "handshaking"

[vestal bronze]

it's only ok because we get the same answer

[ashen bane]

hm i mean

hand waving i think

how is this term called to say you explain smth without much elaborating

in my language its just hand waving

[fossil mural]

yeah probably "hand waving"

but no both of these can be proven formally

...i'm just trying to think through how exactly you do it

[ashen bane]

Am i correct btw with my intuition?

like if it was used to care about order, the probability would still be the same

but the combinatorics of course not

right

[vestal bronze]

there are formal proofs for everything, it's not like this is all poetry

[ashen bane]

ye ye leave the formality

no need

[ashen bane]

just to understand if the intuition is correct here.

[fossil mural]

...yeah tbh i don't know if there's really a better explanation for why not caring about order is fine than "if we did care about order that would just be an extra factor of n! on both of them, so it's fine to cancel those factors"

[ashen bane]

ye

[fossil mural]

i'm not really sure which intuition you're referring to there

[ashen bane]

that the cancelling factor

on both

[fossil mural]

yeah pretty much

[ashen bane]

so the trick again is like @vestal bronze said at first, treating them serialized

since it doesnt affect the probability

sorry for dont understanding you first bro @vestal bronze

@fossil mural you actually clarified it doesnt affect the probs

so thanks now made it more clare

Thank you both

[fossil mural]

i thought about the reasoning for this: given any state of the bag with numbers, you can just remove the numbers, and whether you do it before or after taking out one ball, doesn't affect the probabilities of the final state

as in, if you have "red balls 1, 2, 3, green balls 4, 5, 6, 7, 8, 9", then if you remove numbers to "3 red balls, 6 green balls" and then take out a ball there's a 3/9 = 1/3 chance you get a red ball
whereas if you just take one out while leaving the numbers there, and then forget about what number you drew and just look at the colour, there's a 3/9 = 1/3 chance it was red
it's the same thing

[vestal bronze]

which is what i said "you can do multiplications and they will repeat in numerator and denominator"

[ashen bane]

Thanks

[fossil mural]

and since drawing 3 balls is just drawing 1 ball three times in a row, you can apply this fact three times: think about doing it with numbers all the way through, then consider what happens if you erase the numbers after drawing two balls, then what happens if you erase the numbers after drawing one ball, then what happens if you erase the numbers immediately, which is the same as never having written them on the first place; and each of these steps doesn't change the probability

[ashen bane]

I understaood it better

thanks to both

[vestal bronze]

but you can't see it though

[ashen bane]

i cant

[vestal bronze]

it's not the same calculation when you remove order from every outcome

[ashen bane]

its just understanding it +

ye ye

i guess its complicated

[vestal bronze]

it's only easy when the difference is the identity of balls

in this 2 problems, there's no difference in the order

[ashen bane]

you mean like the common factor in both denominator and numerator are complicated?

that responsible for the remove of serialization

[vestal bronze]

you don't care if you got 2531 or 3125 in problem 2, "the balls are different" is the difference not "the order becomes relevant"

[ashen bane]

ah i think i know what you mean btw

[vestal bronze]

so in this case, it's not complicated

[ashen bane]

aight

[unique spindle]

Someone in here who knows a little bit about Dung's abstract argumentation?

I am trying to understand how to get the admissible sets from something like this

But my brain says NAH

[dire schooner]

not me memorizing proofs for a midterm LMAO

[ashen bane]

ah Russell'a paradox

bugged my mind in 1st semester

[dire schooner]

also halting and other random garbage

Tbh I don't even know if this proof that I put together is sufficient LMAO

mewhen

[unique spindle]

but like

[unique spindle]

how do I even interpret something like this?

[novel ore]

can i have a hint for showing that |{0, 1, 2}^N| <= |{0, 1}^N|

[sick grail]

use a separator/delimiter

alternatively, use two terms for each term of an element of 3^N

[ashen bane]

Bumping something from earlier

@vestal bronze @fossil mural

Is there proof to this?

"Recall that since the sampling is without replacement, the unordered sample is uniformly distributed over the set of all combinations of size n chosen from D."

[earnest umbra]

What book would you recommend to study discrete maths? My teacher's notes are very confusing

rn i'm learning sets, functions and counting

[oak drift]

hello does someone know how the first one is false and the other one true?

in the theory of sets

[ashen bane]

#proofs-and-logic

[oak drift]

I dont need a proof just explaination

[oak drift]

I'll still ask there just in case

[ashen bane]

well i can explain simple

$1 \in {1}$

is true

wait

[sick grail]

\{ not just {

[ashen bane]

ty

[vital dew]

homer

[ashen bane]

this is true right since 1 is in the set(without the brackets)

[oak drift]

yeah one is part of the one set

[ashen bane]

$\emptyset \in {1, 2, 3 , \emptyset}$

[vital dew]

homer

[ashen bane]

this is also true

because the empty set is in the right set

literally inside it

now $\emptyset \not\in {1}$

[vital dew]

homer

[oak drift]

yeah?

[ashen bane]

since the empty set which you can treat as ∅ = {} just set without anything is a math object

[oak drift]

that makes sense

[ashen bane]

and it's not inside the other set

while subset is vacously true

[ashen bane]

because $A \subset B$ if for every x in A, then x in B

[vital dew]

homer

[ashen bane]

so $\emptyset \subset A$ for every set A