Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

1
vote
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
5answers
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
2answers
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
1answer
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
2answers
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
2answers
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
33answers
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
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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
0answers
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
2answers
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
3answers
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
3answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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 ...