**0**

votes

**1**answer

52 views

### Maximal induced cycles on $n$-clique graphs

For any set $X$ we set $[X]^2 = \big\{\{a,b\}: a, b\in X\text{ and } a\neq b\big\}$.
We say a simple undirected graph $G=(V,E)$ is an $n$-clique graph if there are $S_1,\ldots,S_n\subseteq V$ such ...

**0**

votes

**1**answer

96 views

### Problem related to Frobenius coin problem

Call a pair of integers $a,b\in\Bbb N$ with $\mathsf{gcd}(a,b)=1$ a good coprime pair if we have the property that
$$\mbox{ if }ax+by=rs\mbox{ and }ax'+by'=tu\mbox{ for some ...

**1**

vote

**0**answers

32 views

### Show existence maximal clique of order $s$ in an multigraph where each vertex is colored with a set of colors

You are given a multigraph $G$ with $n$ vertices as follows:
$V := (v_1, v_2, \dots ,v_n)$
$C := \{c_1, c_2, \dots\}$, be an infinite set of colors.
$f: V \rightarrow \mathbb{P}_{\le m}(C) $, a ...

**3**

votes

**1**answer

136 views

### Graphs with polynomial volume growth

Let $G = (V,E)$ a graph, equipped with graph distance (i.e. for $x,y \in V$, the distance $d(x,y)$ is the length of the minimum path connecting $x$ and $y$). For $x \in V$ and $r \in \mathbb N$, ...

**5**

votes

**3**answers

379 views

### Where was it first stated that there are no 4-transitive finite groups other than symmetric, alternating and Mathieu groups?

It seems to be well-known that the six-transitive finite groups are the symmetric and alternating groups, and the only other four-transitive finite groups are the Mathieu groups (the statement can be ...

**3**

votes

**1**answer

471 views

### A generalized theorem of Hall's marriage theorem

We all know Hall's marriage theorem as following:
A bipartite graph $G$ with bipartition $\{ A,B \}$ contains a matching of $A$ if and only if $|N(S)|\geq |S|$ for all $S\subseteq A$.
And I am ...

**0**

votes

**0**answers

89 views

### On the Frobenius coin problem [on hold]

Is there an $n_0\in\Bbb N$ such that for every $n\in\Bbb N_{>n_0}$ there are $a,b\in\Bbb N$ with $n<a,b<2n$ with $\mathsf{gcd}(a,b)=1$ such that
1. if $ax+by=rt$ for some $x,y>0$ with ...

**11**

votes

**2**answers

293 views

### Pursuit-Evasion type game on graph (“Flyswatter game”)

An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the ...

**1**

vote

**0**answers

49 views

### Consecutive integers divisible by consecutive small numbers

Given $n$, what is the largest set of consecutive integers in $[n,2n]$ can we have so that each integer is divisible by a distinct element from $[\log n,2\log n]$ (no partiular order)? So apriori I am ...

**0**

votes

**1**answer

235 views

### The weighting function for the infinite product of necklaces

Let us consider the limit $\lim_{n\to \infty}\prod_{p=1}^n N(p,a)$ where $N(n,a)$ is the number of fixed necklaces of length $n$ composed of $a$ types of beads.
Let's rewrite the product in a way ...

**5**

votes

**1**answer

92 views

### Asymptotic enumeration of magic squares

An order-$n$ magic square is an $n \times n$ matrix over the numbers $\{1, ... ,n^2\}$, each appearing exactly once, whose row and column sums are all equal. Sometimes the sums of the diagonals are ...

**3**

votes

**0**answers

77 views

### Weighted maximal number of disjoint singly-generated ideals in the divisibility poset for $\{1,2,\ldots,n\}$

In the mathoverflow question here the asymptotic growth of antichains in the divisibility poset ${\cal P}_n$ of the set of natural numbers $\{1,\ldots,n\}$ is considered. I have a somewhat dual ...

**5**

votes

**0**answers

46 views

### Chromatic numbers for coloring-constrained graphs

I am interested in any and all articles about chromatic numbers applying to constrained colorings of a graph. For example, if a graph must be (properly) colored so that there is a 2-color path ...

**3**

votes

**1**answer

120 views

### Can a length n distributive lattice be embedded into Bn?

Let $\mathcal{L}$ be a finite distributive lattice, then it is known that it can be embedded into a finite boolean lattice (see theorem 8.5. p91 in this note).
Let $n$ be the length of ...

**2**

votes

**0**answers

51 views

### Planar triangulations for which all distinct 4-colorings consist of exactly 6 Kempe chains

Are there any internally 6-connected planar triangulations other than the icosahedron all of whose distinct 4-colorings consist of exactly 6 Kempe chains, one for each of the 6 color-pairs?
Addendum: ...

**3**

votes

**1**answer

127 views

### Exact statistics in the Frobenius coin problem

The Frobenius coin problem guarantees that if $(a,b)=1$, then
$$ax+by$$ does not represent exactly $\frac{(a-1)(b-1)}2$ numbers all below $g(a,b)=ab-a-b$ if $x,y\geq0$ holds.
Assume $m\in[0,ab-a-b]$ ...

**-2**

votes

**0**answers

34 views

### Chance of throwing dices [on hold]

Let's say we have a n-sided dice. And we throw it p-times. What's the formula that shows whats the chance to get the integer k ?

**1**

vote

**1**answer

123 views

### The number of good partitions

This was also posted in stackexchange. However, I have no idea how difficult it is. All hints or references are appreciated!
Consider a set $S$ of $n$ red balls and $m$ blue balls. It is well known ...

**1**

vote

**0**answers

28 views

### Colorful Neighborhoods

Given:
$G:=\{V= \{v_1,\ ...\ v_n\},E\subset V\times V\}, n<\infty$, a symmetric complete, simple graph
$w:=\ \ E \ni e_{ij}\mapsto \mathbb{R}^+$, a weight function for the edges of $G$
$K:=\{c_1,\ ...

**7**

votes

**1**answer

510 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**1**

vote

**0**answers

46 views

### Partitioning the vertex set of a planar bipartite graph into a tree and an independent set

Let $G = (V, E)$ be a planar bipartite graph such that there is a partition $(V1, V2)$ of $V$ where $V1$ induces a tree and $V2$ induces an independent set.
Is there a characterization of such ...

**6**

votes

**1**answer

543 views

### A Zero-Multiplicity Problem Related to Foulkes' Conjecture

I'm a combinatorialist that is interested in estimating multiplicities of irreps of $1^{S_{kn}}_{S_k \wr S_n}$ (the action of symmetric group on uniform partitions). I'm aware of the difficulty (or ...

**6**

votes

**0**answers

76 views

### Upper bound for a sum including Andre polynomial coefficients

Let $ c_{n,k} $ be a sequence defined by the following relations: $\displaystyle c_{n,0} = 1, \hspace{0.1cm} (n \ge 1)$;
$$ c_{n,k} = (k+1) c_{n-1,k} +(n-2k+1) c_{n-1,k-1}, \hspace{0.5cm} (1 \leq k ...

**-4**

votes

**0**answers

30 views

### Counting subset of repeated permutations [on hold]

I'm trying to find a way to find to count specific ordered arrangements of a set with k elements, where each arrangement has n elements.
For example for k=2 and n=3
aaa
aab
aba
abb
baa
bab
bba
bbb
...

**33**

votes

**11**answers

24k views

### Sum of 'the first k' binomial coefficients for fixed n

I am interested in the function $\sum_{i=0}^{k} {N \choose i}$ for fixed $N$ and $0 \leq k \leq N $. Obviously it equals 1 for $k = 0$ and $2^{N}$ for $k = N$, but are there any other notable ...

**0**

votes

**1**answer

79 views

### Undergrad : decomposition of an integer as sum, with constraints [on hold]

I need to know if there is a way to determine in how many ways one can write n as $ n= x_1 + x_2 + \cdots + x_k$ with each $x_j \in \mathbb{N}$, and with the extra restriction that $x_j \leqslant ...

**7**

votes

**1**answer

129 views

### Equalizing Geometric means of Graph Cycles

Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are ...

**3**

votes

**1**answer

179 views

### Minimal Birthdays

In combinatorial game theory: The birthday of a game is defined recursively as 1 plus the maximal birthday of its options, with the zero game having birthday 0.
Suppose we define the quasi-birthday ...

**6**

votes

**1**answer

152 views

### Eigenvalue inequality for regular graphs

I recently proved an inequality relating some of the eigenvalues of a regular graph with each other, and I was wondering if it is already known. I was unable to find it online, and a quick skim ...

**2**

votes

**3**answers

432 views

### The number of submodules of $\mathbb{Z}_q^n$

Observe $\mathbb{Z}_q^n = \mathbb{Z}_q \times \cdots \times\mathbb{Z}_q$ as a module over $\mathbb{Z}_q\equiv\mathbb{Z}/q\mathbb{Z}$, for general $q$.
I am interested in the following questions:
How ...

**8**

votes

**0**answers

158 views

### An abstract zero-sum problem

I would like to know whether the problem described below has appeared in the literature and/or whether similar questions have been studied. I would be very happy to find some references or, if none ...

**9**

votes

**1**answer

171 views

### A Graph-Theory Related Question

Let $n$ be a positive integer and partition a grid of $4n$ by $4n$ unit squares into $4n^2$ squares of sidelength $2$. (The squares with sidelength $2$ have all of their sides on the gridlines of the ...

**2**

votes

**0**answers

63 views

### Number of multipartite partitions with odd components

For some positive integer $r$, by an $r$-vector I will mean an $r$-tuple $(a_1,a_2,\dots,a_r)$ with $a_1,\dots,a_r$ nonnegative integers not all zero, and I will call it odd if $a_1,\dots,a_r$ are all ...

**18**

votes

**3**answers

947 views

### Is the sequence of partition numbers log-concave?

Let $p(n)$ denote the number of partitions of a positive integer $n$. It seems to me that we have for all $n>25$
$$
p(n)^2>p(n-1)p(n+1).
$$
In other words, the sequence $(p(n))_{n\in ...

**12**

votes

**1**answer

582 views

### Maximum number of vectors in a hypercube satisfying given conditions

$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean ...

**0**

votes

**0**answers

15 views

### Is there a shelling of a (threshold)shifted complex, such that any partial shelling is still (threshold)shifted?

first the relevant definitions:
A complex $\Delta \subset 2^{[n]}$ is a family of subsets of $[n]$ that is closed downwards, i.e. if $A \subset B$ and $B \in \Delta$, then $A \in \Delta$.
A complex ...

**4**

votes

**2**answers

267 views

### A property of uncountable almost disjoint families

Let $\mathcal{A}$ be an uncountable almost disjoint family (not necessarily maximal) of infinite subsets of $\mathbb{N}$. Denote by $\mathcal{A}_{\subseteq}=\{ B\subseteq\mathbb{N}:|B|=\omega \wedge ...

**5**

votes

**1**answer

239 views

### Generating function for number of different tessellation checkered rectangle

Let $R_n$ be checkered rectangle sized $n \times 4, n \ge 1$.
Let $a_n$ be number of different $R_n$ tiling with rectangles sized $1 \times 3$.
$\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ ...

**7**

votes

**4**answers

1k views

### Is the Manickam-Miklós-Singhi Conjecture solved? [closed]

This arXiv paper is claimed to contain a proof for the MMS conjecture. But it seems that this manuscript is not yet peer reviewed by other mathematicians. I personally tried to follow the paper, but ...

**2**

votes

**0**answers

57 views

### On low rank $0/1$ real matrices with one connected component

Let $M$ be an $n\times n$ $0-1$ matrix of real rank $r$.
Moreover assume every row of $M$ is distinct and every column of $M$ is distinct. Such a matrix cannot be bigger than $2^r\times 2^r$.
As in ...

**2**

votes

**2**answers

129 views

### Maximum size of a union of incomparable chains

The following question was asked on math.stackexchange, where it received no answers.
http://math.stackexchange.com/questions/1392669/maximum-size-of-a-union-of-incomparable-chains
Let ...

**3**

votes

**1**answer

105 views

### Algorithm to count the number of perfect matchings in non planar graph

I need to count the number of perfect matchings of a certain family of graphs. This family of graph is non planar and a type of snark. For the initial cases, it seems that this number is growing ...

**47**

votes

**5**answers

7k views

### Identifying poisoned wines

The standard version of this puzzle is as follows: you have $1000$ bottles of wine, one of which is poisoned. You also have a supply of rats (say). You want to determine which bottle is the poisoned ...

**2**

votes

**3**answers

748 views

### A conjectured criterion for 4-colorable graphs

I tried to find a solution to this in the web but couldn't.
Can you tell me if the following sentence is correct or else give me a counterexample?
$G$ is $4$-colorable if and only if each sub-graph ...

**2**

votes

**0**answers

95 views

### Zero-one links: how many, and how to produce?

For $m \geq 1$, define a link to be a zero-one word $w=d_0d_1 \ldots d_k$, where $d_0=0$ and $k=2^m-1$ , such that the words
$$ w_0=0^{m-1}d_0, w_1=w_0d_1, w_2=w_1d_2, \ldots, w_k = w_{k-1}d_k $$
...

**5**

votes

**1**answer

231 views

### A remarkable sum over partitions

While studying some seemingly unrelated topological questions, I have experimentally discovered what appears (to me) to be a remarkable sum over partitions. I was wondering if anyone knows how to ...

**3**

votes

**0**answers

61 views

### Fibers of torus equivariant moment maps

Given a closed (possibly singular) projective variety $V$ with a symplectic structure and a torus action, there is a moment map
$\mu: V \rightarrow Lie(T)^*$. Note that the dimension of $T$ could be ...

**2**

votes

**2**answers

279 views

### Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets:
Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...

**13**

votes

**7**answers

1k views

### Can we disallow finite choice?

When people work with infinite sets, there are some who (with good reason) don't like to use the Axiom of Choice. This is defensible, since the axiom is independent of the other axioms of ZF set ...

**11**

votes

**1**answer

144 views

### Graphs with a coloring that majorizes all other colorings

By a coloring of a graph $G = (V,E)$ I mean a map $\kappa:V\to\mathbb{N}$ such that $\kappa(u)\ne \kappa(v)$ whenever $u$ and $v$ are adjacent. (Sometimes this is called a proper coloring but I am ...