So it must just be connected to one other odd vertex.
#discrete-math
quaint star
grizzled laurel
ooooh right
and every simple graph has an even number of vertices with odd degree so if one exists atleast one other has to exist right
yeah
rugged pebble
why is this not onto, f(x) = x^2
near prawn
your question is incomplete
rugged pebble
R -> R
near prawn
can you find a pre image for -1
rugged pebble
i just thought that for onto every element in the target has to be mapped to
oh
lol;
copper ore
last sigil
Try some smaller cases
shell ledge
Anybody want to help ne solve some graph theory stuff in like 50 mins
copper ore
@last sigil can't think of any. Could you maybe help?
well actually I thought of one case
mystic moss
lol @shell ledge is this a test
mystic moss
hm? but why in 50 mins?
mystic moss
ah maybe in a couple of hours 😅 but like why are you considering the time 🤔
shell ledge
So if someone sees the message in the next hour they know
mystic moss
also *reinhard?
shell ledge
Oh yea my dumbass
mystic moss
*diestel?
shell ledge
I just woke up from
mystic moss
in the next hour
right but why
shell ledge
A bad headache filled sleep
So it would take an hour for me to get in the groove avain
Ironically the headache is because of gt
mystic moss
😅 ah okay. yeah post your question whenever you're ready!
mystic moss
hm maybe i can hop in for a couple of minutes
mystic moss
gimme five
sterile flint
i'm being asked for a flow from c to b here for an augmented path and i'm not sure if that's a typo, is that actually possible?
mystic moss
wait @sterile flint why wouldn't this be possible
naive mural
unreal stump
Because that's proper subset
vital dewBOT
- -:
stray reef
f(z,x) has 6 possible values if z=r and 7 possible values if z!=r
the number of elements of A × A with first component r is 7; the rest number 42.
so 6^7 * 7^42
dim wasp
How can i understand these relations?
harsh warren
hey can someone help me, i'm trying to understand how to construct a polynomial transformation
to reduce the hamiltonian path to the hamiltonian cycle
swift agate
Can someone help me to prove this boolean algebra: x+y + y*x' = x+y
mystic moss
@harsh warren what have you tried?
fluid zealot
I am thinking y+y*x' = y
swift agate
@fluid zealot is x'y the same thing as x+y
I worked the left hand side out to x'y
not sure if I did it right
fluid zealot
I'm guessing x' is the complement of x?
swift agate
yes
swift agate
I'm not sure I worked out the left hand side of the equation to x'y but it needs to be completed to x+y so it equals the right hand side
There might be a simpler way starting from the beginning
fluid zealot
Okay... Seems that our approaches are different.
My approach is since
y*x'⊆y
So y+y*x' = y
So x+y+y*x' = x+y
fluid zealot
Yea.
y*1+y*x'=y*(1+x')
rugged pebble
is f(x) = 2x onto
swift agate
@fluid zealot is there any recommended method for finding the shorter way to do it... your method worked and it is clearer than the way I was trying
near prawn
then yea
fluid zealot
@swift agate
I usually would try to see if there's any inclusion relation among the terms.
Also I would use Venn diagram to help me understand the situation.
distant bobcat
Given the divisor relation on a set of positive integers how can I think of upper and lower bounds in this context? Would the lower bound given xRy be a number that divides both numbers perhaps? What about the upper bound?
swift agate
Can anyone give me a hint for proving x*y + x' = y + x'*y' in boolean algebra
harsh warren
@mystic moss i'm not sure what constitutes a polynomial transformation so i don't have anything written down formally yet. but what i'm thinking is that if i want to transform a hamiltonian path problem to a hamiltonian cycle problem, i'd just have to find the hamiltonian path and make sure the last vertex has an edge to the first vertex in the path?
weary tiger
where should i start with this
zenith thorn
Prove they’re subsets of each other
weary tiger
how do i do that
mystic moss
@harsh warren so basically you want to solve the hamiltonian path problem with the hamiltonian cycle problem, not the other way around
because we're reducing HP to HC
harsh warren
oh right
mystic moss
so you're "finding" HCs not HPs
harsh warren
sorry i'm still trying to wrap my head around the concept of reduction
mystic moss
yeah no worries. it's really cool
harsh warren
well in that case it should be simpler right, if we have a hamiltonian cycle we can remove one edge from the first vertex and it'll be a hamiltonian path?
actually any one edge will work
mystic moss
sure, that's one direction though
zenith thorn
Take an arbitrary element in the first set and show it’s in the second set and vice versa @weary tiger
mystic moss
so you've got a reduction that basically is "find an HC on the given graph" and you want this to admit the same graphs as the HP problem
so the one direction you've shown is that if your problem is admitted in the reduction, it's also admitted in HP
but for every graph with a hamiltonian path, is it necessary that it is admitted in the reduction?
mystic moss
no i'm not saying that
harsh warren
what do you mean by "you want this to admit the same graphs as the HP problem"?
mystic moss
so you want to take the original graph and ask a question about it, and you want the answer to this question to be the same as the answer to "does this have a HP"
that's kind of what i meant by "admission"
so the question you have right now is "does this graph have a HC"
harsh warren
the original graph is the one with the HC?
mystic moss
i mean "original" in that you're asking the question about it
so you want to know if a given graph has a HP
harsh warren
oh ok, so i first ask if the graph has a HC, and if so, by showing that HC reduces to HP, if the answer for the first question (does the graph has a HC), then the answer for the second question (does the graph has a HP) should be the same
mystic moss
hm, kind of. i think you have most of the idea
but the question you ask first isn't going to be if the graph has an HC, and we'll soon see why
let me reword that
harsh warren
i've been watching a few videos about NP-completeness, reduction, etc. and i think the concept is pretty clear to me but formally performing a reduction is a problem for me
mystic moss
we want to show that HC reduces to HP. in other words, we want to be able to answer if some graph G has a hamiltonian path using an algorithm for HC. in the end we will run the HC algorithm on some graph G'. in other words, we ask the question if G' has a hamiltonian cycle, and we want the answer for (does G have a HP) and (does G' have a HC) to be the same.
is this more clear?
mystic moss
yes exactly
harsh warren
ooooo ok thank you this is very useful
harsh warren
if i'm going to run the algorithm on G' to find a HP, can i assume that G already has a HC then?
mystic moss
remember you run the HC algorithm on G'
harsh warren
do you see why G' != G?
@mystic moss is this a requirement or is it a 'could be different, could be the same' situation?
mystic moss
i think you flipped them
is this a requirement or is it a 'could be different, could be the same' situation?
i'm fairly certain this is a requirement
they cannot be the same in all cases
harsh warren
so why is G' != G
mystic moss
well okay so then what we're doing is asking if G has a HC and we want the answer to this to be the same as if we asked does G have a HP
do you see why this might not be the case?
harsh warren
sorry, might not be the case of what?
that the answer to if G has a HC and if G has a HP might not be the same?
if the answer for if G has a HC = yes, i'm guessing the answer to G has a HP must = yes
but if the answer for if G has a HC = no, the answer to G has a HP might still = yes
is this right?
mystic moss
yes, exactly
you can have a graph with a HP that doesn't have a HC
so the answers would be different
@harsh warren so you need to tweak G a little
harsh warren
hmmm so this 'tweaking' is the polynomial transformation?
mystic moss
yup
harsh warren
ok so let me clarify: i want to tweak G into G', so the output of whether or not G' has a HC is the same output of whether or not G has a HP?
mystic moss
yes, exactly
harsh warren
thank you very much this has been very helpful, i'm going to go think about how i can tweak G now and i'll be back if you could verify my solution
mystic moss
yeah have fun!
harsh warren
is adding a new vertex and connecting this new vertex to all vertices in G a valid solution?
i tested it on a few graphs with 3-4 vertices and it works but i'm not sure if i thought about all edge cases
mystic moss
yup!
harsh warren
oh perfect
how can i define this polynomial transformation f formally?
the question asks to construct a polynomial transformation f from HP to HC. but what constitutes a 'full' answer to this question? is there a typical format for defining a polynomial transformation?
mystic moss
hm i wouldn't know any "formality"
but i think you would just say that you add a vertex that is adjacent to all other vertices
and then prove that the answer to the questions are the same @harsh warren
harsh warren
oh i'll have to prove them as well?
harsh warren
like from both sides?
mystic moss
yeah
harsh warren
ok i'll work on that. again, thanks a lot!
weary tiger
singletons are recursive right?
and doesn't that just make it essentially trivial
also i think its the wrong channel so if anyone has an idea which one is better for it lmk
cosmic ledge
Hi guys, i am stucked trying to solve an optimization problem. Lets say i make 2 type of cookies everyday. And i have 150kg of A, 90 of B and 150 of C to make them. Cookies1 need 1/1/2 Kg of each component to make 1 unit. They are sold at 10$ each one. Cookies 2 need 5/2/1 Kg, and are sold at 23$. How can i maximize this function?
stray reef
isnt this just a textbook case of a linear programming problem
do you know how to set those up
cosmic ledge
well, i know i am working on 3D space. I know my main function is Cookies1*10 + Cookies2*23 is the function i have to maximize, with the ingredients restrinctions. But the problem is not for me. They guy i am helping is younger and he doesnt even know how to diff. So i am stucked
where Cookiesx is the number of cookies to make
stray reef
doesn't know how to what?
stray reef
differentiate.
cosmic ledge
that
stray reef
anyway this is linear programming, you do not need derivatives lol
cosmic ledge
well, to find max/min i use to differentiate
stray reef
that's for single variable
and even if you take the gradient instead, your function will be linear and hence, yknow
cosmic ledge
yes i know, and maybe somehow this can be wrapped into single variable problem, not sure. But if so, idk how
stray reef
no
cosmic ledge
okey XD
cosmic ledge
the first thing i suggested was to make the inequation, like A*Cookies1 + 5A*Cokkies2 <=150
and so on with the other ones
stray reef
no
okay so
like
can you please not use these absurdly long names
Cookies is 7 letters
cosmic ledge
X and Y for cookies 1 and cookies 2 ?
stray reef
you can do x1 and x2
cosmic ledge
wdym?
stray reef
cosmic ledge
X Y
A 1 5
B 1 2
C 2 1```okey so, isnt this what i had and u told me no?
the first thing i suggested was to make the inequation, like
A*Cookies1 + 5A*Cokkies2 <=150
^
stray reef
you wrote it out very poorly and your notation was sloppy
stray reef
what??
cosmic ledge
ah nvm nvm
ye we have the same okey
so for me, the a), b) and c) and plains on a 3d space
am i wrong???
o.O
stray reef
3d?
oh, ok, there's this random x_3 just standing there in the nonnegativity constraints, it shouldn't be there
anyway where else do you see a third variable
cosmic ledge
f(x1,x2) = 10*x1 + 23*x2
this is on a 3d space
and this plain may intersect the region from the 3 restrinctions. Well 6, counting the non-negative ones
if i am wrong pls tell me
stray reef
first off, it's plane, not plain
cosmic ledge
ah sorry
stray reef
also you're trying to treat the objective function value as another variable
which, no.
you don't do that in optimization.
cosmic ledge
okey, thanks
zenith thorn
Holy, that’s really nice penmanship
stray reef
if you're talking about mine that's kinda sloppy by my own standards
zenith thorn
Even if it was rushed it’s pretty solid
quartz kite
Activities
With sets A and B. Determine the relations:
- R = (a, b); a is a multiple of b
- R = (b, a); b is power of a
- R = (a, b); a is a divisor of b
A = {2, 4, 6, 8, 10} B = {4, 8, 16, 32}
help
oak spire
does it mean if realtion is antisymmetric that is reflexive only
harsh warren
@mystic moss are you here?
oak turret
how would i approach this question?
weary tiger
a_n/a_n-1 = pi n^2 => a_n = a_n/a_n-1 * a_n-1/a_n-2 * ... * a_1/a_0 * a_0 => a_n = 1/pi^2 * pi * n^2 * pi * (n-1)^2 *.... * pi = pi^(n-2) n!^2) or sth
grim swan
@oak turret i would honestly write out a bunch of terms to guess at the answer, then prove the answer is right by induction (which is what they say to do at the end)
weary tiger
my thing gave the formula for n-th term
grim swan
but you can kind of see that every time you go up in the sequence, you multiply by pi and n^2, so accounting for the initial condition is should be pi^(n-2) (n!)^2 like godel said
oak turret
okay i think i get it thanks
mystic moss
@harsh warren yes!
harsh warren
@mystic moss hey! sorry to bother you again but i was trying to do the reverse just now, reducing HC to HP. and i found some solutions online which differs from one another, i'd like to seek your input
mystic moss
yeah gopher it!
harsh warren
so most solutions states to make a copy of a vertex, but some solutions take a further step to add an additional vertex to the copy and the original (like in this picture)
so i'm not sure why these 2 additional vertices are required
can't we simply just check if there exist a HP from the original to the copy
mystic moss
look at each direction. you want to show that a HP in this graph will give you a cycle in the original graph, and a HC in the original graph will give you a HP here
the additional vertices help you ensure the first direction
harsh warren
but if you remove the 2 additional vertices (v' and v) and just state that if there exist a HP from 1 to 1' in G', then there exist a hamiltonian cycle in G, wouldn't that work as well?
mystic moss
okay, so i give you a HP. what would the hamiltonian cycle be?
for example, 5 6 1' 3 1 2 [assume 2 was connected to 4] 4
wait mb
harsh warren
5 6 4 3 1' 2 1 - HP in G'
harsh warren
wait i thought is just returning a yes/no
okay, so i give you a HP. what would the hamiltonian cycle be?
@mystic moss
mystic moss
5 6 4 3 1' 2 1 - HP in G'
okay yeah fair
wait i thought is just returning a yes/no
yes, exactly
but basically you have to be able to show me that okay now that i've got a "yes" for G', how do i know i have a "yes" for G
and you want to do this using the actual HP that you've specified
harsh warren
wait i'm confused. we know that we got a 'yes' for G because we transformed G into G', and have used the HP algorithm on G' to return whether there exist a HP in G' or not. and then if the answer for G' is 'yes' then the answer for G is 'yes' as well
harsh warren
because we found a HP in G' (which we can achieve with/without the additional 2 vertices, v and v')
no?
5 6 4 3 1' 2 1 - HP in G'
this is the HP we found in G' without v and v'
mystic moss
yeah, exactly. so how do we know that there is a HC in G, with this information?
harsh warren
because 1' and 1 are the same vertex in G
wait maybe a better HP in G' will be 1 2 5 6 4 3 1'
and then we can clearly see it starts and ends at the same vertex in G
so here lies my confusion of the need for v and v'
mystic moss
wait maybe a better HP in G' will be 1 2 5 6 4 3 1'
exactly! you need to fix the starting and ending vertices
otherwise you get caught because the starting and ending vertices aren't always adjacent in the HP
does this make sense @harsh warren?
harsh warren
oh so by adding the 2 additional vertices with only 1 degree each, we know that the path must start and end at either of the 2 vertices?
mystic moss
yup!
harsh warren
i'm guessing this step is just to aid the construction of proofs right
mystic moss
yes exactly
near knoll
Can anyone help me with a question
glacial flame
@near knoll Dont ask to ask, just ask the question
near knoll
Bro really
near knoll
Ha that's actually hilarious
grim swan
@oak turret its your classmate
near knoll
That's a bro moment 😂
oak turret
@near knoll we struggling struggling
foggy cloud
so im kinda retarded but can someone help me lol
question: Ten points are placed in the plane with no two on the same horizontal line and no two on the same vertical line. Prove that there must be four points that can be joined to give an upward path, or four points that can be joined to give a downward path.
image: depicts the upward path. The points are any set of 10 points that satisfy the conditions listed.
it doesn't have to be that image it can be another image with 10 points satisfying the condition
grim swan
@foggy cloud for an upward path, do the x and y coordinate need to increase on every step?
foggy cloud
yes
grim swan
ok, i’m thinking there’s a pigeonhole princple argument in here somewhere
foggy cloud
i was thinking something like if you define the highest point, then from then on, the next point has to be below it, and either to the left, or to the right
but idk how to fit it into pigeonhole thing
grim swan
ok i have like a super ugly case argument that works lol
or basically it’s a series of drawings where you descend into a worst case scenario and then it still works
start with the furtherest left point. there are either at least 5 points above that, or 5 points below that
because the possible divisions of the remaining points are 0-9, 1-8, ...
foggy cloud
oh
grim swan
so let’s just say that there are 5 points below the leftmost point, the other case is symmetric
use that sort of thinking like 4 times and draw pictures lol
foggy cloud
but how to fit pigeonhole 😦
grim swan
it didn’t really use pigeonhole in the end
maybe there’s an elegant pigeonhole proof out there
somewhere
:’(
foggy cloud
so what i was thinking was along the lines of
ahh idk how to say it
I
I I
I I I
I I I I
that top thing is supposed to be in the middle
now the ones on the same level aren't actually on the same horizontal axis
dire void
Analysis? Algebra? (I’ve not done either.)
grim swan
though tbh you can pick up both of those as you go along
no you definitely don’t need either of those
graph theory is ground level
minor dagger
if you can understand basic logic and operations on sets u think youll survive
dire void
okay. I have like zero skill points in combinatorics.
grim swan
ok pop quiz
minor dagger
maybe linalg too
grim swan
linalg would help yeah
but not strictly required to get going
ok anyway the pop quiz
dire void
My lin alg is prolly my strongest math right now.
grim swan
i have n points in space
i draw lines between some of them
maybe all of them, maybe none of them, maybe some of them
how many ways are there to do this?
dire void
at most n!
grim swan
ok that’s an upper bound but the actual number is smaller
last sigil
hmm, there is a theorem that tackles the increasing/decreasing problem above called the Erdos-Szekeres theorem
last sigil
Yeah, i've never encountered it before and there is a proof using pigeonhole
grim swan
knew it
i had another lead that actually looked promising
take the left most point, right most, top most and bottom most
this forms a rectangle bounding everything else
and you can use this to naturally partition the rectangle into 5 pieces
there are also 5 points left
trying to see if there’s an elegant way to proceed
anyway @dire void can you try computing it for n = 1, n = 2, n = 3?
dire void
You want some kind of n choose k argument?
grim swan
yeah it’ll end up being that
dire void
Is this subject normally a graduate level subject?
grim swan
nah
i mean, there are mathematicians who do only graph theory
but people start learning in undergrad
dire void
okay. Cool cool.
grim swan
you really don’t need anything to get started
near prawn
except a high pain tolerance
dire void
Lol.
grim swan
draw the horizontal from the leftmost point until it intersects with the vertical from the bottom most point
ok yeah i think you got it
you get 4 outer regions and a center region
having even 2 points in the center is enough, so go ahead and assume there’s 1 point or less in the center
vital dewBOT
ppper:
harsh warren
hi i'd like to check if this notation i built makes sense, can someone tell me what they understand of G' from the notation i built below?
vital dewBOT
ppper:
mystic moss
i think they're adding a vertex to the graph and connecting that vertex to all of the vertices in the original graph (for the HP-HC reduction i'm guessing?). i understood, @harsh warren, but as ann said it seems a bit awkward. like for example maybe denote the edge as (r, t), and define r beforehand (not while building W)
stray reef
why do you even need to write this notationally
like
whats wrong with a verbal desc
'add a new vertex r to G, and connect it to every vertex in G'
harsh warren
i think they're adding a vertex to the graph and connecting that vertex to all o...
yeah exactly this
harsh warren
why do you even need to write this notationally
i feel like it makes it more formal, i was thinking of giving a description as well as a notation
stray reef
no it makes it more obfuscated
harsh warren
hahah ok i might do away with it then
gentle nebula
it doesn't make things any more formal if it is harder to read
people will just hate you more
notice how a lot of things in the adv math section used words
harsh warren
yeah i totally agree but in the example answer my lecturer used a notation form to express his answer so i thought i might do the same
but anyway, thanks for the input and suggestions everyone!
valid wave
a vertice?
stray reef
no
(also, it's vertex, not "vertice".
one vertex, two vertices.)
anyway, no
a clique is a set of vertices which are all connected to one another
this definition should have been given somewhere in your graph theory course
valid wave
ah
so in that case
would 1 be the solution
no wait
that has the most
5 would be the answer then
stray reef
ok first off
there's no such thing as"the" answer here
there are many cliques here which aren't maximal
but you seem to not even understand what a clique is
it's true that each vertex taken by itself forms a clique
but for example
{1,4,5} is a clique in this graph
but {2,4,5} is not a clique
do you understand why {1,4,5} is a clique but {2,4,5} is not? y/n
valid wave
not exactly
stray reef
a clique is a set of vertices which are all connected to one another
a clique is a set of vertices which are all connected to one another
do you understand now why {1,4,5} is a clique but {2,4,5} is not? y/n
valid wave
yes now i follow
glacial flame
Is one vertex by itself a clique?
Mathematical definition of clique helps me understand what a military/political/state clique is 🙂
mystic moss
Is one vertex by itself a clique?
vacuously since there are no pairs of vertices, every pair of vertices is connected through an edge
glacial flame
The definition given here didnt metion edges
stray reef
yes a single vertex is a 1-clique
glacial flame
Then he can just give a vertex and that would be the solution 🙂
He should prove though that there is a bigger clique.
But clique does not count the weights of the vertices, just the number of the vertices themselves?
Wait, these are not weights on the vertices, but their identifiers 😐
?
stray reef
who's "he"
glacial flame
The original poster
remote mulch
somtimes different a from set A can be mapped on the same b in set B
if we take the inverse of those functions won't that have like two outputs
are they still a function then
pale epoch
those functions don't have inverses
remote mulch
so inverse is only for bijective functions?
pale epoch
basically
notice though that we still use the notation $f^{-1}$ even for non invertible functions
but then this denotes the preimage
vital dewBOT
Lochverstärker:
remote mulch
alright thx
wanton sable
can someone help me figure out what i'm doing wrong here?
i feel like my path definitely is a euler circuit but i don't know why it's being marked as wrong
proven shard
Hi sushi hammer
bitter moss
Ay if someone dont help sushi hammer im aboutta get mad
@wanton sable ur correct in ur answer rite
Maybe add commas between the vertices?
sonic path
hello
errant bear
bye
errant bear
um
twilit apex
Hi, i'm new with Algebra; can i ask questions about that topic here?
glacial flame
can someone check this for me please
Hmmm, seems like a really nice proof. I have to doublecheck it though.
Although you can skip the first two lines. Also the third line =O(n^5) where did that come from?
I would start like this.
The definition:
f(n) = O(g(n)) means that there exists a positive k and n0 such that for every n>=n0 it is valid that f(n)<=k*g(n)
g(n)=n^6
f(n) = 1^5 + 2^5 + ... n^5 <= n^5 + n^5 + ... + n^5 = n*n^5 = n^6 = g(n) , for each n.
Thus the existing k and n0 are for example k=1 and n0=1
shell ledge
Another solution is that the polynomial for 1^5 +2^5......n^5 is a polynomial of degree 6
Which isn't hard to prove using induction
urban olive
Guys, I have this set of premises , and the teacher said we need to find a contradiction using laws and inference rules
Any idea on how to start or set this up?
urban olive
<@&286206848099549185>
errant bear
what does the first and second imply if p
urban olive
if p, what do you know about q
That if p is true, then q needs to be true for the expression to be true
Otherwise, would be false
In the second statement
Also I see all of them involves p
urban olive
We have the same situation there
We suppose p is true but we don't know if (q -> r) is true
errant bear
but what do we know about q, from earlier
urban olive
That needs to be true
urban olive
We got R
errant bear
do you see a contradiction?
urban olive
Not really
errant bear
look at the 3rd expression
urban olive
Oh yea
If P is true then we got -R
But from from earlier we show that if P is true we got that R is true too
So there's the contradiction?
errant bear
yup
errant bear
well R can't be both true and false
sour brook
How would one use the pigeonhole principle on the following question? A bowl contains 10 red and 10 yellow balls. How many balls must be selected to ensure 3 yellow balls? If we use the "worst case" method where the first 10 balls are all red, and you have 3 yellow ones after that, the answer is 13. But how would one put this into the form of ⌈N/k⌉?
stray reef
you wouldn't
halcyon sierra
Let $G$ be a graph and $e$ an edge of $G$. Let $G_e$ be the subdivision of $G$ at edge $e$. Show that $\mathcal{C}(G)$ has a sparse basis if and only if $\mathcal{C}(G_e)$ has a sparse basis.
TheRad1:
halcyon sierra
I'm doing this proof for HW, I want to say that if a graph is planar, any topological minor of it is also planar. I can't think of something to cite for that.
I have MacLane's Theorem saying "A graph is planar iff its cycle space has a sparse basis."
stray reef
what's a subdivision, what's a cycle space, and what's a sparse basis?
halcyon sierra
subdivision is taking an edge ab and splitting it into 2 edges ac and cb
cycle space is the vector space created by linear combinations of cycles of a graph
sparse basis is a basis where each edge only appears in no more than 2 elements of a basis of a cycle space
stray reef
hmm...
im not sure i understand your defn of cycle space tbh. do you have a more precise construction?
halcyon sierra
Consider a graph with $m$ edges. Consider vectors in $Z_2^m$. A vector
\begin{pmatrix}
1 \\
0 \\
1 \\
1 \\
0 \\
0 \\
\end{pmatrix}
would correspond to a cycle in the graph formed by edges 1, 3, and 4.
TheRad1:
Compile Error! Click the 
reaction for details. (You may edit your message)
stray reef
oh, these are F2-vector spaces?
rugged sleet
can anyone guide me on where to start with this question
stray reef
think about what properties the tile size must have
specifically, it must be divisible by 280, 336 and 168
and also be as big as possible since you want to use as few tiles as possible
rugged sleet
so im looking for the gcd of they 3 numbers
stray reef
that'll give you the tile size, yes
shouldnt be hard to get the tile count once you have that
rugged sleet
yeah just total area / area of tile
torn adder
Hi there. Before I ask a question, I would like to state that I am preparing for my exam tomorrow and have questions from my semester tests that I'd like to get answers to here. Is that alright, as I don't want this to be construed as asking for helping with an exam?
pale epoch
if you are not asking during the exam, its fine
torn adder
Nice! My exam is still 16 hours away xD yes, I am counting the seconds
Write down a recursive definition of the set S that consists of all binary strings that satisfy all of the
following properties:
• the string ends with 0, and
• the string has length at least two, and
• the length of the string is even.```
How would I do this question correctly? My answer was:
- 00 = A
- 10 = B
- So = A V B
Definition of set S:
S_0 = A V B
S_n = S_(n - 1) x (A V B)```
stray reef
this reads as nonsense
torn adder
Understandably. That's why I'm asking my question here. I couuldn't find an answer after googling for quite a while
stray reef
this is the simplest recursive defn you can have:
- 00, 10 ∈ S
- ∀s ∈ S, ∀x, y ∈ {0,1}, xys ∈ S
torn adder
That second part. It logically translates to
For all elements s of the set S, and all elements x and y of the set {0,1}, there is a combination of elements xys that will be an element of the set S.
Is this correct?
stray reef
this wording kinda sucks ngl
also "combination" please what
xys denotes the concatenation of x, y and s in that order
im saying that if you take any string in S and append any two bits to its left, you'll get another string in S
torn adder
Ok. Please, correct me. I understand that I am failing miserably in your eyes right now Ann, but please, try help me understand correctly 🙂
torn adder
im saying that if you take any string in S and append any two bits to its left, ...
That makes a ton of sense
but how do you enforce this property?:
the string ends with 0, and
torn adder
isnt it obvious
No. Hence the question
stray reef
the two 2-bit strings i declare explicitly as members of S end with 0
and the construction rule of appending two bits of whatever to the start
doesnt do anything to the end
torn adder
oooh
and because s ∈ {00,10} and s is always at the end of xys, the rule is enforced?
stray reef
s need not be in {00, 10}
that would make the rule only applicable once and then never again
at the risk of stating the obvious, yes, the ending symbol of xys is the same as the ending symbol of s.
stray reef
you mean a relation?
torn adder
yes
sorry, wasn't concentrating when I typed that
Ok never mind, found my answer on stackexchange. the answer I found is that:
The relation R is antisymmetric if, whenever xRy and yRx it holds that x=y.
An example of a relation that is antisymmetric but not reflexive is > on the set of integers```
flat harness
yes
foggy cloud
if im trying to prove a statement true for all integers n>=1, and while using induction, and I use the assumptions that the statement is true for n=k-2, n=k-1, n=k. I use n=k to prove that n=k+1 is true. would I require 2 base cases since theres n=k-1 and n=k-2?
flat harness
if you need to use the fact that it holds for k-2 then yes
cause then the indictive step wont garuntee that you can go from 1 to 2
foggy cloud
oh
and for induction proofs, do I HAVE to use k to show k+1 is true?
what happens if I assume k is true, and show that k+2 is true
coral raven
then you can only get k, k+2, k+4, k+6
foggy cloud
oh
coral raven
you see it?
foggy cloud
yes
flat harness
but if you have that funky 2 step induction and you have it for n=1 and n=2 then you have al integers
keen drum
would it be 2^26?
keen drum
actually, would it be 2^(13*13)?
keen drum
ok i hate sets and stuff now thinking about it makes my head hurt
wait if its the power set of all ordered pairs in that ^2
wouldn't it be like 2^2^(13*13)?
weary tiger
In each part below, give a formal proof that the sentence given is valid or else provided an interpretation in which the sentence is false.
(a) ∀x[Y'(x) ∧ Z(x)] → ∃x[Z(x)].
(b) ∃x[Z(x)] → ∃x[Y'(x) ∧ Z(x)].
Please @ me or DM me if you can help.
Thanks in advance
last timber
@weary tiger still need help?
weary tiger
@last timber yea u there?
weary tiger
wait
last timber
can you express a in words?
weary tiger
do u mind DMing so we don't clog the chat?
weary tiger
ok whichever u prefer if it's fine I just wasn't sure
last timber
can you express a in words?
anyway
weary tiger
sure
For all x the condition y(x) is false and z(x) is true implies that there exists an x such that z(x) is true
@last timber
last timber
and how do you think, is that true?
weary tiger
I think so, yes
last timber
i would btw word a bit another way but your way still is appropriate
yes, you are right
because you have that logical conjuction (AND) is true for all x
and conjuction involves Z(x)
and A AND B is true iff both A and B are true
thus it is obvious that if for all x P(x) AND Z(x) then Z(x) is true for at least one x
ok with second one
can you again word it?
weary tiger
yeah but the thing is I need a formal proof using inference rules not with words
I tried with words but my teacher wants it in steps with the inference rules listed
but yeah we can do the second real quick
there exists an x such that z(x) is true which implies that there exists an x such that y(x) is false and z(x) is true
for this one I also think this is true
last timber
@weary tiger for a) with interference rule is A ^ B = T therefore B
for second one you are wrong
[Y'(x) ∧ Z(x)] = T requires that Y'(x) = T
but you know nothing about Y(x)
weary tiger
right but we don't necessarily know it's false
last timber
yes, but neither we do if it is true
last timber
@weary tiger yes
you are wrong in the sense that without any info about Y you can assume nothing
last timber
i mean i can construct a bucnh of examples in suppost of b) or counterexamples
thus conclusion derived in b) is invalid
weary tiger
can you give me an example
last timber
for all x Y(x) is true
and for all x Y(x) is false
first one is counterexample, second one is example in suppost
opaque fern
last timber
does this have sol tho
since 2 and 10 are not coprime
and 3 and 9 as well
ah wait
10, 1001 and 9 are comprme
remote dock
how to you know if function is SOP or POS or neither?
orchid lily
Hi, can anyone help me prove that the two sides sides are equal?
Or just to give me a hit
I am thinking about rewriting this 3^n as (1+2)^n
last timber
(provided he knows binomial formula)
orchid lily
There is no problem, I just have to prove that the left side is equal to the right side
last timber
do you know binomial formula
orchid lily
lol, just realised what I just said
stray reef
and does the binomial theorem applied to (1 + 2)^n not do just that?
last timber
apply it to (1+2)^n
stray reef
$(1+2)^n = \sum_{k=0}^n \binom{n}{k} 1^{n-k} 2^k$
vital dewBOT
Ann:
stray reef
orchid lily
Thank you so much, I was just going to do the same
orchid lily
i wanted them apply it by themselves
I agree here, binomials make me cry..
Thank you @stray reef ❤️
harsh warren
i'm not sure if it's an appropriate channel but can someone explain how the 2nd line is derived from the 1st?
last timber
are you familiar with scalar multiplication and vector addition
harsh warren
yeah i believe so
last timber
so what is rhs then
harsh warren
but we don't know the value of a1 and a2
harsh warren
for example a1 could be 1x2, 2x2, 3x2, etc
vital dewBOT
Ann:
last timber
in other words a_1, a_2 are just some numbers
harsh warren
assuming it's 1x2, then it's (a1, 0) + (a2, 0)
oh just a number
oh wait yeah i think the answer i gave above is when a1 and a2 is a scalar, not a 1x2 vector
so do we just ignore all the 0s on the bottom?
last timber
not ignore but a*0 = 0
last timber
yes
harsh warren
so what do you mean by a*0 = 0
stray reef
any number multiplied by zero gives zero
last timber
that you do not ignore 0's, but yes you will eventually have 0=0+0 which is trivial
harsh warren
but where is this multiplication done
last timber
how is scalar multiplication performed
harsh warren
each value in the vector is multiplied by the scalar?
last timber
yes
harsh warren
but in the equation above, i'm left with vectors, so i'm unsure where you performed any scalar multiplication
oh wait nvm
i get it, that's where the vector addition comes in
i'm an idiot
last timber
then recall that vectors are equall iff all their coodinates are paiwise equal
last timber
yw
karmic nymph
cobalt sky
so we have 8 candidates (8C4)
Then for the second part (referenda = there are 3 options (yes, no, empty)
8C4 * 5C3
Is the right?
burnt herald
can someone explain countable sets?
I don't understand the definition, as well as the example of the functiion shown on the right
last timber
@burnt herald countable set means that it is of the same size as set of naturals
that is why we call it is countable, we can "count" it by the naturals
informally, set with n elements is finite, that is, we can enumerate it by 1, 2, 3, ..., n.
and countable set is set which we can enumerate by all naturals
like 1,2,3,4,..., n...
burnt herald
@last timber Thanks, I understand that part, but the definition "same cardinality as the set of positive integers", Im confused with that
last timber
and countable set is set which we can enumerate by all naturals
do you understand this?
burnt herald
is this set of positive integers defined by the question, or is it saying 1.2,34...infinity
burnt herald
do you understand this?
yes
last timber
this is just another way of saying "it has the same cardinality..." the latter being rigor
because if we can enumerate all items in the set A by some subset of naturals like 1,2,3..., n, then it is obvious that |A|=|{1,..., n}|
this is for finite set
and for countable set it is just generalization: we define one-to-one correspondence between the whole N and the set A
last timber
is this set of positive integers defined by the question, or is it saying 1.2,34...
{1,2,3,...n, ...} is set of positive integers and is the same as set of naturals (unless u define N to include 0)
flat harness
the easiest way I think of countable is if there is a surjection from the natural numbers to the set in question
if yes, countable
burnt herald
is the set input or output?
sorry still trying to link everything and make sense of it
last timber
is the set input or output?
wym
potent oracle
pale epoch
why did you ping helpers without asking a question
pale epoch
well, what do you think?
weary tiger
well for the first one i thought of was c
pale epoch
why?
weary tiger
because i think its saying its not 4-6 and it not a weekday which is true for the statement?
@pale epoch
pale epoch
"its saying its not 4-6 and it not a weekday" that is true
do you think left turns are allowed on weekends even when not between 4-6?
weary tiger
yeah
pale epoch
eh i actually meant: do you think left turns are allowed on weekends between 4-6?
weary tiger
well you can left turn on weekends between 4-6
pale epoch
ok, but answer c) implies you can only left turn if its not a weekday AND not between 4 and 6
pale epoch
but you just said that left turn on weekends are ok no matter the time?
weary tiger
yeah buecause its not a weekday
pale epoch
exactly
so left turns are allowed if its not a weekday or not between 4 and 6
right?
pale epoch
right
the other exercises is just mechanical
you should re-read on how truth tables work
weary tiger
ik i found a video and i should be able to figure it out
lilac bear
<@&286206848099549185>
Does anyone have any idea how to show this?
Let a be an ordinal, show that a U {a} is the smallest ordinal containing strictly a
thx
potent oracle
<@&286206848099549185>
lilac bear
@minor dagger you would know how to prove that? I understand why it's true, but I don't know how to prove it.
minor dagger
😎
potent oracle
erm I don't get the symbols for d 😕
sleek swallow
$\floor{x}$ is the floor function and for any $x \in \bR$, it spits out the greatest integer that is less than or equal to $x$. $\ceil{x}$ is the ceiling function and for any $x \in \bR$, it spits out the least integer greater than or equal to $x$.
vital dewBOT
Abhijeet Vats:
sleek swallow
@potent oracle
sleek swallow
You asked what the symbols were for part d) and I addressed that
Were you referring to something else?
potent oracle
oop I got them answered
potent oracle
pallid lintel
Is there any good textbook that will teach me discrete geometry
minor dagger
#book-recommendations ask here
grim swan
@weary tiger try inducting on the number of vertices
weary tiger
What would be my induction step? I struggle with induction on graphs
grim swan
you know for some fixed n>=3 that any connected graph with n vertices can have 2 vertices removed and remain connected
prove that any connected graph with n+1 vertices can have 2 vertices removed and remain connected
you may need some other stuff along the way, i haven't fully worked it out, but im pretty sure this approach will work
like as i try to think this through, i think it might be easier to prove every connected graph with >= 2 vertices can have 1 vertex removed
and prove that any connected graph with n+1 vertices contains a connected graph with n vertices
all of this should still involve induction
weary tiger
@grim swan is it possible to hop on VC ? I'm a lil confused on why I'm not inducting on the number of edges
grim swan
Can't sorry, but also inducting on the number of edges could work
willow root
does anone know how to do this?
grim swan
Find an injection (0,1) to [0,1]
Then find an injection the other way
For the other way, shrink the interval [0,1] so it fits inside (0,1)
willow root
Bless you
To find an injection, do we just set a f: (0,1) -> [0,1] defined as something like f(x) = y?
grim swan
Yes you want function, idk what your definition means though
willow root
I just defined the function as f(x) = y such that x∈ (0,1) an y∈[0,1]
i dont know if thats right
grim swan
That's not a definition
What is f(.5) for example?
You need to define a specific rule
willow root
welll wouldnt f(.5) = y for some y∈[0,1]?
grim swan
Yeah which one
You gotta tell me
Otherwise you haven't actually defined the function
willow root
omg this is making sense
grim swan
It's supposed to make sense Rigby
lilac bear
<@&286206848099549185>
Does anyone have any idea how to show this?
Let a be an ordinal, show that a U {a} is the smallest ordinal containing strictly a
thx
willow root
@grim swan so I defined g: [0,1] -> (0,1) via g(x) = (x/2) + 1/4 such that x ∈ [0,1]
is this right?
weary tiger
Question, if for every two distinct vertices there exists a hamiltonian path, how can i prove that the graph is hamiltonian
stray reef
why is the last option correct as well when e4 is not included?
you don't need to include e4
summer drift
grim swan
is this right?
Yes, and yes to your previous question
burnt herald
> why is the last option correct as well when e4 is not included?
you don't need...
Thanks!~
is this acceptable?
or do I also need to include "mod 4" on the third last line?
stray reef
looks fine as long as you didnt mess up the arithmetic anywhere
burnt herald
looks fine as long as you didnt mess up the arithmetic anywhere
actually I can skip the third last line and go straight to 3^2?
stray reef
maybe, depending on how anal the grader is
mystic moss
Question, if for every two distinct vertices there exists a hamiltonian path, ho...
try this using induction. also about your previous question--if you've proved that any tree has at least two leaves, try using that directly.
burnt herald
maybe, depending on how anal the grader is
thanks!
potent oracle
Can someone show me how to do this?
Let A = {1, 2, 3, 4, 5}. The following relations are on A
R1 = {(1,1), (1,2), (2,1), (2,3), (3,2), (4,4), (2,5), (5,3), (3,5)}
R2 = {(1,5), (3,5), (2,3), (4,5), (3,3)}
R3 = {(1,1), (1,2), (3,4), (4,4) (1,5), (3,3), (5,5), (2,2),(2,5)}
R4 = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4), (4,5)}
(i) Find R2 U R4. State whether or not if it is reflexive, irreflexive, symmetric
or asymmetric.
it's a practice question similar to an assignment one
quaint star
What have you been able to do? And do you know the definitions of all those terms? @potent oracle
potent oracle
no I don't on both accounts @quaint star
quaint star
You can't find the union?
It's the set containing all the elements in R2 and all the elements in R4
lapis wharf
who's smart
candid hollow
how can i solve A∩X=B?
with A, X and B in P(E) for some set E
i've tried manipulating the equation but i didnt get anywhere
pale epoch
what do you mean by solve?
candid hollow
solve for the set X in terms of A and B
pale epoch
there is no solution if B is not a subset of A
candid hollow
yea
pale epoch
and if B is a subset of A, the only solution is X = B
pale epoch
ehm, the intersection is at most as big as X
ah, wait
you are right, im wrong
you can add to X any element that is not in A
candid hollow
ye
btw the answer is any set that includes B and is a subset of (the compliment of A in E) U B, and i want to prove that
pale epoch
well, first show that any such such that satisfies the equation
then show that if X lacks an element of B or has an "extra" element that is not in (the compliment of A in E) U B does not satisfy that
candid hollow
so you're asking me to prove X is included in (the compliment of A in E) U B using a proof by contradiction?
ooo
pale epoch
essentially, that is one part of it
candid hollow
i actually got it i think
pale epoch
i think that is the easiest way
candid hollow
A∩X=B so x in B => x in A and x in X => x in X so B is included in X
and for the 2nd part, if we assume there exists an x that's in X but not in (the compliment of A in E) U B, that means the x is in the compliment of (the compliment of A in E) U B which is (by some manipulations) equal to A\B, but this contradicts our initial assumption that A∩X=B because x is in X and in A but not in B
is that right?
pale epoch
looks good
then you just have to show that all X with your stated property, actually satisfy the equation as well
pale epoch
sure 👍
candid hollow
@pale epoch btw do you think there's a way to solve it directly?
candid hollow
yea
pale epoch
i don't
candid hollow
rip
pale epoch
well, if you argue that certain things are obvious, then yes
like, you can reformulate this as $A\cap X \subseteq B \land A\cap X \supseteq B$ and then continue arguing
vital dewBOT
Lochverstärker:
pale epoch
if i have (1,2) and (2,1), does that mean (1,1)
yes
pale epoch
if it's already there, adding it won't change anything
pale epoch
but if you are following some algorithm, you probably won't add it again
as you want the algorithm to terminate
rugged pebble
@pale epoch do you think you can tell me the transitive closure on this relation to see if im doing it righ t
R = {(1,2), (1,3), (4,3), (5,1), (5,5), (3,1)}
pale epoch
well, what did you get
pale epoch
seems right
rugged pebble
lol i hope
rugged pebble
Can someone help me prove or disprove this
If R is a partial order on set A, then there is at most one greatest element in A
im pretty sure its true, like i can kinda explain why, i just dont know how to do it in a proof
coral raven
transitivity?
rugged pebble
wdym?
orchid sand
who have a idea about logarithmic function ?
deft dock
yo guys
I am trying to understand why the proving of riemann's hypothesis is important for the distribution of prime numbers, and why the distribution of prime numbers is important as well.
anyone can help?
pale epoch
the very short version is that there is a deep connection between the zeta function and the prime counting function
and proving the riemann hypothesis would lead to a better approximation of the latter
the distribution of prime numbers is not important outside of mathematics
quasi garden
aRb iff |a-b|>=3 I need to show if this is transitive or not how do I solve 
stray reef
@quasi garden do you still need help w this
last timber
this is not true tho
quasi garden
<@354836575944966155> do you still need help w this
Yes
stray reef
"3 Nd +"?
stray reef
the interval [-3, 3]?
or just the integers in that interval, so {-3, -2, -1, 0, 1, 2, 3}
quasi garden
0 to 9
quasi garden
Ok sorry
quasi garden
stray reef
so the domain of your relation is {1,2,3,4,5,6,7}
ok
that makes it a bit easier for me to show you things
3 R 6 and 6 R 2, but not 3 R 2
stray reef
what equation?
quasi garden
We can prove by only giving example and not by solving?
By not solving aRb bRc Nd then getting aRc for not transitive
last timber
by example you can disprove or prove existence
stray reef
is... "Nd" your spelling of "and"
stray reef
We can prove by only giving example and not by solving?
we're DISproving transitivity using a COUNTERexample
quasi garden
Ohk thank you 😇
quasi garden
is... "Nd" your spelling of "and"
Typo
stray reef
you've done it like three times
quasi garden
Ikr 😧 . Short forms
weary tiger
@stray reef
stray reef
??
stray reef
.................... why are you asking me in this channel
also it's none of your business
stray reef
-_-
stray reef
no
and also this is the wrong channel
why's it me specifically that people choose to just bother randomly
urgh
modern arrow
hi guys