discrete-math

[jolly ledge]

may come handy for ya

[vapid drift]

omg this is good for practice

[jolly ledge]

yeah, I found it handy back when I first learnt this stuff

good for checking work definitely

[vapid drift]

ok i will try do do the second part by myself. one last question what does this mena again ↔

[jolly ledge]

it means if and only if

in other words

A if and only if B, means that A implies B, and B implies A

it's different from just asserting that A implies B

for example

A is a square implies that it also is a rectangle

but A being a rectangle doesn't necessarily imply that it is a square

but when it comes to <->, it means that it must be true both ways round

[vapid drift]

so if c is true and (a and b) is true would the if and only if mean T. and if c is false and (a and b) is false then if and only if is true and if c is false and (a and b) is true then the if and only if is false?

[vapid drift]

Are you a teacher?

[jolly ledge]

yep.

[jolly ledge]

nope

hope I helped tho

[vapid drift]

You seriously need to become some sort of dgd or tutorial TA. no one explained this to me as fast and as good as you. This is actually crazy

[jolly ledge]

thanks for the complements, but I ain't rlly at that level yet would consider being one as I gain more experience. Hope you have a nice day, and GL with those qns

[vapid drift]

Thank you !!!

[ivory badge]

Constructivists in shambles

[jolly ledge]

[ivory badge]

((A->0)->0)->A moment

*This is LEM, but you can get A->((A->0)->0) without it

Namely, function application

and that’s A-> - - A

[jolly ledge]

Geez I'm cracking UP SO BADD RN 🤡

[ivory badge]

insanely funny

[unique dove]

I'm at structures, is a structure a specific type of set or are they separate

[coral parcel]

"Structure" is a word with a lot of barely related meanings.

Thus a lot more context is necessary to even understand what you're asking.

[odd garden]

Can anyone help me in logistic proofs?

Can the thing in blue considered as “q”?

Because this makes it simpler

[coral parcel]

Um, can you find even one single truth assignment where the thing you have circled in true has the same truth value of q?

[odd garden]

This is not my section’s work

My professor didn’t even send assignments

I’m justbpraxticing

To prepare before

[odd garden]

<@&286206848099549185>

[coral parcel]

Hmm, perhaps you didn't see that I responded to your question. I'll repeat it in case Discord is acting up:
Can you find even one single truth assignment where the thing you have circled in true has the same truth value of q?

[odd garden]

I already told you this is a previous exam

[coral parcel]

What does that information have to do with what I aksed you?

Can you find even one single truth assignment where the thing you have circled in true has the same truth value of q?

[odd garden]

I don’t get it

[coral parcel]

You asked whether (¬p or ¬q) and ¬q can be replaced with q. That must be because you think they have the same truth value. I'm asking you whether you have tried pugging in even one single truth assignment for p and q to check whether your assumption holds in practice.

[odd garden]

These are laws we follow I don’t think you have to plug in

[coral parcel]

Do me a favor and try a single choice of values to see whether what you ask is true is even in one single case actually true.

I don't care which choice of truth values you try. But try one.

Tell me which truth assignment you tried and which value you got for (¬p or ¬q) and ¬q and which truth value you got for q. Are they they same?

[coral parcel]

Apologies, @odd garden. It suddnely strikes me that you might be asking whether you can let (¬p or ¬q) and ¬q be the formula that is called q in some completely different, generally phrased rule?

[odd garden]

yes she replaced (¬p or ¬q) and ¬q by q

by she i mean my proffesor

not p or q is equivalent to p -> q

[coral parcel]

Are you talking about the "or directly" sidebar?

That starts by replacing (¬p or ¬q) and ¬q by ¬q --- not by q.

[odd garden]

I’m askingn about the or directly

[odd garden]

Yes

[coral parcel]

The blue circled thing does not become q. It becomes ¬q.

[odd garden]

Okay I’m with you

[coral parcel]

After that, ¬q or p becomes q -> p.

[odd garden]

So all the “not” inside are removed?

[coral parcel]

No.

The truth value of (¬p or ¬q) and ¬q is always the same as the truth value of ¬q. Therefore you can replace one with the other.

[odd garden]

But if you go backwards it doesn’t get the same answer

[coral parcel]

I don't know how that is equationally justified in whichever (unknown-to-me) system you're using, but it is easy to check with a truth table.

What do you mean by "go backwards"?

[odd garden]

Like start from q->p

And go on backwards

You will not get back to the blue circled thing

[coral parcel]

If we accept that the truth value of (¬p or ¬q) and ¬qis always the same as the truth value of ¬q.
Then we must also accept that the truth value of ¬q is always the same as the truth value of (¬p or ¬q) and ¬q.
You can replace one with the other, or the other with one. Both replacements preserve meaning.

[odd garden]

You know what this course is weird that’s not maths😐

[iron marsh]

@odd garden humor me for a second. If you think this isn't math, then what do you consider math to be?

[jolly ledge]

Maths and its connections to practically everything be like

[chilly dew]

I’m trying to prove the existence and uniqueness of the transitive reduction of a finite directed acyclic graph

(the transitive reduction of a graph is a graph with the same nodes but a minimal number of edges such that the reachability relation on nodes is the same)

I know in algebra the usual way to prove the existence of some minimal structure is to take the intersection of all objects that satisfy the condition

But I am not sure if graphs G and H (with the same nodes) have the same reachability condition then their intersection does too

I think the answer is most likely no too

I mean heck what am I saying of course the transitive closure exists (either it is the graph or something smaller, the graph is finite so you can just check exhaustively)

The question is how to show uniqueness for direct acyclic graphs

[stray reef]

when numbers go brr, obviously.

theyre the kind of person to say "i was good at math until the alphabet came in" unironically

[jolly ledge]

[devout coral]

hey, i need help regarding de-bruijn graphs:
how many k length circuits are there in the de-bruijn graph B(t,n) where n>=1, k>=n,t>=2

the circuits are not necessarily simple

every calculation I can think of is counting twice (or more) some cycles

[cunning mason]

*Let S be a set equipped with one or several methods for producing elements of S from other elements of S. A subset X of S is said to be closed under these methods, if, when all input elements are in X, then all possible results are also in X. Sometimes, one say also that X has the closure property. *

^ That is from wikipedia

But when talking about relations and closures, S and X would be relations right?

S could be a relation "equipped" with symmetricity, e.g from (x,y) you can produce (y,x)

and X is closed under symmetry if for any (x,y) in X, then (y,x) in X

is that correct?

[brave rock]

No

They are referring to functions specifically.

An example of what they mean is as follows: consider S to be the natural numbers, and its only 'method' will be addition of natural numbers. An example of a subset X closed under this operation is the set of even natural numbers.

We don't usually consider relations to be an example of this kind of thing.

[cunning mason]

ok

what does this mean?
"As every intersection of reflexive relations is reflexive, this defines a closure. "

i know what is a reflexive closure but i dont understand that sentence

[brave rock]

This "closure" is not referring to the "closed" that wikipedia was.

This is, as is so often the case, an informal word not being used for a precise meaning.

[coral parcel]

Be nice. We can do without calling anyone "the kind of person [whatever]" to their face.

[stray reef]

was not exactly a "to their face" moment but point taken

[ember obsidian]

the set
$$\bigcap_{S\supset R\text{ reflexive}}S$$
can be used to define the reflexive closure of $R$, in the sense that its the smallest reflexive relation containing $R$, and proving it uses the fact that an intersection of reflexive relations is reflexive. then we can prove
$$R\cup\brc{(x,x):x\in A}=\bigcap_{S\supset R\text{ reflexive}}S$$
hence both sets define the reflexive closure of $R$

@cunning mason

[vital dew]

eigenglome

[odd garden]

i guess integrals ?

[cunning mason]

for (b), is the set of all equivalence classes ${[x]_S:x\in \mathbb{R}}$

[vital dew]

MyFavoriteAccount

[cunning mason]

because even for irrational numbers, x-x is rational

[brave rock]

That's true for any equivalence relation

It's not clear to me what you mean to say there.

For what it's worth, the equivalence classes of S are not easy to describe in a satisfying way.

[cunning mason]

how would you describe them?

[ember obsidian]

boytjie said its hard to describe them in a way thats meaningfully different from just saying the definition

[cunning mason]

is there an equivalence class for each irrational number? And one equivalence class for all rationals?

[brave rock]

No, there is not a unique equivalence class for each irrational number

for example pi and pi+1 are in the same class. In fact, this holds for both relations.

There is indeed a single equivalence class that contains the rationals

[cunning mason]

then i have no idea what the answer to "what are the equivalence classes" should be like

[brave rock]

I'm inclined to agree.

Here's a more precise substitute that you may find helpful in the first exercise:

For the relation $R$ (not $S$) find a set $X \subseteq \bR$ such that every equivalence class of $R$ is of the form $[x]_R$ for \emph{exactly one} element $x \in X$.

[vital dew]

Boytjie (never-to-be-glomed)

[brave rock]

This ought to lead you to a more satisfying description of what the equivalence classes of R are.

[cunning mason]

but R is not even a equivalence relation

4 - 2 is natural but 2 - 4 isnt so its not symmetric

[brave rock]

Ah haha I misread N as Z.

Try replacing N with Z, and my exercise will make sense.

[cunning mason]

ok

[cunning mason]

what does this mean? That every equivalence class of R has just one element?

[brave rock]

I wish you'd asked this earlier if there was confusion!

Recall that $[x]_R$ is defined as $\build{y \in \bR}{x R y}$.

[vital dew]

Boytjie (never-to-be-glomed)

[brave rock]

This is NOT saying that every equivalence class of R has only one element, not at all.

I am asking you to find a set of so-called 'representatives' for the equivalence classes of R: a choice of element from each one.

[cunning mason]

for all equivalence classes of R, there is a unique x in X such that [x]_R can represent that equivalence class?

[brave rock]

That is what I wrote, yes

[cunning mason]

{x \in R : 0 < x <= 1}

for the integer equivalency class, there is [1],
for the [1.25] equivalncy class, there is [0.25]
etc etc

is it correct?

[brave rock]

That is correct, that is a nice example of a set of representatives

[cunning mason]

what about for (c)?

for any real number x, [x] is {x/100, x/10, x, 10x, 100x, 1000x...}

[brave rock]

Try repeating my exercise for the relation T. You may find it trickier.

[cunning mason]

maybe {x \in R : \forall z in Z( |x-10| < |x*10^z - 10|)}

[brave rock]

Maybe you can give a simpler characterisation of this set

It's not clear to me at a glance what elements are in it.

[cunning mason]

all real numbers x such that x is closer to 10 than any x*10^z

for example 50 wouldnt be in since 5 is closer to 10

[fossil mural]

do you have an example of a number that is in that set?

[cunning mason]

5

[fossil mural]

...oh right yeah 5 works

[brave rock]

OK sure

Another set that I believe works is $(0.1, 1] = \build{x \in \bR}{0.1 < x \leq 1}$

[vital dew]

Boytjie (never-to-be-glomed)

Boytjie (never-to-be-glomed)

[fossil mural]

it isn't

[brave rock]

So that would've been a nice way to write that set down.

[fossil mural]

1 isn't in the set because 10 is closer to 10 than 1 is

[brave rock]

Yes, so I wrote (1, 10].

Not [1, 10].

[fossil mural]

1.1 isn't in the set because 11 is closer to 10 than 1.1 is

[brave rock]

Ah there we go

Let me think for a moment

[ivory badge]

Logarithm

log(x)-log(y) in Z

(Base 10)

[brave rock]

Well there is an issue, which is 20/11 and 200/11 are equal distances from 10, so the uniqueness property that I requested is not satisfied. so in fact neither are in the set of representatives, meaning that their class is not represented.

But anyway, if we exclude one of them then the set ought to be (20/11, 200/11].

@cunning mason you may want to look at the discussion here

[cunning mason]

how did you come up with this?

[ivory badge]

Well, you can get any element in R by scaling it right?

[brave rock]

I think of the equivalence class as just moving the decimal point in a number around

we can set the decimal point to be before the first zero in order to get representatives. That would actually be [0.1, 1) but nevermind.

(0.1, 1] is equally good.

[brave rock]

What I mean by this is that 0.123 T 1.23 T 0.000123 etc

Whoops, T not R.

There are some details here, such as the fact that 1 = 0.9999... but I believe it works out anyway.

Whoops, you also need to worry about negative numbers. Well I won't go into details.

A true set of representatives would be (-1, -0.1] u {0} u [0.1, 1)

[weary tiger]

Can someone explain what is the author doing here? (the highlighted section)

[grand totem]

Bit late but I'd agree with this. The Wikipedia article is very vague with their definition. To make things a bit more precise:

Fix any set $S$. Let's call a pair $(X,y)$ with $X\subseteq S$ and $y\in S$ a \emph{rule}. We say a set $A\subseteq S$ is \emph{closed} w.r.t a rule $(X,y)$ iff $X\subseteq A$ implies $y\in A$.

Now the vague Wikipedia definition of "a set S equipped with methods for producing elements of S from other elements of S" can be seen as equipping our set $S$ with an entire system of rules $R$, i.e. $R$ is a set of rules or equivalently a subset of $ \mathscr{P}(S)\times S$.

Now given such system $(S,R)$ we of course say $A\subseteq S$ is closed if it is closed w.r.t. all rules in $R$. We're interested in the \emph{least} closed subset of $S$. That set is unique (since it's the least one) if it exists. To show that it does exist one can proceed in more than one way, but the simplest one is to take $\bigcap {A\subseteq S\mid A\text{ is closed}}$ (prove that this is the least closed set).

[vital dew]

Neverbloom

[grand totem]

Your example was the closure of relations. To illustrate, fix a set $S$ and a relation $R$ on $S$ and suppose we're interested in the least equivalence relation containing $R$.

Then this is exactly an instance of the phenomenon above. Our background set is $S\times S$ and our rule set is the union of $${(\varnothing,(x,y))\mid x,y\in S \text{ and } xRy},$$ $${(\varnothing,(x,x))\mid x\in S},$$ $${({(x,y)},(y,x))\mid x,y\in S}$$ and $${({(x,y),(y,z)},(x,z))\mid x,y,z\in S}.$$

[vital dew]

Neverbloom

[grand totem]

Sorry for the monologue but I thought it would be worth mentioning since inductive definitions like that are scattered throughout mathematics but outside of computer sciency literature it isn't really addressed on its own, and even there it's mostly folk knowledge you'd find in random papers or texts.
The only reference that is always included when this does get mentioned is a short paper by Aczel "An introduction to inductive definitions" if you're interested in more.

[weary tiger]

Anyone wanna chat

[jolly ledge]

#chill or discussion if it's not related to maths/discrete maths in the case of this channel

[orchid idol]

does anyone know where to find like a huge set of counting problems with solutions

[weary tiger]

this https://www.hmmt.org/www/archive/problems or search for the archive of past problems in math contests

i dont remember if they have solutions tho

[median dew]

i want to ask a few questions:

question 1: if we place s balls into s-1 buckets V1, V2,...,Vs-1 that are arranged on a cycle, then there is an index j so that for every 1<=k<=s-1 the buckets Vj,Vj+1,...,Vj+k-1. have together at least k+1 balls.

question 2: by pigeonhole principle, we get that for every 3<=l<=n-2, there are two neighbors of x that together with it from a cycle of length l.

question3:prove mental's theorem using induction on n, but remove only a single vertex each time.

does anyone can deal with?

[thorn bay]

I don't understand this notation

why is [r] equal to [r - 1/2]?

oh

I understand now

[iron marsh]

It's just a definition they game for that funky notation

[cunning mason]

what is the point of the y in a rule (X,y)?

a subset A of S is closed w.r.t a rule (X,y) iff A being a subset of X implies y is an element of A?

for example the reflexivity rule (X,y), X would contain all reflexivity pairs, but what is the point of the y

[grand totem]

The elements of X are the ones that "create" y. Think of X as premises and y as the conclusion. So a single rule is an instance of how to create a new element from old ones.
Hence A is closed under that rule iff when all the premises are in A, then so should be the conclusion.

[grand totem]

No, for reflexivity we'd have empty premises (unlike symmetry and transitivity it doesn't have any premises)
So for a single element x, ( ∅, (x,x) ) would be one instance of reflexivity (and then we do that with all x of the set our relation is defined on)

[cunning mason]

i understand

[cunning mason]

what does "system (S,R)" mean?

[grand totem]

A set S and a set of rules R on S

[odd prism]

If I want to prove ZxZ is countably infinite, can I just enumerate Z to show it is countable? I think there’s a theorem where if A and B are countable infinite, AxB is countably infinite?

[little prism]

well you should try proving that theorem

otherwise there isnt really a lot to do

proving that ZxZ is countable is essentially the same proof as showing that AxB is countable

[stray reef]

it's not hard to enumerate Z^2 either

[supple herald]

Guys how should I map from R to R^2?

[brave rock]

You can map from R to R^2 in whichever way you like haha

Tell us the actual question at hand

[weary tiger]

Hm

Interesting, lol

[stray reef]

send every x ∈ R to (420, 69)

[vital dew]

flebron

[crude shore]

Ah, I think the same inclusion-exclusion logic works.

[cunning mason]

the correct solution says $T={(X,Y)\in A/S\times A/S:\exists x\in X\exists y\in Y(xRy)}$

[vital dew]

MyFavoriteAccount

[cunning mason]

but isnt this also valid? $T={(X,Y)\in A/S\times A/S:\forall x\in X\forall y\in Y(xRy)}$

[vital dew]

MyFavoriteAccount

[cunning mason]

they'd have to be equal then since its says "unique", or the exercise is invalid

OK, i checked and since R is compatible, those relations are the same thing

[weary tiger]

Is it possible to know the number of possible hypergraphs with a n of nodes and m edges? Thinking in the adjacency matrix representation I feel like it should be 2^(mn)/(m!n!) But I'm not sure if I'm not double-counting somehow. Maybe there are row permutations equivalent to column permutations. If there are how would I count this?

[brave rock]

There are 2^n -1 possible edges, since they are just nonempty sets of vertices. A hypergraph with m edges is then simply a choice of m of these edges. So there are (2^n - 1) choose m such hypergraphs.

I hope the definition I had in mind is the one you did too.

@weary tiger see above

[coral parcel]

Without a clear statement that we're counnting vertex-labeled graphs, I'd say that overcounts isomorphic hypergraphs.

[brave rock]

True, I didn't think about isomorphism

[coral parcel]

And it's hard to correct for the overcounting because the amount of overcounting of each isomorphism class depends on how symmetric it is.

[weary tiger]

Whatever the function h(n,m) counting the hypergraphs with n nodes and m edges; h(n,m)=h(m,n) because for any hypergraph we can construct it's dual by assuming each edge is a node in the dual and each node is an edge in the dual connecting the edges in the primary.

I wonder if we can at least derive more properties like this

[coral parcel]

That might get you a multi-hypergraph, e.g. if you start with two vertices joined by a (two-ended) edge.

[weary tiger]

What would a two-ended edge be?

[coral parcel]

An ordinary edge.

[brave rock]

Indeed the definition I had in mind was a 'simple' hypergraph.

Implicitly I also assumed the vertices were labelled, as tropo pointed out earlier.

[coral parcel]

Or for a less trivial example, there is exactly one simple hypergraph (in Boytjie's sense) with 2 vertices and 3 edges, but several non-isomorphic ones with 3 vertices and 2 edges.

[weary tiger]

Hmm, that's true. So there are more constraints in the adjacency matrix.

Or maybe I described the dual wrong. Maybe I have to use the incidences as nodes in the dual

I know there is a way to decribe hyper-graphs as standard bipartite graphs where the first partition represents the hyper-nodes and the second one represents the hyper-edges. The connection between partitions would be the incidence

[coral parcel]

Yeah, but we need to accept multiple edges before the concept is symmetric under interchanging "nodes" for "edges". If we accept two different nodes that are incident to exactly the same edges, then after dualizing you'd have two edges with the same incident nodes.

Or, alternatively, declare that the ordinary K_2 is not a hypergraph.

[weary tiger]

Is that the only problematic case?

[coral parcel]

More like the simplest problematic case.

[weary tiger]

By definition a hyper-graph is V and E where E \subseteq 2^V. So each e \in E is s.t. e \subseteq V. My intuition is that each e could be represented as a bit-set of size |V| so the list of all those bit-sets would be a bit-map of adjacency. Since, at first there is no constraint I could think of the transpose as just another bit-map, but this time the rows would be the edges and the columns would be the vertices. You pointed out the K2 case. It would be the matrix [[1][1]] with transpose [[1 1]], this transpose would be interpreted as one vertex and two equal edges connecting it. So I guess the constraint is that we cannot have two vertices with exactly the same edges connecting them

Can you think about a problematic case that is not within this pattern?

[coral parcel]

So I guess the constraint is that we cannot have two vertices with exactly the same edges connecting them
Right, if you're willing to make that restriction, you do get a duality between vertices and edges.

[true shore]

How is 8g wrong? It’s the same concept as 8b and I got that one right

How is that wrong as well?

[steep creek]

G should be right

[true shore]

How abt second picture

[steep creek]

I’d assume it’s right because the relation is defined by (-1,-2) being an element of S

And it meets the conditions of x being greater than or equal to y

[true shore]

Yeah I just wanted to make sure I wasn’t being tricked

Like if (-1)S(-2) was a trick question or something

But yea I told them it’s rigt they haven’t emailed me back though

I got a 95 without those points

[steep creek]

-1S -2 is just saying S contains the pair (-1,-2)

[true shore]

Right

I know

I knew I had either a 100, 97, or an 87

When I got 95 I was like nah something is not right lol

[steep creek]

You should ask your professor then

Always worth getting the most points you can

[true shore]

I emailed ta’s they prob checking now

Yea of course

[steep creek]

Ahh yeah

[true shore]

Ty buddy

[steep creek]

Np

[true shore]

They gave me 2 extra points lol I knew I got a 97 on that test

[crude shore]

Hi folks 🙂 Let P(n) be the set of partitions of a positive integer n. Is there a nice relation between P(n) and P(n+1)?

[vital dew]

flebron

There's this relation at least: If $P_k(n)$ is the set of partitions of $n$ into $k$ numbers, then to create $P_k(n)$ we can take $P_{k-1}(n-1)$ and append $\{1\}$ to each partition, and then take $P_k(n-k)$ and add $1$ to each number in each partition. The union of these two sets is $P_k(n)$.

[crude shore]

Got what I needed 🙂 Specifically, the generalization of that statement is: Let $A_k(S) = {s + (k,) \mid s \in S}$ be a function that appends $k$ at the end of every partition in a set $S$. Let $P_i(n)$ be the set of partitions of $n$ that use parts of size at least $i$. Then we have $P(n)$, the partition number of $n$, is $P_1(n)$. Furthermore, we have $P_i(n) = {(n)} \sqcup \bigsqcup_{j = i}^{\lfloor \frac{n}{2} \rfloor} A_j(P_j(n - j))$.

[vital dew]

flebron

[odd garden]

can someone explain proof by contraposition in like fortnite terms

i don't understand the thing in black

i understood why we used n=2k but after i'm lost

[vale cairn]

If you don't survive til the last 5, then you don't win the fortnite game. So if you did win the game, you did survive til the last 5

If you play fortnite all day long, then you won't sleep. So if somebody sleeps well, then they aren't playing fortnite all day lol

[cedar spindle]

yo fortnite is pretty good

[brazen epoch]

I want to understand the summation and do you know any resource that will be helpful and here is an example problem i do not understand

[pure hearth]

https://www.khanacademy.org/math/algebra/x2f8bb11595b61c86:sequences/x2f8bb11595b61c86:constructing-arithmetic-sequences/a/converting-recursive-and-explicit-formulas-of-arithmetic-sequences, something like this probably helps

also answer to your problem

[opaque sage]

can anyone help me with this one

it is combination with repetition but I forgot how to do this

[opaque sage]

This one please

[faint copper]

Hi, is this permutation even ? if so why?
Is there a proper definition for it?

[stray reef]

what definition(s) have you seen for the parity of a permutation, and what makes them all improper?

[faint copper]

If the number of inversions in a permutation is even, the permutation is considered even in parity. If the number of inversions is odd, the permutation is considered odd in parity.
Then the permutaiton in the example is even.

[stray reef]

... you didn't answer my question of "what makes this definition you saw improper", and also i am pretty sure you're wrong about this permutation being even. how many inversions does it have?

i count seven inversions:
(1,2)
(1,3)
(1,4)
(1,5)
(3,4)
(3,5)
(4,5)
which makes this an odd permutation

[faint copper]

hmm, but I thought an Inversion is a pair elements a,b in the set so that :
a < b and σ(a) > σ(b).
With (1,2), 1 < 2 but not 2 > 5.

Also I don't know how to answer your second question, I am sorry

So if write down σ as a set :
σ =: {(1,2), (2,5), (3,4), (4,3), (5,1)}
I count :
(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5) also odd inversions, so it is odd

[coral parcel]

Looks like Ann was stating inversions by listing the σ(b) and σ(a) rather than the a and b. So her (1,2) inversion is the same as your (1,5).

(When you have the permutation written out as cycles, as here, it is easier to see the parity by looking at detect the length of the cycles, than to go all the way to the definition of inversion. We know in general that a 3-cycle is an even permutation and a 2-cycle is odd, so their product is an odd permutation).

[faint copper]

I understand now, I probably got tunnel vision and was looking only into the definition , so thank you guys

[vale cairn]

The "right" answer is wrong because if you plug in p false and q true you should get true

I agree with yours

[jolly ledge]

yee

[jolly ledge]

what was it? Your answer seems correct to me.

?

[jolly ledge]

ahhh

icic

[chilly dew]

am I the only one who doesn't see why Backus-Naur form deserves it's own name

it's like, the most reasonable and obvious way to write a production rule

Oh I guess the usage of | is pretty handy

[little prism]

well how would you want to refer it when talking someone without being able to say a name

[chilly dew]

refer to what

a particular rule?

I would just say "you can turn any occurence of a substring X into the string Y"

or literally write down X -> Y

[little prism]

like imagine talking to someone who wants you to build something and you arent sure what exactly they mean. wouldnt it be handy to just be able to tell them "write down what you mean exactly using the BNF" and then for the other person to know what you are talking about and giving you exactly what you want

instead of using some other notation and then having to explain the notatin they are using and so on

[chilly dew]

I guess it is a standardization, but like for two symbols lol

[little prism]

are we talking about the same thing? that seems like an incredible oversimplification

[coral parcel]

I think perhaps "Backus-Naur form" is mainly a way to credit Backus and Naur for the idea (and courage) to use context-free grammars at all to communicate the syntax of an invented language between humans, rather than simply as a theoretical concept for theorizing about the nature of languages in general, and/or analyzing already existing languages.
The particular contributions of the symbols ::= and | and <blah> are not in themselves all that of an intellectual achievement, but you need some hook to hang the name on.

[chilly dew]

Ah that would make sense

[little prism]

there are lots of things in math that were born from not very amazing ideas. but its good that they have names. also you cant overstate how much of your thinking now was formed by the way stuff is taught that back then was not known and had to be invented. stuff that is obvious now was far from obvious back then

[chilly dew]

Yeah, my original motivation to the question was “why did two guys slap their name on this thing that doesn’t really add any additional value to the theory”

[little prism]

I can't speak for this particular example but most stuff in math is named by someone else

"those people did that thing first, lets call that thing after these people"

[coral parcel]

Neither of them named the notation themself.

[chilly dew]

Good on them

[timber barn]

Which one is statement and which one is statement function?

[coral parcel]

I'd guess that a "statement function" in your context just means a formula that contains a variable that is not bound within the formula itself.

[timber barn]

statement can only be true or false

Like the sun is yellow

[coral parcel]

If my interpretation is right, then the exercise wants you to be familiar with the fact that "P(2,n)" isn't true or false until we have decided what "n" means -- but "forall n P(2,n)" does have a truth value that doesn't require us to know an n in advance.
(At the level where you're being asked this, you're most likely not supposed to notice that both of them are really meaningless until we have decided what "P" means.)

[chilly dew]

is the transition function literally a partial function in that it doesn’t specify what to do (i.e. specifies that you halt) for certain (state, symbol) pairs, even possibly pairs where the state is not a final state?

or is calling it a partial function just emphasizing that it is not defined for certain pairs (state, symbol) when state is a final state

But then it would be more appropriate to call it a partial function on the set Q x Gamma

Reading the definition literally would imply that a Turing machine can halt even when it hasn’t reached a final state, and that just seems weird

[opal crescent]

yes

[opal crescent]

honestly I prefer the term "accepting state" rather than "final state" for this reason

the goal of a turing machine is to accept or reject words

if your machine couldn't halt on non-final/non-accepting states, then (assuming your word triggers a finite execution on the machine) rejection wouldn't even make sense

it wouldn't even exist

@chilly dew

[chilly dew]

I see

On the other hand certain presentations (like Sipser’s Intro to ToC”) specify a single accept and a single reject state, and the transition function is total (not partial)

I’m sure it’s computationally equivalent, but that’s the easiest way to think about it imo

[opal crescent]

yeah there's a metric ton of equivalent-ish definitions for TMs

[chilly dew]

multi-tape, one-sided,

those are the only others I know of

[nocturne ingot]

I recently finished my discrete math course, and the whole concept interested me greatly, seeing as it's summer and my university's logic classes are only available in the spring, are there any online resources which do a good job picking up where discrete left off? Many-valued greatly interest me, but the talk of lattices confuses me

[undone karma]

What does the <S> means in this context?

[undone karma]

It also appears here. Checked the preliminaries but there is no mention

[pale epoch]

usually this notation is used for generating set

if S is a set of vertices that would be the graph containing S as vertices and edges being all the edges of the original graph that only connect vertices in S

but im just guessing here

[manic ice]

whats the topic that you guys have studied that is the hardest? for me i'd say simplex method/big m but what do you all think

[sour oak]

https://i.imgur.com/wCOKBRk.png
https://i.imgur.com/RCXMR5U.png

Why is this wrong? v1 and v2 are on a cycle

v(g) >= 3

G is connected

but isn't v3 a cut vertex?

[weary tiger]

I know nothing about Graph theory but I want to know wdym by overdetermined set of simultaneous eqs?

[sour oak]

OK i think i realize the issue here

he uses "any" to mean "all"

I think

[pastel tulip]

if you have n eqs and m < n unknowns it is overdetermined. there is no guarantee a solution exists

[iron marsh]

What are cut vertices?

[sour oak]

https://i.imgur.com/t3ZC4Rx.png

but I'm fairly certain he means "all" when he says "any"

[weary tiger]

uh yeah I see

[iron marsh]

@sour oak if I am understanding it correctly, the I don't think your example picture was a counter at all

p.s. all and any do not have a similar enough meaning to aasume that.

[iron marsh]

To make sure I understand it right, what is your disconnector in this set?

[sour oak]

v2<->v3

or

if we're talking about the cut

then just v3

[iron marsh]

So what you claim to be the disconnector of G i s v2, v3 and the edge that connects the two?

[sour oak]

well the theorem is about cut vertices, so the vertex-disconnector is just v3

[iron marsh]

My point is is that the things you cut, don't actually satisfy that c(G-X)>c(G), so it doesn't really apply here

[sour oak]

they do

imagine cutting v3

now you have the connected component v1, v2, and all the unnamed

and the one on the far right

all alone

that's a component in and of itself

[iron marsh]

But this cut didn't add more connected components to G-X

Quite the opposite in fact

[sour oak]

why not?

[sour oak]

this has 1 connected component

after removing, there's 2

[iron marsh]

.....oh, I thought the count was referring to the number of edges and vertices

This makes more sense

[sour oak]

https://i.imgur.com/6E4xVhg.png

[iron marsh]

Sorry about that, I got a little confused

[sour oak]

it's ok, his language is confusing I think

[iron marsh]

So to clarify, what exactly do we mean by a connected component?

[sour oak]

also annoyingly he uses \nu for something and v(g) for the number of vertices in a graph

[iron marsh]

I think I got it, but I wanna make sure

[sour oak]

"In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph"(from wikipedia)

basically if u can get from a to b its part of the component

[iron marsh]

So they are basically parts of the graph that are disconnected from each other?

[sour oak]

yeah

https://upload.wikimedia.org/wikipedia/commons/thumb/8/85/Pseudoforest.svg/1280px-Pseudoforest.svg.png

uh

so here are 3 components

[iron marsh]

Okay I'm with you. So yeah the wording is a little funky, but for "any two vertices of G, there is a two cycle," that means pick any two random (distinct) vertices, and there is always a two cycle between then

I'm with it now

[sour oak]

what he meant is that all distinct (u,v) lie on a cycle

yeah

that's what I figured

then it makes sense too

[iron marsh]

Don't worry, I got it now

That is an interesting claim. Have you tried to prove it yet?

[sour oak]

not formally

https://i.imgur.com/m2AzVCr.png

this is what a cut would look like, if one existed

[iron marsh]

A cut-vertex , would just be a removed vertex right?

[sour oak]

yeah

that creates another component

[sour oak]

so u see it has to look like this

and there can't be an edge between the two blobs(the other part of the graph)

[iron marsh]

Well, wouldn't it look more like an edge with a vertex in the middle?

Like this?

[sour oak]

i mean that's just the same thing

it's just that either the left or the right enter the blob

[iron marsh]

two edges+one vertex and one edge+two vertices seem a bit different, and possibly a noteworthy distinction

[sour oak]

it is not different, your two edges have a connection somewhere in the blob

i just put it in the blob

https://i.imgur.com/L1N2iWH.png

[iron marsh]

why?

[sour oak]

you just drew this

i put the one you put in "the middle"

in red

the ones on the left(or right) just go into the blob

it's the same thing basically

[iron marsh]

Okay sure

[sour oak]

so anyways if this isn't the case(there is no cut), then there must be an edge like so:

https://i.imgur.com/sxOCIji.png

so that's one direction

no cut => there must be such an edge => there is a cycle

[iron marsh]

I can't say I understand your argumetn

[sour oak]

the claim is
A connected graph(>3) has no cut vertices <=> all (u,v) have a cycle

[sour oak]

if there is no cut, then there has to be an edge between the two blobs

which means that there is a cycle for all (u,v)

[iron marsh]

I see the idea, how would you go about this if there were more than 2 components?

[sour oak]

the graph is connected so there is 1 component

[iron marsh]

nvm

[sour oak]

https://i.imgur.com/Zzn7pBF.png

this is how a cut looks like

(in red)

so if there is no cut

there has to be something like this

[iron marsh]

I understand

[sour oak]

https://i.imgur.com/vKs26Eu.png

yeah ok

this material is hard smh

the other direction is a bit harder i think

[iron marsh]

Well, if every (u,v) has a cycle between then, we can view each graph as a collection of sub-cycles. So if we can show this is true for a cycle graph, then it's pretty easy to extend it into the collection

Consider u-v-w be three vertices that connect to each other. And let c_1,c_2,..., c_i be the cycles that (u,v) and (v,w) share. Remove v from the graph. Every c_i has 1 connected component after v is removed. Since v and w are in a cycle, v and w are still connected, so the collection of cycles c_i are all still connected.

We conclude that there are no cut vertices because the graph will always remain connected, no matter what v we remove

There's an even better way to go about this. Assume all (u,v) have a cycle between them in X, and remove a point u_1 from X. Since removing a vertex from a cycle still makes the graph connected every point still connects to every other -> the graph is connected.

You can iron the details, but that idea is definitely more efficient

[sour oak]

interesting

I think the issue might be that (u, v) can have a cycle like u->v->u

or actually that is not a cycle

[sour oak]

It has to be insufficient

[iron marsh]

Not sure what you mean?

I'm trying to show that if we take a connected graph such that all (u,v) are in a cycle (connected is a consequence of this), that even if you remove a vertex, the graph will still be connected, aka no cut vertices.

[sour oak]

I know what you're trying to show

but I wonder if that is good enough

[iron marsh]

Absolutely.

[sour oak]

The proof in the booklet uses induction and all that, so unless he wanted to complicate matters... idk.

[iron marsh]

Look at individual cycle graphs, call it C_n where n is the number of vertices. If you remove a point on C_n, then that is isomorphic to a path graph

Path graphs are connected.

[sour oak]

It makes perfect sense to me.

https://i.imgur.com/6qOQYaO.png

https://i.imgur.com/CTJXkZc.png

[iron marsh]

Lovely. Now consider the graph X such that all (u,v) are on a cycle. We know if we remove any vertex, say u_0 for every cycle any points u,v share, there is a path between them (in that cycle), so X\{u_0} is connected

That direction is dond

They may have gone a different way about it, but you don't have to. This way is pretty efficient and it proves exactly what we need to

[sour oak]

you would agree that any graph with a cut vertex also contains a bridge, and that they overlap?

that is

if (u1, u2) is a bridge, then either u1 is a cut, u2 is a cut, or both in some cases.

hence if there are no bridges... no cuts.

and uh

no cuts -> no bridges

actually that might be incorrect

https://i.imgur.com/CqluDF0.png

this has a cut vertex, but no bridge.

[iron marsh]

Not sure what a bridge is to say

[sour oak]

instead of removing a vertex you remove an edge

but same thing otherwise

[sour oak]

=>
G has no cut-vertices and at least 3 vertices => assume by contradiction that there are some (u,v) that are not on a common cycle => then there is no back-edge from v to u(even through some other u') =>

1. if u has neighbors => u is a cut, since removing it means you cannot get from v to N(v)(neighbors of v)
2. if u has no neighbors => v is a cut, since you cannot get from v's neighbors back to u.
   => contradiction to G having no cuts => all(u, v) are in a common cycle

[sour oak]

I feel like this is still missing something

[iron marsh]

Why?

[sour oak]

Just because there is a path on the cycle doesn't mean all paths are connected, right?

or at least you haven't convinced me of that in the proof

[iron marsh]

Every two vertices are on a cycle, so every two vertices have a path that connect to them.

[sour oak]

what if that path was severed by u_0

[iron marsh]

Since this is true for every two vertices (u,v), the graph must be connected, because a connected graph is one where you can create a path from one vertex to any other

[iron marsh]

Draw a cycle graph and think about why cutting a point doesn't change the fact it is connected

[sour oak]

I am convinced of this already but the proof seems lacking mathematically

if that makes sense

[iron marsh]

Short answer, there are two paths between any two distinct points, one with u_0 and one without.

You can formalize the path if you wish.

[sour oak]

<=
G is has a cycle between all(u,v) => G is connected => if we remove any vertex v, then ?

[iron marsh]

Then any two points still lie on a cycle in the graph, so there is a path between them that did not contain u_0 (the one we cut) on the cycle

[sour oak]

that's not necessarily true, what if the only cycle contained u_0?

[iron marsh]

Yes it is. Draw a dang cycle...

Remove a point.

You can always find a path for two points when (u,v) is excluded

[sour oak]

a path, you said a cycle.

idk.

[iron marsh]

Help me understand what you're not getting please

[sour oak]

I feel like you're the one not getting me. I'm already convinced by your argument but I feel like if I wrote this proof in a test, for example, I'd get a big fat 0.

Maybe I should just email the prof and see what he says.

[iron marsh]

Why? It's mathematically sound

You got from point a to point b making no false assumptions, or too many assumptions, and showing all the facts you needed to along the way

This is the basis of a proof. If you do this, you've successfully constructed a proof.

[sour oak]

Alright.

[iron marsh]

The argument they gave is over the top and admittedly most of it is completely unnecessary

Which is fine...it's still a proof, just not the most efficient one.

Hell, there may be a better one than what I did, but the one we have is efficient, and I hope it makes sense to you.

[native dragon]

I'm pretty sure that this is a classic proof for whitney's theorem

[native dragon]

Also you do realize that even if u, v aren't on a common cycle, there can still be multiple paths from u to v right?

[sour oak]

Yeah but how is that relevant? Having a path is not enough for there not to be a cut(which is the claim)

[native dragon]

How is u a cut vertex though

[spark cedar]

guys may i ask a question about bfs and dfs

if this channel is not appropriate i can send it from dm

[brave rock]

It is. In the future I would recommend just asking.

[native dragon]

just ask

[spark cedar]

Which one is a minimum spanning tree that start from Eskişehir with Breadth First Search algorithm?

i thought it is third one but im not sure i always mix bfs and dfs

there are also distance values between them should i also share it

[native dragon]

well the third one isn't a tree right? I'm assuming the red edges are the traversed parts

[spark cedar]

yes red lines mean visited

[native dragon]

breadth first search means you start from a vertex and visit the verticies closest to it

so the vertex itself, then its neighbors, then neighbors of neighbors, etc

[spark cedar]

so second one is okay

[native dragon]

Yeah

[spark cedar]

thanks a lot

what about in dfs

in this question it asks for dfs

[native dragon]

DFS it's sort of like a path where you move to one vertex, and then from that vertex you try to move on to the next vertex

[spark cedar]

starting from eskisehir

[native dragon]

I'd say it's the first one

Because it looks like you started from eskisehir and then walked to three other nodes

and then when your path ends

you return to eskisehir and travel the remaining node

[spark cedar]

yess now i got it

thanks a lot

this topic is related to discrete math right? im sorry if im asking them in a wrong channel

there is also one more term minimum spanning weighted tree, is that mean visiting all nodes with the shortest way

[mossy arch]

hey i have a question regarding the wording here

what are all k-tuples with coordinates in {0, 1}, wierd language

[opal crescent]

it's a binary string with k bits if you want

(x_1, x_2, ..., x_k) with all the x_i's being 0 or 1

@mossy arch

[mossy arch]

ah

that sounds plausible, so what does that have to do with 'coordinates'

like what is a coordinate

[native dragon]

it's a cube graph

[opal crescent]

well hypercube

but yeah

[native dragon]

the idea that each vertex has a 'name', like for example (0,1) and (1,1)

and you connect each vertex together if their coordinate differs by 1

like (0,1) and (0,0) would be connected

for a k=3 case something like (1,1,1) and (1,0,1) would be connected

[mossy arch]

but (0,0) and (1,1) are not

[native dragon]

some sources call it 'cube'

[mossy arch]

i see thanks

[native dragon]

no they're not

drawing out the k=3 case you can see why it's called 'cube/hypercube'

[mossy arch]

it really should not be called a cube if k > 3

[thorn bay]

I was solving an recurrence relation, I crunched some numbers in python and arrived at a sequence but I can't find a closed form formula

wolfram gives a generating function:

Can I possibly arrive at a closed form solution with this generating function?

[iron marsh]

Out of curiosity, is there anything wrong with my argument for this?
Short version: For any two distinct points on a cycle, there are exactly two non-intersecting paths (excluding endpoints of course) between them. Therefore, if we remove a vertex, just choose the path without said vertex. For the graph X, every (u,v) has a common cycle, so we can apply the same idea to show there is a path for each one even after removing a vertex.

This was only a proof for the converse btw.

[opal crescent]

there's a match in OEIS for your sequence https://oeis.org/search?q=4%2C14%2C50%2C178%2C634, the closed form is there

a(n) = a*c^n - b*d^n, a := (5 + sqrt(17))/(2*sqrt(17)), b := (5 - sqrt(17))/(2*sqrt(17)), c := (3 + sqrt(17))/2, d := (3 - sqrt(17))/2.

at least if you want to work it out by hand you can check now

(the OEIS sequence is a little bit shifted compared to yours, starts at 1 instead of 4)

[thorn bay]

omg thanks a lot

[native dragon]

I mean yeah this is the proof for the converse

the other direction -> if the graph is 2-connected then every (u,v) is in a common cycle is what's trickier

[rose wasp]

How would you calculate the number of legal tic-tac-toe states? I can't figure it out

[native dragon]

btw a graph is 2-connected if the # of vertices you need to delete to disconnect it is at least 2 - hence the same as no cut vertices

[native dragon]

Also I think the formal terminology for paths like these is "internally disjoint"

cause none of the internal vertices intersect

[iron marsh]

Ah, internally disjoint. That''s definitely better wording, thanks.

[quiet tendon]

Can someon explain why this hold

If its a prime there is an edge

[iron marsh]

Not a theorem, just the way they defined the edges for V for this particular problem.

[quiet tendon]

Uhm so it normally doesnt hold?

But i still dont understand why it holds in this case

[brave rock]

It holds because we defined it that way.

This is like responding to ‘Let a = 2.’ by saying ‘but why does a = 2?’

[quiet tendon]

But I mean this is like way harder

It may be easy to see for u because u are so knowledgable but I don’t see it

What is so special about this particilar set of vergices

[brave rock]

No, it's exactly the same.

The vertices alone do not have any edge information.

They are, to repeat, defining what edges exist.

[quiet tendon]

So what besides the vertices sets makes it to have this property

[brave rock]

Nothing. Again, they are defining it!

[quiet tendon]

Oh wait

U mean it like that

So they just say this property hood

Hold*

[brave rock]

Yes

[quiet tendon]

Because that would make so much more sense

I was searching for any relations

[brave rock]

Idk how I could make this any clearer. They are defining the graph to have this property.

[quiet tendon]

My english isn’t that great mb

[iron marsh]

It's like relations. Usually we are given that xRy if and only if some property of x and y holds.
But that property for x and y is the definition for the relation.

[quiet tendon]

But thank you guys

[iron marsh]

But whatever that property is is usually given to us. Not because it was true by some theorem or what not, but because that's what we define to be true.

[quiet tendon]

Ah i see they give it either like this or in a picture i would assume

[supple geyser]

Can someone explain this question to me? I'm very confused

Starting from the recursive definition of set A described below, which element does not belong to this set?

Let A be a set of non-negative integers defined
per:
Base Pitch: 2ЄA, 5ЄA and 8ЄA.
Recursive Step: If xEA and (x+3)EA, then (x+1)ЄA and (x-1)ЄA

The answer must be one of the numbers below:

1
3
4
6
7

[iron marsh]

Look, at each of the base numbers

2 is in A, 2+3=5 is in A. By the recursive step, 1 and 3 must be in A.

So currently A has 1,2,3,5, and 8

We can continue with the base numbers: both 5 and 5+3=8 are in A, so 4 and 6 are in A.
Technicaly from here, we can do process of elimination since we now know 1,2,3,4,5,6,8

We now know 7 is the problem, but let's try to figure out why. In order to potentially be a new element in A, it must be one number smaller or larger than that element (from the x+1 and x-1).

So let's first check if we can do anything for 6.
Well, 6 is in A...but 9 is not, so we cannot apply the recursive step.

Similarly, 8 is in A, but...11 is not, so we cannot use the recursive step.

We cannot apply the recursive step for 6 or 8, so 7 cannot be in the set.

@supple geyser I hope this was useful to you

[jolly ledge]

this animation 💀

[weary tiger]

bro what the hell bro

[quiet tendon]

I don't understand this question his method is someone introduced himself to everyone I understood that part but why does that mean his partner will be automatically not introduced to anyone

they aren't introduced together right

oh I think I understand it

[quiet tendon]

my reasoning is everyone got a different answer so u start with someone being 8 then u know someone has to be 0 and knowing that everyone had a relation with that 8 that dot with no lines becomes 0 if u continue like this someone has to be 7 and someone gets 1 etc.

[quiet tendon]

why is the amount of edges in a complete graph n choose 2

I understand the other one with the summation of degrees = 2E

[brave rock]

An edge in K_n corresponds to an unordered pair of vertices

i.e., a choice of two vertices.

[quiet tendon]

oh so therefore from the n vertices u choose 2?

and what do u mean by unordered

[brave rock]

I mean they are not ordered, so the pair (1,2) and (2,1) are indistinguishable.

This is precisely what n choose 2 counts.

[inner otter]

you should also know it is n * (n-1) / 2, since the n vertices connect to each of the other (n - 1) vertices. divide by 2 if it is undirected and there are no loops

[quiet tendon]

ye I understood this one

I know it's equal to nC2

but it's kinda hard to see it from the nC2 part

oh wait I can see it as how many pairs of vertices does there exist too right?

[quiet tendon]

hey I understand this theorem but it's a bit confusing what A means here I thought it means arrows but that would be incorrect then is it just an arbitary letter?

[native dragon]

Isn't |A| just the # of edges?

[quiet tendon]

oh that might be the case

cuz then u say the degrees of all the in arcs is the number of edges = the number of out arcs which makes sense

and then 2* times the edges = the summation of all the degrees

[stray reef]

A is the set of edges.

by the looks of it.

or i guess arcs since they're directed

that's why it's called A for Arcs

[stray reef]

don't conflate a set with its cardinality

[quiet tendon]

but whats the difference by saying it's the cardinality of arcs when u write |A|

[native dragon]

oops typo

[native dragon]

|A| are how many elements are in A

[quiet tendon]

ye

so whats wrong about saying amount of edges actually?

[stray reef]

nothing

but that's |A|

not A itself

[quiet tendon]

oooh

I see

[quiet tendon]

are u btw good at doing proofs?

[stray reef]

you could say that i am, yes.

but why do you need to ask me specifically this specific question?

[quiet tendon]

I am trying to figure this out

[stray reef]

what do you really want? help with a proof problem?

[quiet tendon]

but it's pretty hard

[quiet tendon]

if u can help me that would be realy nice

[stray reef]

ok so you're reading through somebody else's proof

[quiet tendon]

huh

no I mean

explaining how I handle this question

[quiet tendon]

well the question is to proof it

[stray reef]

1. Ignore the proof written in the lower half of the picture. How do I do this question?
2. I am reading through the proof written here, but part or all of it doesn't make sense to me.
3. I've read and understood the proof here in its entirety. It makes sense to me written out like this, but how could I have come up with it?
4. I have something to ask that's not any of the above options, and will now clearly articulate it.

which of these best describes you?

[quiet tendon]

oh uhm let me see

I think 2. and 3. would hlep me

I don't understand it fully but also how do I come up with it

I was never good at proofs btw

I think he uses this property right

oh wait I tihnk this one

[stray reef]

ok

then lets first read through the proof carefully step by step

i'll now rearrange it into a neat bullet-pointed list for ease of comprehension

or give my best attempt at doing so

[quiet tendon]

I do understand some parts tho

[stray reef]

\begin{enumerate}
\item Assume that $G^{-u}$ and $G^{-v}$ are both trees, and denote their edge sets by $E(G^{-u})$ and $E(G^{-v})$.
\item We have that $|E(G^{-u})| = |E| - d(u)$ and $|E(G^{-v})| = |E| - d(v)$.
\item $G^{-u}$ contains $|V| - 1$ vertices, and is a tree.
\item By point 3, $G^{-u}$ contains $|V|-2$ edges.
\item Points 3 and 4 are also true for $G^{-v}$ verbatim.
\item By points 4 and 5, we have $|E(G^{-u})| = |E(G^{-v})| = |V| - 2$.
\item By points 2 and 6, we have $|E| - d(u) = |E| - d(v)$.
\item By point 7, we have $d(u) = d(v)$, as desired.
\end{enumerate}

[vital dew]

Ann (glomed)

[stray reef]

@quiet tendon please read through this proof and tell me the first line at which you get stuck

[stray reef]

ok

[quiet tendon]

why does that hold?

[stray reef]

$G^{-u}$ is $G$ with $u$ excised

[vital dew]

Ann (glomed)

[quiet tendon]

ye

[stray reef]

this means we throw out node $u$ and everything that was connected to it

[quiet tendon]

but isn't that just G^v?

[vital dew]

Ann (glomed)

[stray reef]

$d(u)$ is the number of edges connected to $u$, and hence the number of edges that get thrown out

[vital dew]

Ann (glomed)

[quiet tendon]

so u get G with u and v

and then u throw out the u

[stray reef]

G is a graph and it has two vertices named u and v yes

G^-u is the result of excising vertex u from graph G

[quiet tendon]

but if u throw out u

won't only v be left?

[stray reef]

no

nobody said u and v were the only vertices to exist in G

[quiet tendon]

oh

ahh

so it's saying all the orignial edges

• the edges which belonged to u

and the edges belonging to u are just d(u) because the degrees of it says how many edges were connected to them

oh I think I understand 2 now

[stray reef]

wording kind of sucks, but yes.

[quiet tendon]

how do I word it more nicely?

[stray reef]

d(u) is the number of edges connected to u, so that's how many edges are thrown out.

[quiet tendon]

oh ye I meant that I think

[stray reef]

repeat this instruction

read through this proof and tell me the first line at which you get stuck

[quiet tendon]

3. shouldn't the vertices be |V| - all the vertices in u

[stray reef]

all the vertices in u

how many is that

consider u is a vertex

[quiet tendon]

oh I saw u as a set of vertices

but it's just 1 particualr

[stray reef]

it says at the beginning of the problem

[quiet tendon]

I see

[stray reef]

Let G = (V,E) be a graph and let u, v ∈ V be two distinct vertices in G.

this unambiguously tells you u and v are in fact individual vertices and not sets thereof.

[quiet tendon]

ah and if they were sets it would've been said explicitly right?

[quiet tendon]

oh I understand it now

but it's just hard for me to come up with these things

[stray reef]

well, yes... such information is typically given in as clear a fashion as possible

yeah so as for coming up with this

[quiet tendon]

like how do I get as good as u

[stray reef]

this particular proof was a counting argument

like, the thing that was crucial to know was that a tree contains one less edge than the number of vertices

[quiet tendon]

the ones I have seen so far are proof by construction and proof by contradiction

[quiet tendon]

well I knew that but it's just sometimes hard to see oh I gotta use it here

[stray reef]

so perhaps to help yourself come up w/ those better, you could familiarize yourself with some quantitative results

for graph theory specifically

handshake lemma comes to mind

[quiet tendon]

handshake lemma?

[stray reef]

sum of all degrees equals twice edge count

[quiet tendon]

oh that one

I know that one too

[stray reef]

right

[quiet tendon]

so basically

most of the proofs I just need to know 1 particular key information

[stray reef]

i mean i dont have any silver bullets for you

[quiet tendon]

or theorem

[stray reef]

its a matter of practice

the more theorems you know (and prove for yourself at least once), the more results you see, the more proofs you read, the better your brain will be at making those connections

[quiet tendon]

I see

I will try one more in a couple of minutes by myself then

[stray reef]

k

[quiet tendon]

but the thing is these theorems or info that u need are very logical but it's just hard to see like I gotta work to this theorem or smth

[stray reef]

but if you want to ask me for help then please keep the question itself and your solution and your query separate

so that i dont get confused

[quiet tendon]

well I tihnk it's just I gotta work to proof this so I think of all the theorems about d(u) and d(v) concercing trees

is that good thinking?

[quiet tendon]

ah okay I will do that mb previous time

[stray reef]

dunno.

giving pointers on how to think about a particular problem post-factum is hard

[weary tiger]

Is this correct? I have an informal counting based intuition of why it's true but I don't know how to prove it

[quiet tendon]

question:

answer:

nodes are vertices btw

I understand the solution

but how do u come up to use contradiction

like how do u see that purely from only knowing the question

[brave rock]

You don't. Math requires creativity.

[quiet tendon]

okay but I somehow have to see it right

so say if I give u a set of question can u see what kind of proof u use?

[brave rock]

If you thought about it for a long time, and tried a lot of different things, maybe you would have thought about this.

[brave rock]

An experienced mathematician can.

But nobody can solve every possible question.

[quiet tendon]

so say I give u this

do u go like

okay this question needs contradiction

this needs construction

can u instantly see that?

[brave rock]

Pretty much, yes.

[quiet tendon]

huh

wtf

[brave rock]

But I have seen all of this before.

[quiet tendon]

oh for real?

[quiet tendon]

are we at the same school?

[quiet tendon]

and how do u do that

[brave rock]

I think about it, and because I have experience, I realise what the proof is going to look like.

[quiet tendon]

but can u explain your thought process

[brave rock]

If you want to ask a question, then just ask.

[quiet tendon]

I did

[brave rock]

But no, I cannot explain how I come up with ideas in general. This is actually a topic of research.

[quiet tendon]

what does it mean to be a topic of reserach

[brave rock]

People are actively doing research on how it is that people come up with ideas on how to prove things.

[quiet tendon]

isn't that just thinking

[brave rock]

Can you explain how you create thoughts? I think no.

[quiet tendon]

but isn't that using brain

[brave rock]

OK, then I guess my answer to your question is "I used my brain." Good luck.

[quiet tendon]

no I didn't meant to be like that

I guess that's not what u mean then

[quiet tendon]

can I ask a specific question

[brave rock]

Just ask

[quiet tendon]

for part b

so it's very logical

because if u take 1 path as u are going to v

and returning to u from the other path

u always have an cycle

but is it relay necessary to write all that

[brave rock]

If that is what your course expects you to do, then yes, it is necessary.

[quiet tendon]

but I meant like would you write it the same way?

[quiet tendon]

as long as the proof is right it's enough

[brave rock]

Depends on the context. If I were to be explaining it to someone just beginning to learn how to prove things well, then yes I think I would prove it like that. If I were doing it for another reason perhaps I would be less verbose.

[quiet tendon]

ah okay

well I guess I try to learn it this way then

but it's like so hard to come up with how he wrote by myself

[fossil mural]

for me at least, i wouldn't immediately see "methods" like contradiction, i would just see the "reason" for why the statement should be true

then once i intuitively understand why the statement is true, i have enough experience writing proofs that i could convert that into a fully written-out argument if i wanted to

[quiet tendon]

well for me I most of the time would see this is true or not

but to proof it

is a different story

[brave rock]

If you cannot prove it, then I daresay you don't actually understand why it's true.

So you should try working on that

[quiet tendon]

oh

I guess that's true

do u know

if I am in this situation

I can choose E H or I right

all of them cost 3

so it shouldn't matter right which I choose

blue ones are permanente

the red ones are temporary

[cunning mason]

does this relation have a name

or does it represent some property of functions or something

[brave rock]

We would say that f factors through g, I believe

so f R g if f factors through g

[ivory badge]

Yep

[cunning mason]

ok, is it true that f factors through any injective function?

[ivory badge]

Remember what I said earlier about f(x)=f(y) <- g(x)=g(y)

If g is injective, there’s something you can do with that

*note that the injective g is also R->R, you can’t just take any injection into R of course

[brave rock]

That is indeed true, you can try proving it if you like.

[ivory badge]

I think we talked some about this yesterday or so?

Though proving this shouldn’t be too hard directly

[brave rock]

I think MFA has the skills to prove this now, it seems like a good exercise

[ivory badge]

Indeed, it’s definitely possible with what he could know

[cunning mason]

is it valid?

[brave rock]

Yeah that works, gj

It should be noted that we don't use \mathfrak R for the real numbers, we use \mathbb R.

[quiet tendon]

hey I tried to do this question

what first came up to me was using contradicition

but why is that not the right choice

oh is it because it's too general, there aren't numbers given for example d(u) >= 2 or smth

and what is meant by components

[quiet tendon]

I tried to use this strategy but for every proof they are using a different method it looks like

[ivory badge]

I’ll now suggest going a step further.

Assume f(x)=f(y) -> g(x)=g(y), then prove there is a function h such that g = h o f

[cunning mason]

is f or g injective?

i didnt fully understand what you were saying yesterday

[ivory badge]

Nope

They’re just functions R->R

[cunning mason]

ok ill try

[ivory badge]

I definitely had a bit of a rambling train of thought til I cleaned it up

[stray reef]

what strategy?

[ivory badge]

Figure it out?

[cunning mason]

not yet

is the image of f a subset of the image of g?

isnt h just the identity relation

nvm

[ivory badge]

No, consider g = constant on 1, f = identity

Buuuut, as a hint in that same vein, ||g^-1(g(x)) contains f^-1(f(x)) [as in, the preimages/fibers/inverse images]||

[cunning mason]

is it the partition generated by f a refinement of the partition generated by g?

[ivory badge]

Yeah basically

That’s the implication, after all

Or, to phrase it more suggestively in the direction we’re going, g’s is coarser than f’s

[cunning mason]

what are these partitions called? and from this is it possible to infer that there exists a function h such that g = h \circ f?

[ivory badge]

“Partition generated by f” or “equivalence relation generated by f”

And yes, I’m pretty sure it is possible

In fact, there’s a couple different ways you could I believe

[uneven silo]

hmm

the proofs in discrete math are tough

[zinc kettle]

problem from my exam:
there are 5 colors A B C D E and a square. We need to color square's corners using these colors. How many distinct ways of coloring there are, considering that a square is considered the same if it's flipped/rotated in some way or its colors differ like this A<->B C<->D

for example: squares $^{AB}{CA},^{CB}{BA},^{BA}{AD}$ are the same but $^{BA}{CA}$ differs

[vital dew]

ta

[zinc kettle]

i dont know the answer but i think some ppl might find it interesting

[chilly dew]

I came up with the following statement + proof. Does it look good?

Let f, g: S -> S be functions. Consider the following statements:

1. There exists an injection h such that f = h ∘ g.
2. f(x) != f(y) iff g(x) != g(y).
3. There exists an h such that f = h ∘ g.

Then it is true that (1) -> (2) and (2) -> (3).

(1) -> (2):
f(x) != f(y) implies that g(x) != g(y) or else f(x) = f(y). Similarly if g(x) != g(y) then f(x) = h(g(x)) != h(g(y)) = f(y) by injectivity.

(2) -> (3):
For each x in im(g) observe that f is constant on the set g^-1(x) by the hypothesis. Thus we can define h: im(g) -> S by sending x to the the single element in the singleton f(g^-1(x)) and clearly f = h ∘ g.

[chilly dew]

hints:

• ||do casework on the number of distinct colors in a coloring. the final answer will be (4c0)*a + (4c1)*b + (4c3)*c + (4c4)*d, where a, b, c, d are the counts you find for 1, 2, 3, and 4 distinct colors, respectively.||
• ||your cases will have their own subcases, but exploiting symmetry can significantly reduce the overall counting||

[chilly dew]

(Assuming there is no hole in my proof.) I was initially surprised that this was true given that I have never seen it written down anywhere + it is pretty simply stated. But then I realized, no one really cares about if a map factors through another map; usually when we talk about a map factoring through another map the "lifting map" is canonical

[ivory badge]

I mean yeah, though whether it factors at all is sometimes useful even if not uniquely, since it can let some things be easier locally

Also, you can get something like

f(x)=f(y)-> g(x)=g(y) as a sufficient condition for some h to exist to factor through

(Not necessarily injective )

[chilly dew]

I think you want the other way around but yeah

I realllly wanted a single iff statement but alas

[ivory badge]

Nah, since if this implication was false, you most certainly could not get g=hf

[ivory badge]

also g=hf implies the implication hypothesis, so it’s a bit iff-looking

[weary tiger]

QUESTION:

Where can I find/google the information about a positive integer solution x, y, z to 313(x^3 + y^3) = z^3 ?

https://courses.csail.mit.edu/6.042/spring18/mcs.pdf only mentioned that it has a positive integer solution, and in the solution x, y ,z each have more than 1000 digits.

[jolly ledge]

,w 313(x^3 + y^3) = z^3

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by kiameimon#0

[jolly ledge]

,w positive integer solutions for z = cbrt(313) cbrt(x^3 + y^3)

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by kiameimon#0

[jolly ledge]

Weird

Welp, I suppose we'd have to work it out manually

[weary tiger]

Oh thanks everyone. My online friend googled out here https://math.stackexchange.com/questions/1613119/a-diophantine-equation-with-only-titanic-solutions

[jolly ledge]

wow.

thanks for sharing

[zinc kettle]

in my college we mostly used group theory and burnside lemma to solve this kind of problems. it does involve casework

[wild field]

hi guys, I need some help to understand a question, if a set X has 4 elements, how many relations of X are symmetric and unreflexive?

Is It 12?

[brave rock]

I don't think so, no.

It's not clear, though, if you mean irreflexive, or just not reflexive, as these mean different things. In any case I think you've undercounted a lot!

[wild field]

irreflexive sorry

[ivory badge]

The whole “not x” meaning like “not necessarily x” type naming conventions get me sometimes honestly

[brave rock]

Me too for sure

[chilly dew]

Ah certainly that would be more direct, I figured you were just constructive counting

[chilly dew]

in the construction at the very end for h, we needed f to be constant on g^-1(x) for it to work, i.e. g(a) = g(b) -> f(a) = f(b)

right? @ivory badge

Oh wait we have our f and g switched lol

sorry for the ping

[ivory badge]

real

[jolly ledge]

Complex

[tepid oak]

i have a generating function question in help 15 which i am stuck on

[pine canopy]

https://i.imgur.com/3Mq9M9E.png

Can someone help me understand what a path-system is?

This is the only explanation

wdym each of its components is a path?
i.e a graph that has multiple connected components? because it doesn't really make sense w/ the theorem

I can't even really think of a graph where d(G) >= n/2 and has 2 separate components?

that has to be impossible

[coral parcel]

Yes, it must mean connected components.

Note that the theorem doesn't speak about G itself being a path system, but about G[S] being one.

(Where G[S] is probably notation for something like an induced subgraph).

((Edge-induced subgraph, that is)).

[pine canopy]

hmm

[pine canopy]

so like without vertices not in its edges

for example
v1-v2-v3
and S = {(v1, v2)}
my graph is
v1-v2 and NOT v1-v2 v3

[coral parcel]

Yeah -- not that it makes much difference if you view an isolated vertex as a degenerate case of a path.

I wonder if they forgot an assumption about s, such as |S|=s, though.

[pine canopy]

https://i.imgur.com/c5K0Ek2.png

basically like so

(marked edges are S)

[pine canopy]

oh?

yeah I guess it does make sense, in this case I assumed s=0 but |S| = 4

it still worked out... but maybe it's not sufficient

would it be proper to email my professor to ask about this?

its his notebook...

[pine canopy]

it still worked however

This theorem seems a bit silly... like you just need so many edges, it is fairly obvious your S will be part of the HC

d(g) >= n/2 is already enough to prove there is a HC

even if you pick |S|=1 , (n+1)/2 means that you need to add at least 1 edge to your graph that already has a HC(which means it visits S)

[coral parcel]

Consider this, though. The graph has 8 nodes and is 5-regular, but there's no Hamiltonian cycle that includes the red path system.

... despite apparently satisfiying the assumptions of the theorem with s=2.

[coral parcel]

Or for that matter, this, with n=12, delta(G)=10, s=8, |S|=11.

[neat pasture]

yo

can anyone help me with a divide and conquer algorithm

preferably in a dm setting

[brave rock]

Just ask your question; people who can help will answer.

[neat pasture]

Dont really want my code leaked thats why

I'd rather put in dm

[brave rock]

Good luck with that

[jolly ledge]

overflow exists

[neat pasture]

can someone help me draw a DFA

[ivory badge]

.

Ask questions directly not some weird roundabout asking for help without giving the question

[cunning mason]

regarding question 5, all the previous exercises are the same for f:A->B and g \circ f :A->C right?

[ivory badge]

Well it’s another function

Idk anything interesting about it

[cunning mason]

why would there be theorems that apply to the composition of two functions but not to a single function

[coral parcel]

It's asking for theorems that relates facts about gof to facts about g and/or f.

For example, if f(A)=B and f(B)=C then (gof)(A) = C.

[ivory badge]

What can you say about the image of g o f related to that of f or smth

Ye

[neat pasture]

"Draw a DFA for language of binary representations of natural numbers divisable by 2 by not 4. Use at most 5 states and the empty string, 0, 1, 00, 100, etc should be rejected"