discrete-math

[hollow token]

They can also give us a specific graph type and we need to explain its characteristics (which is basically just theory without much analytical approach) or tell us to explain all graph types

Like N_n, K_n, C_n, etc.

[dire walrus]

N_n? Rest I can understand

[hollow token]

Neutral graph

A single point without any edges IIRC

[dire walrus]

i have never heard of that term ever

[hollow token]

I think it's just annotated as N_1

oh sorry its null graph, mb

https://en.wikipedia.org/wiki/Null_graph

[dire walrus]

\bar{K_n} makes sense to me

but honestly, I think considering the empty graph as a graph is... umm... a choice

[hollow token]

N_n = null graph
K_n = complete graph
P_n = path graph
C_n = cyclic graph
W_n = wheel graph
K_n,m = bipartite graph

and there's one more i think that i forgot about

[dire walrus]

You have to remember the notations?

[hollow token]

nvm that's all

[hollow token]

yes, and their characteristics

[dire walrus]

also, K_{n,m} is not bipartite, it is the complete bipartite on n+m vertices

[dire walrus]

that sounds appalling

[hollow token]

yeah i apologise it's still all jumbled in my head

[dire walrus]

For us, we gladly tell the students what a notation means

or our profs tell us

and for characteristics, what are the things you have to remember? Eigenvalues? Eigenvectors??

Because I don't remember anything that cannot be argued in a single line

[hollow token]

More specifically:

• Number of vertices (V)
• Number of edges (E)
• Order
• Size
• Diameter
• Radius
• Complement
• Denote which ones can be autocomplimentary (isomorphic to its own complement)

[hollow token]

^

[dire walrus]

how does order differ from number of vertices?

what even is size?

[hollow token]

one sec

[dire walrus]

But mmmmm... why remember when you can derive

[hollow token]

My uni is very cooked

[dire walrus]

the autocomplimentary thing is cool. A quick check is the number of edges. If it is not n(n-1)/4, for sure it is not autocomplimentary

so a quick check is whether n=0 or 1 mod 4. If not, no chance it is autocomplimentary

[hollow token]

So to check if it's autocomplimentary is to check if n=0 or if n equiv 1 mod 4?

[hollow token]

also apparently |V| = Order and |E| = Size

This is basically what the task says:

Describe the graphs N_n, K_n, C_n, P_n, K_m,n and W_n -- determine their V and E, denote their Order, Size, Diameter and Radius; describe their complement and denote the ones which can be autocomplimentary. Write at least one example of each. Write down definitions of all terminology used and elaborate upon them.

I am probably failing this one :p

But I can at least do BFS and congruences

Thank you for all your help!

[dire walrus]

No worries

Sorry had to go for dinner

[dire walrus]

This is necessary, but not sufficient.

[hollow token]

Yeah I need to learn about that

[dire walrus]

The proof is simple

What is the union of a graph and its complement?

Say the graph is on n vertices

[hollow token]

The union? It's the original graph with all its neighbours mapped identically, I believe?

I know that a graph is isomorphic if f : V -> V' keeps the adjacency list in tact, in other words: forall u,v in V u ~ v <=> f(u) ~ f(v)

[dire walrus]

Right, we will come to that

[hollow token]

So you are asking about V union V'?

[dire walrus]

Yup

[dire walrus]

Also there is more needed in this definition. V and V' must be of the same size

[hollow token]

I see

[hollow token]

Also I don't know the answer to this question

[dire walrus]

Think in terms of pictures

If you had a graph, what does its complement look like?

[hollow token]

Like a cross turning into 2 parallel lines?

[dire walrus]

Not exactly that description

Like, if there was an edge in G, can the complement of G have that edge?

[hollow token]

No

[dire walrus]

And if the complement of G has an edge, can G have that edge?

[hollow token]

No

[dire walrus]

So do you agree that the complement is exactly the graph you get if you deleted all the edges and added all the edges that was not previously there?

[hollow token]

Yes

[dire walrus]

Now how about this then?

[hollow token]

It's all the possible edges for a given graph G

[dire walrus]

Yup

That graph has a name

You even mentioned it once

[hollow token]

bipartite?

[dire walrus]

No?

[hollow token]

wait no its complete graph

K_n

[dire walrus]

You have a bunch of vertices, and all possible edges as you said

Yup! Bingo

How many edges does this have?

[hollow token]

It should have n(n-1)/2 edges

[dire walrus]

beauty

[hollow token]

I am so amazed I remember the binomial something something

[dire walrus]

so |E(G)|+|E(G')|=n(n-1)/2, agreed? Where E(G) is the edge set of our graph and E(G') is the edge set of the complement of G.

[hollow token]

It should be E(...)

[dire walrus]

edges my bad yes

[hollow token]

but yes

[dire walrus]

But, isomorphic graphs have the same number edges, right?

[hollow token]

Yeah, they should

[dire walrus]

not just autocomplimentary, in general

If G and H are isomorphic, they have the same number of vertices, same number of edges, same everything

[hollow token]

yeah my bad, i figured that what i said was wrong

[hollow token]

yes

[dire walrus]

then |E(G)|=|E(G')|, correct?

for our case?

[hollow token]

it should be, I think?

or actually, i guess not necessarily?

[dire walrus]

We are working with autocomplimentary graphs, so G andf G' are isomorphic (G' is the complement of G)

[hollow token]

Oh, then yes

[dire walrus]

right

then solve for |E(G)|

what do you get?

[hollow token]

You mean solve from |E(G)|+|E(G')| = n(n-1)/2?

It's just |E(G)| = n(n-1)/4

[dire walrus]

right!

[hollow token]

Since |E(G)|+|E(G')| = 2|E(G)| iff |E(G)| = |E(G')|

[dire walrus]

Now just some number theory

4 must divide n(n-1) [number of edges cannot be a fraction]. Since n and n-1 cannot both be even, 4 must divide exactly one of them. If 4 divides n, then n=0 mod 4. If n divides n-1, then n=1 mod 4.

Following?

[hollow token]

Yes

[dire walrus]

Well then you have your result

[hollow token]

So that's how we get condition n = 0 mod 4 or n = 1 mod 4

[dire walrus]

If G is autocomplimentary, then the number of vertices in G must be 0 or 1 mod 4

[dire walrus]

yes!

[hollow token]

you are implying 0 mod 4, right?

[dire walrus]

wdym?

[hollow token]

here i mean

n = 0 mod 4 or n = 1 mod 4

[dire walrus]

it can be 1 mod 4 too

[hollow token]

yeah okay just making sure i got that right

[dire walrus]

but this is only necessary. This modulo condition is not sufficient

[hollow token]

then we have to check for bijection on f, yeah?

[dire walrus]

(In fact, given a graph, it is very hard to check if it is actually autocomplementary. In fact it is almost as hard as checking if two graphs are isomorphic, and finding an efficient algorithm for which is like a holy grail for complexity theory researchers)

[hollow token]

yeah we only really have one example of an autocomplimentary graph

and its C_5

everything else that we glance over is just not autocomplimentary

[dire walrus]

mmmm

I know all Paley graphs are autocomplimentary

[hollow token]

i think we haven't mentioned Paley graphs

[dire walrus]

understandable

the construction of those graphs requires finite fields

[hollow token]

to be fair this is 1st year CS math

[dire walrus]

bachelors I suppose?

[hollow token]

yeah

am hoping to go for a MSc

[dire walrus]

Here is a cool paley graph

[hollow token]

Ohh, that looks really cool

[dire walrus]

well, good luck to you!

[hollow token]

so far the best math I had was involving proofs, relations and operators on number sets

[hollow token]

thank you! I'll definitely need it

[dire walrus]

Well, I don't know where you are studying, but maybe you will get to see some cool math

the pg programs in cs ()we don't have an ug for cs) at our place is... well... lackluster in math

it is good for cs folks wanting jobs, but eh...

[hollow token]

PG, UG?

[hollow token]

the math here is fairly rudimentary compared to everything else

[dire walrus]

post-graduate, undergraduate

[hollow token]

ah

[dire walrus]

,ti .kernel

[vital dew]

This user hasn't set their timezone! Ask them to set it using ,ti --set.

[dire walrus]

blehh

[hollow token]

i live in bosnia

[dire walrus]

ah

[hollow token]

GMT+2/CET

[dire walrus]

far from my place haha

,ti

[vital dew]

The current time for nekomatism is 12:44 AM (IST) on Mon, 23/06/2025.

[hollow token]

here for 1st semester we had 7 step solutions for graphs (range, 1st derivatives, 2nd, etc.), uhh the tasks where you find if the rhs is divisible by the lhs, integrals, and differential equations

i passed that with a 10 (highest mark here), and for math 2 (2nd semester) i passed my midterm with a 7

[dire walrus]

marks barely matter honestly

take it from someone who had terrible ug and pg scores

[hollow token]

yeah but to be fair they matter for me because of my scholarship

[dire walrus]

ohhh...

[hollow token]

I need to be passing to qualify, and need to keep a GPA of 8.0+ for bonuses

[dire walrus]

yeah I was talking about the long run, but if you have a scholarship, you gotta be careful

[hollow token]

its not that strict, i mostly want to aim for those bonuses lol

as long as you pass every year they'll fund you

But yeah in the long run i understand marks dont really make a difference

Ive been a software dev for 10 years, mainly in uni just to get a BSc so i can find work more easily

[dire walrus]

Oh that's nice! Hopefully you will enjoy it!

Completely unrelated, but that furina banner is fire :D

[hollow token]

Thank you! I found it on Pinterest

[limpid leaf]

I need to show that this graph is non-planar using Kuratowski’s Theorem, stated as

A graph is planar iff it does not contain a subdivision of K_5 or K_3,3 as a subgraph
The definition of "subdivision" I have been given doesn't seem very rigorous, but I get the impression that a vertex added in a subdivision should have degree 2, so we can only use g in one "divided" edge of the subgraph (please correct me if I am wrong about this).

Any pointers or solutions appreciated :)

these are my attempts so far

[odd heart]

Both of your attempts ignore g and any of its edges altogether, so they won't work (if you remove g and all adjacent edges from the original graph, it becomes planar). Note that subdivision involves vertices of degree 2, but that means the vertex should have degree 2 in the subgraph, so intuitively you could ignore 4 edges adjacent to g and then consider it as subdivision (for example, if you remove the edges gb, gc, gf and ge, then the resulting graph is a subdivision of one where there's no g, but there's an edge directly joining a and d)

[limpid leaf]

The dashed lines in my attempts are meant to indicate edges that could be divided by g, but the problem is that in both cases there are more than one of these necessary

Sorry, that wasn't clear

[odd heart]

Just one should suffice.

As a hint, try to keep the edge "ad" and find K3,3 as a subgraph in that.

[limpid leaf]

found it!! b,a,e; c,d,f

thank you

[odd heart]

@limpid leaf This one is much easier if you have the other theorem (Wagner's theorem) which involves contractions (just contract AB and DE, and you get K5, unless my intuition fails me): https://en.wikipedia.org/wiki/Wagner's_theorem

My favourite example for this is the Petersen graph, where you're very tempted to look for K5:

But to invoke Kuratowski's theorem you actually need to find a subgraph that's a subdivision of K3,3

With Wagner's theorem you just contract the edges connecting the outer five to the inner five and there's your K5

[limpid leaf]

Unfortunately I am studying for an exam and probably won't get away with quoting other theorems, but this looks interesting to know in general, thank you :)

[rocky torrent]

Now i officially hate math

Like complex numbers makes no sense, teacher making theorems with name and i dont even know what he is yapping about like what in the fuck is "Omnibus theorem"

I don't find it ANYWHERE

I mean nothing makes sense

[odd heart]

Your feelings are valid, but this is not the channel in which to air them (I'd recommend #discussion or #chill )

[rocky torrent]

But i came here to understand complex numbers

[odd heart]

Still not the best channel, probably #precalculus or #prealg-and-algebra

[hidden totem]

curious why you're learning about majorization

what is the context for this? why are you screenshotting an LLM output?

[rocky torrent]

because the presentation is not in english

and so i translated it

[hidden totem]

can you at least explain the context then? what math level, what topic?

[rocky torrent]

because the dog teacher asked for it in exam

[rocky torrent]

university

discrete math

infinite set

[rocky torrent]

thats bad

cuz everything i learnt is from "discrete math"

so i am not sure anymore 😭

[hidden totem]

very weird that a discrete math course would go over both complex numbers and majorization from a set context

[rocky torrent]

nono

first of all

0. natural number

2. sets

3. inf sets

4. algebra+complex number

5. number theory

[rocky torrent]

something like modulo and things like that

and that ugly three line equal sign

[neon harbor]

If your course is literally taught by a dog then I would understand your frustration, but if not I think your attitude is the main issue

[rocky torrent]

i just cant learn it man

[elder light]

Ugly??

[dreamy coral]

Honestly i would really like a class being taught by a dog i love dogs

[neon harbor]

Me too, maybe dogoligical algebra for example, dogs are very good at chasing diagrams

[rocky torrent]

Mayb

[rocky torrent]

I failed 3 times in exam

[dreamy coral]

that proves more about yourself than it does your prof

[rocky torrent]

Duh

But i studied !!!!

[dreamy coral]

you might be studying ahead of where youre currently at

i would recommend going back to earlier content and building understanding from there

that would help with later concepts of course

[rocky torrent]

Can you help me with one specific thing?

[dreamy coral]

probably not, i dont know much set theory myself

[rocky torrent]

Nono its not set theory

[dreamy coral]

ah

[rocky torrent]

Its modulo stuff

[dreamy coral]

possibly

oh like modular arithmetic

[rocky torrent]

I dont understand ahhh

Tmr= full remaining system
Rmr =reduced remaining system

Im not sure how you call it

[dreamy coral]

i think its a residue system

im still not fully sure what its saying

[rocky torrent]

Same

There is also that euler function

😭

[quick folio]

it's talking about how residue systems remain reside systems under certain operations

in particular adding any integer to every number inside a residue system gives you another residue system, and multipling every number in the system by a fixed number that is coprime to m gives you another reside system

[rocky torrent]

👀

What...

[quick folio]

it's an important lemma for proving some important results in basic number theory

[dreamy coral]

Wait a minute thats an application of cosets from group theory isn't it

[quick folio]

yes basically

this is how naive NT is taught w/o group theory lol

[dreamy coral]

Aka my terrible elementary NT class

Doing algebra before NT would make that class 2 weeks long

[quick folio]

yeah basically

[rocky torrent]

And why is that my teacher named it with something i cant find in the internet

[quick folio]

well you haven't shared enough for me to tell you why

[rocky torrent]

It says omnibus theorem

But all i see is statistics lmao

[quick folio]

preliminary results I'm getting says that omnibus is a method, not a name

but you'll have to ask your teacher

[odd heart]

It also might be something specific to Hungarian

[rocky torrent]

Its a damn bus type

😭 🙏

[odd heart]

Omnibus in general means something general/encompassing.

It's almost certainly used here more as a descriptor than as a proper theorem name

[rocky torrent]

Bruh

I see

[odd heart]

It's also a bus type in English, although I'm not sure whether it's a damn bus type.

https://en.wikipedia.org/wiki/Man_on_the_Clapham_omnibus

[rocky torrent]

Alright

[cloud rampart]

they mean exactly the same thing, bus is just short for omnibus (which is dated)

nowadays it usually means an anthology or collection

[cunning widget]

Hi, i am just wondering what the difference between an element and an object is in this context: "A tuple with n elements, an n-tuple, is a collection with n objects in which both the mutual order and the number occurrences of each object count."

[dire walrus]

(potato, tomato, potato, potato, mango) is a 5 tuple, and it is different from (potato, mango, tomato, potato, potato) and both of them are different from (potato, potato, potato, tomato, mango)

The 'potato', 'tomato' and 'mango' are your objects. They are also called elements here

There is no difference in this context

[cloud rampart]

an object is a thing that exists in general whereas an element is a member of a particular collection

[dire walrus]

in this context, they mean the same thing, right? We do say tuple with n things or tuple with n elements interchangeably (or at least I do, maybe that is wrong?)

[cloud rampart]

well the elements of a tuple are also objects so for the purposes of the above sentence they could be interchanged

[dire walrus]

yeah alright phew

[cunning widget]

understood, so they are just used as synonyms in this context?

[cloud rampart]

yeah in this instance it doesn't matter

but in general let's say you're working with integers, and the tuple (1,3,4). then the numbers 1, 2, 3, 4, and 5 are all objects. 1, 3, and 4 are elements of the tuple and 2 and 5 are not elements of the tuple

[cunning widget]

aah, now it all makes sense, thank youu

[cunning widget]

Yes, they are indeed different from each other because the elements in each 5-tuple are arranged differently. In other words, each tuple has its elements in a different order compared to the rest, right?

[dire walrus]

yes!

The ordering in a tuple matters a lot

[cunning widget]

yess

got it, thanks

[cunning widget]

Alsoo, how can the empty set be a subset of the set A = {a, b}? I dont really understand, because the empty set has no elements, while A has the elements a and b, and by definition "A subset is a set B whose elements are all elements of another set A." Lets say B is the empty set, how is it a subset of A then?

[cloud rampart]

all zero elements of the empty set are members of A

it's what we call vacuously true

[cloud rampart]

basically if it were untrue you should be able to find at least one element for which it is not true (a counterexample). if no counterexample exists then by default the claim is considered true

[cunning widget]

aah, got it

[dire walrus]

Mathematically you write this as "B is a subset of A" if "for all x (x in B implies x in A)" is true.

Let's test it with B as the empty set. For all x (x in the empty set implies x in A). But look! x in the empty set is false by default, so the implication is true automatically. Thus the empty set vacuously satisfies the definition of an empty set as cloud said.

[cunning widget]

i seee, thanks a lot

[dire walrus]

I know this might not be appropriate for the intended audience, but I would be a little careful while making this statement because iirc, this is only valid in classical logic, right?

A proof/procedure showing no counterexample exists does not immediately give me a proof/procedure for the universally quantified statement is what I remember.

[past rivet]

Hmmm

As far as I remember, one of de Morgan’s laws still holds constructively

$\neg (A \vee B)$ should be equivalent to $\neg A \wedge \neg B$?

[vital dew]

Pseudonium

[fossil mural]

yes, that's true

[past rivet]

Or more generally $\neg (\exists x . P(x))$ should be equivalent to $\forall x . \neg P(x)$

[vital dew]

Pseudonium

[past rivet]

It’s the other one that doesn’t work

Constructively you should have $(\exists x . \neg P(x) )\implies (\neg(\forall x . P(x)))$

[vital dew]

Pseudonium

[past rivet]

But I think the reverse implication does not hold constructively

[fossil mural]

yeah

if you have $\exists x. \neg P(x)$ and $\forall x. P(x)$ then you can get a contradiction by taking a witness $x$ for the $\exists$, putting it into the $\forall$, and observing that it satisfies $P(x) \land \neg P(x)$ which is obviously nonsense

[vital dew]

bee [it/its]

[past rivet]

mhm

[fossil mural]

but you wouldn't expect the other direction to be provable because, intuitively, $\neg (\forall x. P(x))$ provides no information, it's an entirely negative statement

[vital dew]

bee [it/its]

[past rivet]

mhm

[dire walrus]

So not exists x not P(x) implies forall x P(x) constructively? [sorry on my phone, and latex typing just is clumsy here]

[fossil mural]

and in fact we can get WLEM out of it
$\neg (\forall x \in 2. (P \leftrightarrow x))$ is provable, because it expands out to basically $\neg (P \lor \neg P)$, but if you could then conclude $\exists x \in 2. \neg (P \leftrightarrow x)$, then that's $\neg P \lor \neg \neg P$

[vital dew]

bee [it/its]

[fossil mural]

no

[past rivet]

Is this “weak law of excluded middle”?

[fossil mural]

yes

[dire walrus]

Beauty...

[past rivet]

Interesting, this is the first time I’ve come across it

[dire walrus]

At least my 2 am tipsy brain did not remember wrong.

[fossil mural]

$\neg \exists x. P(x)$ is equivalent to $\forall x. \neg P(x)$, but that means that if you have $\neg \exists x. \neg P(x)$, all you can get from that is $\forall x. \neg \neg P(x)$

[vital dew]

bee [it/its]

[dire walrus]

Right, that was what I argued in my head semantically, but I was not sure if I was remembering correctly

Thanks so much, and good night. I can now sleep in peace.

[past rivet]

I’m pretty sure this is just a special case of $(\exists x . P(x)) \implies Q$ being equivalent to $\forall x . (P(x) \implies Q)$

[vital dew]

Pseudonium

[past rivet]

Just by taking $Q = \bot$

[vital dew]

Pseudonium

[fossil mural]

yes it is

[past rivet]

universal properties~

[dire walrus]

Couple of cool questions I found today. Sharing one of them now, might share the other later.

Suppose we have $n$ letters and $n$ envelopes, with each letter having exactly one correct envelope. Let $D(n,k)$ count the number of ways to put the letters in envelopes such that exactly $k$ of them are correctly matched. What is $$\sum_{j=0}^n jD(n,j)\ ?$$

[vital dew]

Nekory

[coral parcel]

Well, if you divide by n!, you get ||the expected number of correctly matched letters if you just choose envelopes at random -- which by additivity of expectation must be ...||

[dire walrus]

This is one solution! Beautiful, love to see probability rear its head in places like this.

[true venture]

The total number of fixed points in all permutations of [n]. I'd think there is a nice egf A(x,y) = Sum_{n,k} x^n y^k for the number of permutations of [n] with k fixed points. Then taking A(x,y) d/dy and setting y=1 gives the egf series of sum jD(n,j) for each n. I think

[true venture]

Could also do some binomial coefficient sum

[flat summit]

can sombody help me on this problem it says how many sequences length n that consist of elements 0,1,2,3 and that 0 and 1 are not together

i tried recursion but the problem is if i have a sequenc lets say length 3 and if the second to last number is 2 or 3 i have 4 sequences but if the second to last number is 1 or 0 i cant really put a 0 or a 1 so i only have 3 sequences

so i need like a system of recursions but idk how to set it up

[true venture]

Another way to try is to subtract the sequences with 0 and 1 together from the 4^n sequences of {0,1,2,3}.

[cerulean wind]

count the number of sequences of length n with no consecutive 0’s and 1’s that end in 0, 1, 2, or 3, then add them together. that is, if a_n is the number of sequences of length n which end in 0 and have no consecutive 0’s and 1’s, b_n is the number of sequences of length n which end in 1 and have no consecutive 0’s and 1’s, similarly for c_n and d_n, then

s_n = a_n + b_n + c_n + d_n

where s_n is the number of sequences of length n that don’t contain any consecutive 0’s and 1’s.

now we have
a_{n+1} = a_n + c_n + d_n = s_n - b_n

b_{n+1} = s_n - a_n

c_{n+1} = s_n

d_{n+1} = s_n

so s_{n+1} = 4s_n - (a_n + b_n)

but you can write a_n + b_n in terms of s_n and s_{n-1} to get

s_{n+1} = 3s_n + 2s_{n-1} with
s_0 = 1 (the empty list) and s_1 = 4

now you have a homogenous linear recurrence of whose characteristic polynomial has two distinct roots, say x and y, so

s_n = c_0 x^n + c_1 y^n

where c_0 and c_1 are some coefficients determined by the initial conditions

[rocky torrent]

hai

i wanna know something

what does it means?

i know N is natural numbers but what the plus means?

[cloud rampart]

can you show the context in which it appears?

it's probably the positive natural numbers (i.e. the naturals excluding 0)

[rocky torrent]

oh?

it appeared on this

number theory

[brave rock]

This is not enough context

[rocky torrent]

well i guess its positive number

[dark bolt]

Excuse me. Does anyone know how to solve exercise, and most importantly, explain, because there are 0 ideas in general, the teacher doesn't like the argumentation with AI?

[flint sentinel]

A is a subset of Nn+m\Nm and B is a subset of Nn+m\Nn

C is a subset of Nn+m

I am so lost

[flint sentinel]

k is a natural number and k>=2 I looked at the answer of the proof and still dont get it so hopefully someone can help me out

Answer:

[cerulean wind]

you have to give more context to your questions

for people to be able to help you

at least give the full problem statement and what you have tried

[barren panther]

Isn't N... positive numbers? 😭

[cerulean radish]

Depends on the writer, for some it's the set of nonnegative integers

[barren panther]

Oh ok

[gritty bronze]

any idea to what the other methods might be?

[quick folio]

there are truth functional / propositional arguments one could use, but those are somewhat unnecessary here

[gritty bronze]

thanks! I was interested in what the other methods might be

[odd heart]

You could axiomatize propositional logic using something like Hilbert's system, and conduct a syntactic proof using your axioms and some rule of inference (Modus Ponens will usually suffice as the base rule): https://en.wikipedia.org/wiki/Hilbert_system

A syntactic proof basically works by taking your axioms as the starting "valid" statements; and repeatedly using rules of inference to create new valid statements from the existing ones.

[gritty bronze]

thanks outsider!

[compact cape]

hey is anyone active

[outer peak]

yh me

[compact cape]

ok wanna chat

[waxen robin]

Denote $p_n=|\mathcal{P}n|$, and define a set $\mathcal{L}{n+1}={L(z_1,z_2): z_1\ne z_2\in\mathcal{P}_n}$ where $L(z_1,z_2)$ is the line that goes through $z_1,z_2\in\bC$(does not matter for my question).

The book gives an upper bound $|\mathcal{L}_{n+1}|\le \frac12 p_n (p_n+1)$.

Why is this the bound, and not $|\mathcal{L}{n+1}|\le\frac12 p_n (p_n-1)$, as an element in $\mathcal{L}{n+1}$ is by choosing two distinct points in $\mathcal{P}_n$, so it should be $\binom{p_n}2=\frac12 p_n (p_n-1)$.

(I'm asking this question in this section because although the definitions are related to Field Theory stuff, my question focuses on the combinatorics of it).

[vital dew]

𝒢𝒾𝓃𝑔𝑒𝓇 𝑀𝒶𝑔𝓂𝒶

[stone laurel]

could someone try and help me with this please?

[cinder hornet]

OH HELL Yiiiiisssss

[robust monolith]

I'm not sure if this is the right channel, but I'll ask anyway. Is morphism a synonym of homomorphism?

[coral parcel]

In some contexts, yes.

"Morphism" is a somewhat more general term that is used in category theory.

But pretty much everything that is called a "homomorphism" will also be a "morphism" in the appropriate category. (And then every morphism in that category will be a homomorphism).

On the other hand, there are categories whose morphisms are not called "homomorphisms".

[tropic moth]

the suspense is killing me! must be... what? IT MUST BE WHAT? WHATS IN THE BOX?

[coral parcel]

1

[dire walrus]

2

Actually I never wrote down my solution to that problem.

[dire walrus]

Double count the set ||{(s,j) \in S_n x [n] | s(j)=j}||

[coral parcel]

No, 1

[dire walrus]

count with me tropo 😭

2 comes after 1

[coral parcel]

That works too. 👍

(And convincing a skeptical listener of the handwavy probabilities in my approach would probably lead to something like that anyway).

[primal glade]

How to do 3 and 4

[tired summit]

Good question! What have you tried?

[primal glade]

Yeah

But i got wrong

So i give up, instead of miserably trying random stuffs, i prefer to ask other people to help.

[tired summit]

Recall the definition of induced subgraph

[primal glade]

Ik but i still don’t know how to get those answers

[stray reef]

what are P_n and C_n

[dire walrus]

Path graph on n vertices and cycle graph on n vertices respectively (at least that is what standard notation says)

[dire walrus]

Mmmm... For 3, ||the maximum value of n is 2 because if you take 3 vertices, you immediately get a cycle.||

For 4, ||the maximum n should be 3 because if you take at least 3 vertices, the induced subgraph is a clique and cliques are not cycle graphs unless n=3.||

[coral parcel]

If 6 is a correct answer for the first question, P_n would need to be a path graph with n edges.

[coral parcel]

The nice thing about complete graphs is that they're the same no matter how you reorder the vertices.
So, for example, if you pick 5 vertices and take the induced subgraph, it will look the same no matter which 5 vertices you pick.
Thus there are really only 8 different induced subgraphs of K_7 (from the empty graph up to K_7 itself), so you can just consider each of those in turn to see if any of them happen to be a P_n or C_n.
(Start from the low end; fairly quickly you should discover a pattern that convinces you it's futile to continue towards larger induced subgraphs).

[dire walrus]

ah okay I kind of did not see the first two questions

slightly changes my answers then

[coral parcel]

Let the OP find them, though.

[dire walrus]

yup

[cunning widget]

Onee question, is there any limit to how small or large a set can be? Is it correct to say that a set can be infinitely large, but it cant be smaller than the empty set?

[hardy zinc]

Set of real numbers R

Infinite

[past rivet]

This is correct

[tall crescent]

Sets can have arbitrarily large cardinality: the set of Natural Numbers {1, 2, 3, ...} has infinitely many elements for example. It is true that the empty set is a subset of every set and there is no proper subset of the empty set, so in that way the empty set is the smallest possible set

[hardy zinc]

Algtop grind?

[past rivet]

I will get back to it dw

[dire walrus]

You can in fact prove that there is always a set with cardinality more than any set you can come up with because power set of a set X is always bigger than the set X.

[hardy zinc]

Is that because the power set always contains the null set?

[past rivet]

You prove this with Cantor’s diagonal argument

[odd heart]

Not really; adding just one element to an infinite set isn't usually going to give you a set of larger cardinality. The power set turns out to be "quite large" compared to the original set, in a way which is guaranteed to make bijection between them impossible (as formalized by Cantor's diagonal argument).

[prisma lily]

yep, just as an example, (0, 1) and R have the same cardinality, but of course (0, 1) is a subset of R

[cunning widget]

uuh, this made it so much clearer why the empty set is considered the smallest set, thanks

[cunning widget]

yess

[cunning widget]

what do you mean by power set?

[fossil mural]

the power set of X is the set of all subsets of X

[cunning widget]

aaah, i see

[fossil mural]

so for instance the set of all subsets of N is strictly larger than N (and in fact it turns out to be the same size as R)

[cunning widget]

N as for the set of all natural numbers, and R as for the set of all real numbers?

[cloud rampart]

yes

[cunning widget]

oh wow, thats cool

[primal glade]

yeah i got it, for 3 the answer is 1, cuz it only needs 2 vertices which has an edge of 1.

[hexed rune]

Suppose $x_0=e, x_{n+1}=x_n+log(x_n)$. How fast does $x_n$ grow?

[vital dew]

EmmaGhost

[hexed rune]

I'd like it to be o(n)

[fossil mural]

it's not even O(n) because the amount that it increases by each time is unbounded

(proof: the sequence is unbounded because x_n > n by induction; log is unbounded and strictly increasing; so log(x_n) is unbounded)

i'm not sure there's going to be any "nice" formula for the exact growth rate

[hexed rune]

Sorry I meant something else when I said o(n) 😔

I meant I needed it to grow strictly faster than n

x_n/n\to infty

Ultra posted something in discussion which showed it was lower bounded by nlog(n)
https://stackoverflow.com/questions/22618778/calculating-the-recurrence-relation-tn-tn-1logn

But it would be nice to know larger lower bounds at least

Like maybe it's superpolynomial

[fossil mural]

i think it probably isn't but i'm not quite sure how to prove it

[hexed rune]

You think n^2 is enough?

[fossil mural]

ok well it's O(2^n), because log(x_n) < x_n and x_{n+1} = x_n + x_n would be the recurrence for 2^n

but that means log(x_n) <= log(2^n) = n log(2) ~ n, so it's O(n^2) because we add at most n each time

but that means log(x_n) <= log(n^2) = 2 log(n) ~ log(n), so it's O(n log n) because we add at most log n each time

(up to various constant factors)

...and we also have a lower bound of n log n, so it's actually Theta(n log n)? i guess?

i wasn't expecting it to be something so nice but i guess it's just n log n

[hexed rune]

Nice

Thanks

[dire walrus]

<@&268886789983436800> more here

[chrome fossil]

can any one help me

I need a source to understand the discrete structure I am in uni and they have completed 7 chapters mids are done and i got a terriblr score like 7/35 now I need help but could'nt find a usefull yt channel

[prisma lily]

@chrome fossil do you wanna send a summary of your course content?

[primal glade]

How to do b?

[cerulean wind]

what are the multiples of 1 in V?
what are the multiples of 2 in V?
what are the multiples of 3 in V?
.
.
.

for example, every number in V is a multiple of 1, so the vertex labeled 1 will have edges from it to every other vertex, including itself

now, the only question i have is if you are using directed graphs or not

because non-directed graphs won’t be able to capture asymmetry

if you are not using directed graphs, then (b) cannot be represented by a graph

[primal glade]

Everything, 2,4,6,8 and 3,6,9

[primal glade]

What is a directed graph

[cerulean wind]

don't worry about it for now

[primal glade]

Okay

[cerulean wind]

it seems that you are not using them

[primal glade]

Yeah

[cerulean wind]

so, what i said about (b) not being possible holds

[primal glade]

Why

If x is 4 and y is 2 does it works?

[cerulean wind]

well, the rules were to draw an edge between vertices x and y if and only if x ~ y

[primal glade]

Okay

[cerulean wind]

but if you draw an edge 2 - 4, there is also an edge 4 - 2

but 4 is not a multiple of 2

[primal glade]

Ohhhhh

I seee

[cerulean wind]

and that's what i meant about graphs not being able to capture asymmetry

they will only ever be able to capture symmetric relations because of this

however, if you generalize to directed graphs, then you can capture asymmetric relations

because each edge has a direction, a start and an end

[primal glade]

I got it

So 4,2 can be also written as 2,4?

[primal glade]

Let me google it

[cerulean wind]

idk what you mean by this

[primal glade]

I mean the edge

[primal glade]

This

[cerulean wind]

yea, an edges in graphs don't care about the start and end vertices

[primal glade]

Could you teach me how to prove it using directed graph?

[cerulean wind]

well, a directed graph is just like a graph, but we care about direction of the edges.
so, you may have seen a definition of a graph as like, a set of vertices V along with a set of edges E, each of which is a non-empty set of at most two vertices in V

for example, if V = {1,2,3,4} and E = {{1},{1,2},{2,3},{3,4},{4,1}}

then we get a square with a loop around the vertex labeled 1

a directed graph is similar

it starts of with a set of vertices

but instead of the edges being a subset of the powerset of V, the edges are a subset of the cartesian product of V with itself, V x V

so if V = {1,2,3,4}

and E = {(1,1),(1,2),(2,3),(4,3),(1,4),(2,1)}

then we get a square graph again, in shape only

for example, for the edge (1,2), we draw an arrow from 1 to 2, not just an edge

so 1 -> 2

to indicate that the edge starts at 1 and ends at 2

since (2,1) is in E, then we also draw an arrow 2 -> 1

[primal glade]

Okay

[cerulean wind]

these arrows are usually called directed edges

we say that the directed edge (2,1) is directed from 2 to 1

does this make sense so far?

[primal glade]

Yep

[cerulean wind]

cool

so if you want to modify your question,

you can say, draw a directed edge from x to y if and only if x ~ y

and you can now represent the relation in (b) with a directed graph in this way

[primal glade]

Like this?

Where 6 and 9 , 4 and 6 don’t have any arrows so it’s impossible

And for the third one is a tree not a graph so it’s impossible for y to be a multiple of x?

[cerulean wind]

that is a bit hard to read for me

but i have drawn it here for you

y is a multiple of x is the same as x divides y, written x | y

the colors don't mean anything, just for clarity

[cerulean wind]

you don't want to repeat vertices

there is only one of every vertex

this is correct

those dang self-edges

[primal glade]

Oh.

I just divided mine in 3 parts

[cerulean wind]

i would avoid doing that for now

its fine for visualization purposes

[primal glade]

So since 4 6 8cant go back to 2

So it is impossible?

[cerulean wind]

its impossible to represent the relation in (b) without directed edges, yes

[primal glade]

Ohhh tysm

https://tenor.com/view/thx-thank-you-thanks-gif-13519278

[primal glade]

Am I doing those correctly?

[dire walrus]

,rotate 90

[dire walrus]

for graph theory, drawings should be your mantra (If you were trying to show the graphs are isomorphic, then yes, your solution is correct)

[cerulean wind]

surprising that you did this without drawing it lol

[dire walrus]

it is not hard

there is only vertex of degree 4. Just match that and the rest is almost automatic

[cerulean wind]

yea, but its like playing with a higher difficulty for no reason haha

[dire walrus]

new game +

[cerulean wind]

lmao

make the graph iso without drawing the graph

[dire walrus]

in polynomial time

Reminds me of a cool question : Suppose you have access to a graph-isomorphism oracle (that is, an oracle whom you can give two graphs and it would answer yes if they are isomorphic and no if they are not). Then show that you can count the number of isomorphisms of a given graph in polynomial time (polynomial in the size of the graph).

[This is in fact a hunch why graph isomorphism testing is probably not in polytime]

[primal glade]

alr thx

[primal glade]

Cuz I cooked.

[cerulean wind]

indeed

[cerulean wind]

this is cool

haven't seen it before

[dire walrus]

if you get stuck, feel free to ask for a hint

the hint is cool itself lmfao

[cerulean wind]

trying to see how like, having the iso oracle will help with self iso's

[primal glade]

You also play genshin?

[dire walrus]

used to, till like 5.4

[primal glade]

Oh.

[dire walrus]

I still keep up with the story, but no time to play. 10 to 10 is uni time now

[primal glade]

I see

[cerulean wind]

a naive approach would just go through all of the |V|! permutations of the vertices

but thats not polynomial in the size of the graph

[dire walrus]

yup

that is a problem

[dire walrus]

you are not using the oracle

since this is essentially the brute force solution to the graph isomorphism problem itself

test everything

[cerulean wind]

true

[cerulean wind]

lets hear that hint

don't think imma get this one on my own

[dire walrus]

Orbit-Stabilizer theorem

[cerulean wind]

nah

i don't believe you lmao

[dire walrus]

i am serious

[cerulean wind]

alr lets try it lol. Iso(G) is a group after all

[dire walrus]

it's Aut(G)

but yes

[cerulean wind]

potato potato

[dire walrus]

Iso(G) sounds to me like the set of isogenies of the algebraic group G

[cerulean wind]

the heck is an isogeny

[dire walrus]

surjective morphism with finite kernel

I am just memeing

[cerulean wind]

oh lol

why is having finite kernel important tho lol

[dire walrus]

it works well in that case and makes sense when we look at varieties. Elliptic curves give good inutition of what we mean by isogenies.

[cerulean wind]

i am not familiar with ag unfortunately

[dire walrus]

yeah dw, as I said, I am memeing around

I have a paper submission due in like a week and I am stressed af

any luck with the graph iso problem?

[cerulean wind]

i think?

[dire walrus]

go on

[cerulean wind]

the stabilizers of the action of Aut(G) on itself by left multiplication are trivial

so if we can find a non-trivial iso, i think we can just iterate it

to get all of them? (by orbit-stabilzer)

i must be tripping here

that doesn't feel right tho

like, i must be doing something wrong, since this won't get me all graph isos of a graph with two components

[cerulean wind]

oh oh

its not just iterates

nvm then

i haven't gotten anywhere

[dire walrus]

Okay second hint : ||Fix a vertex v_1 and suppose you know to which vertices v_1 can go to using the automorphisms (orbit of v_1). Can you somehow use this?||

[dire walrus]

not a bad idea... how about letting Aut(G) act on the graph?

a little more details is in the second hint

[cerulean wind]

im gonna keep thinking about this one tmrw

[dire walrus]

sure sure tyt

[half rock]

I haven't studied much graph theory, but I'm curious about the idea of this thing. if I have a map and the associated graph, I can think of this as "embeddable on a plane" in some way, but if I allow two vertices which are opposite on the map to be adjacent, suddenly something changes. what are the terms I'm looking for here to formalize this?

not looking to do any serious math with this, I'm actually looking into board game design and just started thinking about some questions, but I'm not sure how to refer to these graphs or what precisely changes when we allow something like this

[dire walrus]

what do you mean by "two vertices which are opposite on the map"?

[half rock]

ok lets just talk about a map with states. lets say there's a state A on the left side of the map, some stuff in between then a state B on the right side, and they don't share a visual border on our physical map

if we decide that they are adjacent despite that, maybe there's a teleporter, then the graph is different because we've added an edge between those states

but something is different about this graph, can we represent in 2d like we did the first one (with basic moving of the borders)? I'm tempted to say that we can't always do that (imagine if A is completely surrounded by non-B states?)

[dire walrus]

okay, so kind of saying that you are gluing the left edge and the right edge?

[half rock]

yeah in a way, but they don't necessarily have to be at the edges of the map

even on a sphere, maybe we could glue two points on the sphere together through the middle

[dire walrus]

okay, a sphere makes more sense

so let us say you take your map and add an extra point at infinity to make it a sphere (an inverse stereographic projection). Then do you want to call diametrically opposite points on the sphere as opposite?

[half rock]

sure

[dire walrus]

okay then, the structure you get by gluing oppsoite points (on a sphere) is the projective plane

this is why your embedding changes

https://en.wikipedia.org/wiki/Real_projective_plane

[half rock]

I will look into this, thanks!

[dire walrus]

np!

[primal glade]

Help

[dire walrus]

odd number of leaves

mmmmmmmm

[primal glade]

Yeah

[dire walrus]

if k number of leaves, then total number of vertices is k+4

the total degree is?

then the number of edges is?

can you do now?

[primal glade]

Let me try

[primal glade]

The total degree is 2k+6 and the edges is k+3?

[dire walrus]

2k+6?

[primal glade]

Yeah?

Cuz n=k+4and u plug in to the formula

[dire walrus]

what formula?

[coral parcel]

How does 10+7+4+2+(1+1+1+....+1) with k ones become 2k+6?

[primal glade]

2(n-1)

The sum of degrees

[dire walrus]

but you are given the degrees

[coral parcel]

I think the idea is to set that equal to the sum of degrees as computed by actually adding up the degrees.

[dire walrus]

yup, i was trying to push them towards that

[summer sable]

Find $\sup_{A \in O_n(\mathbb{R})} \sum_{1 \leq i \leq j \leq n} a_{ij}$ and determine its asymptotic behaviour as $n \to +\infty$.

[vital dew]

Slomenist

[summer sable]

A = (a_i,j)
(no the sup is not ~ n√n we are only summing over the upper triangular part of the matrix not all the coefficients)

[lethal girder]

I just started my discrete math class this week and was wondering if anyone had any tips on my methodology in showing work.. thanks

[quick folio]

it looks fine

a little long winded but that's never hurt anyone

[lethal girder]

I think I got carried away with the feeling of chalking lol

[little prism]

a truth table wouldnt hurt. much more efficient way of writing down whats going on, easier to read

[coral parcel]

Hmm, are you talking about Jett's post? Where would you put a truth table there?

[odd heart]

Yeah, truth tables for statements with quantifiers seem tricky

[little prism]

well, more just a table with columns x, P(x), Q(x), P(x) or Q(x)

I figured truth table was close enough as a term

[coral parcel]

Hmm, right.

[flint sentinel]

Hi, I had a quick question. I have an exam coming up, and we’re doing combinatorics proofs using a method that’s not very well known, so there’s very little material to practice with or to check your answers. I was wondering if anyone is familiar with the following method: (I have to use this specific method from my professor, so no other approach is accepted). If you are familiar with it, could you please help me with some questions? This part counts for 33% of my grade :/

Example of such a proof:

[quick folio]

looks good!

it's an interesting proof method, I like it a lot

I would write g instead of f^-1, because otherwise that's confusing notation

[flint sentinel]

ye true.

May I dm you by any chance with some questions?

or should I just post it here?

[quick folio]

sure

[dire walrus]

I just want to comment that step 3 can be avoided by just modifying step 2, let me call it step 2'. In step 2' you can count X in a different way, namely by picking k+1 elements, then picking one of them to be x, the rest to be your set A. This is exactly the right hand side count.

But I guess this goes against the philosophy of what you are trying to do? Or are you allowed to do this?

[flint sentinel]

True! My prof just said that over the last few years she noticed some students did not fully understand the proof and sometimes created some functions that would not make sense at all so in this step we need to check if it is actually correct and well defined.

The part of the f o f^-1 must be in the proof tho but the well defined step is normally not needed

[dire walrus]

Right. I was just hoping you can avoid the whole f business by double counting the same same set

[flint sentinel]

no sadly not would have been nice tbh

[primal glade]

Help

[winged delta]

What can you say about each component?

[primal glade]

Maximal subgraph

[winged delta]

Sure, sure

I think you may be overthinking it

What does Euler say about each component?

[little prism]

the question is clearly asking you to draw examples

have you done that

[stray reef]

have you done what the question, and now also Denascite, have said?

do you still need help with this, actually?

[gusty dome]

Is it true? $\bigcup_{a\in I}\bigcup_{b\in J_a}C_b=\bigcup_{b\in \bigcup_{a\in I}J_a}C_b$?\
In my opinion Yes. Because
\begin{align*}
x\in \bigcup_{b\in \bigcup_{a\in I}J_a}C_b&\iff \exists b_0\in \bigcup_{a\in I}J_a (x\in C_{b_0})\
&\iff\textcolor{red}{ \exists a_0\in I (\exists b_0\in J_{a_0})(x\in C_{b_0})}\
&\iff \exists a_0\in I \exists b_0\in J_{a_0}(x\in C_{b_0})\
&\iff x\in \bigcup_{b\in \bigcup_{a\in I}J_a}C_b.
\end{align*}

[vital dew]

Topological Afzal

[gusty dome]

i have a bit doubt on red colored line

[random sparrow]

how to write the symmetrical difference of two sets using a set builder

[coral parcel]

I've proposed an answer in #recreational-math. Please don't crosspost the same question between several channels -- it leads to wasted work if people start answering in one channel without having seen what was already said in the other.

[random sparrow]

,, A \triangle B = { x \mid (x \in A \lor x \in B) \land (x \notin A \lor x \notin B)}

[vital dew]

Renato

[random sparrow]

but idk how to simplify

[random sparrow]

im sorry, I just thought this channel was more appropriate

[coral parcel]

The general drift looks alright to me -- but I don't understand that happens between the red line and the one below it. As far as I can see you're just removing a set of parentheses which don't really have any semantic effect anyway.
And the step between the last two lines seems to skip over some details that might be half the real meat of the argument.
I think the logical structure of the argument would be clearer if instead of bounded quantifiers exists x in A.p(x) you write the bounds explicitly as exists x(x in A and p(x). That gives more freedom to to replace x in A by equivalents without worrying about violence being done to the quantifier syntax.

[coral parcel]

Yes, I think it is. But now, due to the crossposing, I've posted my answer in the other channel because that was where I saw the question first!

[gusty dome]

this makes sense, thank you Troposphere

yeah i left some detail in last two lines cuz it was easier imo

[true venture]

How can you count words of length n over some finite alphabet, counted up to permutations of the letter labels and reversal of the word? Ex. the following words of length 3 with 3 possible letters, 122, 211, 322, 311, 221, 331 are all equivalent under these rules.

Can Burnside's lemma be used here?

[primal glade]

Yep but I can’t find a pattern

[primal glade]

Yeah, but using equations not the example drawing method.

[quick folio]

here's a hint - euler's formula is true when there's one connected component, so clearly it's to do with the fact that there are more than 1 connected components

try playing around with that

[stray reef]

show the examples you've drawn

[primal glade]

Here is what I found, v-e+(f1+f2)= 4, and an unconnected graph has 2 components( one is the isolate vertex and the other is the other part of the graph), thus one component must have 0 face. Then I found v-e+f always 1 more than the number of components

[stray reef]

... what are f1 and f2?

unconnected graph has 2 components (one is the isolate vertex)
incorrect, this need not be the case

[weary tiger]

Greetings. I would like to verify whether this claim is correct:

A finite subset of N is always semilinear because it's a finite union of singletons that are linear sets.

I think this is true for a finite subset of N^k as well in general

[little prism]

examples. plural. you are only supposed to draw things and count

[marsh raven]

is possible to get back to state here?

unsigned int get_random_U32_number(){
    // get current state
    unsigned int number = state;
    // XOR shift algorithm (in 32 bits)
    number ^= number << 13;
    number ^= number >> 17;
    number ^= number << 5;

    state = number; // updaet random number state
    return number;
}

i can't possibly think that

[broken pivot]

in West's text Combinatorial Mathematics, he makes the claim that $\sum_{i=1}^{n-1} i$ counts the number of pairs of elements in $[n] = {1,\dots ,n}$, saying that the sum "groups the pairs by the larger element, applying the sum principle ($i$ pairs have larger element $i+1$)." I'm having trouble parsing his explanation, does anyone have any insight as to what he means, or perhaps a more intuitive explanation as to why this is the case?

[vital dew]

clover

[cloud rampart]

let's apply it to n = 4. there are 10 elements, sorted by the value of their largest element:
i = 1: {1,1} (1 pair)
i = 2: {1,2}, {2,2} (2 pairs)
i = 3: {1,3}, {2,3}, {3,3} (3 pairs)
i = 4: {1,4}, {2,4}, {3,4}, {4,4} (4 pairs)
so adding 1 + 2 + 3 + 4 will total up the amount of pairs in [4]

you can also see that it we bumped it up to n = 5, we would have to add a fifth row with 5 elements (one for each other possible element), and the previous rows would be unaffected, so the number of pairs of elements of [5] would be the previous sum + 5

applying a more general argument should show you that the pattern continues indefinitely

[broken pivot]

this is extremely helpful

thank you!

[scenic heart]

How many words can be formed using 7 letters from the word "PERMUTAION" (yep, not "PERMUTATION") all the vowels stays together?
My approach : We have 5 vowels and 5 consonants.
Treat the vowels as one block. So within the block the vowels can be rearranged 5!
Now we have 3 blocks. One vowel block and two consonant blocks.
The vowel block can be placed at the first, middle and the last. If it's at first it has 2 blocks that can be rearrange with 5 consonants. Meaning 5! × 5p2
But it can be in the middle and last position so net rearrangement is 5!×5p2×3
Am i correct?
Please explain.

[coral parcel]

After you've arranged the vowels, just rearrange {P, R, M, T, N, vowel-block} for another 6! possibilities.

Wait, no, you want 7-letter words.

Yeah, then I think you're right.

[scenic heart]

Chatgpt, Gemini and other AI's giving me difficult answers. They are giving me different solutions at different time.
Can you recheck it again kindly?

[coral parcel]

!nogpt

[lofty cloud]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[primal glade]

Face of component 1 and 2

[primal glade]

Okay

[broken pivot]

sorry to ping you, but I have a followup question. You iterated from i=1 up to n=4, but the sum says we should iterate from i=1 up to n-1=3, so is the summation bound that West gives incorrect?

maybe this summation is discounting reflexive pairings?

I think that must be it because, in the case of [4], using the sum from 1 to 3 returns 6, which is the number of ways to choose 2 items from a set of 4

[cloud rampart]

yeah it seems that in order to recover your formula you would discount pairing a number with itself

in which case you remove the last element of each row but the argument is otherwise the same

[broken pivot]

this makes sense

thank you for your insight

I was going fucking insane trying to think what he was trying to say with his explanation in the text

[void forge]

Guys is there a way to compute the number of subsets easier

[vocal island]

wdym? Of a finite set?

[void forge]

Ye

Like {1,2,3,4,5,6}

[dreamy coral]

yes but lets motivate it

[void forge]

I dont like counting

[dreamy coral]

we can make the counting process a bit less painful

[void forge]

K

[dreamy coral]

remember from our talk a moment ago that {1} has 2 subsets, {1,2} has 4

[vocal island]

For each element you can either have it in your subset or not. So the possible subsets are 2^n, where n is the number of elements in your set

[dreamy coral]

{1,2,3} has empty, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

[void forge]

Ok

[dreamy coral]

man i wanted them to realize this

[vocal island]

oh, i am so sorry

[dreamy coral]

thats alright

[void forge]

I thought it was 2n but its 2^n

[dreamy coral]

we can actually still use this opportunity to practice induction

[dreamy coral]

true, but how do we prove it?

im not sure if ur familiar with induction or not

[void forge]

Ummmm

I read about it

[dreamy coral]

i can remind you real quick

[void forge]

Theres a proof i remembet

OHH

[dreamy coral]

if we think of the natural numbers as steps to some sort of machine working, then they sort of become like dominoes

[void forge]

ITS THAT if P(x) is true then P(x+1) is also true

[dreamy coral]

yep

[void forge]

I used it on proving that 1+2+...+n=n(n+1)/2

[dreamy coral]

see how its like dominoes?

if i have a chain of dominoes and i want to make sure all of them fall over

theres really only two things i need to be sure about

if i have one domino itll always knock down the next

and the first domino is knocked down

[dreamy coral]

lets try doing induction to show that a set with n elements has 2^n subsets

(which is to also say that the size of its power set is 2^n)

ok so for the first case, the empty set, we have 1 subset

so it works at n=0

then were gonna assume that a set with k elements has 2^k subsets

if we add a new (k+1)th element to the set, we can add it to any of the previous subsets we had from the last set, and itll be a subset of the new one, right @void forge ?

[void forge]

Ye

[dreamy coral]

formally we can say that if $T$ was a subset of ${1,2,...,k}$ then $T \cup {k+1}$ is a subset of ${1,2,...,k,k+1}$

[vital dew]

hiidostuff

[dreamy coral]

but we also have that each previous T is still a subset of our new set

so we have that at least 2^k subsets are still subsets

but now if we add k+1 to each subset we get a subset

so there 2 * 2^k = 2^k+1 subsets

@void forge thats our proof

pretty cool huh?

[void forge]

Ye

I have another way

So we wanna prove that a set S containing n elements has 2^n subsets

If n=0 then S is the empty set and has only 1 subset which proves P(0) is true (P(n)=S having 2^n substes)

Suppose that P(n) is true and then let S have n+1 elements and let js one of them be a

Now let S-{a}={x in S | x not equal to c} then S-{a} has n elements and thats 2^n subsets

Now every subset OF S either contains or doesnt contain a and those that dont are subsets of S-{a} so there r 2^n of them

But those that do have a consist of those that dont have a but with a adjoined

There are 2^n of that aswell so now it becomes 2^n2^n=2^n2=2^(n+1)

Thus P(n+1) is true and P(n) is also true

Well for non negative n but thats my proof

[void forge]

The fancy n is meant to be a multiplication

[void forge]

I think bro disappeared

[dreamy coral]

yeah sorry i was busy for a moment lol

[void forge]

Its ok

[dreamy coral]

seems the proof is essentially equivalent to what i did with induction so good work

[void forge]

👍

I hate proofs tho

[swift lagoon]

hi

guys

I'm a big fan of math

👍

[void forge]

Us too

[swift lagoon]

may i join in your conversation?

[void forge]

Does everyone else denote equivalence relations as R

Like the fancy capital R

Or js my book

[swift lagoon]

looks like i'm gonna be your students

no s sorry

[void forge]

[swift lagoon]

where are you from

[void forge]

UK

[glass venture]

Which book is it

[dreamy coral]

Yeah

Usually its like xRy or smth

[void forge]

Its called " a first course in abstract algebra" fourth edition

By John B.Fraleigh

[glass venture]

oh nice lol I'm self studying the same one (assuming it's fraleigh)

[swift lagoon]

oh my sister is studying in University of Oxford

[glass venture]

ah yeah nice

[void forge]

Exactly

[dreamy coral]

We say a relation R on a set X is a set of ordered pairs (x,y) of members of X

And that the relation between two elements a and b holds if (a,b) is an element of that set

[void forge]

K

[dreamy coral]

@void forge from here it'd be a good thought exercise to think about how we can define a function

Based on the definition of a relation

[void forge]

If theyre not then the relation isnt equivalent

[dreamy coral]

Then the relation doesn't hold

[void forge]

Yk i never thought about that

[swift lagoon]

why not get some exercise to do

[void forge]

The notation {x|P(x)} is js so ez to forget what it does

[dreamy coral]

Fortunately a function is super close to a relation

There's just one more piece of info you need to add

[void forge]

Idk

A function is on an x and not a set?

[dreamy coral]

Functions are on sets

Something to note is that a function is a relation, just with a further detail

[void forge]

Like a specific property?

[dreamy coral]

Yes

There's something that the ordered pairs cant have in common

[void forge]

Hmmmmm

Idk bro

[dreamy coral]

The first entries cant be the same in any of them

(That's essentially the same as the vertical line test)

An input cant map to more than one output

[void forge]

Oh

Is that what mapping means i didnt get to that yet

[dreamy coral]

Function and map basically are the same

Usually people talk about mappings on elements from my experience tho

Smth like "The function f on the set X maps each x to x^2"

[void forge]

So the map this

\S:F→D

[dreamy coral]

So 2 is mapped to 4

[void forge]

Oh

$\phi$

[vital dew]

The sigma

[void forge]

My first language isnt even english

[radiant oyster]

hahahaha this is funny out of context

[tired summit]

No it's not

[worthy saffron]

This bothers me; my discrete math course is defining a cycle so that it can repeat vertices

I don't understand why they wouldn't just use the standard terminology

[cerulean wind]

a cycle is just a path with the same start and end vertex.
a simple cycle is one which visits each vertex exactly once, the start and end vertex exactly twice.

in other words, it is a cycle in which only the start and end vertices are equal.

besides, every simple cycle is a cycle and every cycle is a concatenation of simple cycles

why is this bothersome for you?

[worthy saffron]

I never heard the terminology cycle/simple cycle before and when I looked it up the circuit/cycle terminology seemed to be the dominant one

I was being a bit complain-y, sure there are multiple ways of defining it and they're all valid, but I think it's more sensible to name cycles so that all cycles are cycle graphs.

[cerulean wind]

yea, i suppose

[maiden talon]

@errant sequoia uff

[paper swift]

Guys, I'm very noob at Number Theory, I'm trying to integrate Mathematics (especially NT and Combi) and Computational Task together, I wanna research on those topics, especially I'm fascinated to solve problems from https://www.projecteuler.net
But I don’t know how can I approach, I wanna start from project euler. I need complete roadmap since I'm absolute beginner. Besides, I want solid foundation of NT as well as Combi and Its implementation on CS as well as solving problems.

[agile magnet]

There's a Project Euler discord server (DM me if you want a link). You'll probably get better help there for the CS stuff + specific problems.

If you start a problem and there's a math thing you need help on, then this server would be good for asking about the math thing.

[odd heart]

<@&268886789983436800>

Pah

Beaten

I was too careful not to ping @modern_day_gatsby, next time I'm going to consider them collateral damage.

[worthy saffron]

Just wanted to vent but it's not really a big deal... got a point off on my discrete math exam because I wrote something like (this isn't the exact same question for obvious reasons, but it's the same structure)

1 + 2 + ... + n + n+1 = n(n+1)/2 + n+1

And I "missed" the associative property step where I had to write...

1 + 2 + ... + n + n+1 = (1 + 2 + ... + n) + n+1

...first. Like, we're allowed to skip steps when distributing and factoring so that felt a bit arbitrary.

[granite knot]

Damn they were harsh on you

[worthy saffron]

It was a single point on a 50-point exam, I got all other 49 points, and I recall now the professor saying the associative property step in an in-class example (though I don't think he said specifically that this step was required), so it's like, okay sure whatever, but I'm glad I got the validation I was looking for 😛

[little prism]

if you wrote it in sigma notation it would be a much more noticable step. and in terms of general proof writing style, it highlights what you are going to do next which is a good thing

still a bit harsh

[gaunt moss]

ngl i took discrete and forgot everything afterward

[dreamy coral]

I probably would try to remember it considering that discrete is like basic proofs

[paper swift]

Sure brother, I would like that

@agile magnet

[fossil mural]

yeah that's... i mean i kind of get it, because if you let students "skip steps" like that you'll get all sorts of cases where they skip over something that is in fact not that hard but that they don't know how to fill in, ...but also like. what. why that in particular

[quaint zinc]

@agile magnet regarding the pumping lemma, what I don't quite get is this: we have a really long string right, and we need to choose vxy smaller or equal in length to p to pump, so then, how do we know how long that can be if we don't have an actual value for p? Do I take a segment with a only a single letter? 2? 10? 100?

Or do we assume that since s is so long, the segment vxy is length p? But then that also doesn't help it doesn't tell us how many characters that is.

I think what I don't get is what p represents in the first place. Is it the minimum length of s such that when constructing it using production rules, a non terminal gets repeated? Idek

[agile magnet]

I'll paste this here for convenience

I mean study the proof given here. You have to argue that no matter the decomposition of s into uvxyz, if the decomposition satisfies some of the conditions then it must violate other conditions

[agile magnet]

and we need to choose vxy smaller or equal in length to p to pump
so in the proof in the video, he argues that for s_2, no matter how you split it up into s_2 = uvxyz if uvxyz satisfy condition 2 and 3 then condition 1 must fail

in another proof you may argue that no matter how you split up s into uvxyz if it satisfies condition 1 then condition 3 must fail

that difference is dependant on the problem and the proof, I can't give you a general rule

[quaint zinc]

bruh its simply beyond the capabalities of my nugget I think. Its not like im ever gonna come across it again though so ill just leave it be ig

thanks anyway

[coral parcel]

In general your strategy would be to define a whole family of ever longer strings in your language, and argue that none of them can be pumped anywhere.
Then, if you assume the language is context-free, then no matter which number the pumping lemma gives you as p, it will contradict one of your examples.

[hardy zinc]

Just to check, if $R$ is a relation between $A$ and $B$, and if $(a,b)\in A\times B$ with $(a,b)\in R$ then it follows that $(b,a)\in R^{-1}$ right

[vital dew]

Real Lost Fruit

[hardy zinc]

By definition

[coral parcel]

Yes, by definition of R^-1.

[spice token]

guys does the binary operation need be closed on the finite set for it to be an algebraic structure? are all agebraic strucutres closed? then why do terms like "groupoids" exist, isnt that for closure ? needexpertopiniononthis

[spice token]

@coral parcel can u give a quick ans pls

[coral parcel]

Do not ping random people for help.

[granite kettle]

What is principle of inclusion exclusion

[agile magnet]

If $A$ and $B$ are two finite sets, how do you compute $\abs{A \cup B}$?

[vital dew]

Spamakin🎷

[agile magnet]

(ping me when you reply)

[velvet sandal]

can anyone help me solve this?

[quick folio]

first apply the normal euclidean algorithm to 27 and 146 to solve 27a + 146b = 1

[velvet sandal]

ok

I am past that, just somewhat confused, was out of class for a week and online notes are not that helpful. ChatGPT is telling me to use a EEA Table to solve this, but it doesn't make much sense, what would be the steps proceeding that?

[quick folio]

I don't know what an EEA table is

[velvet sandal]

Extended Euclidean Algorithm table

[quick folio]

it's just the normal euclidean algorithm with extra steps

essentially what I explained written out

[craggy flint]

use euclidean algorithm to get bezout's coefficients and one of them is the inverse of the number ur looking for

which would be the coefficient being multiplied by a

[stray reef]

!nogpt

[lofty cloud]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[stray reef]

actually wait do you still need help w this

[fervent nacelle]

ZXDVDSSVSSFSDFSFSF

[rapid kernel]

So what does it mean here by there exists a walk that visit each edges exactly once? In definition of Eulerian graph

So it doesn't need to complete graph

[runic lava]

in my understanding, it means of you trace the graph with a pen to reach every node, you only trace it once and you don't trace it more than once i.e. you don't trace it again while trying to reach every node

[rapid kernel]

Yes, thank you

What does it mean degree of u is number of indices i such that u = v_i? Does it mean that deg(v_i) = 2i?

I don't think so because what if there is graph v_0 -> v1 -> v2 -> v3.

[runic lava]

according to your screenshots, it just means the degree of u is the number of edges containing the node

yea i can't quite extract what the proof is saying exactly

according to the first screenshot, each of v1 and v2 must have degree 2

but the second says

degree equal twice the number of indices i

if degree is 2, 2=2×i. Therefore the number of indices is 1. Now idk what is that indices and why is that 1

i guess it's just a proof for the eulerian graph to prove how it visits an edge exactly once only

because in a non-eulerian graph, a node can be contained by more than to edges and therefore have degree ≥ 2. So the proof for eulerian graph just emphasizes how a node of the degree corresponds to the node itself since it's only being visited once

[rapid kernel]

I don't get it because in my example how this proofs work

[runic lava]

i haven't really studied graphs so idk

I'm sure watching on YouTube or searching online can fill up the gaps u don't understand

[fossil mural]

no, it says the number of indices i

as in you count how many there are

for instance if you have the walk A, B, C, D, E, A, C, E, B, D, A, and that visits every edge exactly once, then the vertex D, which is not the first or last node in this walk, occurs twice, meaning it must have degree 4

which makes sense because we can just read off from this walk what exactly its edges are - C, D, E means it has edges to C and E, and B, D, A means it has edges to B and A

to spell it out further, we have the sequence v_0 = A, v_1 = B, v_2 = C, v_3 = D, v_4 = E, v_5 = A, v_6 = C, v_7 = E, v_8 = B, v_9 = D, v_10 = A

and the indices i with v_i = D are i = 3 and i = 9, in particular there are two of them, so the number of indices i with D = v_i is 2

because the number of elements of {3, 9} is 2

[rapid kernel]

Yes it is correct

Thank you I got it

[primal glade]

How to find the chromatic number of this graph?

[winged delta]

Shouldn't be hard to show it's not 2

It's small enough that I would try brute forcing a 3 or 4 coloring after that

[hidden totem]

you mean brute forcing a 3 coloring

brute forcing a 4 coloring effectively does nothing because it won't get you anywhere close to figuring out that 3 isnt possible and since its planar the four color map theorem guarantees 4

[winged delta]

Well I wasn’t sure what the answer would be until I tried it, but yeah, 4’s always possible

If 3 weren’t, the hope is you’d find some reason why during the brute forcing

[hidden totem]

oh ||since this is a famous graph, i found the chromatic polynomial haha||

[tired summit]

Yeah, the graph is the ||dodecahedral graph||

[odd heart]

I mean, there's an algorithm for determining the chromatic polynomial, so the comedy option is to use that, and then find the first integer for which the chromatic polynomial is not zero

[hidden totem]

yeah i just meant since it's a well known graph i didn't need to use that algorithm, it was a simple lookup

[odd heart]

Yeah, and also by "comedy option" I meant that this algorithm would be quite tedious on a graph this size

And just feeling it out and trying to find a 3-coloring (or an argument why it fails) would probably be faster

[weary tiger]

Hey fellow math peoples, so I have a question, when you perform a discrete-time fourier transform on a signal; what does the complex output actually represent? Because I assume I cannot just change frequency by just modifying the discrete-time fourier transform?

[quick folio]

well it's the frequency domain in discrete space

the discrete fourier transform really is the same as the CT fourier transform but discrete

Because I assume I cannot just change frequency by just modifying the discrete-time fourier transform?
I don't understand what you mean here

[weary tiger]

What I mean is; say I had a discrete version of a 1Hz sine wave sampled at a frequency of 100Hz, performed a discrete fourier transform on it, and, say added 5+0i to every value in the frequency domain, and then used the inverse discrete fourier transform, would the resulting signal be of a higher frequency?

[quick folio]

saying that the resultant signal having higher frequency is a confusing statement, since you've increased the amplitude of every frequency of the signal

the resultant signal is not even going guaranteed have a fundamental frequency anymore, it's going to be a bunch of jumbed noise

[weary tiger]

I see

That makes sense

[quick folio]

if you have a periodic signal and you want to increase its frequency, then you just uniformly shift its fourier transform to the right (assuming no aliasing happens)

[weary tiger]

So, instead of doing that, could I instead zero-pad the input signal and then shift the fourier transform into the higher frequencies?

[quick folio]

yeah

[weary tiger]

So say I wanted to shift every frequency down by a factor of 1.35, do I have to zeropad before the signal starts in the time-domain?

(In order to shift down)

[quick folio]

it's definitely a good idea

but it's not strictly necessary for every signal

[quick folio]

like the issue with just moving down without zeropadding, is that if the bandwidth of your signal is too wide then the lowest frequencies might wrap back around to the right when you shift the frequencies

so in practise yes do it

[weary tiger]

I got it! Thank you!

[rigid night]

For a non-negative integer $n$, what is the number $N_n$ of tuples $(i_1, ..., i_{n-1})$ of non-negative integers such that $\sum_{j = 1}^{n-1} (n-j) i_j = (n-1) i_1 + ... + i_{n-1} < n$? In particular, an informal ``geometric'' estimate suggests [ N_n \sim \frac{1}{(n-1)!} \times \prod_{j=1}^{n-1} \frac{n}{n-j} = \frac{n^{n-1}}{(n-1)!^2} \mathrlap{\qquad\text{as $n \to \infty$;}} ] is this true?

[vital dew]

Raghuram

[sinful peak]

What are some of the harder/more misunderstood topics people see in a discrete math class?

[spice token]

Are these two equal

[little prism]

what can you say about cycles of certain lengths

[stray reef]

do you think they are or do you think they aren't

[spice token]

They don't have the same properties

[stray reef]

ok, which property distinguishes them?

[spice token]

Hamiltonian cycle

[stray reef]

so you're saying that one of them has a hamiltonian cycle and the other does not?

[spice token]

Shouldn't this only be 1 why is the answer 24 bruh

[spice token]

Yes

[stray reef]

ok, which one does and which one does not?