Skip to content
Complete graph with...
 
Notifications
Clear all

Complete graph with 2022 vertexes with two colored edges: prove that you can remove one color and still there is path between every two vertexes

1 Posts
1 Users
0 Likes
44 Views
Guest
Illustrious Member
Joined: 1 year ago
Posts: 72614
Topic starter  

$begingroup$

There are 2022 vertexes in a complete graph. There is edge between every two vertexes. All edges are blue or red.

And the problem is to prove that you

  • always can choose one of two colors (either blue or red)
  • then delete all edges of given color (so graph would be only one colored)
  • and in the result graph there would still be path between every two vertexes

I tried to prove it with some logical reasoning. And I think I understand it, but description is very vague. I am looking for more mathematical/graph language description.

My reasoning steps:

  1. We assume that this is not possible, then the result graph would contain some vertexes A and B so that there is no path between them.
    We assume that we deleted all blue edges and now only red ones are left.

  2. There is some subgraph that contains vertex B and there is path from B to every other vertex in this subgraph. Remember that all edges are red.

  3. The same is for vertex A and subgraph that contains vertex A and there is path from A to every other vertex. Edges are red.

  4. So we have two subgraphs Asub and Bsub, there are no paths from Asub to Bsub. Otherwise our first assumption would not be true.

  5. This means that those subgraphs where connected with blue edges before we deleted them. Each vertex in subgraph A were connected to subgraph B every vertex (with blue edge).

And now logically thinking if we put back all blue edges and remove red edges, then we would be able to go from every vertex to every other vertex using blue edges. This part is very vague...

I also tried another approach - to start with 3 vertexes, then add the fourth one etc. But it doesn't work for me either.

$endgroup$


   
Quote

Unreplied Posts

is_user_logged_in() undefined at shutdown in plugin context

The function is_user_logged_in() is not available at shutdown (plugin context, not theme).

I want my plugin to run only (1) on front-end pages and (2) when the user is not logged in.

This partially works, but it also runs on Divi builder front-end pages, so I need to add !is_user_logged_in:

if (!is_admin()) {
    add_action('shutdown', function () {
        // Do some ob_start() and PHP_Tidy() stuff...
    }, 0);
}

Unfortunately changing my conditional to if (!is_admin() && !is_user_logged_in()) fails with:

Uncaught Error: Call to undefined function is_user_logged_in() in...

How can I find the next following line containing a specific string, then append that to the current line? (Notepad++)

I guess I’m trying to do two things using Notepad++:

  1. Find a line containing a comma character, then
  2. Find a subsequent line that contains the word “Proximity”, then copy that entire line, and append it to the current line in #1 above. The line containing “Proximity” could be any number of lines down from the original line.

Here’s a mock up:

“SCOTT, Michael”
“Office Manager”
“Card Number Card Format Disabled”
“0273ADNC PAC Proximity Reader False”
“Random rubbish”
“SCHRUTE, Dwight”
“Card Number Card Format Disabled”
“0897FFRF PAC Proximity Reader False”

Should become:

“SCOTT, Michael ; 0273ADNC PAC Proximity Reader False”
“SCHRUTE, Dwight ; 0897FFRF PAC Proximity Reader False”

I added the semicolon just to help me parse it later. I also want to remove any extra lines other than the line containing the comma (also contains the names), and the “Proximity” line.

Any ideas are appreciated!

Why is a field extension $L:K$ normal if and only if $text{Aut}(L:K)$ acts transitively on the set of homomorphisms $Lto overline{K}$?

$begingroup$

According to Wikipedia, given the algebraic extension $L:K$, the following are equivalent:

$a)$ The minimal polynomial over $K$ of every element in $L$ splits in $L$.

$b)$ $text{Aut}(L:K)$ acts transitively on the set of homomorphisms $Lto overline{K}$ where $overline{K}$ is the algebraic closure of $K$.

I have found nothing similar to the above result (equivalence of the conditions) in Stewart’s Galois Theory, and thus I’m wondering why are the conditions above equivalent?

$endgroup$

Can connect to Droplet only using root user

I’m trying to set up a Digital Ocean Droplet, and i have created a new user to follow best practices and also so that i can run the code command, because it isn’t allowed as the root user.
I can login using
ssh -i ~/.ssh/id_rsa root@droplet_ip
but running
ssh -i ~/.ssh/id_rsa my_user@droplet_ip
returns my_user@droplet_ip: Permission denied (publickey).
Why is this issue occuring?
I also have managed to change the user after logging in as root using sudo su my_user, but when I try to run code it says
mkdir: cannot create directory ‘’: No such file or directory which is very odd.

Any help will be greatly appreciated 🙂

Using a list in batch file

I need to copy a file if exist to a list of destinations. The Destination contain %variables% . When I run it appears to be taking the literal path as given in the array list.

How can I make it use the variable in the array list?

The lnk and the Shortcut_Locations.txt are located in same folder as script.

@echo off

pushd "%~dp0" 

set source_file=App1.lnk

set destination_list=Shortcut_Locations.txt

for /f "tokens=*" %%I in (%destination_list%) do (
    if exist "%%I" (
        copy /Y "%source_file%" "%%I"
    )
)

POPD

Shortcut_Locations.txt content

\server1data\%username%Desktop\
%appdata%OpenShellPinned\
%appdata%OpenShellPinnedGGHC\

Proving set is Borel in $S^{n-1}$

$begingroup$

I am reading Mattila’s “Fourier analysis and Hausdorff dimension”, the author leaves as an exercise to prove that the set $S_infty$ is a Borel set. I will now define the set $S_infty$:

Theorem 5.1: Let $Asubsetmathbb{R}^n$ be a Borel set with $text{dim}A=sleq1$. Then for all $tin[0,s]$
$$ text{dim}{ ein S^{n-1} : text{dim}P_e(A)<t }leq n-2+t $$

Where $P_e: mathbb{R}^nto mathbb{R}$, is the proyection $P_e(x) = ecdot x$ for some $ein S^{n-1}$. For the proof the autor takes $sigma<tleq s$ and finds a Borel measure $mu$ with support on $A$ such that $0<mu(A)<infty$ and such that $I_sigma(mu)<infty$, where $I_sigma(mu)$ is the energy defined as

$$ I_sigma(mu) = iint |x-y|^{-sigma},dmu x,dmu y.$$

He then has to prove that

$$S_infty = {ein S^{n-1} : I_sigma(mu_e) =infty}$$

is a Borel set. Where $mu_e(B) = mu(P_e^{-1}(B))$ is the push-forward of $mu$ under $P_e$.


This is what I tried doing:

begin{align*}
I_sigma(mu_e) = int_{-infty}^inftyint_{-infty}^infty |x-y|^{-sigma},dmu_ex,dmu_ey &= int_{mathbb{R}^n}int_{mathbb{R}^n} |ecdotxi – ecdotzeta|^{-sigma},dmu xi,dmuzeta \
&= int_{mathbb{R}^n}int_{mathbb{R}^n} |e|^{-sigma}|xi – zeta|^{-sigma},dmuxi,dmuzeta\
&= int_{mathbb{R}^n}int_{mathbb{R}^n} |xi – zeta|^{sigma},dmuxi,dmuzeta\
&= I_sigma(mu),
end{align*}

where I’m using that because $ein S^{n-1}$ then $|e| =1$. But then I get stuck and I do not know how to continue with the calculations, because the set
$${ ein S^{n-1} : I_sigma(mu)=infty }$$
doesn’t make sense to me, maybe my previous calculation is wrong.

$endgroup$

Problem with PID – Zabbix Server on Ubuntu (WSL2)

I’m having trouble trying to start Zabbix Server (6.4) on WSL2. When I try the following command:

service zabbix-server restart:

I received the following message:

 * Stopping Zabbix server zabbix_server
No process in pidfile '/var/run/zabbix/zabbix_server.pid' found running; none killed.   [ OK ]
 * Starting Zabbix server zabbix_server   

And Zabbix Server does not start:

service zabbix-server status:

 * zabbix_server is not running

Inside the log file (/var/log/zabbix/zabbix_server.log), is found the follow message repeated several times:

13660:20230417:160028.155 [Z3001] connection to database 'zabbix' failed: [2002] Can't connect to local MySQL server through socket '/var/run/mysqld/mysqld.sock' (13) 

Followed with the message in the end of the file:

13660:20230417:160028.155 database is down: reconnecting in 10 seconds 13660:20230417:160032.344 Got signal [signal:15(SIGTERM),sender_pid:15318,sender_uid:0,reason:0]. Exiting ... 
13660:20230417:160032.344 Zabbix Server stopped. Zabbix 6.4.1 (revision 546e284fd7c).

But I already installed the mysql-server normally, and it is running without any kind of problem.

How can I connect from a mac to a windows?

I have two computers on the same local networks and I have installed OpenSSH Server on the windows and activated the 22 port communication on the windows.

Then in my mac i put

ssh username@ip_of_windows

however, it doesn’t let me connect on terminal. The connection just disappears without any error. What am I missing?

thank you!

Cox’s exercise 5.1 on (eventually) proving ring of integers is a dedekind domain

$begingroup$

Note: It seems that $LaTeX$ rendering is very broken, either for my Firefox browser or for the site. Here is an example: $mathfrak{a}_{n} = mathfrak{a}_{n + 1} = cdots$ turns into $mathfrak{a}_{n} = mathfrak{a}_{n + 1} = cdots$. I can’t fix it, so I have rendered it and pasted an image below. Hopefully it will be fixed soon. (I might make a meta post, not sure if that’s the right move).

Update: It seems to be fixed when I submitted the question? It rendered as broken LaTeX (and very slowly, unlike now where it’s instant). I have moved the image to the bottom, in case the problem is occuring for others.


Hi! I am reading Cox’s “Primes of the Form $x^2 + ny^2$“, and am on Chapter 5 (it’s a speedrun from number fields to Hilbert’s class field). I am attempting exercise 5.1, and I have done some parts, so I am both asking for verification for my solution as well as hints for the rest.

Things we have stated:

Proposition 5.3. For a number field $K$

(i) $mathcal{O}_K$ is a subring of $mathbb{C}$ whose field of fractions is $K$.

(ii) $mathcal{O}_K$ is a free $mathbb{Z}$-module of rank $[K : mathbb{Q}]$.


(a) Show that a nonzero ideal $mathfrak{a}$ of $mathcal{O}_K$ contains a nonzero integer $m$. (Hint: …)

My solution: Let $alpha neq 0$ be in $mathfrak{a}$. Of course it is algebraic, so let the monic integer polynomial $f(x) = a_0 + a_1x + cdots + a_{n – 1}x^{n – 1} + x^n$ be its minimal polynomial. Now, $langle alpha rangle subset mathfrak{a}$. In particular, for all integers $i geq 1$, the elements $alpha^i$ are in $mathfrak{a}$. This then means $sum_{i geq 1} a_i alpha^i in mathfrak{a}$, and since $f(alpha) = 0 in mathfrak{a}$, we have $m = a_0 in mathfrak{a}$.


(b) Show that $mathcal{O}_K / mathfrak{a}$ is finite whenever $mathfrak{a}$ is a nonzero ideal of $mathcal{O}_K$. Hint: if $m$ is the integer from (a), consider the surjection $mathcal{O}_K / mmathcal{O}_K to mathcal{O}_K / mathfrak{a}$. Use part (ii) of Proposition 5.3 to compute the order of $mathcal{O}_K / mmathcal{O}_K$.

My Ideas: From above, we know that $langle m rangle subset langle alpha rangle subset mathfrak{a}$, so my intuition tells me that this surjection definitely exists. (In my intuition, everything’s a module / vector space, so this surjection is just a projection map?) However, I don’t know how to explicitly describe it.

To compute $left|mathcal{O}_K / mmathcal{O}_Kright|$, from the proposition above we know that $mathcal{O}_K cong mathbb{Z}^{[K : mathbb{Q}]}$, so $mathcal{O}_K / mmathcal{O}_K$ is just $left(mathbb{Z} / mmathbb{Z}right)^{[K : mathbb{Q}]}$ and the order is $m^{[K : mathbb{Q}]}$. This part makes sense but feels a little hand wavy? Or is it justified as is?


(c) Use (b) to show that every nonzero ideal of $mathcal{O}_K$ is a free $mathbb{Z}$-module of rank $[K : mathbb{Q}]$.

My solution: Fix a nonzero ideal $mathfrak{a} subset mathcal{O}_K$. We know that $mathcal{O}_K / mathfrak{a}$ is finite and $mathcal{O}_K cong mathbb{Z}^{[K : mathbb{Q}]}$, so $mathfrak{a}$ has to be a product of $[K : mathbb{Q}]$ infinite subgroups of $mathbb{Q}$, i.e. $mathfrak{a} cong prod_{i = 1}^{[K : mathbb{Q}]} m_imathbb{Z}$. This is easy to prove by a simple proof by contradiction.


(d) If we have ideals $mathfrak{a}_1 subset mathfrak{a}_2 subset cdots$, show that there is an integer $n$ such that $mathfrak{a}_n = mathfrak{a}_{n + 1} = cdots$. Hint: consider the surjections $mathcal{O}_K / mathfrak{a}_1 to mathcal{O}_K / mathfrak{a}_2 to cdots$, and use (b).

My solution: Again, my intuition tells me the surjections $mathcal{O}_K / mathfrak{a}_i to mathcal{O}_K / mathfrak{a}_{i + 1}$ exists, but I don’t know how to construct them. Anyways, I claim that if $mathfrak{a}_i neq mathfrak{a}_{i + 1}$, then $left|mathcal{O}_K / mathfrak{a}_{i + 1}right| < left|mathcal{O}_K / mathfrak{a}_iright|$. This holds because for $alpha in mathfrak{a}_{i + 1} setminus mathfrak{a}_i$ is a nonzero element in the kernel of the surjection. Since the quotients are finite, it must eventually stop and hence there are no infinite ascending chains.


(e) Use (b) to show that a nonzero prime ideal of $mathcal{O}_K$ is maximal.

My ideas: Let $mathfrak{a}$ be a prime ideal of $mathcal{O}_K$, and suppose that $mathfrak{a} supset mathfrak{b}$ (i.e. $mathfrak{a}$ is not maximal), which gives $mathcal{O}_K / mathfrak{b} subset mathcal{O}_K / mathfrak{a}$. Thinking about everything as $mathbb{Z}$-modules, we can write $mathcal{O}_K cong prod_{i = 1}^{[K : mathbb{Q}]} mathbb{Z}$ as ordered coordinates, and similar that $mathcal{O}_K / mathfrak{b} cong prod_{i = 1}^{[K : mathbb{Q}]} mathbb{Z} / m_i mathbb{Z}$ and $mathcal{O}_K / mathfrak{a} cong prod_{i = 1}^{[K : mathbb{Q}]} mathbb{Z} / n_i mathbb{Z}$. By the inclusion, we know that $m_i mid n_i$, and for at least one $j$, $m_j neq n_j$. However, for such $j$ we have that $n_j = m_j cdot left(frac{n_j}{m_j}right)$ i.e. $mathbb{Z} / n_j mathbb{Z}$ is not an integral domain, and hence the product ring is not an integral domain, which means $mathfrak{a}$ is not prime.


For you for your help in advance!

enter image description here

$endgroup$

Share: