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,511
questions
5
votes
1
answer
419
views
Maximum graph cut in directed planar graphs
Maxcuts are known to be NP-hard. Maxcuts in undirected planar graphs are known to be P.
I think I've seen somewhere an approximate solution to maxcuts in directed planar graphs but I've never heard ...
6
votes
2
answers
1k
views
Presentation of the pure Artin groups
Let $W$ be a Coxeter group attached to a Coxeter matrix with entries $m_{ij}$ . The presentation of $W$ is given by
$$W= < T_1, \dots, T_n | T_i^2=1, T_iT_jT_i \ldots = T_jT_iT_j \ldots, i \neq ...
1
vote
0
answers
162
views
Proof technique for packing constant-size paths with degree constraints in a tree with a perfect matching
For my research I am interested in finding disjoint copies of certain "good structures" in graphs which are trees with a perfect matching. So let $T$ be a tree with a perfect matching $M$. I am ...
2
votes
0
answers
912
views
Guessing game with guess cost
This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...
9
votes
1
answer
535
views
What is the state of the art for the Turán number of $K_{4,4}$?
In Chung and Graham's "Erdős on Graphs: His legacy of unsolved problems," they discuss several open problems concerning Turán numbers for bipartite graphs.
There is a construction which gives graphs ...
15
votes
7
answers
3k
views
Compressing Graphs (Kolmogorov complexity of graphs)
What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov ...
16
votes
4
answers
2k
views
Point sets in Euclidean space with a small number of distinct distances
It is well known and not hard to prove that the regular simplex in n-dimensions is the only way to place n+1 points so that the distance between distinct pairs of points is always the same. My general ...
5
votes
1
answer
312
views
Article about partitions with forbidden parts/multiplicities
I am looking for an article, most likely from the 90s, that generalized the bijection between partitions with odd and distinct parts by explaining how a bijection between the forbidden parts could be ...
4
votes
2
answers
364
views
A Min Max problem for graphs? Is it well-known?
Dears
Let $G$ be a graph with $n$ vertices and let $T(G)$ be the set of all bijections from vertices $V(G)$ of $G$ to the set $\{1,\dots,n\}$. Let $E(G)$ be as ususal the set of edges of $G$.
Is the ...
15
votes
1
answer
705
views
The hypercube: $|A {\stackrel2+} E| \ge |A|$?
I have a good motivation to ask the question below, but since the post is
already a little long, and the problem looks rather natural and appealing
(well, to me, at least), I'd rather go straight to ...
6
votes
1
answer
821
views
Sums of binomials with even coefficients
While looking for a closed form of a expression I worked myself to a formula that resembles the Vandermonde convolution, but is summed over even binomial coefficients only.
$\sum_{k=0}^n\sum_{l=0}^n{...
0
votes
2
answers
2k
views
non negative integer solutions : Diophantine Equations [closed]
I want to know the exact number of non-negative integer solutions of $a_1 + 2a_2 + \ldots + k \cdot a_k = n$.
I know that it is the co-efficient of $x^n$ in $(1 - x^{a_1})^{-1} \cdot (1 - x^{a_2})^{-...
8
votes
2
answers
3k
views
Eigenvectors and partitions of graphs
Let G be an undirected graph with the node set $V$ and the Laplacian matrix $L$. Let $N(v)$ denote the neighbors of a node $v$ and $|N(v)|$ its degree. Then a partition $\pi=(V_1, V_2, \ldots, V_k)$ ...
5
votes
6
answers
2k
views
How many 0, 1 solutions would this system of underdetermined linear equations have?
The problem:
I have a system of N linear equations, with K unknowns; and K > N.
Although the equations are over $\mathbb Z$, the unknowns can only take the values 0 or 1.
Here's an example with N=11 ...
7
votes
1
answer
479
views
Combinatorial Problem
Any ideas or references on how to approach this problem? Every element in a set has a parameter $p_i \geq 0$ and $c_i \geq 0$. The objective is to find a subset which maximizes
$\prod_{i \in S} p_i + ...
3
votes
2
answers
1k
views
Sum of series where exponent is sum of arithmetic progression
How do I get the sum of such a sequence:
$$1 + x^{-1} + x^{-3} + x^{-6} + \dotsb,$$
where the exponents are actually sum of arithmetic progression? I.e.,
$$x^{-0} + x^{-(0 + 1)} + x^{-(0 + 1 + 2)} + x^...
1
vote
1
answer
1k
views
Applications of ham sandwich type results. References? A general principle?
Lately there has been a lot of interest on applications of the ham sandwich theorem and related results. There is a bunch of lecture notes and surveys that touch upon the subject. I dont know of any ...
6
votes
0
answers
420
views
Higher K-theory of Orlik-Solomon algebras (and possible generalizations?)
This topic of this question is a bit outside my comfort zone, and I should say that my end goal is to really understand how much "graph theory" is captured by contraction-deletion relations. ...
19
votes
1
answer
1k
views
Number of distinct values taken by x^x^...^x with parentheses inserted in all possible ways
For what positive x's the number of distinct values taken by x^x^...^x with parentheses inserted in all possible ways is not represented by the sequence A000081? Is it exactly the set of positive ...
2
votes
1
answer
8k
views
Sum of combinations
Is there a quick formula to find the ratios; $\displaystyle\frac{r(k)}{rtotal}$ for $k=1 \dots n$ without calculating the numerator and the denominator where;
$\displaystyle r(k) = \sum\limits_{i=1}^...
4
votes
5
answers
477
views
Some questions concerning a random number process
Consider the following Markov process: Start with an integer $N = N_0$. Now repeatedly choose an $N_i$ uniformly at random in the range $[1...N_{i-1}]$ until $N_i = 1$ at which point one terminates ...
29
votes
3
answers
1k
views
Stirling number identity via homology?
This is a question about the well-known formula involving both types of Stirling numbers:
$\sum_{k=1}^{\infty}(-1)^{k}S(n,k)c(k,m)=0$,
where $S(n,k)$ is the number of partitions of an $n$-element set ...
8
votes
2
answers
779
views
A hypercube-related graph
For integer $n\ge 3$, consider the graph on the set of all even vertices of the $n$-dimensional hypercube $\{0,1\}^n$ in which two vertices are adjacent whenever they differ in exactly two coordinates....
9
votes
0
answers
205
views
Reference for sparseness of incomparability graphs implying sparseness of covering graphs
If a partial order on $n$ elements has $m$ incomparable pairs, then its covering graph (aka Hasse diagram aka transitive reduction, the graph of pairs of elements that are comparable but are not the ...
5
votes
2
answers
775
views
theta functions from fock space
Is it possible to get theta functions from free fermions? I'm looking for proof of identity
\[ \sum_{n = -\infty}^\infty (-1)^n q^{n^2} = \prod_{j=1}^\infty \frac{1-q^j}{1+q^j} \]
maybe as a matrix ...
0
votes
1
answer
655
views
Deriving a closed form for rolling a sum $n$ with $k$ dice using stars and bars [closed]
I am trying to derive a closed form for computing the number possible outcomes of rolling $k$ dices such that the sum is $n$.
This seems to be the problem of finding number of positive integral ...
2
votes
0
answers
138
views
$f$-vector of graph connectivity
For a connected graph $G$, let $N_i$ be the number of connected subgraphs of size $i$. The vector $\langle N_0, N_1, \dots \rangle$ is also known as the $f$-vector for the graph.
As a superset of a ...
9
votes
3
answers
490
views
Equilibrium configurations of ions on n-Dim balls.
Given an n-dimensional electrically neutral, solid metal ball (a point for n=0; a rod, n=1; a disc, n=2; a solid ball, n=3; ...), place N=(n+1)! identical ions on the ball. As one of my favorite ...
2
votes
0
answers
147
views
Smallest size for an incomplete tournament with property $S_k$
By a well-known probabilistic argument due to Erdos, if $k>1$ is an integer then for all large enough $n$, there an asymmetric relation $R$ on $X=\lbrace 1,2, \ldots ,n \rbrace$ (i.e. $R \subseteq ...
4
votes
2
answers
853
views
Distribution of a maximum
I am reposting a question on math.stackexchange which did not recieve good questions.
The orginal questio is at https://math.stackexchange.com/questions/73091/distribution-of-a-maximum.
Randomly ...
2
votes
0
answers
276
views
Characteriszation of certain kinds of polynomials
My question:
Is there a known characterization for polynomials $P\in \mathbb{R}[x,y]$
with the property that
$$P(x,y) = 0 \wedge P(y,x) =0 \Rightarrow x = \overline{y}$$
and the number of the ...
15
votes
2
answers
965
views
Groups with a rational generating function for the word problem
This question comes more from curiosity than a specific research problem. Let G be a group and S a finite symmetric generating set. By the WP(G,S) I mean the set of all words in the free monoid on S ...
5
votes
1
answer
1k
views
Symmetric basis of harmonic homogeneous polynomials
Recently, a question about the beautiful theory of harmonic polynomials made me aware there is something
I've wanted to know for a long time.
As is well known, for any number of variables $n$ and ...
4
votes
1
answer
468
views
Generalization of the "double cap conjecture" to a vector space with complex field
The conjecture that I proposed in
Maximal set on hypersphere that does not contain pairs of orthogonal vectors
is in fact known as the "double cap conjecture", as noted by Guillaume Aubrun.
See for ...
10
votes
4
answers
1k
views
Binomial coefficient in Andrews' partition book
First of all, I think MathOverflow is a very great community to discuss math, either basic or advanced, and I'm glad to participate here. It's my first post, so I'm sorry if i did anything wrong, and ...
14
votes
3
answers
1k
views
A curious generalization of Helly's theorem
Here is a curious conjectural extension of Helly's theorem.
It may follow (if true) from a useful theorem of the kind asked in this MO question:
Conjecture: Let ${\cal F}=P_1,P_2,\dots,P_m$ be a ...
10
votes
1
answer
447
views
For what range of edge probability does the following property hold for random graphs?
Let $G(n,p)$ denote the Erdős–Rényi model of random graph. For a given function $p = p(n)$ we say that $G \in G(n,p)$ asymptotically almost surely has property $\mathcal{P}$ if
$$\mbox{Pr}[G \mbox{ ...
9
votes
1
answer
1k
views
A Desirable Extension of the Nerve Theorem
##Backgroud
The Nerve Theorem (see nLab;) asserts that given a finite collection $\cal K$ of compact sets with the property that all non empty intersections of sets in the family are homotopically ...
5
votes
1
answer
182
views
Proability of a word being fulfilled in the symmetric group
Let $S_n$ be the symmetric group on $n$ letters, let $g\in S_n$ be a fixed element of order, say, roughly $n^2$ (e.g. two large disjoint cycles of coprime length), let $w(a,b)$ be a reduced word in ...
12
votes
6
answers
2k
views
A sum involving derivatives of Vandermonde
Consider the standard Vandermonde $V(x_1, \ldots, x_n) = \prod_{i < j} (x_i - x_j)$.
I am intersted in the calculation of the following expression for fixed $k$:
$$\sum_i (x_i)^k (d/dx_i)^k V(x_1 , ...
14
votes
1
answer
533
views
Arctic regions in higher dimensional zonotopes
Same way as the two dimensional tilings by rhombi come from minimal surfaces in a $D$ dimensional cubical lattice as mentioned in this answer, one can consider higher dimensional zonotopes tiled by ...
3
votes
1
answer
238
views
Bounding the success time of a coupon collector like problem
Consider the complete graph on $n$ vertices. Each step, one chooses one of the $\binom{n}{2}$ edges iid uniformly at random. Say a sequence of choice is successful if there is some permutation of the ...
0
votes
1
answer
420
views
Lower bounds for partial sums of multiplicative functions
The motivation for this enquiry is to understand something about the impact of multiplicativity for $f:\mathbb{N}\rightarrow\mathbb{C}$ on the conditional convergence of Dirichlet series
$$F(s)=\...
4
votes
2
answers
240
views
Number of tuples satisfying the following condition
I try to find an upper estimate of the number of integer tuples $(i_1,\ldots,i_M)$ such that $i_1!\cdots i_M!\leq s$ for a given real number $s$. I'm especially interested in asymptotics of this ...
8
votes
2
answers
1k
views
"Coarse" Arctic Circle Theorem
Uniformly random dimer tilings of aztec diamond region will have an "artic" circle appear in the middle.
..
....
......
........
........
......
....
..
What happens if we make the ...
8
votes
1
answer
1k
views
Has anyone seen this graph?
I recently constructed the graph shown below in the process of investigating some problems regarding line graphs and homomorphisms, and then happened to see it on wikipedia. I was wondering if anyone ...
9
votes
4
answers
1k
views
Is this Ramsey-type problem an open problem?
A blog claims that the following Ramsey-type (or van der Waerden type) problem is open:
If the natural numbers are colored with finitely many colors, must there exist x and y (not both 2) such that x+...
5
votes
1
answer
2k
views
Decomposition of a complete graph into maximal matching subgraphs
Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge?
For example, consider $K_4$ with vertices $V=${1,2,3,4}...
21
votes
4
answers
2k
views
Rhombus tilings with more than three directions
The point of this question is to construct a list of references on the following subject: Fix vectors $v_1$, $v_2$, ..., $v_g$ in $\mathbb{R}^2$, all lying in a half plane in that cyclic order. I am ...