Homework Problems and Essays

Chapter 8 Homework Problems and Essays

Problem 8.0.1. P1.

Define an \(m\)-ary string to be an ordered list of length \(n\) where each entry is an element of \([m]:=\{1,2,\ldots,m\}\text{.}\) We denote by \([m]^n\) the set of \(m\)-ary strings of length \(n\text{.}\)

Systematically list the elements of \([3]^3\) and explain using written sentences what your system is for listing all of these elements.
🔗

🔗
Give a recursive proof, following the structure of the recursive proof of Theorem 2.1.8, that

\begin{equation*} |[m]^n|=m^n \, . \end{equation*}

🔗

🔗

🔗

Problem 8.0.2. P2.

How many binary strings of length \(n\) are there with exactly two ones and \((n-2)\) zeros? Express your answer as either a function of \(n\) or as a recursive expression. Give an argument, i.e., a proof, explaining why your solution is correct.

🔗

Problem 8.0.3. Essay 1.

Write an essay in which you reflect on a meaningful mathematical experience from your past. This might be a positive experience or it might be a negative experience, but it should be something that was influential in your mathematical life, and you should explicitly discuss how mathematical ideas/concepts were involved in this experience. As a prompt for your writing, consider some of the following questions (you do not need to respond to all of these, rather use them to help you get your writing started).

Was this influential because of the mathematical content you learned, or because of a personal experience that took place in a mathematical context, or because it changed how you thought about yourself with regard to mathematics, or something else entirely?
🔗

🔗
Did this experience cause you to take on future challenges, or to avoid certain challenges?
🔗

🔗
What was different about this experience from other similar experiences that makes this one stand out in your memory?
🔗

🔗

This assignment should be 500 words, which is equivalent to two pages, 12 point Times New Roman, double spaced. Your grade is based on completion only (in other words, if you complete the assignment and it meets the length requirement and responds appropriately to the prompt, then you get full credit).

🔗

Problem 8.0.4. P3.

In this problem, we explore another property of binomial coefficients. Equations such as this are known as combinatorial identities, because they are equalities of expressions involving combinatorial values. Using the technique of disjoint union decompositions, prove that for any \(0\leq k \leq n\text{,}\) we have

\begin{equation*} \binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+\cdots +\binom{n-1}{k}+\binom{n}{k} = \binom{n+1}{k+1} \, . \end{equation*}

🔗

Problem 8.0.5. P4.

Give a combinatorial proof showing that

\begin{equation*} \sum_{k=0}^nk\binom{n}{k}=n2^{n-1} \, . \end{equation*}

🔗

Problem 8.0.6. P5.

Singmaster’s conjecture

en.wikipedia.org/wiki/Singmaster%27s_conjecture

is an open problem in mathematics, meaning that it is a problem that has not been solved by anyone. Note that the number \(1\) appears infinitely many times in the triangle of binomial coefficients. The open problem is as follows: Is there a fixed integer \(N\) such that every positive integer other than \(1\) shows up at most \(N\) times in the triangle of binomial coefficients?

🔗

Make as much progress as you can on this open problem; I don’t expect you to find a solution, but you should spend 2-3 hours thinking about this! Your goal is to do something more than check examples; the examples should lead you to make some interesting observations about the problem, to understand it a bit better. Why do you think it might be true? Why might it be false? Are there any properties of binomial coefficients that support your comments? Are there any positive integers for which this is obviously true? You can do this using only pencil and paper, or using mostly computational experiments, or you can use a mix of these. However, you need to provide a narrative in sentences/paragraphs explaining your thinking and the results of your investigations. (Seriously, write down everything you’re thinking and every idea you try, even if it doesn’t go anywhere.)

🔗

Problem 8.0.7. P6.

For each positive integer \(n\text{,}\) express in terms of Fibonacci numbers the number of sequences

\begin{equation*} (a_1,a_2,\ldots,a_n) \end{equation*}

with each \(a_i\in \{0,1\}\text{,}\) such that

\begin{equation*} a_1\leq a_2\geq a_3\leq a_4\geq a_5\leq a_6\geq \cdots \, . \end{equation*}

🔗

Problem 8.0.8. P7.

Find a relationship between the Fibonacci numbers and the number of compositions of \(n\) where every part is an odd number. Prove that your answer is correct.
🔗

🔗
A subset \(A\subseteq [n]\) is called large if we have that \(k\geq |A|\) for every \(k\in A\text{.}\) So, for example, \(\{3,5,7\}\) is large while \(\{2,4,6\}\) is not large. We define that the emptyset \(\emptyset\) is large. Let \(L(n)\) be the number of large subsets of \([n]\) (including the emptyset). Find a relationship between \(L(n)\) and the Fibonacci numbers and prove that your answer is correct.
🔗

🔗

🔗

Problem 8.0.9. P8.

In this problem you will prove that

\begin{equation*} \binom{n}{k}=\frac{n!}{k!(n-k)!} \end{equation*}

holds for all \(0\leq k\leq n\text{.}\) Let \(N(n,k)\) denote the number of ways to select \(k\) elements from \([n]\) and write them in a linear order, i.e., write them as a permutation.

Prove that

\begin{equation*} N(n,k)=\binom{n}{k}k! \end{equation*}

using only the combinatorial interpretation of \(\binom{n}{k}\text{.}\)

🔗

🔗
Prove that

\begin{equation*} N(n,k)=n(n-1)(n-2)\cdots (n-k+1) \end{equation*}

🔗

🔗
Using the previous two parts of this problem, prove that

\begin{equation*} \binom{n}{k}=\frac{n!}{k!(n-k)!} \end{equation*}

🔗

🔗

🔗

Problem 8.0.10. P9.

Prove that

\begin{equation*} c(n+1,2)=n!\sum_{i=1}^n\frac{1}{i} \, . \end{equation*}

Note that \(\sum_{i=1}^n\frac{1}{i}\approx \log(n)\text{,}\) and thus this shows that \(c(n+1,2)\) is approximately \(n!\log(n)\text{.}\)

🔗

Problem 8.0.11. P10.

A permutation \(\pi\in \ss_n\) is an involution if all cycles have length \(1\) or \(2\text{.}\) Let \(i_n\) denote the number of involutions in \(\ss_n\text{.}\) Prove that

\begin{equation*} i_{n+1}=i_n+ni_{n-1} \end{equation*}

where \(i_0:=1\) and \(i_1=1\text{.}\)

🔗

Problem 8.0.12. P11.

A permutation \(\pi\in \ss_n\) is called connected if

\begin{equation*} \{\pi_1,\pi_2,\ldots,\pi_j\}\neq \{1,2,\ldots,j\} \end{equation*}

for every \(1\leq j\lt n\text{.}\) Let \(C(i)\) denote the number of connected permutations in \(\ss_i\text{.}\) Prove that

\begin{equation*} \sum_{i=1}^nC(i)(n-i)! =n! \, . \end{equation*}

🔗

Problem 8.0.13. Essay 2.

Read the following blog post by Keith Weber, a professor of math education at Rutgers University who studies how undergraduate students understand proofs in mathematics:

https://blogs.ams.org/matheducation/2015/02/10/mathematics-professors-and-mathematics-majors-expectations-of-lectures-in-advanced-mathematics/

After you read this article, complete the following essay.

This will be an essay of length at least 500 words, which is equivalent to at least 2 typed pages with 1 inch margins, 12 point Times New Roman font, double spaced. (You can write a longer essay if needed.)
🔗

🔗
Your essay should respond to the following three questions.
- The article describes four expectations that professors have for students, but which are usually mis-communicated. For each of these four expectations, do you respond more like the students in their surveys, or more like the professors? Why?
  🔗
  
  🔗
- The discussion at the end of the article has some recommendations for faculty in their courses. Which of these recommendations do you think you would find most helpful for your learning, and why?
  🔗
  
  🔗
- What is one thing you might change about your approach to your math courses after reading this article? Why is this the thing you would choose to change?
  🔗
  
  🔗
🔗
🔗

Your grade is based on completion only (in other words, if you complete the assignment and it meets the length requirement and responds appropriately to the prompt, then you get full credit).

🔗

Problem 8.0.14. P12.

Recall that \(I_{n,k}\) is the number of permutations in \(\ss_n\) with \(k\) inversions, and \(A_{n,k}\) is the number of permutations in \(\ss_n\) with \(k\) descents. Give a combinatorial proof that

\begin{equation*} I_{n,k}=I_{n,(n(n-1)/2)-k} \end{equation*}

and

\begin{equation*} A_{n,k}=A_{n,n-1-k} \, . \end{equation*}

🔗

Problem 8.0.15. P13.

In the first part of this problem, you will prove by induction that

\begin{equation*} \sum_{j=1}^n j=\frac{n(n+1)}{2}\, . \end{equation*}
1. First, verify the base case for the induction argument, i.e., check that this is true for \(n=1\text{.}\)
  🔗
  
  🔗
2. Second, assume that this is true for all values less than \(n\text{.}\) In particular, this means that we assume we have already verified that
  
  \begin{equation*} \sum_{j=1}^{n-1}j=\frac{(n-1)n}{2}\, . \end{equation*}
  
  To prove that the induction step holds, use this to prove that the equation holds for \(n\) as follows: write
  
  \begin{equation*} \sum_{j=1}^n j = \left(\sum_{j=1}^{n-1} j\right) + n \end{equation*}
  
  and then substitute the formula for the \(n-1\) case and simplify with algebra.
  
  🔗
  
  🔗
3. Explain in your own words why this shows that the formula is true for any positive integer \(n\text{.}\)
  🔗
  
  🔗
🔗
🔗
Prove by induction that

\begin{equation*} \sum_{j=1}^nj^2=\frac{n(n+1)(2n+1)}{6}\, . \end{equation*}

🔗

🔗

Comment for those who are interested: These two formulas are ones that students learn (and typically forget) in Calculus I. However, these are special cases of a beautiful formula called Faulhaber’s formula which is a formula for the sum of the \(p\)-th powers of the first \(n\) positive integers: https://en.wikipedia.org/wiki/Faulhaber%27s_formula.

🔗

Problem 8.0.16. P14.

A graph is called \(k\)-regular if every vertex has degree \(k\text{.}\) How many edges does a \(5\)-regular graph on \(10\) vertices have?
🔗

🔗
Does there exist a \(121\)-regular graph on \(1013\) vertices? Why or why not?
🔗

🔗

🔗

Problem 8.0.17. P15.

A graph \(G\) is bipartite if the vertex set of \(G\) can be partitioned as \(V=A\uplus B\) in such a way that every edge in \(G\) has one endpoint in \(A\) and one in \(B\text{.}\) Prove that \(G\) is bipartite if and only if every cycle in \(G\) has an even number of edges.

🔗

Problem 8.0.18. P16.

Suppose a tree \(T\) has exactly one vertex of degree \(i\) for each \(2\leq i\leq m\) and all other vertices have degree \(1\text{.}\)

How many vertices does \(T\) have?
🔗

🔗
For each \(m\text{,}\) explain how to construct an example of a tree with this property.
🔗

🔗

🔗

Problem 8.0.19. P17.

A graceful labeling of a tree \(T\) on \(n\) vertices is a mapping

\begin{equation*} f:V(T)\rightarrow \{1,\ldots,n\} \end{equation*}

so that for each edge \(\{x,y\}\text{,}\) the value of

\begin{equation*} |f(x)-f(y)| \end{equation*}

is distinct from the value on any other edge. The path graph of length \(n\), denoted \(P_n\text{,}\) is the graph with vertex set \(\{1,2,\ldots,n,n+1\}\) and edges \(\{i,i+1\}\) for every \(1\leq i\leq n\text{.}\) Show that every \(P_n\) has a graceful labeling.

🔗

NOTE: A well-known and extremely challenging unsolved conjecture is that all trees admit graceful labelings. This is known for some trees but not all trees.

🔗

Problem 8.0.20. Essay 3.

Watch the following YouTube video from Numberphile (13 minutes, published 29 Jan 2024): https://www.youtube.com/watch?v=fczN0BCx0xs After you watch this video, complete the following essay.

This will be an essay of length 500 words, which is equivalent to 2 typed pages with 1 inch margins, 12 point Times New Roman font, double spaced.
🔗

🔗
Write a critical review of this Numberphile video. Imagine that you are writing your review for a journal for undergraduates in mathematics and the sciences, so your primary audience is undergraduate math/cs/engineering/etc majors and minors.
🔗

🔗
Like any critic, you will respond positively to some things and negatively to others. Unlike many critics, you need to justify your opinions and provide detailed explanations for your claims.
🔗

🔗
You should consider the following questions:
🔗

🔗

Your grade is based on completion only (in other words, if you complete the assignment and it meets the length requirement and responds appropriately to the prompt, then you get full credit).

🔗

Problem 8.0.21. P18.

Find the sequences of edges to build the tree corresponding to the Prufer code \(442233114\text{,}\) and explain your reasoning for how you find the edge at each step.
🔗

🔗
Find the Prufer code for the tree pictured below. Explain how you find the array \(A(T)\) step-by-step as you go through the algorithm.
🔗

🔗

🔗

Figure 8.0.22. Tree for homework problem.
🔗

🔗

Problem 8.0.23. P19.

Fix a connected graph \(G\) on vertex set \([n]\text{.}\) Let \(T\) and \(T'\) be two spanning trees of \(G\text{.}\) Prove that there exists a sequence of spanning trees of \(G\)

\begin{equation*} T=T_1, T_2, T_3,\ldots, T_k=T' \end{equation*}

such that \(T_{i+1}\) is obtained from \(T_{i}\) by deleting an edge from \(T_{i}\) and adding an edge from \(T'\text{.}\)

🔗

Problem 8.0.24. P20.

Let \((d_1,\ldots,d_n)\) be a sequence of positive integers. Using Prufer codes, prove that the number of spanning trees of \(K_n\) where the degree of vertex \(i\) is \(d_i\) is

\begin{equation*} \frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots (d_n-1)!} \, . \end{equation*}

🔗

Problem 8.0.25. P21.

For each of the following sequences, (1) construct the corresponding threshold graph and (2) compute its degree sequence.

SIIISSISI
🔗

🔗
IIIISIIIISS
🔗

🔗
SSSSIISS
🔗

🔗

🔗

Problem 8.0.26. P22.

For each of the following degree sequences, (1) compute the corrected Durfee number and (2) determine whether or not it is the degree sequence of a threshold graph. If it is a threshold graph, find a sequence of S and I operations that produce a graph with this degree sequence. Explain your reasoning.

\(\displaystyle (9, 8, 8, 8, 7, 7, 7, 7, 6, 5, 4)\)
🔗

🔗
\(\displaystyle (7, 5, 5, 3, 3, 3, 1, 1)\)
🔗

🔗
\(\displaystyle (6, 6, 6, 6, 6, 5, 5, 2)\)
🔗

🔗

🔗

Problem 8.0.27. P23.

For each of the following sequences, use the Havel-Hakimi test to determine whether or not it is a graphic sequence. Show your work and explain your solution.

\(\displaystyle (5, 4, 4, 4, 4, 4, 4, 3)\)
🔗

🔗
\(\displaystyle (7, 6, 6, 5, 5, 5, 4, 3, 3, 2)\)
🔗

🔗
\(\displaystyle (6,6,6,6,5,3,1,1)\)
🔗

🔗

🔗

Problem 8.0.28. Essay 4.

Read the following article from Quanta magazine: https://www.quantamagazine.org/maths-bunkbed-conjecture-has-been-debunked-20241101/ After you read this article, complete the following essay.

This will be an essay of length at least 500 words, which is equivalent to at least 2 typed pages with 1 inch margins, 12 point Times New Roman font, double spaced. (You can write a longer essay if needed.)
🔗

🔗
Your essay should respond to the following three questions.
- Was this article effective at communicating the mathematics of the bunkbed conjecture? Why or why not? (Give specific examples from the article to justify your claims!)
  🔗
  
  🔗
- What was something you thought was interesting about the article? Why was it interesting to you?
  🔗
  
  🔗
- What do you personally think the answer should be to the questions raised at the end of the article about proofs that are only true with high probability? Be detailed with your reasoning! It is acceptable to have a mix of responses to this issue, but you need to clearly explain your thoughts.
  🔗
  
  🔗
🔗
🔗

Your grade is based on completion only (in other words, if you complete the assignment and it meets the length requirement and responds appropriately to the prompt, then you get full credit).

🔗

Problem 8.0.29. P24.

Apply the bubble sort algorithm to the following permutation. Show your work step-by-step.

\begin{equation*} \pi = 923856714 \end{equation*}

🔗

Problem 8.0.30. P25.

Apply the stack sorting algorithm to the following permutation. Show your work step-by-step.

\begin{equation*} \pi = 21436587 \end{equation*}

🔗

Problem 8.0.31. P26.

Find a bijection between the set of stack-sortable permutations in \(\ss_n\) and the set of \(213\)-avoiding permutations in \(\ss_n\text{.}\) Explain why your bijection is correct.
🔗

🔗
Find a bijection between the set of stack-sortable permutations in \(\ss_n\) and the set of \(132\)-avoiding permutations in \(\ss_n\text{.}\) Explain why your bijection is correct.
🔗

🔗

🔗

Problem 8.0.32. P27.

Consider the set \(\Bin_n\) of binary strings of length \(n\) with the uniform distribution. Let \(X\) be the random variable where \(X(w)\) is the number of times a consecutive sequence of \(k\) copies of \(1\) appears in \(w\text{.}\)

Write \(X\) as a sum of indicator random variables.
🔗

🔗
Find \(E(X)\text{.}\)
🔗

🔗

🔗

Problem 8.0.33. P28.

Let \((\Omega, P)\) be a finite probability space and let \(X\) be a random variable on \(\Omega\) such that \(X(x)\geq 0\) for every \(x\in \Omega\text{.}\) We define \(P(X\geq a)\) to be the probability that \(X\) takes on a value greater than or equal to \(a\text{,}\) i.e.,

\begin{equation*} P(X\geq a):= \sum_{x \in \Omega, X(x) \geq a} P(x) \, . \end{equation*}

Prove that for any \(a > 0\text{,}\) the following inequality, which is known as Markov’s Inequality, holds:

\begin{equation*} P(X\geq a)\leq \frac{E(X)}{a} \, . \end{equation*}

🔗

Problem 8.0.34. P29.

In P28 you proved Markov’s Inequality, which we will now apply.

Consider the set of subsets of \([n]\) with the uniform distribution. Use Markov’s Inequality to prove that at most half of all subsets of \(\{1, 2, \ldots, n\}\) contain greater than \(\frac{n-1}{2}\) adjacent pairs of the form \(\{i, i+1\}\text{.}\)
🔗

🔗
Consider \(\ss_n\) with the uniform distribution. Use Theorem 4.5.7 and Markov’s Inequality to prove that the probability that \(\pi\in\ss_n\) has at least \(k\) fixed points is less than or equal to \(1/k\) for any \(k\geq 1\text{.}\)
🔗

🔗

🔗

Problem 8.0.35. Essay 5.

Read the course syllabus on the Canvas homepage for MA 415G. After you read the syllabus, complete the following essay.

This will be an essay of length at least 500 words, which is equivalent to at least 2 typed pages with 1 inch margins, 12 point Times New Roman font, double spaced. (You can write a longer essay if needed.)
🔗

🔗
Your essay should respond to the following three questions.
- Section 3 of the syllabus begins with a quote from Timothy Gowers. Given what you have seen so far in combinatorics, do you agree with his assertion about the way that the "important idea of combinatorics" appear? Why or why not?
  🔗
  
  🔗
- So far we have investigated techniques for solving enumeration, classification, and expectation problems. Which of these have you enjoyed the most? Which have you enjoyed the least? Why? Give specific examples from the homework and/or notes to illustrate your opinions.
  🔗
  
  🔗
- Page 2 of the syllabus lists four mathematical practices that students will develop in MA 415G, in addition to the eight questions of combinatorics. Which of these practices do you feel you have improved on the most so far this semester? Which do you are most in need of further development?
  🔗
  
  🔗
🔗
🔗

Your grade is based on completion only (in other words, if you complete the assignment and it meets the length requirement and responds appropriately to the prompt, then you get full credit).

🔗

Problem 8.0.36. P30.

Fix a positive integer \(k\text{.}\) Given an Erdos-Renyi random graph \(G(n,p)\text{,}\) let \(X\) be the random variable that counts the number of vertices of degree \(k\text{.}\) Find the expected value of \(X\text{.}\)

🔗

Problem 8.0.37. P31.

Given an Erdos-Renyi random graph \(G(n,p)\text{,}\) let \(X\) be the random variable that counts the number of paths of length \(2\) in \(G(n,p)\) (that is, sets of three distinct vertices \(\{u,v,w\}\) such that \(\{u,v\}\) and \(\{v,w\}\) are edges in \(G(n,p)\)). Find the expected value of \(X\text{.}\)

🔗

Problem 8.0.38. P32.

A \(4\)-cycle in a graph is a set of four distinct vertices \(\{v_1,v_2,v_3,v_4\}\) such that the edges \(\{v_1,v_2\}\text{,}\) \(\{v_2,v_3\}\text{,}\) \(\{v_3,v_4\}\text{,}\) and \(\{v_4,v_1\}\) are all in the graph. Given an Erdos-Renyi random graph \(G(n,p)\text{,}\) let \(X\) be the random variable that counts the number of \(4\)-cycles in \(G(n,p)\text{.}\) Find the expected value of \(X\text{.}\)

🔗

Problem 8.0.39. P33.

Consider the cycle \(C_{10}\) with vertices \(\{1,2,3,\ldots,10\}\text{.}\) Let \(M\) be the matching containing the edges \(\{1,2\}\) and \(\{5,6\}\text{.}\) Find a sequence of augmenting paths \(P_1,P_2,\ldots\) to create a sequence of matchings \(M_1,M_2,\ldots\) that start with \(M\) and end with a maximum matching. Give brief explanations of the steps in your process.

🔗

Problem 8.0.40. P34.

Let \(K_5\) be the complete graph on vertices \(\{1,2,3,4,5\}\text{.}\) For each edge \(e=\{i\lt j\}\) in \(K_5\text{,}\) define the weight function \(w(e):=3j-i\text{.}\) Apply Kruskal’s algorithm to find a minimum spanning tree of this graph. Give brief explanations of the steps in your process.

🔗

Problem 8.0.41. P35.

Suppose that \((G,w)\) is a finite graph with edge weight function \(w\) where the value of \(w\) is distinct for each edge; in other words, every edge has a unique weight. Prove that the minimum spanning tree of \(G\) is unique.

🔗

Problem 8.0.42. Essay 6.

Read the document "A Framework for Ethical Decision Making" from the Markkula Center for Applied Ethics, which you can read either on the web or as a pdf:

web page version: https://www.scu.edu/ethics/ethics-resources/a-framework-for-ethical-decision-making/
🔗

🔗
pdf version: https://www.scu.edu/media/ethics-center/ethical-decision-making/A-Framework-for-Ethical-Decision-Making-2025.pdf
🔗

🔗

After you finish the reading, complete the following essay.

This will be an essay of length at least 500 words, which is equivalent to at least 2 typed pages with 1 inch margins, 12 point Times New Roman font, double spaced. (You can write a longer essay if needed.)
🔗

🔗
Your essay should respond to the following three questions.
- The article presents six ethical lenses that can be used when considering ethical decision making: the rights lens, justice lens, utilitarian lens, common good lens, virtue lens, and care ethics lens. Which two of these lenses resonate most strongly with your personal thoughts about ethics? Why? Which of these lenses do you feel least connected to at this moment? Why?
  🔗
  
  🔗
- The article presents a sequence of ten questions to consider in the process of ethical decision making. Suppose you are working as a member of a team, for example in a professional or personal context, and your team is going through the ethical implications of different options for resolving an issue. Which two of these questions do you think would be most challenging to engage in conversation with the other people on your team? Why?
  🔗
  
  🔗
- What was one aspect of this document that you found surprising or unexpected? What made it stand out to you?
  🔗
  
  🔗
🔗
🔗

Your grade is based on completion only (in other words, if you complete the assignment and it meets the length requirement and responds appropriately to the prompt, then you get full credit).

🔗

Problem 8.0.43. P36.

Consider the configuration model for the degree sequence \((2,2,2)\text{.}\) Find all the looped multigraphs for this degree sequence and compute the probability for this looped multigraph in the configuration model. Explain all of your work to obtain your solution.

🔗

Problem 8.0.44. P37.

Consider the network with vertices \(\{1,2,3\}\) and edges (some appearing more than once) \(\{12,12,13,13,13,23,33\}\) (this means there is a single loop at \(3\)). Compute the modularity function (as given in Definition 5.6.9) for the vertex partition \(V_1=\{1\}\) and \(V_2=\{2,3\}\text{.}\)

🔗

Problem 8.0.45. P38.

Modify the code from Example 5.5.7 and run it in https://sagecell.sagemath.org/ to sample \(10,000\) times from the configuration model with degree sequence \((2,2,3,3)\text{.}\) How many looped multigraphs did you find? Are you guaranteed to see every possible looped multigraph in your sample? Why or why not?

🔗

Problem 8.0.46. P39.

Seymour’s second neighborhood problem

en.wikipedia.org/wiki/Second_neighborhood_problem

is an open problem in mathematics, meaning that it is a problem that has not been solved by anyone. Let \(G\) be a graph without loops or multiple edges. Assign to every edge a direction, that is, for each edge \(\{i,j\}\text{,}\) either direct the edge from \(i\) to \(j\) or the opposite. This turns \(G\) into a directed graph.

🔗

The first neighborhood of a vertex \(v\) in a directed graph is the set of all vertices that are at distance one from \(v\) (this means there must be an edge pointing from \(v\) to the neighbor). The second neighborhood of \(v\) is the set of all vertices that are at distance two from \(v\text{.}\) Note that these two sets are disjoint, and neither contains \(v\text{.}\)

🔗

The open problem is as follows: For every directed graph \(G\text{,}\) does there exist a vertex \(v\) such that the second neighborhood is at least as large as the first neighborhood?

🔗

Make as much progress as you can on this open problem; I don’t expect you to find a solution, but you should spend 2-3 hours thinking about this! Your goal is to do something more than check examples; the examples should lead you to make some interesting observations about the problem, to understand it a bit better. Why do you think it might be true? Why might it be false? Are there any properties of directed graphs that support your comments? Are there any directed graphs for which this is obviously true? You can do this using only pencil and paper, or using mostly computational experiments, or you can use a mix of these. However, you need to provide a narrative in sentences/paragraphs explaining your thinking and the results of your investigations. (Seriously, write down everything you’re thinking and every idea you try, even if it doesn’t go anywhere.)

🔗

Problem 8.0.47. P40.

The no-three-in-a-line problem

en.wikipedia.org/wiki/No-three-in-line_problem

is an open problem in mathematics, meaning that it is a problem that has not been solved by anyone. See the wikipedia page for an explanation of the problem.

🔗

Make as much progress as you can on this open problem; I don’t expect you to find a solution, but you should spend 2-3 hours thinking about this! Your goal is to do something more than check examples; the examples should lead you to make some interesting observations about the problem, to understand it a bit better. Why do you think it might be true? Why might it be false? Are there any properties of grids that support your comments? Are there any grids for which the answer is obvious? You can do this using only pencil and paper, or using mostly computational experiments, or you can use a mix of these. However, you need to provide a narrative in sentences/paragraphs explaining your thinking and the results of your investigations. (Seriously, write down everything you’re thinking and every idea you try, even if it doesn’t go anywhere.)

🔗

Problem 8.0.48. End-of-Class Reflection.

Type a 1000 word essay in response to the following prompt. This is the equivalent of 4 pages in 12 point Times New Roman font, double-spaced.

What were six of the most important discoveries or realizations you made in this class? In other words, what are you taking away from this class that you think might stick with you over time and/or influence you in the future? What have you experienced that might have a long-term effect on you intellectually or personally? These can include things you had not realized about mathematics or society, specific homework problems or theorems, etc. These can be things that made sense to you, or topics where you were confused, points that you agreed/disagreed with in the readings or class discussions, issues that arose while working on your assignments, etc.
🔗

🔗
Explain why these six discoveries or realizations are important to you.
🔗

🔗
You should include a combination of observations about both mathematics and your habits, practices, and beliefs about mathematics.
🔗

🔗

This assignment grade is based only on completion (i.e. if you turn it in, it meets the length requirement, and it appropriately responds to the prompt above, then you get full credit).

🔗

Prev TopNext