**1**

vote

**1**answer

228 views

### A problem on counting k-subsets of {-n,-n+1,…,n-1,n} satisfying that sum of elements equal to 0

I'll use another way to give the question besides the title.
Define
$$ A_k(n) = \frac{1}{2 \pi \mathrm{i}} \int_{|q|=1} \left( \frac{1}{2 \pi \mathrm{i}}\int_{|z|=1}\prod_{j=-n}^{n}(1+qz^j) ...

**1**

vote

**1**answer

147 views

### Associative binary operations defined on a finite set

We can easily test the commutativity of a binary operation on a set of $\ n\in\mathbb{N}\ $ elements by observing the symmetry of the $\ n\times n\ $ multiplication table.
I was looking for a ...

**1**

vote

**1**answer

171 views

### Counting edges in embeddable CW-complexes in R^3

Using Euler's formula ($V-E+F = 2$ where $V$, $E$ and $F$ are the number of vertices, edges and faces), we can easily count the number of edges in maximal graphs that are embeddable in plane: 3n-6. I ...

**1**

vote

**1**answer

223 views

### How many types of jigsaw puzzle pieces in n dimensions?

I was partitioning jigsaw puzzle pieces with some friends yesterday and we noticed that there are 6 types of pieces:
All 4 sides have a knobby bit sticking out
1 side has a knobby bit sticking out
2 ...

**0**

votes

**1**answer

113 views

### Expected rank of players in a Bradley-Terry round-robin tournament

Let $[n]$=$\{1,\dots,n\}$ be a set of players in a round-robin tournament. Each player $i$ has an associated skill parameter, $\lambda_{i}$, and the probability that player $i$ defeats player $j$ is ...

**15**

votes

**0**answers

206 views

### Is the Poset of Graphs Automorphism-free?

For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$.
...

**1**

vote

**1**answer

199 views

### Known results on cyclic difference sets

Is there any infinite family of $v$ for which all the $(v,k,\lambda)$-cyclic difference sets with $k-\lambda$ a prime power coprime to $v$ have been determined?
A subset $D=\{a_1,\ldots,a_k\}$ of ...

**3**

votes

**0**answers

70 views

### What is this expander-mixing-type graph property?

Fix $C>0$. I am interested in graphs with the following mixing property:
$$\Big|E(S,T)-\frac{1}{2}|S||T|\Big|\leq C\sqrt{|S||T|\max\{|S|,|T|\}}$$
for every disjoint $S,T\subseteq V$. Note that ...

**9**

votes

**5**answers

758 views

### Examples of ubiquitous objects that are hard to find?

I've been wrestling with a certain research problem for a few years now, and I wonder if it's an instance of a more general problem with other important instances. I'll first describe a general ...

**3**

votes

**1**answer

434 views

### Estimate the sum $\sum_{k=1}^n \frac{2^k}{k}$ [closed]

I am concerned with the following sum
$$\sum_{k=1}^n \frac{2^k}{k}_{\displaystyle ~.}$$
It seems that sum must be computed by someone, but I do not know.
By the way, I can figure out a power ...

**3**

votes

**0**answers

55 views

### Distribution of the evaluation (at a non-trivial root of -1) of polynomials with small coefficients

When we studied some cryptographic protocol, we came accross the following problem, which seems linked to the uniformity of the residues of small multiplicative subgroups of $\mathbb{F}_q$.
Problem
...

**2**

votes

**1**answer

143 views

### Regular graphs with $a$ and $b$ Hamiltonian edges

Special case of this question.
Let $G$ be $r$-regular Hamiltonian graph.
An $a$ edge is an edge which is on every Hamiltonian cycle.
A $b$ edge is an edge which is on no Hamiltonian cycle.
$a(G)$ ...

**6**

votes

**0**answers

174 views

### Fomin-Kirillov algebras and Schubert calculus

In
Fomin, Sergey; Kirillov, Anatol N. Quadratic algebras, Dunkl elements, and
Schubert calculus. Advances in geometry, 147--182, Progr. Math., 172,
Birkhäuser Boston, Boston, MA, 1999. MR1667680 ...

**7**

votes

**2**answers

271 views

### Sets whose elements are mutually “weakly” coprime?

Fix $n$ and $k$. I want a set $S\subseteq\{1,\ldots,n\}$ with the property that for every $x\in S$,
$$\mathrm{gcd}\bigg(x,\prod_{y\in S\setminus\{x\}}y\bigg)<\frac{x}{k}.$$
How small should a ...

**3**

votes

**0**answers

99 views

### Another Generalization of a Problem of Steinhaus

In his book of problems from elementary mathematics Hugo Steinhaus asked the following:
Is it possible to find an infinite sequence of real numbers $x_1,x_2,...$, such that
$x_1$ lies in the ...

**2**

votes

**1**answer

183 views

### Question about a proof in Graham and Lehrer's “Cellular algebras”

I'm sorry if this question is too basic for MO. I'm reading a paper by Graham and Lehrer "Cellular algebras" and have trouble understanding one step in a proof of a crucial theorem. I suppose that the ...

**3**

votes

**2**answers

256 views

### Ultrafilter-based Fourier-Walsh-like Functions

Here is a (little wild) question about Boolean functions with countably many variables and a wild analog for Fourier-Walsh functions and analysis based on them.
Let $x_1,x_2,\dots,x_n,\dots$ be ...

**5**

votes

**1**answer

215 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 ...

**7**

votes

**2**answers

289 views

### Graphs with many edges avoided by Hamiltonian cycles

Let $G$ be a $3$-connected Hamiltonian graph with at least one edge that belongs to each H-cycle of $G$. Some authors (e.g. in the link given here) call such an edge an a-edge and an edge that belongs ...

**4**

votes

**2**answers

177 views

### Number of unlabelled planar graphs

What are the best known bounds on the number of non-isomorphic (unlabelled) planar graphs on $n$ vertices? Is there a simple proof that this number is at most exponential in $n$?

**3**

votes

**1**answer

263 views

### A partition problem

This question is motivated by an old math contest problem, and is a generalization of the original problem. I will write out the original problem as motivation.
Let us say that $n$ is $p$-Savage, for ...

**1**

vote

**2**answers

115 views

### A definite integral of hypergeometric function 2F1

I am wondering whether there exists a closed form for the definite integral
$$F(x)=\int_0^1t^{-a}(1-t)^{N}(1-xt)^{-a}{}_2F_1(-a,k-a-1/2,k-a;4xt(1-xt))dt,$$
where $a\in(0,1)$ and $N,k$ are positive ...

**0**

votes

**0**answers

118 views

### When is a power of an indeterminate in an ideal with 2 generators?

If I have an ideal ${\frak a} \colon= (f(X,S), g(X,S))$ of height $2$ in ${\Bbb C}[X, S]$, is it easy to know what power of $S$ is contained in $\frak a$? For example, what is the minimal number $m$? ...

**1**

vote

**1**answer

196 views

### Is this Graph parameter known?

Let $\lambda(G)$ denote the edge-connectivity of $G$.
Consider the following parameter:
$\rho(G) = \max_{X \subset V(G)} \min(\lambda(G[X]), \lambda(G[V(G) - X]))$
Has this parameter been studied? ...

**5**

votes

**0**answers

106 views

### Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph

According to a conjecture:
Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common.
Equivalent statement here
Main question:
...

**2**

votes

**1**answer

146 views

### About an equivalent to Tutte's 5-flow Conjecture

A while back I remember reading that F. Jaeger proved that Tutte's $5$-flow conjecture is equivalent to a statement about the co-planarity of a certain set of points in some euclidean space. But I ...

**0**

votes

**1**answer

171 views

### a block design question

Is it possible to show that every 1-design $D$ with $\lambda=4,k=4$ on $v$ points (for $v$ that is a multiple of $3$) contain some 1-design $Q$ with $\lambda=1,k=3$ on $v$ points such that every block ...

**3**

votes

**2**answers

222 views

### Can the Vertices of cubic graph be partitioned into and induced cycle and a forest?

Let $G$ be a $2$-connected $3$-regular graph. Can $V(G)$ be partitioned into $V_1$ and $V_2$ where
$G[V_1]$(the induced subgraph on $V_1$) is a cycle of $G$ and $G[V_2]$ is a forest (Acyclic ...

**2**

votes

**1**answer

136 views

### Is the set of edge of a cubic graph the union of a cycle and and an Acyclic graph?

Let $G$ be a $2$-connected $3$-regular graph. Is it true that $E(G) = E_1 \cup E_2$ where
$G[E_1]$(the induced subgraph on $E_1$) is a cycle of $G$ and $G[E_2]$ is a forest (Acyclic subgraph) of $G$?
...

**31**

votes

**33**answers

4k views

### Structures that turn out to exhibit a symmetry even though their definition doesn't

Sometimes (often?) a structure depending on several parameters turns out to be symmetric w.r.t. interchanging two of the parameters, even though the definition gives a priori no clue of that symmetry. ...

**1**

vote

**0**answers

66 views

### Quadratic transformation of hypergeometric function 2F1

I want to know whether there is some transformation between
$_2F_1(a,b;c;x)$ and $_2F_1(a',b';c';x(1-x))$.
Here is an example called the Kummer quadratic transformation, which may be known to most of ...

**2**

votes

**1**answer

101 views

### Ranks of higher incidence matrices of designs

In 1978 Doyen, Hubaut and Vandensavel proved that if $S$ is a Steiner triple system $S(2,3,v)$ then the $GF(2)$ rank of its incidence matrix $N$ is
$$
Rk_{2}(N)=v-(d_{p}+1),
$$
where $d_{p}$ is the ...

**2**

votes

**1**answer

174 views

### Are all symmetric idempotent Latin squares known?

Are all symmetric idempotent Latin squares known?
There is such a square of order $n$ if and only if $n$ is odd. However, is there a classification of all of them?
(The motivation for the question ...

**11**

votes

**1**answer

400 views

### Are There Always Group Generators Which Give Unimodal Growth?

Suppose $G$ is a $k$-generated finite group. Is there always a set of $k$ elements which generate the group and have a unimodal counting function?
Background:
The counting function, $f(n)$, is a ...

**6**

votes

**2**answers

369 views

### Number of isomorphism types of finite groups

Are there some good asymptotic estimations for the number $F(n)$ of non-isomorphic finite groups of size smaller than $n$?

**2**

votes

**0**answers

78 views

### Counting regular Hypergraphs

The problem of counting regular graphs on $n$ vertices is notoriously hard. It seems like counting regular hypergraphs on $n$ vertices should be much easier (I am placing no uniformity condition). ...

**8**

votes

**2**answers

577 views

### How to find counterfeit coins by weighing

In one variant of the classic counterfeit coins problem you are given a bag of $n$ numbered but otherwise identical looking coins and a scale and your job is to find which coins are counterfeit. ...

**1**

vote

**3**answers

185 views

### Constructions of $2-(v,3,3)$-designs

I am looking for ways to construct an infinite family of designs with parameters $2-(v,3,3)$ and apart from some doubling-type recursive constructions (such as in this paper) I haven't found anything ...

**20**

votes

**3**answers

2k views

### How many different numbers can be obtained as product of first $n$ natural numbers?

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot ...

**4**

votes

**1**answer

105 views

### Counting the number of $(d_v,d_c)$ regular bipartite graphs

I am trying to count the number of $(d_v,d_c)$ regular bipartite graphs. To be specific, let $n,m,d_v,d_c$ be positive integers such that
$$n\times d_v=m\times d_c.$$
Then, what is the number of ...

**13**

votes

**1**answer

475 views

### Counting 2m X 2m 0-1 matrices with m ones in each row and each column.

Given $m>1$, what is the number of $2m\times 2m$ matrices, made of $0$ and $1$, such that each row has exactly $m$ ones, and each column has exactly $m$ zeros.
I am not sure if this is a ...

**3**

votes

**0**answers

184 views

### Binary search with maximum consecutive lies about “is X in subset S?”

Here's the original problem:
Alice tells Bob "I have thought of an integer between 1 and 2000. Tell
me 1000 numbers. If your set contains my number, I'll give you this
prize." Bob really wants ...

**7**

votes

**0**answers

150 views

### A Product Related to Partitions with Largest Part n

This is a finite version of a problem of mine entitled "A product related to unrestricted partitions." It has the advantage that, at least for small values of n, it is easily solved.
Begin with the ...

**6**

votes

**1**answer

95 views

### Maximizing ratio volume/diameter^n by an affinity

Suppose we have a convex compact body $D\subset \mathbb R^n$. We can try to apply affine transformation keeping the volume and decreasing the diameter of $D$.
It is clear that there is a constant ...

**2**

votes

**1**answer

107 views

### Representability of sets of infinite sequences sharing common prefixes and factors (i.e. infixes)

Here we are concerned with the space $X^{\omega}$ of infinite sequences. Denote by $F_n(\xi)$
the set of factors (consecutive finite subsequences) of length $n$ and consider the set
$$
K_n(\xi) = ...

**8**

votes

**2**answers

219 views

### Inequalities for averaging over partially ordered sets

Let's start from a classical inequality:
If $0\le a_1\le\cdots\le a_k$ and $0\le b_1\le\cdots\le b_k$ then
$(a_1+\cdots+a_k)(b_1+\cdots+b_k)\le k(a_1b_1+\cdots+a_k b_k)$.
It can be written also in ...

**2**

votes

**1**answer

179 views

### Coloring of subgraphs of G^n

Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , ...

**2**

votes

**1**answer

198 views

### efficient arithmetic with (short) Conway games?

We consider "games" in the sense of ONAG. Conway's definition of a game $G$ as a pair $G = \{L \mid R \}$ of sets of games, together with the definitions of inequality and the arithmetic operations ...

**5**

votes

**1**answer

141 views

### The line graphs of complete graphs and Cayley graphs

Let $n>3$ be an odd integer and let $K_n$ denote the complete graph on $n$ vertices.
For which integers $n$ the line graph $L(K_n)$ is a Cayley graph?
For even $n$, it follows from a result of ...

**3**

votes

**1**answer

134 views

### Cohen-Macaulay versus shellable simplicial complexes

There are some discussion of shellable simplicial complexes here
Testing simplicial complexes for shellability. My question is the following:
Assume that $\Delta$ is a pure simplicial complex on a ...