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.

Filter by
Sorted by
Tagged with
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. ...
Mikko Korhonen's user avatar
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 ...
Richard's user avatar
  • 1,363
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 ...
aorq's user avatar
  • 4,934
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/...
Robert Bailey's user avatar
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. ...
Adam Crume's user avatar
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 ...
user0o's user avatar
  • 31
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 ...
James Propp's user avatar
  • 19.4k
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 ...
burtonpeterj's user avatar
  • 1,689
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'...
Alex's user avatar
  • 151
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 ...
user30706's user avatar
  • 171
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$ ...
Tal H's user avatar
  • 273
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 $...
Jernej's user avatar
  • 3,433
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$....
Hans-Peter Stricker's user avatar
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 ...
Matt Brin's user avatar
  • 1,585
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,...
fnklberg's user avatar
  • 267
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, ...
Manta's user avatar
  • 83
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,\...
KEW's user avatar
  • 181
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-...
jsliyuan's user avatar
  • 651
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) ...
Mark S.'s user avatar
  • 613
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 ...
jigsawmnc's user avatar
  • 141
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 ...
rishig's user avatar
  • 143
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 ...
László Kozma's user avatar
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 ...
Moshe Schwartz's user avatar
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$ ...
POJ's user avatar
  • 63
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 ...
Richard Stanley's user avatar
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 ...
Cosmin Pohoata's user avatar
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 ...
Alberto Rivelli's user avatar
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 ...
Seva's user avatar
  • 22.8k
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)=...
Aaron Meyerowitz's user avatar
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 $...
Stefan Kohl's user avatar
  • 19.5k
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: ...
user avatar
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 ...
Uli Fahrenberg's user avatar
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 ...
Daniel Niv's user avatar
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 ...
Chris Bowman's user avatar
  • 1,191
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 ...
Nik Weaver's user avatar
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 \...
Yuichiro Fujiwara's user avatar
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 ...
Aaron Meyerowitz's user avatar
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 $...
Nik Weaver's user avatar
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\...
user 566's user avatar
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) $$ \...
john mangual's user avatar
  • 22.6k
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 ...
jonessekjns's user avatar
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 ...
Sam Hopkins's user avatar
  • 22.7k
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$ ...
totheend's user avatar
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 ...
Felix Goldberg's user avatar
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 ...
innerproduct's user avatar
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 ...
Christian Rinderknecht's user avatar

1
167 168
169
170 171
211