All Questions
41
questions
17
votes
2
answers
3k
views
Why do graph degree sequences always have at least one number repeated? [duplicate]
Why do graph degree sequences always have at least one number repeated?
$(1, 2, 2, 3)$ = Valid, as you can see, because the $2$ is repeated.
$(1, 2, 3)$ = Not possible to construct a graph with ...
17
votes
2
answers
3k
views
Minimum Cake Cutting for a Party
You are organizing a party. However, the number of guests to attend your party can be anything from $a_1$, $a_2$, $\ldots$, $a_n$, where the $a_i$'s are positive integers. You want to be prepared, ...
10
votes
1
answer
660
views
Sparse Ruler Conjecture
Sparse Ruler Conjecture, hard: If a minimal sparse ruler of length $n$ has $m$ marks,
easy: $m-\lceil \sqrt{3*n +9/4} \rfloor \in (0,1)$.
hard: $m+\frac{1}{2} \ge \sqrt{3 \times n +9/4} \ge m-1$...
9
votes
1
answer
246
views
Recovering a partition of 50
The sum of 10 numbers, not necessarily distinct, is 50. When placed appropriately in the circles of this diagram, any two numbers will be joined by a line if, and only if, they have a common divisor ...
8
votes
2
answers
2k
views
Find an infinite set of positive integers such that the sum of any two distinct elements has an even number of distinct prime factors
I have attempting to solve this using the infinite ramsey theorem, with colouring based on whether the sum of two vertices has an even or odd number of distinct prime factors.
This is leading to an ...
7
votes
1
answer
189
views
Count pairwise coprime triples such that the maximum number of the triple is not greater than N
Problem Statement:
Given N you are to count the number of pairwise coprime triples which satisfy $1≤a,b,c≤N$.
Example:
For example N=3,
valid triples are (1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,1,3),(1,3,1)...
7
votes
1
answer
833
views
Traversing the infinite square grid
Suppose we start at $(0.5,0.5)$ in an infinite unit square grid, and our goal is to traverse every square on the board.
At move $n$ one must take $a_n$ steps in one of the directions, north,south, ...
4
votes
1
answer
113
views
Freeing banks from debts- a nice combinatorial problem
There are $N$ banks with each having some some (possibly negative) integral balance with them. We say, a bank is in debt if its balance is less than rupee $0$. In each step, a bank may
borrow $1$ ...
4
votes
1
answer
301
views
Is this a known result on graph products?
Consider two undirected graphs $G=(V,E)$ and $H=(I,F)$.
Denote by $\mathcal N_G(v)$ (resp., $\mathcal N_{H}(i)$) the first neighborhood of a node $v\in V$ (resp., $i\in I$), including $v$ (resp., $i$)....
4
votes
0
answers
109
views
How many connected nonisomorphic graphs of N vertices given certain edge constraints?
Background:
I’m helping a colleague with a theoretical problem in ecology, and I haven’t quite the background to solve this myself. However, I can state the problem clearly, I think:
Problem statement:...
4
votes
0
answers
85
views
How many partitions of natural numbers into composite numbers are there?
In a graph-theoretic context the following question arose:
Given a natural number $n$. In how many ways can it be written as
the sum of composite numbers?
As an example, the number $64$ can be ...
4
votes
0
answers
1k
views
Original Research Topics for High School Student [closed]
I'm a grade 12 student interested in Number Theory, Graph Theory and Combinatorics and I am currently looking for ideas for an original research project/paper in mathematics. I was hoping that someone ...
3
votes
1
answer
181
views
A certain partition of 28
Given a multiset of positive integers, its P-graph is the loopless graph whose vertex set consists of those integers, any two of which are joined by an edge if they have a common divisor greater than ...
3
votes
1
answer
315
views
Rearranging rows of a matrix
Let $n,r,k$ be positive integers such that and $k \geq 2$. Consider the set of integers $\{1,2, \cdots, n\}$. I need to arrange these integers in a $kn \times r$ matrix in such a way that the entries ...
3
votes
1
answer
541
views
Is there a connection between König's infinity lemma and primes?
Google search yields the paper by RH Cowen called Generalizing König's infinity lemma. Due to my insufficient technical background, I am afraid, I cannot fully appreciate the paper.
Tout court, ...