Bài đăng

A theorem of Gaddum and Nordhaus

   Given a graph G with n vertices. Let G' be the complementary graph  of G, which has the same vertex set as G and two vertices are adjacent in G' iff they are not adjacent in G. Let \chi(G) and \chi(G') be the chromatic number  of G and G'. In 1956, two mathematicians Edward Alfred Nordhaus and Jerry William Gaddum obtained the following estimates:    (i) 2\sqrt{n} <= \chi(G) + \chi(G') <= n + 1    (ii) n <= \chi(G)\chi(G') <= ((n + 1)/2)^2    The result was written in the paper "On complementary graphs", which was published in The American Mathematical Monthly. To show that \chi(G)\chi(G') >= n, we assume that the vertices of G can be colored by k colors and the vertices of G' can be colored by k' colors. For each vertex v, let G(v) be the color of v in G and G'(v) be the color of v in G'. Since for any two different vertices v, u, either v is adjacent to u in G (which means that G(v) and G(u) must be different) or...

Những ngày đầu học tập tại Đức

Hình ảnh
   Tôi đặt chân đến Đức vào một ngày cuối tháng 10, ngay sau vài tuần mỏi mòn chờ đợi visa. Đúng ra tôi phải đến sớm hơn, nhưng vì lý do visa nên tôi mới đến trễ như vậy. Và tôi đã có những ngày tiếp theo khá vất vả để có thể bắt kịp với việc học tại Đại học Bonn.  1. Làm bài tập theo nhóm - Một trải nghiệm giúp tôi nhận ra nhiều điều    Khi học các môn học tại Đại học Bonn, trừ những môn seminar hoặc môn chủ đề tự chọn (nội dung thay đổi theo từng năm), sinh viên sẽ phải tham gia một trong các giờ bài tập và phải hoàn thành đầy đủ bài tập mỗi tuần. Một điều khá thú vị là sinh viên được khuyến khích làm bài tập theo nhóm, và khi tôi hỏi về việc làm bài tập một mình, tôi nhận được câu trả lời như sau.     Tôi học 4 môn thì có 2 môn là tôi phải làm bài tập theo nhóm. Tuy nhiên, do những tuần đầu tôi không ở Bonn nên việc tìm bạn chung nhóm là khá khó. Cuối cùng, nhờ sự hỗ trợ của trang web trường và của trợ giảng, tôi cũng tìm được nhóm. Tôi nghĩ tô...

Some "annoying" stuffs in Category Theory

1. "Small category" is small??    A category is small if the class of its object forms a set . For example, the category of set is NOT  a small category since the collection of all sets is not a set by a well-known paradox. As a result, the category of topological spaces  is also not a set because it must be "bigger" than the category of set, since sets only differ in elements, but topological spaces differ in elements and open/closed (sub)sets.    This might contradict with our usual sense about small/large things, because sets are often so big that we find it hard to control them. But category theory has reached another level, where set might be regarded as the "simpliest" structure/level.  2. "Constant" simplicial set    From our usual sense, "constant" means some stuff should be fixed and invariant of the variables/factors involved. Meanwhile, a constant simplicial set is defined in a very special way: it is the category in which th...

Some interesting facts about Vietnamese

Here is a collection of interesting facts about the language of Vietnamese (tiếng Việt) that I just found out when talking to my friends, who are all Europeans, in Bonn (Germany).  1. In Vietnamese, grandson and nephew are called the same (cháu trai). Similarly, granddaughter and niece are also called the same (cháu gái).  2. In Vietnamese, you can use the same pronoun "em" to call your younger sibling, no matter whether it is your younger brother or your younger sister. Similarly, this pronoun can be used to call someone who is just a few years younger than you, no matter whether this person is a man or a woman.  3. However, when referring to your older sibling, you must use the pronoun "anh" to call your older brother and the pronoun "chị" to cold your older sister. Similarly, you can use the pronoun "anh" to call a boy who is just a few years older than you and the pronoun "chị" to call a girl who is just a few years older than you. ...

Trước khi đi du học ngành toán tại Đức

Hình ảnh
Bài viết này tổng hợp những câu chuyện mang tính cá nhân về quá trình tôi chuẩn bị cho chuyến du học tại Đại học Bonn (Đức), một ngôi trường khá danh tiếng về ngành toán. Tôi đã chia sẻ khá đầy đủ những kinh nghiệm hữu ích cho mọi người trong  quyển guideline này , do đó trong bài viết này tôi sẽ đề cập đến những khía cạnh khác, chẳng hạn như trải nghiệm của tôi với các giáo sư ở Đức, hướng nghiên cứu của bản thân, hay là cả những câu chuyện mang tính giải trí cực cao.  1. Trước khi có ý định đi Đức, tôi KHÔNG BIẾT GÌ về Đại học Bonn và những trường khác ở Đức      Hồi năm thứ 1 và năm thứ 2, tôi chỉ tập trung học chứ gần như không tìm hiểu về các nhà toán học cũng như nơi công tác của họ. Lúc đó tôi chỉ thấy các trường ở Mỹ hấp dẫn vì có khá nhiều hướng nghiên cứu, hơn nữa hầu hết các trường đều có các giáo sư làm về đại số  và tổ hợp , những lĩnh vực tôi yêu thích nhất vào lúc đó. Tôi cũng biết rằng  Giáo sư Phan Thành Nam là một trong những cựu si...

The "natural" language of graphs in model theory fails when we consider multigraphs

Hình ảnh
 1. Preliminaries    Briefly speaking, a  language   consists of a set of constant symbols, a set of relations and a set of function symbols. Moreover, each relation or function symbol is associated with a natural number indicating the (fixed) number of members in that relation/function. In other words, a relation/function in a language is forced to involve a fixed number of members. A real-life example of a such relation is the (normal) marriage relation, which must be between exactly two people. The formal definition of a language is as follows.  The formal definition of a language (taken from the book "Model Theory: An Introduction" written by David Marker)    Based on a given language L, we can construct an L-structure , which is defined as follows.      If there exists a bijective mapping n from an L-structure M to an L-structure N such that the following holds    then we say that M and N are L-isomorphic . ...

"Mưa đỏ", "Còn gì đẹp hơn" và ...

Hình ảnh
   Tôi có dịp đi xem phim "Mưa đỏ" tại Cinestar Sinh Viên vào ngày 17/09/2025, đúng 1 ngày (+53 năm) sau ngày kết thúc 81 ngày đêm chiến đấu bảo vệ thành cổ Quảng Trị (16/09/1972). Những cuộc chia ly, nỗi đau được thể hiện trong bộ phim cũng như trong các bài hát chủ đề khiến tôi không thể nào quên được. Dù chưa từng sống trong thời kỳ đó, nhưng những câu hát như "Hết kháng chiến nếu con còn chưa về/ Mẹ ơi vui lên mẹ có đứa con anh hùng" hay "Người mẹ ấy tìm con giữa tiếng reo dân tộc" vẫn để lại cho tôi cảm xúc rất đặc biệt.  1. Một số tấm ảnh chụp ở cuối phim 2. Tôi tự đàn và hát bài "Còn gì đẹp hơn"    Tôi rất thích bài "Còn gì đẹp hơn" của Nguyễn Hùng, một phần là vì tôi đã bị ấn tượng với bài hát trước đó của anh (và nhóm MAYDAYs) là "Phép màu". Tôi không đủ kiến thức về âm nhạc nên cũng không biết dùng từ nào để có thể mô tả chính xác giai điệu của bài hát này. Tuy nhiên, thỉnh thoảng giai điệu đó đã vang lên bất chợt tr...