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
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 ...
Evgeniy's user avatar
  • 51
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 ...
Yaping Yang's user avatar
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 ...
Bart Jansen's user avatar
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. ...
Alex R.'s user avatar
  • 4,902
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 ...
Matthew Kahle's user avatar
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 ...
user avatar
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 ...
Edmund Harriss's user avatar
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 ...
user11235's user avatar
  • 543
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 ...
Alireza Abdollahi's user avatar
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 ...
Seva's user avatar
  • 22.8k
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{...
Rasto S.'s user avatar
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})^{-...
Sai Nikhil's user avatar
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)$ ...
Anna's user avatar
  • 83
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 ...
Bee San's user avatar
  • 153
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 + ...
sks's user avatar
  • 73
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^...
edwin11's user avatar
  • 31
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. ...
Gjergji Zaimi's user avatar
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}^...
Nick's user avatar
  • 31
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 ...
ARupinski's user avatar
  • 5,181
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 ...
Gary Kennedy's user avatar
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....
Seva's user avatar
  • 22.8k
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 ...
David Eppstein's user avatar
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 ...
john mangual's user avatar
  • 22.6k
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 ...
user18748's user avatar
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 ...
David Harris's user avatar
  • 3,397
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 ...
Tom Copeland's user avatar
  • 9,937
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 ...
Ewan Delanoy's user avatar
  • 3,565
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 ...
Fan Zhang's user avatar
  • 167
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 ...
Per Alexandersson's user avatar
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 ...
Benjamin Steinberg's user avatar
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 ...
Pietro Majer's user avatar
  • 56.5k
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 ...
Alm's user avatar
  • 1,159
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 ...
Guilherme's user avatar
  • 103
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 ...
Gil Kalai's user avatar
  • 24.2k
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{ ...
Matthew Kahle's user avatar
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 ...
Gil Kalai's user avatar
  • 24.2k
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 ...
Łukasz Grabowski's user avatar
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 , ...
Alexander Chervov's user avatar
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 ...
Gjergji Zaimi's user avatar
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 ...
John Jiang's user avatar
  • 4,354
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)=\...
Kevin Smith's user avatar
  • 2,470
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 ...
phlipsy's user avatar
  • 141
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 ...
john mangual's user avatar
  • 22.6k
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 ...
David Roberson's user avatar
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+...
idmercer's user avatar
  • 377
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}...
FreeQuark's user avatar
  • 377
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 ...

1
183 184
185
186 187
211