Questions tagged [co.combinatorics]
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
10,515
questions
18
votes
1
answer
973
views
Lower bounds on the number of elements in Sylow subgroups
I posted this question on Math.SE (link), but it didn't get any answers so I'm going to ask here. This is an edited version of the question.
Let $p$ be a prime and $n \geq 1$ some integer. ...
17
votes
1
answer
890
views
Randomly switching street lights, in a square city
This is a combinatorics-probability question, best stated however in "recreational" terms. Imagine a $N\times N$ city, meaning that we have $N$ horizontal streets, and $N$ vertical streets. At each ...
5
votes
4
answers
331
views
Majority vote of total orders
Fix an odd natural number $k$. Suppose we have $k$ total orders on the same (finite) set $X$. Define a tournament on the vertex set $X$ by putting a directed edge $x\rightarrow y$ if a majority of ...
6
votes
2
answers
1k
views
Systems of simultaneous real quadratic equations
Starting from a problem in spectral graph theory, I got dragged into a problem in combinatorial matrix theory about constructing $n\times n$ real orthogonal matrices with a specified pattern of zero/...
5
votes
2
answers
879
views
Maximum distance within a subset of permutations
I'm modelling a scheduler that accepts a sequence of requests and outputs a sequence of responses, one response per request. It can partially reorder requests, but only within a finite queue. ...
3
votes
1
answer
441
views
What is the expected value for this
If there are $8$ random points in the plane whose horizontal coordinate
and vertical coordinate are uniformly distributed on the open interval
$\left(0,1\right)$, what is the expected largest size of ...
6
votes
1
answer
434
views
Bijective proof of Ramanujan's congruence
Is there a known bijective proof of Ramanujan's congruence for the partition function modulo 5? E.g., is there a construction that for every $n$ congruent to 4 mod 5 gives a permutation of the ...
2
votes
2
answers
688
views
Runs in coin flips
Let $P(j,k,n)$ be the probability of getting $j$ uniform runs of length $k$ from $n$ fair coin flips. What's the best way to compute $P$? I have no idea how difficult it might be; if it's a very ...
3
votes
0
answers
172
views
Are numbers $h_{r,s} = \sum_{k} P(r;s;k) \frac{1}{n^{2k}} \bigg(1-\frac{1}{n}\bigg)^{n-2k}$ irrational?
I asked this question on MSE and Mike Spivey gave an insightful answer. I decided to put it here nevertheless in case someone else gets interested. If this violates rules on MO, please let me know, I'...
1
vote
2
answers
227
views
Lower bound for constrained ordered partitions (i.e., compositions)?
An ordered $m$-partition (also called a composition) of an integer $n$ is an ordered sequence of positive integers $a_1, \ldots, a_m$ such that $\sum_i a_i = n$. Such a partition is $N$-constrained if ...
13
votes
1
answer
502
views
Permanent of a matrix of odd integers
It is clear that the permanent of an $n\times n$ matrix which entries are odd integers, is an even number, as it is the sum of $n!$ odd numbers. I am interested in finding the highest power of $2$ ...
4
votes
1
answer
560
views
Generating non-isomorphic graphs by adding edges to a given graph
This question is in a way related to the one I posted on math.se. Since the question there did not produce any final answer I am trying my luck here!
I am given a fairly large graph $G$ and subsets $...
2
votes
3
answers
597
views
Unique circular ordering of edges around a vertex
Consider the property of a vertex $v$ of a planar graph $G$ that the circular ordering of its edges is the same (upto orientation) for every graph embedding $\pi$ of $G$ into the plane $\mathbb{R}^2$....
6
votes
0
answers
267
views
Families of triangulations of polygons in the plane
Let $P$ be a polygon in the plane. An "efficient" triangulation of $P$ is one that introduces no new vertices. We require that all introduced edges be straight and inside $P$. Every polygon in the ...
5
votes
2
answers
553
views
connected components of a real hyperplane arrangement
Let us consider the following configuration of hyperplanes in the real
vector space V with coordinates $z_1,\ldots,z_n$: the hyperplanes are
numbered by all the nonempty subsets $J\subset I=\{1,\ldots,...
8
votes
1
answer
445
views
What is the probability that a random subset of a finite group is generic?
Definition 1: Given a group $G$, a subset $X \subseteq G$, and a natural number $k$,
we say that $X$ is (left) $k$-generic in $G$ if there are $k$ many left translates of $X$ that cover $G$.
That is, ...
9
votes
0
answers
239
views
An inequality for the ratio of standard Young tableau with {1,2,...,k} in the first row
For a partition $\lambda \vdash n$, define $\dim \lambda$ to be the number of standard Young tableaux of shape $\lambda$, and $\dim \lambda/(k)$ as the number of standard Young tableaux with $1,2,\...
7
votes
2
answers
744
views
counting triangle free graphs
Given $n$, the number of vertices, what is the number of triangle-free simple graphs on $n$ vertices (or asymptotically)?
A more difficult problem is, given $n$, $m$, what is the number of triangle-...
1
vote
0
answers
163
views
What is known about infinite diminished disjunctive compounds of loopfree partizan combinatorial games?
Background
Basic theories of loopy (normal-play) games which may go on forever under the usual disjunctive sum (the game ends when there are no moves available for you in any component on your turn) ...
12
votes
4
answers
3k
views
What are the major open problems in design theory nowaday?
I gather that the question whether the Bruck-Chowla-Ryser condition was sufficient used to top the list, but now that that's settled - what is considered the most interesting open question?
1
vote
1
answer
302
views
Integral solutions to $a_1 \times a_2 \times ... \times a_k = N$ [closed]
How many integral solutions are possible for the equation $a_1 \times a_2 \times \ldots \times a_k = N$ where each of $a_1, a_2, \ldots, a_k$ satisfy the property $0 \leq a_i \leq 9 $?
The question ...
14
votes
4
answers
775
views
Largest permutation group without 2-cycles or 3-cycles
The largest permutation group without 2-cycles is $A_n$, which has size $n!/2$. I think the largest permutation group without 2-cycles or 3-cycles is much smaller, but I can't figure out if it should ...
4
votes
1
answer
263
views
Alternative proof for counting problem in graphs
Let $G$ and $H$ be graphs, let $\vec H$ be a fixed orientation of $H$.
Denote by $D(G,\vec H)$ the number of orientations of $G$ that contain a copy of $\vec H$ and denote by $D'(G,H)$ the number of ...
3
votes
2
answers
247
views
A sum related to the Johnson association scheme
Hi everyone,
In the process of studying a problem in the Johnson association scheme I came across the following sum:
$$\sum_{k\geq 0}(-1)^k\binom{n}{k}\binom{a-k}{a-b}\binom{c+k}{b}.$$
All the ...
6
votes
2
answers
297
views
Minimal period of arithmetic progressions occurring in sets of positive density.
Let $A$ be a subset of ${\mathbb N}$ with positive upper-Banach density, and for each integer $k\geq3$, define $R_k=R_k(A)$ to be the smallest positive integer $r$ such that $A$ contains a length $k$ ...
21
votes
5
answers
2k
views
A question on the Laurent phenomenon
This question is motivated by my answer to 109955. It gives a
recurrence relation satisfied by a function $P(n)$ whose terms a
priori are rational functions (of three variables) with complicated
...
0
votes
0
answers
140
views
Reference Request: a paper by Yoseloff about a proof of Sperner's Lemma
Dear Overflow,
Apologies in advance if I'm posting this in the bad place, but I was hoping some of you could point out to me a place where I could read online the following paper by Yoseloff, where ...
3
votes
2
answers
3k
views
Coloring a graph by Maximum Independent Set extraction
recursively extracting a MIS from an undirected simple graph $G$ does produce a minimal coloring for $G$ ?
I searched extensively the internet and found a paper [1] which answer partially to this ...
4
votes
1
answer
449
views
Covering all, but $k$ points with affine subspaces
For non-negative integer $d\le n$ and $k\le 2^n$, how many affine subspaces of co-dimension $d$ are needed to cover all, but exactly $k$ elements of the vector space ${\mathbb F}_2^n$, and what are ...
1
vote
0
answers
158
views
For which triples of cycle structures $\alpha,\beta,\gamma$ are there permutations $x,y$ with $C(x),C(y),C(xy)=\alpha,\beta,\gamma?$
This question is motivated by the answer to this one There is also another followup. The question there was " Given integers $m,n,k \gt 1$ construct permutations $x,y$ with $o(x)=m,o(y)=n$ and $o(x,y)=...
32
votes
3
answers
3k
views
Order of products of elements in symmetric groups
Let $n \in \mathbb{N}$. Is it true that for any $a, b, c \in \mathbb{N}$ satisfying
$1 < a, b, c \leq n-2$ the symmetric group ${\rm S}_n$ has elements of order $a$ and $b$
whose product has order $...
14
votes
1
answer
776
views
Order of elements
Consider natural numbers $m,n,k > 1$. There are finite groups $G$ containing elements $x,y$ such that $o(x) = m, o(y) = n$ and $o(xy) = k$. After embedding these groups in $S_\mathbb{N}$ we drive: ...
1
vote
1
answer
167
views
Covering of a partial order by upwards convex sets
First off: I'm not an expert in order theory, so some of my terms might be off; correct them if you wish.
Let me call a subset $A$ of a lattice $(S,\le)$ upwards convex (not sure if that's actually ...
2
votes
3
answers
366
views
Complex Zeroes of Stirling functions of the second kind
My motivation to the following question stems from the discussion at Zeros of "exponential" function about the real zeroes of Stirling numbers of the second kind, I am curious in exploring ...
9
votes
1
answer
840
views
Littlewood Richardson rule and seminormal basis of Specht modules
Background
Seminormal Basis of Specht modules of $\mathfrak{S}_n$
Let $\lambda$ be a partition of $n$. A $\lambda$-tableau is a
bijection $\mathfrak{t}:\lambda \to \{1,2,...,n\}$. We say a ...
5
votes
1
answer
397
views
faces in the discrete cube
This arose from a question Gil Kalai asked about a problem I posed involving the Fourier transform on the discrete cube. Maybe it is more tractable. I'm afraid I'm not sure how to do this kind of ...
7
votes
0
answers
719
views
Largest set of integers without 3-term arithmetic progressions mod $n$
I am interested in a sharp bound on the largest possible size $e_3({\boldsymbol{Z}_n})$ of a subset $S \subset \boldsymbol{Z}_n$ such that for any three distinct elements $a, b, c \in S$ we have $a+b \...
11
votes
1
answer
407
views
Polyominoes with double contact
Here is a problem which arose from an earlier question. I'll change the terminology but not the question: A polyomino is a region with a connected interior made by joining one or more unit squares ...
33
votes
1
answer
3k
views
Fourier transform on the discrete cube
Notation: identify an element of $\{-1,1\}^n$ with the set $S \subseteq \{1, \ldots, n\}$ on which it takes the value $-1$.
The following is an asymptotic question. "Close to one" means "more than $...
1
vote
2
answers
555
views
Is there formula name and proof for this theorem ? [closed]
The formula answers: how many tuples $(\sigma_1,\sigma_2,...,\sigma_n)$ of elements of a given group G such that
(1) $\sigma_i\in C_i$ , where $C_i$ stands for conjugacy class.
(2) $\sigma_1\...
3
votes
0
answers
182
views
spectrum of a polygon and zeta function
Let $\Delta(x,y) = 1,0$ according to whether $(x,y)$ is in some polygon (symmetric with respect to the diagonal axis).
E.g. The convex hull of three points (taken from a paper on dominoes)
$$ \...
10
votes
1
answer
591
views
Combinatorial Proof of Real Analysis Identity
In this question, a proof using real analysis is given of the following identity $$ \sum_{n=1}^{\infty} \frac{(n-1)!}{n \prod_{i=1}^{n} (a+i)} = \sum_{k=1}^{\infty} \frac{1}{(a+k)^{2}}$$
Is there a ...
13
votes
6
answers
4k
views
Non-constructive proofs vs. efficient algorithms
My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity.
The wikipedia article on constructive proof begins, "a constructive ...
0
votes
0
answers
147
views
A good upper bound on the size of k-biclique in random bipartite graphs.
Let $G = (X \cup Y, E)$ be a random bipartite graph, where $X$ and $Y$ are the set of vertices and $E$ the set of edges. I want to find an upper bound of the largest biclique in which exactly $k$ ...
4
votes
2
answers
717
views
A Problem about affine transformation
Problem: Suppose that $f:\;\mathbb{R}^2\to\mathbb{R}^2$ is an injective mapping from the 2-dimensional Euclidean plane into itself which maps lines into (instead of onto) lines and whose range ...
8
votes
2
answers
590
views
A Problem about partitioning $S^2$
Question: Can the 2-dimensional sphere $S^2$ be partitioned into four nonempty sets such that every circle in $S^2$ passes through just three of these four sets?
Here, "just three" means "exactly ...
4
votes
2
answers
325
views
Is there an infinite number of combinatorial designs with $r=\lambda^{2}$
A quick look at Ed Spence's page reveals two such examples: (7,3,3) and (16,6,3).
If there is a known classification and/or name by which such designs go, I'd love to know about them too.
EDIT: I ...
4
votes
1
answer
352
views
Convex polyhedral decomposition of spheres
Is there a decomposition of $S^2$ into $k$ (geodesically) convex polyhedra that are congruent to each other? What about $S^n$ for $n>1$?
Remarks:
A polyhedron is defined as an area enclosed by a ...
1
vote
2
answers
1k
views
An identity involving a sum of binomial coefficients
I am moving through a classic paper (On Average Height of Planted Plane Trees by Knuth, de Bruijn and Rice, 1972), and I would like to trade a weaker result for simpler mathematical tools, because my ...