#discrete-math
weary tiger
weary tiger
because there are 26 letters in the alphabet
gusty bay
Sure
weary tiger
wouldnt it be 26+26
gusty bay
No.
weary tiger
oh
gusty bay
26*26 would imply that you have 26 options for the first letter, and 26 for the second
Is this what you're trying to find though? All possible two letter combinations?
weary tiger
yeah
weary tiger
would it be 2?
gusty bay
What's your final answer?
weary tiger
gusty bay
No
weary tiger
im so confused
gusty bay
Well
okay
I see how you did that
A better way of thinking about this would to say 2*26
It's the same thing, but it's better in this sense:
You have two options for the first letter, and 26 for the second
This is a more general approach that works with other things
Adding is a very specific approach that doesn't always work
Does that make sense?
weary tiger
gusty bay
So yes, the answer is 52
weary tiger
yeah I get what youre saying now
gusty bay
Your reasoning is shaky
You have two options for the first letter, and 26 for the second
weary tiger
thank you
@gusty bay
wouldnt this be true tho?
If the union of two sets is empty, then each set is empty as well. Therefore, if the union of two sets is empty, then they are disjoint (both being empty).
dapper rose
you are correct
weary tiger
@dapper rose so how would this statement be incorrect?
this is for my final and he said they are all incorrect did he make a mistake>
?
dapper rose
ye this question seems wrong
weary tiger
so weird... do you think I should say this is correct? @dapper rose
dapper rose
ye, and I would email the person in charge
last sigil
Just provide a counterexample
weary tiger
would it just be if n is = to an odd number or is that too easy?
dapper rose
isn't this assessed
weary tiger
im not understanding your 24 is 8n statement
gusty bay
@weary tiger Question 2 is correct, seems to be a typo
weary tiger
@gusty bay thats what im thinking as well
weary tiger
yeah
tepid smelt
but i think that he wants you to say intersection rather than union
weary tiger
what you mean
sleek swallow
$A \cup B = {x \in A : (x \in A) \lor (x \in B)} = \phi \implies (x \in A) \lor (x \in B)$ is false. Hence, there are no elements in either A or B.
$A \cap B = {x \in A: (x \in A) \land (x \in B)}$ has to, then, be empty since both propositions in the conjunction are false. There are no elements that satisfy the given open sentence. Hence, they are disjoint.
vital dewBOT
Abhijeet Vats:
wooden spear
HA this is a good example of a non-expert designing a question
I can see what they did
Correct statement: "If the intersection of two sets is empty, the sets are disjoint"
"Hmm I want to turn it into a false statement for the exercise so I'll change intersection to union"
😵
weary tiger
@wooden spear so you think I would be safe to say that its actually true? Because technically it is
wooden spear
It depends on whether the person grading it is a mathematician or not
sleek swallow
?????
wooden spear
⁉️
sleek swallow
Dafuq
Like I proved earlier, if the union is empty, the open sentence must be false and both propositions must be false.
clever nacelle
In Theory of Computation: give an example of a computable language
lethal sequoia
,w permutation (2346)(3425)(54)
vital dewBOT
lethal sequoia
@dapper rose I got something like this but it’s not the same as my result
My result was (1)(2536)(4)
vital dewBOT
Requested by EpicGuy4227#1118
lethal sequoia
Okay great! Thanks! I was so confused lol
Kept checking numerous methods with my answer for an hour or so
dapper rose
np
open glacier
How do i form bijection between [4,inf) and (2,10)
Task is to prove equivalence by forming bijection between those sets
glossy adder
construct one between (4,inf) and (2,10) first
this is easier because of reasons
use something like tan
open glacier
@glossy adder ive got no idea how to do that
faint narwhal
He told you how
open glacier
Dude i don't know how to use tan to form a bijection between sets
I don't see him giving instructions for that @faint narwhal
pale epoch
i told you yesterday, that you can do it in steps, because the composition of bijective functions is bijective. you could e.g. go from (4, inf) to (0, inf) to (0,1) to (0,8) to (2,10)
or do something similar with tan
if you don't know how to construct bijections between any sets, maybe you should try studying
deep jewel
I think we use tree probability and bayes' rule to solve this problem but
I am not certain if my p(2/5 defects) or p(2/5 defects given there's a defective printer) are correct
the second image is what i wrote up
can anyone confirm this?
river leaf
Hey guys.
Let $n \in \mathbb{N}$ and $(a_1, a_2, \dots, a_n) \in \mathbb{Z}^n$.
Prove that there are $i, j \in {1, \dots n}$ with $i \leq j$ so that:
$$ n \text{ divides } \sum_{k=i}^{j} a_k$$
Can someone give me an approach for that prove?
vital dewBOT
Paul2708:
faint narwhal
There's a nice pigeonhole argument here
weary tiger
What have you thought of so far? @river leaf
river leaf
Honestly, I have no idea how to start.
I tried to get a pattern by doing some examples, but I'm not sure how to solve it in general
weary tiger
Okay
Consider the sums a_1, a_1 + a_2,..., a_1 +...+ a_n @river leaf
And like Zopherus said, you can use the pigeonhole principle
But before that you have to figure out how you can use it 
Ping me if you want more help
river leaf
So we tried to figure out what the containers are. Well, we assume that the n elements are s_n = a_1 + ... + a_n like you already said. We tried to build the differences s_n - s_(n-1), ..., s_n - s_1 as (n-1) containers, but we think that's not the right way. xd @weary tiger
weary tiger
I could give you one more hint @river leaf
But the problem is instructive imo so I guess it would be better if you keep thinking
Hmm I guess I could give you a little hint which doesn't spoil much if you want
river leaf
I would take it :p
weary tiger
Okay so you have to show that n dividies something
Do you know any stuff which is related to divisibility?
river leaf
Just the definition: a|b <=> ax = b
river leaf
gcd(n, x) > 1?
weary tiger
It's also about remainders and stuff
river leaf
Well the last thing I can think of are zero divisors?
river leaf
yes ^^
weary tiger
Okay so when does n divide a number a
river leaf
if a = 0 (mod n)
river leaf
If s_k = 0 (mod n) => i=1, j=k
Otherwise..?
river leaf
There is not always a k with s_k = 0 🤔
river leaf
I'm aware of that.
So to get to 0, we have to subtract sums.. I'm sorry for being so lost xd
weary tiger
Ecactly! @river leaf
But that's not always the case
We can also have all sums having different remainders mod n
Which would imply that one of them is 0 mod n
But in case not all have different remainders, 2 must have the same so you can subtract them like you said @river leaf
Do you see what I mean?
river leaf
Yes, I understand
And the containers regardig to the pigeonhole principle are the sum remainders from 1 to (n-1)?
clever nacelle
In Theory of Computation: give an example of a computable language
Would this be something like turning 1s into 0s?
pale epoch
what makes you think that
tbf i'm not sure what a computable language is supposed to be, i know what a decideable language is or a computable function, but i have never heard of the term computable language
wait, computable is just a synonym for decideable in this case
then the answer is no
clever nacelle
Thank you for replying, computable is not the same as decidable.
pale epoch
how is it defined then
lethal sequoia
@fossil otter hey, was the answer n! ?
fossil otter
no
fossil otter
wait
yeah no
there are actually two ways to approach the problem
the first is the way i described before
the second is to choose what elements you want in the cycle first, and then how many cycles can be formed by those elements
@lethal sequoia
gusty bay
In my class, they say that a set is countable if you can form a bijection between it and the naturals or a subset of the naturals
Wouldn't an injection suffice though?
Since that would prove $|S|\leq|\mathbb{N}|$?
vital dewBOT
Momo:
stray reef
does your class define countable to mean countably infinite
ie the classes of finite sets and countable sets are disjoint, with their union given the name of "at most countable"
glossy adder
well that's what they said was said in their class
presumably by their prof
an injection would suffice in that case but it's trivially equivalent anyway
if you have an injection to a subset of the naturals you can just restrict the codomain to get a bijection to a subset of the naturals
stray reef
not my question
does your class say countable to mean countably infinite only
or are finite sets considered countable as well
gusty bay
finite sets are countable
lethal sequoia
@fossil otter I give up....
fossil otter
@lethal sequoia
lethal sequoia
@fossil otter Thank you so much! That makes a lot of sense
I just couldn't see it
fossil otter
It's np, counting problems can be tough
lethal sequoia
Yea, combinatorics is the hardest class I'm taking right now
plucky stirrup
hey guys i am confused about reading this
is it saying ( A intersect B ) is a subset of A
stray reef
yes
plucky stirrup
or is it saying A intersect B & B is a subset of A
ok so the first one
gotcha yeah that makes
sage bloom
what is the big O of log n ?
Is there some property of log that we can leverage to figure this out?
sick yarrow
if v(x): x is a manager
and
M(x,y): x earns more than y
What is the logical expression that states
"Every employee who is not a manager earns less than every employee who is a manager."
If anyone could help that'd be awesome ❤️
sleek swallow
$\forall x,y: \lnot{v(x)} \land v(y): M(y,x)$
For all x,y such that x is not a manager and y is a manager, y earns more than x.
vital dewBOT
Abhijeet Vats:
sleek swallow
That seems to be the correct logical expression, but I'm a bit uncertain about the notation I've used. It seems rather......unsatisfactory for some reason :/
@sick yarrow
sick yarrow
appreciate it 🙂 Good enough for me to read. And it helped.
sleek swallow
No worries
tranquil jewel
Where can I get some really good notes and stuff that cover most or all the topics and things in discrete math
pale epoch
discrete math is a very vague term
tranquil jewel
weary tiger
did you figure it out @gusty pasture ?
weary tiger
LOL
gusty pasture
Test n = 1 5-1=4 1/2(3+5) = 4 n=1 holds
n=k
k
E (5j-1) = k/2(3+5k)
j=1
how does that look?
weary tiger
what is the j=1 part?
gusty pasture
yes
no idea how im supposed to repersent that on a normal keyboard
so i just type "E"
vital dewBOT
Botnuke:
weary tiger
uh
wooden spear
Boolean algebra nice
weary tiger
what are the other options for the set one
gusty pasture
they all pull from the same answers pool
the ones i havent used are
(A U C) n (A U B)
8
7
x + yz'
x'y
thats it
weary tiger
dont think what you had for the set one was right
was the other answer choice (A U C) n (A U B) or was it (A U C) n (C U B)
i dont think associativity can work like your answer and i dont think distributivity can work like the answer in the pool
i dont know any boolean algebra btw so i have no comment on the x and y business
lean leaf
Given a set of possible output values and a set of possible input values, is it possible to determine the function that maps the input values to the output values?
I have A = {(0, 1), (0, 2), (0, 0), (1, 0), (1, 2), (1, 1), (2, 0), (2, 1), (2, 2)} which is the set of possible input values and B = {-1, 0, 1} which is the set of possible outputs.
I can send all the mapping I have too, if it would help.
obtuse lance
there aren't enough constraints, you could map these points from A to B in many different ways
you need some more conditions to force a unique choice of function
lean leaf
Oh, I have the exact mappings I need. I'll send it.
f(0, 1) = -1
f(0, 2) = 1
f(0, 0) = 0
f(1, 0) = 1
f(1, 2) = -1
f(1, 1) = 0
f(2, 0) = -1
f(2, 1) = 1
f(2, 2) = 0
Is it possible to find f just with that?
last sigil
Not a unique one at least
lean leaf
Oh. Why?
stray reef
uh
okay wait
is all you want simply a function A -> B
if so, these nine lines alone define it
stray reef
f(x,y) = { 0 if (x,y)=(0,0), -1 if (x,y) = (0,1), 1 if (x,y) = (0,2), ...
last sigil
Super long piecewise 
stray reef
nine pieces only.
lean leaf
Oh, I was hoping I could do it a bit cleaner than that... shame. :c
stray reef
it's a different story if you want to be able to plug in values other than the ones you've listed as possible inputs, of course
last sigil
I mean the one above has a pattern of x - y, with inputs (x, y), except f(2, 0) = -1 & f(0, 2) = 1
lean leaf
Yeah, I tried that but that 2 keeps bothering me.
And nah, I won't need other values.
I was trying to find a clean way of mapping the choice of two players in a rock-paper-scissors game (tuples in A being all the possible choices with 0 = rock, 1 = paper and 2 = scissors) to how many points each player gained (with 1 = victory, -1 = loss and 0 = tie). I just need to find what the first player gained and multiply by -1 to find what the second player gained.
Oh, well...
@last sigil It would still be cool if you explained the parabola with three points thing.
last sigil
No, it was just an example that a unique function doesn't exist
I am gonna keep thinking about this
obtuse lance
you could try some modular arithmetic, sines/cosines and just guess at it probably fastest way without getting your hands too dirty
or do you specifically want a polynomial?
last sigil
I was considering some comparisions
obtuse lance
kinda fun now that I'm reading the actual problem
f(x,y)=-f(y,x)
idk might be a simple way to represent this with a determinant
then just evaluate it to get the polynomial or w/e
lean leaf
Hm.
obtuse lance
it might be easier to make rock as -1, paper as 0, and scissors as 1
lean leaf
Wait, I'm still trying to understand that f(x,y)=-f(y,x).
Oh.
That's actually a good idea.
obtuse lance
I thought of it as f(x,y) = first player's score and s(x,y) = second player's score
then f(x,y) = - s(x,y)
and then of course the other relation I already wrote too
obtuse lance
more specifically, the entries of f(x,y) are a 3x3 skew symmetric matrix
since f(x,y)= -f(y,x) is literally transposing and looking at the indices
obtuse lance
f(x,y)=f(x+1,y+1) if we take the convention that 2=-1 mod 3
since we're shifting say, rock and paper to paper and scissors so you maintain the losing cycle
lean leaf
Hum, that still yields 2 in some cases, doesn't it?
wooden spear
This reminds me of the fact that every 5-periodic sequence can be expressed in closed form as a combination of $\cos(2\pi kn/5)$ and $\sin(2\pi nk/5)$ for $k=0,1,2,3,4$
vital dewBOT
Icy001:
obtuse lance
well mod 3 there's no difference between -1 and 2
so just freely interchange them and don't worry about it
lean leaf
I don't get it.
lean leaf
Yeah, that works for most cases.
lean leaf
F_3... sorry?
obtuse lance
it just means the finite field with 3 elements
just mod 3 arithmetic
nothing more to say, that solves it perfectly, couldn't ask for something better
lean leaf
But I can't mod 3 all of them.
lean leaf
It will change the other results.
obtuse lance
then yes, you can
stray reef
you are really better off just putting all your 9 values in a matrix.
such that the game corresponds to the first player choosing a row and the second choosing a col
obtuse lance
if x-y ==2 : return -1
else: return x-y
idk I guess it depends on which convention you picked for rock, paper, scissors too
might need to alter slightly but idk over all it doesn't really matter haha
obtuse lance
you're welcome
arctic blaze
so im trying to count ways of distributing distinguishable objects in indistinguishable boxes
and ive come across the notation S(n,k)
and i cant figure out what that means
haaalp
valid cape
Good morning!
How am I supposed to solve this? I've been able to solve this using a python IDE, but I'm pretty sure there's other way to do it
regards,
daring bane
what is graph symmetrization?
sour arrow
@valid cape
Still looking for it?
sour arrow
It's easy enough to see that 9115 = 2 (mod 701)
So you can also find 2^2015 (mod 701)
valid cape
and how do I find it?
sour arrow
Now, 701 is also prime, so you can use FLT:
2^700 = 1 (mod 701)
Which in turn gives
2^2100 = 1 (mod 701)
valid cape
oh, so I'm supposed to use fermat little theorem
sour arrow
Well I don't know what you're supposed to do lol. Is this an assignment?
valid cape
I'm just studying for an exam
I'll have it on tuesday
and I was struggling to do that exercise
sour arrow
Are you expected to know FLT?
valid cape
yes
sour arrow
Cool cool. Then yeah this gets a lot easier
valid cape
I've been procrastinating so I didn't actually study it xD
sour arrow
a^(p-1) = 1 (mod p)
Just lower the mod by 1, anything to the power of that is guaranteed to be equivalent to 1
If the mod is prime, anyway
stray reef
2^2100 = (2^700)^3 = 1^3 = 1 (mod 701)
sour arrow
2^700 = 1 (mod 701)
This means that anywhere we see a 2^700, we can just replace it with 1. Modular arithmetic is nice like that.
2^2100
= 2^700 × 2^700 × 2^700
= 1 × 1 × 1
= 1 (mod 701)
gusty bay
vital dewBOT
Momo:
faint narwhal
What related theorems or ideas do you know about things of this form?
gusty bay
Pretty much just fermat's little theorem which i dont think is applicable here
faint narwhal
Anything related to fermat's little theorem?
gusty bay
I mean I could keep reducing by factoring out a 2 from the exponent every time but
That seems very tedious for an exponent of 26
and a mod of 35
faint narwhal
There are better ways
gusty bay
I don't know them
faint narwhal
You do
faint narwhal
Just look through your notes
At the theorems you learned
see if any of them are applicable at all
gusty bay
This is my modular arithmetic note
It has almost no theorems @faint narwhal
LOL
Well almost no theorems related to this
faint narwhal
Ever heard of Euler's theorem or Chinese remainder theorem? Or do you know why Fermat's Little theorem works?
gusty bay
No I haven't heard of either of those
This was a problem from fall 2015 though, so maybe it was just taught then...
faint narwhal
Either of those will work, or if you know how Fermat's Little theorem works you can also figure it out
gusty bay
I was thinking factors
@faint narwhal I figured it out
Part of the proof of RSA
Works for 3^24
vital dewBOT
Momo:
sour arrow
@gusty bay
I think Zoph is referring to Euler's equation, which is:
a^φ(n) = 1 (mod n)
Luckily 35 = 5×7 so it's a pretty easy computation of φ(35)
Note FLT is a special case of this when n is prime
gusty bay
<@&286206848099549185> Can I get help with my problem?
sour arrow
gusty bay
@sour arrow The one above your reply 😛
gusty bay
<@&286206848099549185> Anyone?
daring bane
what's the idea behind induction on trees?
daring bane
<@&286206848099549185>
pale epoch
it's the same idea behind regular induction
daring bane
I am trying to prove that by adding an edge between two leaves, it creates a cycle. Is the following correct, it's just a part of the proof
vital dewBOT
Totoxic:
stray reef
,,, why not just say "take the unique path from x to y in our tree. adding xy will make it into a cycle"
daring bane
The exercise specifically asks to prove this first :/
stray reef
prove what
that adding an edge joining two ends of a path makes a cycle?
isn't that obvious
daring bane
Well i am taking an Introductory course on Discrete Mathematics and yes it is obvious, but I am required to show why is this obvious in order to show that i understand the concept. Also I need to get good at showing proofs since I still find them a bit hard. (especially induction)
but anyway thank you 🙂
daring bane
I am reading the Invitation to Discrete Mathematics by Matousek J ,Nesetril J right now as this is the book suggested by my course. The definitions sometimes are really different from the usual one found on internet. For example It took me quite long to understand that symmetrization of directed graph stand for the underlying graph of a directed graph.
Here is a definition from the book
By the way @stray reef do you suggest any good additional material for Graph Theory/Discrete Mathematics?
vital dewBOT
Ann:
stray reef
you called this P
now you went and added an edge
e = xy
so you get
$(x, e_1, v_1, e_2, \dots, e_t, y, e, x)$
vital dewBOT
Ann:
daring bane
alright thanks, this makes my understanding much better. Hopefully I will improve in later proof writings 🙂
stray reef
alright
if you want a particular point of improvement:
you attempted to do a proof by contradiction where a direct proof would've done just fine.
daring bane
I aimed to do a proof by contradiction because I want to improve on that as well, since it's an important point when doing structural induction on trees
stray reef
i mean
i guess it gets easier with mathematical maturity
determining when proofs by contradiction are appropriate that is
daring bane
ight, thank you for your advice : )
opal ember
yea here
long thistle
S1 = { {3}, {1,2} }
S2 = { {1,3} , {2} }
S3 = { {3,2}, {1} }
S4 = { {1} , {2}, {3} }
S5 = { {1,2,3} }
now i believe the hass diagram would contain a graph showing everything being connected to S5 in some way but for example S5 is at the top of the diagram and S4 is below S2, S1,S3 which are all below s5?
(a) List the set of all partitions of the set {1, 2, 3}. Hint: There are five of them.
(b) Define: Partial Ordering.
(c) Define r on the set of all partitions of {1, 2, 3} by P1 r P2 if every set in P1 is a subset of a set in P2. This
relation is a partial ordering on the set of all partitions of {1, 2, 3} draw the ordering diagram (Hasse diagram) for r.
i am on part C
please help
cerulean crypt
I'm trying to prove n^7 = n (mod 42)
I assume this follows from the fact that n^7 = n (mod 7)
I can't think of how I would deduce the first one from that though.
wooden spear
You also need to look at mod 6
weary tiger
Hey, on this last step, where we're trying to find the particular solution, why is A*2^n multiplied by n?
sour arrow
2^n is a part of the homogenous solution and so is not in the particular. If this ever happens where they match, then multiply your guess by n.
olive dragon
Hello, I need help with a problem, could someone please see if you can help, thanks!
wooden spear
Relevant content
In more serious news, ``put 4 in 2A" means to substitute $b=5m$ into the equation $b^2=5q^2$
vital dewBOT
Icy001:
olive dragon
thats p=5m but I got it now, thanks
wooden spear
the way this guy writes p 
olive dragon
I was so confused, I had to ask the person to confirm what it was..
Another question..
And answer..
Do I need to prove sqrt(n) being rational for any n? or is this good enough
lean creek
That easy counterexample is sufficient lol
And it's irrational
You just need to show one counter example
olive dragon
so its rational for some and irrational for other integer n
lean creek
yes
olive dragon
I think I should include that in my solutions, just to state a point
olive dragon
Okay, thank you
sweet eagle
@olive dragon yea
the logic is like this
Imagine someone told u like "It has never rained ever."
To prove it false, you just need one counter example
you show them that it rained yesterday
proved
olive dragon
Thats a really good explanation @sweet eagle !
Discrete Math is kinda hot, I'm getting attracted to it 
weary tiger
@sweet eagle what's the difference between consistent, and maximally consistent?
winter jackal
does anyone here know anything about weighted directed graphs
I don't really have a specific question, but the topic is coming up in something I'm working on
maybe like links to relevant sources?
lean leaf
So, dumb question... if two sets are disjoint, there is no way one could be a subset of the other, right?
dapper rose
consider any set S and ø
lean leaf
Hm, ø is a subset of S, right?
dapper rose
correct
stray reef
is it?
dapper rose
then try prove it
lean leaf
Like, if I have a non-empty set A and a non-empty set B and I say they are disjoint... they have no elements in common, right?
Their interesection is the empty set.
stray reef
well that is what it means for them to be disjoint yes
lean leaf
Then one can't be a subset of the other, because being a subset implies that every element of the first belongs to the other.
Roight?
stray reef
well not quite
you have to say that since say A is nonempty it contains at least one point x
and by disjointness that point x is not in B
therefore A isn't a subset of B
lean leaf
By point you mean element?
stray reef
yes
lean leaf
And I must specify that the sets are not empty for that to be true?
Because the empty set is a subset of every set.
stray reef
yes
lean leaf
Okay. Thank you. 
gusty bay
This looks close to FLT but not quite, how did they get this?
<@&286206848099549185>
stray reef
$a^{\varphi(n)} = 1 \pmod{n}$ when $a$ and $n$ are coprime
vital dewBOT
Ann:
orchid pawn
no you do both ways for "if and only if"/iff
weary tiger
analog sonnet
Nice questions
weary tiger
lol sorryy im new here
not sure if i did the right thing asking here
Idk how to do any functions
analog sonnet
A function is basically a pairing between elements from two sets, called domain and codomain
analog sonnet
Is this question part of the exam?
analog sonnet
I want to quote the following rule from #rules: "1. Requesting help during an exam a bannable offense."
weary tiger
LMFAOO thanks
weary tiger
you right ty
pale epoch
lmao
sleek swallow
Just fail the exam if you don't know the content, i suppose. It's better to do that
pale epoch
recently i read a study, how a phone lying on the desk next to them makes students perform worse
even if the phone is off
maybe you should not take a phone into the exam room
sleek swallow
Idk, if I knew that i didn't study hard enough for an exam and I could pass with a cheat sheet or whatever, I'd still choose to fail & retake the course.
It's a clear indication of my lack of understanding of the material.
weary tiger
arent you a good boy
weary tiger
^^
faint narwhal
<@&268886789983436800>
weary tiger
Money too
sleek swallow
Yeap. So understand the material and you probably won't fail 🙂
weary tiger
Thanks for your complete lack of understanding that i had a lot of personal things going on @sleek swallow
faint narwhal
Just stop, this is a pointless argument
weary tiger
Bet
last sigil
last sigil
Just post question; not saying I can solve it
last sigil
Well, I am bout to disappoint you cause I got no idea
glossy adder
I have a "succint combinatorial proof" (relatively)
consider making a choice from 3 things n times
might want to spoiler that hang on
||I have a "succint combinatorial proof" (relatively)
consider making a choice from 3 things n times
let's say choosing either 1,2 or 3 for example
you can think of each term as representing how many of your choices aren't 1
the first term is a 1 which corresponds to none of your choices not being a 1
then the (n choose 1)* 2 corresponds to one of your choices not being a 1
when none of your choices are 1, you must first choose which it is
and then choose which of 2 or 3 you will make the choice
which is where the 2 comes from
to generalise to get each term
consider if you have k choices which aren't 1
you much first choose which choices they are, giving n choose k
then you must choose which are 2 and which are 3
giving 2^k
but you know obviously that there are 3^n ways to choose 3 things n times giving the result pictured||
shut rivet
im reading 1 ssec
dapper rose
I was gonna suggest (1+2)^n but that doesn't get extra credit
shut rivet
@glossy adder are you still here? I'd like to discuss
glossy adder
ok
glossy adder
just talk here
shut rivet
okay
1 sec
so you say I can think of each term as representing how many of your choices are not a 1
the first term would evaluate to 1, as the only option is 1?
shut rivet
okay, so I have infinitely many choices but they are all 1?
glossy adder
you have n choices
shut rivet
okay
glossy adder
but they're all 1
glossy adder
huh
glossy adder
0 if anything
shut rivet
okay cool
sorry I'm just trying to wrap my head around this proof
okay, so you say I am making a choice from 3 things, but I don't understand why each term represents the choices that are not 1
@glossy adder
glossy adder
you're making a choice from 3 things n times
shut rivet
and each term represents how many choices are not 1 at what point
glossy adder
ok think about a string of length n
whose characters can be either 1,2 or 3
what you're doing is basically counting all the strings of this form
the choices I'm referring to are which character is used in any given position in the string
there are 3 possible choices in each position: 1,2 or 3
shut rivet
anyone home?
static ivy
uhhh about the question u poseted earlier
i think u can look at the right term as:
u have 3 groups, u wanna divide n people into those 3 groups
so for every person u have 3 options, hence the 3^n
on the right left term
lets change it up and make it more readable
so sigma[(n)choose(k) * 2^k ] (k=0,n)
(sorry i dont know how to use the math bot)
now u can read this as
first choose k people , and then for each of them they have 2 options, group 1 or group 2 , and the rest of them (the remaining n-k people we didnt choose) automatically go to group 3
a single choice to do that
@shut rivet
on another note, im stuck trying to solve the following
robust mango
Are you trying to prove this identity?
static ivy
yeah
i have an approach that soon enough turned into a dead end as well
i tried to explain the right term by suggesting we are choosing n couples out of 2n people
first we choose one couple , we have n options
then we choose n-1 couples
and on the left, we choose k people, then another k people to match them with
but im unsure about the quantity of couples and this free k
robust mango
I'm not sure what to make of it as well, tbh
I mean you can prove it by induction, but it'll be hard if you do it your way
static ivy
to be fair , i wasnt limited to solving it my way
robust mango
because that squaring, then multiplying by k again messes up the choosing process
static ivy
i was just practicing proving by combinatorics
maybe i should try induction
i have another approach
not too different but feels better
right term:
in a class of n boys and n girls, we choose one
couple
left term:
we choose k boys, and we choose k girls,
and then we choose one couple out of the k
possible couples```but this time
this term is left unexplained
tidal plinth
@static ivy Firstly, if you choose k boys and k girls, you don't automatically get (well defined) k couples — so k is not the number of ways of choosing one couple out of k + k uncoupled boys and girls. Secondly, even if you coupled them first, finally you're only choosing one couple, and you'll be overcounting that if you sum it up for all k — unless you specify that you're also counting all the ways of forming couples and then choosing one couple, but even that's not really right
static ivy
hmmmmmm about the first thing u said
isnt the fact im choosing k out of n twice (rather than k out of 2n) assuring me well defined couples?
@tidal plinth
and yeah the i guess ur right about the other things u said
it doesnt really add up
tidal plinth
No it doesn't assure well defined couples unless you choose the second k with order, so it should be nPk = n!/(n - k)!.
static ivy
ah ur right
actually ,are u right?
think of it as potentially creating 2 sets (no order) of boys and girls
{jack,dave} {liz,jennifer}
i then create a function
f(jack) = liz
f(dave) = jennifer
or the other way around
thats exactly 2 possible couples
tidal plinth
Is n = 2 and k = 1 here? Then k = 1 is a special case where you don't need to do additional work to define couples
tidal plinth
Boys = {A, B, C}
Girls = {F, G, H}
What are all the different sets of 2-couples?
{AF, BG}, {AF, BH}, {AF, CG}, {AF, CH}
{AG, BF}, …, {AG, CH}
{AH, BF}, …, {AH, CG}
{BF, CG}, {BF, CH}
{BG, CF}, {BG, CH}
{BH, CF}, {BH, CG}
That's 18
No, I missed some. Lemme edit
static ivy
just to be clear, are u going for the k =3 example?
tidal plinth
No, n = 3 (three boys, three girls), and k = 2 (we want two couples)
static ivy
ok
tidal plinth
(I missed the couples without A earlier)
tidal plinth
(3C2)² = 9
(3C2)×(3P2) = 18
tidal plinth
Maybe… Out of 2n, first you choose 1: 2n ways of doing that.
Then you choose n - 1 out of the remaining 2n - 1: C(2n - 1, n - 1) ways of doing that.
So you've got 2n×C(2n - 1, n - 1) ways of doing those two in succession.
But now you need to combine these [the first 1 and the next n - 1] in some way that makes the above exactly a double-counting, so you end up dividing by 2
static ivy
hmmmm
well thanks for ur help dude
i have another one im stuck in if ur interested
i tried to read the right term as the ways to arrange the numbers 1 to n+1 in a line without the possiblity that all of them are in the right place
(1,2,3,4,...n+1)
and on the left term...k as the number of items that are in their wrong slot, BUT.....there cant only be one wrong slot item, there has to be at least 2
well that alone is not the only reason my plan collapsed
analog sonnet
Why wouldn't you prove this equality by induction? It doesn't need the tedious step in translating it to a combinatorial setting
Although I guess if you're practicing combinatorics in particular, go ahead by any means :p
tidal plinth
That's boring. Also, combinatorialists have this fetish for discovering combinatorial proofs
Yeah, it's good practice for developing that kind of thinking
Also, by TIT, you should simply be R/J
static ivy
i agree with everything u guys said
i just have this urge to get better at this since i feel like im lacking the skill
analog sonnet
TIT?
tidal plinth
Third Isomorphism Theorem
analog sonnet
Ahh, yes yes
tidal plinth
@static ivy I have the same urge, hence why I'm discussing these wtih you xD
analog sonnet
I'm of the opinion that interesting algebraic identities can be derived from combinatorial settings much more easily than the other way around
At least that's where I see the joy of combinatorics
tidal plinth
I guess the joy here is that of playing Sherlock Holmes
static ivy
this second problem i posted feels doable
especially since my lecturer mentioned it is
i think he even wanted us to do it using combinatorics
tidal plinth
@static ivy Yeah. I'm thinking along these lines (for the LHS): Let the n + 1 items (and their corresponding places) be numbered 0, …, n.
For item #k (k > 0), pick any of the places 0, …, k - 1. (k ways)
Put all the items k + 1, …, n in their own respective places. (1 way)
Permute the remaining k items [0, …, k - 1] in the remaining k places. (k! ways)
Since item #k is not in place #k, all of these are guaranteed to be permutations in which not all items are in the correct place. But other than that, is there some undercounting and overcounting going on?
static ivy
im trying to think if the permutation 234561 is included here for (n=5)
if im limited to choosing between only the first k items for item #k
can 1 for example be in the last slot
(6xth slot)
as far as im understanding what u mean i think we are undercounting 😮
tidal plinth
To match it with my description, I'll rewrite that permutation as 123450.
Now, for k = 5, 5 can be put in any of the places 0, …, 4.
→ Put it in place 4: ____5_
Put all the items k + 1, …, n in their own respective places. But this is empty (since k + 1 = n = 5 now).
Permute the remaining k items in the remaining k places (which includes place 5):
→ 123450
static ivy
following this method i think all the options we land are *****6 ****56 ***456 **3456 *23456
where * means item in the wrong slot
oh damn
the *'s were fucked
let me edit
(lets ignore the last one on the list for now since its impossible)
am i understanding this correctly?
tidal plinth
You missed one. When k is the last item (6 here), you're forced to put it in one of the first five place, so there's ******, where 6 is one of the first five *s
Wait, do you know about lexicographical ordering of permutations?
I just realised that's what we have here
static ivy
i dont think i know this term haha
tidal plinth
Nevermind then. But look it up later, because it's interesting, useful, and it's basically what we're doing now so you'll understand it easily after this
Gah. Be back shortly
static ivy
hey thanks a lot for the help dude
i will read about it
also the point i was trying to make is that we might not be counting things like
****65
for example
since we only permulated 0 - k-1
tidal plinth
Back
@static ivy But when we permute 0, …, k - 1 the partially completed permutation looks like this:
_ _ … _ (k + 1) … n ← Item #
0 1 … k (k + 1) … n ← Place #
And item #k is in one of the first k - 1 places.
So one of the items 0, …, k - 1 is forced to be in the place k
For example, let the items (and places) be 0, 1, 2
k = 1: Item #k = #1 can be in any of the places 0, …, k - 1, that is, just place 0 so: 0 _ _
Next, item #(k + 1) = #2 must be in place 2, so: 0 _ 2.
Finally, item #0 can be permuted in the remaining places, so that gives: 012.
k = 2: Item #k = #2 can be in any of the placse 0, …, k - 1 = 0, 1, so: 2 _ _ and _ 2 _.
There's no item after #2, so nothing to do in the second step.
Finally, items #0, #1 can be permuted in the remaining places, so that gives:
2 0 1, 2 1 0 (from 2 _ _) and 0 2 1, 1 2 0 (from _ 2 _)
static ivy
Ohhh I see it now
tidal plinth
Here's another way though. You know how number systems (binary, decimal, …) work:
Each place has a value [in decimal, the place values are 10⁰, 10¹, …], and in each place, the digit can have any value from 0 to k - 1, such that if you multiply k by the place value it spills over and becomes the next place value. So in the decimal system, no digit can be greater than 9, because 10×10ⁱ = 10ⁱ⁺¹, which is the next base value.
[And if we allow such values, the representation is no longer unique]
Now we can define a "factorial base", where the place values are factorials, 1!, 2!, …, instead of powers of a fixed base. Examples:
5 = 2×2! + 1×1! = "21"
6 = 1×3! + 0×2! + 0×1! = "100"
In this system, the kᵗʰ place value (starting from the least value) is k!, so the "digit" in this place can be at most k, since (k + 1)×k! = (k + 1)!, which is the next place value.
It's not hard to see that using this system, we can uniquely represent every non-negative integer:
Given N, let n! be the largest factorial less than or equal to N.
Write N = q×n! + r in the quotient-remainder form [division algorithm].
Now q×n! is already in the required form, and recursively, we can find the factorial representation of r as well (which is guaranteed to involve only 1!, …, (n - 1)!, since r < n!).
This shows, in fact, that to represent any number less than (n + 1)!, you need only places 1!, …, n!. Moreover, if you assign all possible (valid) values to these places, you get every number between 0 and (n + 1)! - 1. That is, if you fill up
_×n! + _×(n - 1)! + ⋯ + _×2! + _×1!
in all valid ways [place k has a number between 0 and k], you get all the numbers between 0 and (n + 1)! - 1 once each.
And if you don't allow all places to be zero at once, you get the factorial representations of exactly (n + 1)! - 1 numbers
That gives the RHS
tidal plinth
For the LHS, count the number of representations in which not all places are 0, in the following manner:
Let the kᵗʰ place have any value other than 0: That is, 1, …, k. So k ways.
Let the places after k all be 0. (So only 1 way)
Let the first k - 1 places have any valid values. But the first k - 1 places, when allowed to take all possible values, represent the numbers 0, …, (k! - 1). Thus, there are k! such assignments.
Therefore, we have k×k! numbers where the kᵗʰ place has value between 1 and k and the places k + 1, …, n are all 0s (and the first k - 1 places have all possible values).
Thus, the total count is Σ k×k! (where k ranges from 1 to n)
There is actually a natural one-to-one correspondence between these factorial representations and the permutations, and that gives the lexicographical ordering of permutations
And this is exactly the sort of result we hope to find by "reverse engineering" such identities @analog sonnet
analog sonnet
Massive props 👏
This goes to show that my combinatorics game is, without a doubt, quite weak
Given the "factorial base" information, I could probably engineer such an identity, but to reverse engineer is not really in my league, so to say
So what's your background in combinatorics? You seem to know what you're talking about
ornate thorn
I understand what the problem is asking but I can't seem to find an example for x and y, how would I find the values for x and y? LHS x = 1 + 2y RHS x = -y/5 right?
ornate thorn
solving that for y will give me x?
sleek swallow
Well, the statement is just telling you that there exists an ordered pair (x,y) that satisfies both linear equations. That's all it's telling you. If you're trying to find that ordered pair and if you have 2 linear equations in 2 variables, what should you do?
ornate thorn
that's what i'm asking
sleek swallow
Well, have you ever solved two equations in two variables?
sleek swallow
Well, sort of
You should use the first equation and solve for x in terms of y. Then, you need to substitute that into the second equation. That will give you your value of y. Then, you can use that to get your value of x.
Aye?
ornate thorn
👌
tidal plinth
Was away. @analog sonnet I work in algebraic graph theory. Also, I teach an undergraduate discrete mathematics course to engineering students.
analog sonnet
Awesome! I'm but a mere PhD candidate in applied maths for micro-electronics
I like graph theory, I followed an introductory course on it during my Masters
tidal plinth
I'm also doing my PhD (part time, while working as a lecturer full time). What maths do you apply to micro electronics? Transforms? [There's some applications of graph theory to circuit design, but I only know of that, I don't know it]
ornate thorn
Why are there two cases? I understand n must be 3k+1 for it to be a positive integer but I don't understand why the 2nd case exists
stray reef
the remainder of n upon division by 3 is always either 0, 1 or 2
you've excluded 0 by saying 3 doesn't divide n
but the other two are still there
3k+1 does not cover all non-multiples of 3
ornate thorn
man i'm so screwed
i want to cry
im about to fail all of my classes because I couldn't figure out which one to study more of.. now i've successfully not studied enough of each to pass any of them
rapid herald
first time?
kind tapir
Let $3 | n^2$, then $2v_3(n) = v_3(n^2) > 0$ and so $3 | n$.
vital dewBOT
Intel:
kind tapir
p-adic orders provide really elegant solutions to some stuff
and they basically provide more language for some of the intuition provided by the fundmental theorem of arithmetic
for this proof, you just need to see that $v_p(a^n) = nv_p(a)$ and that $p | a \iff v_p(a) > 0$
vital dewBOT
Intel:
faint narwhal
p-adic orders literally add nothing
Its just really a concise way to say "this number is divisible by p this many time"
tidal plinth
@faint narwhal Sure it works, but why would you mismatch brackets that way?
vital dewBOT
Zopherus:
tidal plinth
That's why I said it works for sure, but it's unsettling
tidal plinth
Ah
analog sonnet
@tidal plinth it's mostly data analysis as of now
tidal plinth
Not my favourite thing, to be honest
analog sonnet
I'm currently looking into symbolic regression
lean creek
oh wait I think I've looked into this at a cursory level haha
like AIC, BIC, Mallows Cp?
analog sonnet
I had to look those terms up, but they seem to be quite deep into the field of stats
analog sonnet
I only know a bit of stats
lethal sequoia
Hi guys, can someone explain the orbit of c in a group? Relating to combinatorics
tidal plinth
More context?
I mean, if you know what a group action is, then then orbit of a point x (in the set on which the group acts) is the set of all points that x is mapped to by the action of the whole group
(Just like the orbit of a planet is the set of all points that it is moved to under the action of gravity of the sun [admittedly a simplification])
But if you could provide more context, especially what you mean by "relating to combinatorics", maybe we can be more helpful @lethal sequoia
lethal sequoia
Thanks for the quick answer @tidal plinth
My text mentions the orbit in relation to colorings in a group
tidal plinth
Necklace problem?
tidal plinth
Hm. In this context, it is useful to think of the orbit of a point as the set of all its "equivalent" points [indeed, we can define it as an equivalence class].
Consider an almost trivial example: Let ΔABC be an isosceles but non-equilateral triangle with AB = AC (≠ BC). What are the symmetries of this triangle?
Only these: Reflection along the perpendicular bisector of BC (which passes through A), and the trivial symmetry of doing nothing.
In terms of permutations: {(), (BC)} (identity; and interchanging B and C)
Thus the group G = {(), (BC)} acts on the set of vertices of the triangle: V = {A, B, C}.
What is the orbit of A in this action? {A}
What is the orbit of B in this action? {B, C} (and that's the orbit of C as well)
Thus, B and C are, in some sense, equivalent to each other, while A is equivalent only to itself.
This equivalence is intuitively obvious. If I remove the vertex labels, you won't be able to tell which vertex is B and which C — but you'll be able to tell me which one A is. And you'll also be able to tell me that the other two vertices are B and C in some order.
When you define a group acting on a set of points, you're sort of identifying the group with "symmetries" of the points (if you define it in some meaningful way, that is).
Then the orbits tell you which points are "equivalent" in the sense of being able to be transformed into one another under the symmetries — that is, which points you will not be able to tell apart from one another if they were unlabelled
lethal sequoia
Okay it's slowly starting to make sense
tidal plinth
Now in the necklace problem, say you have six beads, and you colour them with two colours alternately: say every odd numbered bead is red and every even numbered bead is blue: RBRBRB
The beads are all identical except for the colours you've given them, and even then all the red ones are identical and all the blue ones are identical. So if I rotate the necklace by two "steps" (two beads), the original 123456 = RBRBRB becomes 345612 = RBRBRB.
But without the labels, these are identical
Similarly, if I flip the necklace over, keeping beads 1 and 4 in their place; swapping 2 and 6; and swapping 3 and 5, it still looks the same
proud falcon
Is it possible for me to make a bipartite graph with 3 vertices in 1 set and 4 in another?
tidal plinth
@proud falcon Sure, there's no restriction on the numbers of vertices in the partite sets (except that both must be non-empty). For example, the complete biparite graph K₃,₄ is one such
proud falcon
Oh and with each vertex having exactly 2 degrees
tidal plinth
@proud falcon No. What is the relation between degrees and number of edges in a graph? In a bipartite graph?
proud falcon
2|E|
lethal sequoia
@tidal plinth So the orbit is just looking at the set with elements that are equivalent to each other. So orbit of R = {1,3,5}?
tidal plinth
@lethal sequoia To apply group actions to count the different necklaces you can make with a given collection of beads, let X be the set of all possible necklaces you can construct if you consider all the beads distinct. And the group acting on this set is the dihedral group of order 2n (where n is the number of beads). But the action has to be defined carefully
@lethal sequoia That's the tricky part here. We are going to consider different possible necklaces as different points in the set on which the group acts. The beads are not the points
Consider a labelled hexagon 123456, which represents spaces for the beads to occupy.
And if you have two colours, red and blue, then naïvely the number of different neckalces you can make are C(6, 3) (you choose three places for the red beads; and the others are blue)
But if you consider the alternating-colour necklace RBRBRB from before, and what seems like another alternating colour necklace BRBRBR, in reality these two are equivalent (you can get one by rotating the other one step)
@proud falcon Right, and in the case of a bipartite graph with bipartition (V₁, V₂), what is the sum of the degrees of vertices in V₁? What about V₂?
@lethal sequoia So what we really want to count is the number of different orbits of the action
(Each orbit gives all the different configurations of the essentially the same necklace)
@proud falcon Note that each edge is incident with exactly one vertex in V₁ and one vertex in V₂.
lethal sequoia
Oka
@tidal plinth Okay, thanks! I think I just need to sit with it for a wihle
while* and think about it a bit more
tidal plinth
Yeah
There's actually a lot going on, and once you see it, it's simple, but it's definitely confusing at first
It helps to take a small case (like 3 + 3 beads) and draw all possible necklaces (20) and see which ones are the same
proud falcon
I'm not really sure
tidal plinth
@proud falcon Try drawing some bipartite graph and counting:
o o o
\ /\ /
o o
V₁: 1 + 2 + 1
V₂: 2 + 2
How do you think this relates to the number of edges?
proud falcon
Sum of degrees is 8, so there are half the number of edges?
tidal plinth
That's true for all graphs. What's special here?
proud falcon
Vyn I'll be honest I'm a dumb kent.
tidal plinth
o o o o
\ | / /|
o o o
V₁: 1 + 1 + 1 + 2 = 5
V₂: 3 + 1 + 1 = 5
#Edges = 5
The degree of a vertex counts the number of edges incident with it.
Therefore the sum of the degrees of all the vertices in V₁ counts the total number of edges incident with vertices in V₁.
But every edge is incident with exactly one vertex in V₁, so the sum of the degrees of vertices in V₁ is ______?
It's okay to make an informed guess (based on the examples at least)
proud falcon
|V1| + 1
tidal plinth
Blame that coincidence on my poor choice of examples. But consider this: There's some symmetry in the definition of V₁ and V₂. I mean, in both those examples, we could easily have called the lower set V₁ instead of V₂. The graph structure itself doesn't tell us which is which. But if we rename V₁, then |V₁| + 1 no longer gives the correct answer, so that can't be it
Okay, here's the thing:
Since each edge is incident with exactly one vertex of V₁, each edge is counted exactly once by each vertex in V₁.
The degree of a vertex counts the number of edges incident to it.
So the sum of all degrees of vertices of V₁ counts the number of edges in the graph
But the exact same argument works for V₂: The sum of all the degrees of vertices of V₂ also counts the number of edges in the graph
Therefore both these degree-sums must be equal (check this in those two examples) even if the number of vertices in the two sets and their individual degrees are different
So, suppose you have a bipartite graph with 3 vertices in one partite set and 4 vertices in the other. Can all the vertices have degree 2?
What will be the sum of vertices in V₁ in this case? What about in V₂?
Are these equal?
6 = 8?
proud falcon
Each edge is counted twice by each vertex in V1, so if V1 has 3 vertices, then that is 6 degrees
But then if each edge is counted twice by each vertex in V2 and it has 4 vertices, that is 8 degrees.
So they aren't equal
tidal plinth
Correct
So no such bipartite graph exists
In fact, no graph with 7 vertices having all vertices of degree 2 can be bipartite (but that's just a little bit harder to show: You'll have to show that if all the vertices have degree 2, then the graph is a disjoint union of cycles. Then in this case, the only possibilities are — the graph is a cycle on 7 vertices; or it is the union of a triangle and a 4-cycle — but both of these graphs contain odd cycles (the graph itself in the former case and the triangle in the latter case), so they are not bipartite)
(Alternatively, you can consider all possible bipartitions of the 7 vertices: 1 + 6, 2 + 5, 3 + 4, and use the degree-sum argument to rule out each case)
proud falcon
I see, since V1 requires 6 edges in order to have all vertices having a maximum degree of 2, but V2 requires 8, it's not possible
tidal plinth
Yeah.
(But not "maximum degree", just "degree". If you change it to:
Does there exist a bipartite graph with 3 vertices in one partite set and 4 in the other, where every vertex has maximum degree 2? Then the answer is yes)
proud falcon
Oh yeah, sorry, I meant degree of 2. So they all have degree of 2.
What if the graph wasn't bipartite, as in I allowed a single edge in V1 to connect to another edge in the same group. How can I verify this is possible using that logic?
tidal plinth
Then, observe that the path graph is bipartite (it has no cycles). So bipartition P₇, and you'll get a (3, 4) bipartition
o o o
/ \ / \ / \
o o o o
Make the first and fourth vertices in the lower partition adjacent
If you think only of the degrees without thinking of the structure, then you can let the degrees be 2, 2, 2 in the first partite set, then in the second set they must be 2 + 2 + 1 + 1
Which means you have exactly two vertices with degree 1 in the second set. So make they adjacent to each other, so they'll both have degree 2
proud falcon
Honestly a lot of this stuff is over my head, so ty for taking the time to explain it. Saved me a lot of trouble.
Thought I'd be done with graph theory after my discrete maths class last year 
Well I guess it was actually useful after all
gusty night
good place to learn this stuff? heard of brilliant.org but how about a free one lol
last garden
ivory badge
@last garden what part is messing you up
kind tapir
@faint narwhal
p-adic orders literally add nothing
it's just a really concise way to say "this number is divisible by p this many time"
exactly
which is a very useful thing to talk about when you think of natural numbers as their prime factorisation without explicitly mentioning everything
ivory badge
i mean, your p-adic order can be turned into a norm boy in a concise manner, so you can complete Q wrt this norm or whatever
daring bane
How can you prove that for a tree T with n>=3 verticies and k>=2 leaves, it is sufficient add k-1 edges to T to turn it to a 2-connected graph. Prove how are these edges added and than prove the resulting graph is 2 connected. I used induction on this problem but my answer wasn't marked right and it was commented that induction is not necessary here.
boreal lion
I think you could choose a particular leaf and connect all others leaves to it. In a tree every pair of vertices is connected by the only path, this path should be included in some path between leaves. And with additional edges you added these paths turned into cycles
tidal plinth
It's the math of things you can count
(But only if you can't count them too easily)
torn turret
is there a name for a graph which is made of the non-edges of another graph?
it doesn't look that useful so i'm not surprised if there isn't
mostly because it does some funky things to the adjacency matrix
craggy gale
I've seen the word "complement" being used for this I believe
torn turret
alright thanks
craggy gale
You're welcome
torn turret
oh wow you can use it to speed up some algorithms!
boreal lion
In proofs of the graph theory statements this graph consistently appears iirc
tidal plinth
@torn turret Yes, that's complement graph, and there are some elementary but interesting results involving that (including stuff with its adjacency matrix)
These are some basic ones you can try to prove:
- For any graph
G, at least one ofGandḠ(its complement) are connected. (In fact, ifGis disconnected, thendiam(Ḡ) ≤ 2. - If
diam(G) ≥ 3[includingdiam(G) = ∞], thendiam(Ḡ) ≤ 3. - If
Ghas six [or more] vertices, then eitherGorḠhas a triangle (a complete subgraph on3vertices).
torn turret
- (first part) Consider the sets of vertices that correspond to connected components of
G. IfGis connnected, we are done. Otherwise,Gcontains more than1connected component. Then, inḠ, each pair of these sets form a complete bipartite subgraph. Therefore, every vertex in the pair is connected to every other vertex in the pair. Therefore, all the vertices ofḠare connected, andḠis connected.
tidal plinth
The phrasing is a bit off, in my opinion, but yeah, that's essentially correct
[Of course, this applies: https://www.reddit.com/r/math/comments/7unynn/on_mathematicians_different_standards_when/]
torn turret
i'm just a really interested high school senior, so thanks for the tips!
my proof could benefit from labeling everything and describing the complement procedure better
tidal plinth
Oh, nice! It's good to develop your intuition, and you should definitely focus on that when writing a proof, and polish it only later (sometimes it may happen that when making the proof rigorous, some flaw comes to light and destroys the proof — but if you worry about this from the start, you may not be able to come up with any proof)
tidal plinth
@torn turret You may like the book Graph Theory - A Problem Oriented Approach, by Dan Marcus.
(The title itself is an accurate description)
torn turret
thanks, i'll add it to my reading list. i'm trying to get through an abstract algebra book and i have a diff geo one lined up too, also trying to learn category theory because it's fun and provides insight into coding
so i'm not sure i'll even get through those lol
i downloaded the book though, thanks
tidal plinth
I've learnt some category theory from different sources. At the moment, I'm planning to study Spivak and Fong's Applied Category Theory (MIT OCW), principally by reading their book Seven Sketches in Compositionality (http://math.mit.edu/~dspivak/teaching/sp18/7Sketches.pdf).
And by giving online text-seminars on it to a group of interested friends (through Telegram)
sick fiber
Can anyone explain in intuitive way of finding no of cycles of length k in labelled and unlablled complete graph ?
<@&286206848099549185>
obtuse lance
what's the difference between a cycle in a labeled vs unlabeled complete graph?
sick fiber
Hmm, @obtuse lance in unlabelled i beleive we can 1 cycle only. Lets say we have 4 vertices there is just 1 way to have cycle
But for labelled, having bit confusion to grasp
obtuse lance
ok cool
not entirely sure myself but I think I have an idea
how many places can you start?
on K_n let's say
sick fiber
Okay
obtuse lance
then how many places can we go to
and so on
we'll over count, but then fix it up in a bit
sick fiber
Could u rephrase what r places here ?
obtuse lance
vertices
K_n is the complete graph on n vertices
how many places do we have to choose to start a cycle from?
on the unlabeled graph
should be obvious, this isn't a trick question
sick fiber
In a complete graph we need just 2 vertices and we can get cycle ryt ?
obtuse lance
I don't know, I think you might need 3
but maybe 2 is technically a cycle in graph theory definitions
tidal plinth
You definitely need three, since you're not considering multigraphs
obtuse lance
that doesn't answer my question earlier
how many places do we have to choose to start a cycle from?
K_n has n vertices so there are ...
tidal plinth
https://discordapp.com/channels/268882317391429632/496785905474994186/659078257429184532
That's not a cycle in the graph. And anyway is not relevant since the question is how many cycles of length k there are
obtuse lance
how do you link messages like that @tidal plinth ?
sick fiber
I think he copied the link to the message and paste that
tidal plinth
@obtuse lance You need to enable Developer Mode in your Discord settings
Then you'll get the Copy Link option on messages (in the usual list of options for each message)
sick fiber
Here here
tidal plinth
I learnt that recently, in one of the rooms on this server, I think xD
[I'm quite new to Discord]
obtuse lance
I've seen people do it and thought it was super handy
but couldn't find it from just googling weirdly
tidal plinth
Same here. I googled, failed to find anything, and then asked
sick fiber
Yeah i have answered in order to have cycle we need 2 vertices out of n but it was wrong obv