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
4 votes
3 answers
235 views

Best strategy for a combinatorial game

Consider the following scenario. We have 20 balls and 100 boxes. We put all 20 balls into the boxes, and each box can contain at most one ball. Now suppose we are given 5 chances to pick 20 out of ...
Magi's user avatar
  • 281
5 votes
1 answer
276 views

Convexity of the expectation of boolean functions

Let $$f:\{-1,1\}^n \to \{-1,1\}$$ be a monotone, odd ($f(-x)=-f(x)$) Boolean function. Let $$F:[0,1]\to[0,1]$$ denote the probability that $f(x_1,...,x_n)$ where $x_1,...,x_n$ are i.i.d. $\pm1$ R.V. ...
gidi's user avatar
  • 61
22 votes
2 answers
736 views

A q-rious identity

Let $[x]_q=\frac{1-q^x}{1-q}$, $[n]_q!=[1]_q[2]_q\cdots[n]_q$ and ${\binom{x}{n}}_{q}=\frac{[x]_q[x-1]_q\cdots[x-n+1]_q }{[n]_q!}$. Computer experiments suggest that $$\det \left(q^\binom{i-j}{2}\...
Johann Cigler's user avatar
3 votes
1 answer
149 views

Are there any more polytopes whose 2-faces are identical 4-gons?

What are examples for convex polytope $P\subset \Bbb R^d,d\ge 3$ for which holds $P$ is 2-face transitive (that is, all 2-faces are equivalent under the symmetries of $P$), and all 2-faces of $P$ are ...
M. Winter's user avatar
  • 12.5k
6 votes
0 answers
123 views

Squared squares and partitions of $K_{nn}$

This is inspired by a recent question. Define a square square sum (SSS) of order $n$ to be any partition $$n^2=\sum_1^tc_ii^2 \tag{*}$$ of $n^2$ into square summands. Call it perfect if all $c_i \leq ...
Aaron Meyerowitz's user avatar
3 votes
0 answers
141 views

Noncrossing partitions in Hopf algebras/monoids via compositional inversion

Partition polynomials constructed from the face structures of the associahedra (OEIS A133437) and permutahedra (A133314) comprise the antipodes/compositional inverses in a Faa-di-Bruno-type Hopf ...
Tom Copeland's user avatar
  • 9,937
1 vote
0 answers
113 views

A question about partitions into distinct parts

This question is a variant of the question posed by Brian Hopkins. Let $\operatorname{pdist}(n)$ be the number of partitions of $n$ into distinct parts. Also, let $\operatorname{pdist}(S, n)$ denote ...
David S. Newman's user avatar
15 votes
7 answers
1k views

Examples of proofs by making reduction to a finite set [closed]

This is a very abstract question, I hope this is appropriate. Suppose $T$ is some claim over some infinite set $A$, for example, let $A$ be the set of all loopless planar graphs, and $T$ be the claim "...
4 votes
1 answer
183 views

Applying a simple involution to Hall-Littlewood polynomials

Consider the Hall-Littlewood polynomial $$ P_\lambda(x_1,\ldots,x_n;t)=\sum_{\sigma\in S_n/S_n^\lambda}\sigma\left(x_1^{\lambda_1}\cdots x_n^{\lambda_n}\prod\limits_{\lambda_i>\lambda_j}\dfrac{x_i-...
Spencer Leslie's user avatar
4 votes
1 answer
114 views

What is the probability of an empty convex $k$-gon among many given points?

Given a finite number of points in the plane in general position, call a convex subset empty if its hull doesn't contain any other of the points. For a big number $n$ of randomly distributed ...
Wolfgang's user avatar
  • 13.2k
3 votes
0 answers
172 views

Find every prime $p$ such that $p^3$ divides $(p-1)!+1$ [duplicate]

My main question is similar to the title: Are there any primes $p$ such that $p^3$ divides $(p-1)!+1$? It is hard to find all $p$ such that $p^2$ divides $(p-1)!+1$ (Wilson primes). So, in my ...
apple's user avatar
  • 501
3 votes
1 answer
176 views

Strict unimodality of bipartite partitions

For non-negative integers $k$ and $l$ let $p(k,l)$ denote the number of vector partitions of $(k,l)$. In other words, $p(k,l)$ is the number of ways of writing $$ (k,l) = (k_1,l_1)+\dotsb + (k_r,l_r), ...
Amritanshu Prasad's user avatar
12 votes
2 answers
945 views

How rare are unholey permutations?

For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$. Given a permutation $\pi$ of $[n]$, we define the holeyness $D(\pi)$ of $\pi$ as being $...
H A Helfgott's user avatar
  • 19.3k
2 votes
0 answers
150 views

The topological complexity of polytopes

Polytopes arise naturally when modelling fundamental structures in Biology such as RNA and proteins [1,2]. Recently, it occurred to me that a complexity measure on the topology of polytopes might be ...
Aidan Rocke's user avatar
  • 3,827
5 votes
1 answer
263 views

Diameter of Cayley graphs of finite simple groups

Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article). THEOREM 1.1. There is a constant $C$ such that every nonabelian finite simple group $G$ has a set $S$ ...
khers's user avatar
  • 235
4 votes
0 answers
210 views

How frequent are permutations with small interleaving?

For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$. Let $\pi$ be a permutation of $[n]$. For simplicity, assume that $\pi$ is an $n$-cycle. ...
H A Helfgott's user avatar
  • 19.3k
12 votes
4 answers
578 views

A specific collection of subgraphs in $K_{70, 70}$

Does there exist a collection of subgraphs $\{\Gamma_i\}_{i = 1}^{24}$ of $K_{70, 70}$, that satisfy the following two properties: 1)$\Gamma_i \cong K_{i, i} \forall 1 \leq i \leq 24$; 2)Any edge of $...
Chain Markov's user avatar
  • 2,618
5 votes
0 answers
101 views

Dinitz Conjecture extension to rectangles

The Dinitz Conjecture, which was proved later in a more general form by Galvin, stated that given an $n\times n$ array, its elements could be filled exactly like a latin square, where the elements in ...
vidyarthi's user avatar
  • 2,007
3 votes
0 answers
140 views

Under what conditions on $A$ and $v$ is the size of the sumset $v \cdot A + A$ over $\mathbb{F}_p$ equal or close to $|A|^2$?

Let $p$ be a prime, let $A$ be a subset of $\mathbb{F}_p$, and let $v \in \mathbb{F}_p \setminus \{0\}$. Under what conditions is $|v \cdot A + A|$ (that is, $|\{ va + b : a \in A,\ b \in A \}|$) ...
Daira-Emma Hopwood's user avatar
2 votes
1 answer
524 views

List coloring of tripartite graph [closed]

Let $G$ be a tripartite graph with partite sets $A,B,C$. The graphs $A\cup B$, $B\cup C$ and $C\cup A$ are each bipartite. Let the maximum degree of the graph be $\Delta$. Now, we know that the ...
vidyarthi's user avatar
  • 2,007
0 votes
1 answer
236 views

Showing equality of Eberlein polynomials

I have thought about the following question a long time and still got no progress. Currently I am writing my master thesis about association schemes in combinatorics and need an equality which seems ...
McRatchet's user avatar
0 votes
1 answer
91 views

If the core of a graph is a forest, then it is Class 1

It is a standard result, due to Fournier, that if the core of a graph (the induced graph by the vertices having their degrees equal to maximum degree of the graph) is a forest (acyclic), then the ...
vidyarthi's user avatar
  • 2,007
1 vote
1 answer
96 views

Are non-trivial interval-isomorphic posets lattices?

We say that a partially ordered set $(P,\leq)$ is interval-isomorphic if for all $a<b \in P$ we have $P \cong [a,b]$, where $[a,b]=\{x\in P:a\leq x\leq b\}$. Suppose $(P,\leq)$ is interval-...
Dominic van der Zypen's user avatar
9 votes
2 answers
370 views

Every possible number of partitions by restricting parts?

Write $p(n)$ for the number of integer partitions of $n$. For $S \subseteq \{1, \ldots, n\}$, let $p_S(n)$ be the number of partitions of $n$ with all parts in $S$. So $p(n) = p_{\{1,\ldots,n\}}(n)$....
Brian Hopkins's user avatar
5 votes
1 answer
403 views

Iterated derivative and rectangular standard Young tableaux

We first make a few definitions, seemingly out of the blue (they are introduced/defined in this paper). Let $F^0_{a}(z) = (1-z)^{-1}$ and define recursively $$ F^{k+1}_{a}(z) = z^{a-1} \frac{d^a}{dz^...
Per Alexandersson's user avatar
7 votes
0 answers
176 views

Matrix of high rank mod $2$: must it have a large non-singular minor (with disjoint rows and columns)?

Let $A$ be a $2n$-by-$2n$ matrix with entries in $\mathbb{Z}/2\mathbb{Z}$ such that, for every $2n$-by-$2n$ diagonal matrix $D$ with entries in $\mathbb{Z}/2\mathbb{Z}$, the matrix $A+D$ has rank $\...
H A Helfgott's user avatar
  • 19.3k
1 vote
0 answers
136 views

Strategy of Responder in Rényi Ulam Liar Games

I tried posting this in Math Stack Exchange but got no responses, so I figured I could try my luck here. My main concern is that I can't figure out how to get started on my "research" (bear with me, I'...
FrasierCrane's user avatar
5 votes
2 answers
391 views

What is this sequence counting?

While solving (a system of) a system of linear equations level-by-level recursively, I am finding some redundant equations for level $n\geq5$. The reason why the redundancies arise is because $P(n)\...
TheTwistedSector's user avatar
2 votes
1 answer
167 views

Tighter lower bound of the lower triangular sum of an arbitrary Latin square

In this math.stackexchange.com question I seek a tighter bound than the one I presented in there in the question. Rob Pratt puts forth a conjecture in his answer motivated by the dual problem of the ...
Hans's user avatar
  • 2,169
16 votes
2 answers
514 views

Surprising appearances of Painlevé transcendents

What are some of your favorite examples of enumerative problems whose answer ended up being (related to) a solution to one of the Painlevé equations? I have seen examples from enumeration of classes ...
8 votes
2 answers
474 views

Lusztig's $q$-analog of weight multiplicity with product formula

For partitions $\lambda, \mu \vdash n$, the Kostka-Foulkes polynomial $K_{\lambda,\mu}(q)$, a $q$-analog of the Kostka coefficient $K_{\lambda,\mu}$, has a combinatorial description, due to Lascoux ...
Sam Hopkins's user avatar
  • 22.7k
2 votes
0 answers
85 views

chromatic class of graphs of order $n$

Let $\mathcal{G}(n)$ be the isomorphism class of simple graphs of order $n$. We say two graphs in $\mathcal{G}(n)$ are chromatic equivalent if their chromatic polynomials have an equal linear ...
GA316's user avatar
  • 1,219
28 votes
1 answer
2k views

How can I improve my formal definitions?

I am a Software Architect and not very familiarized with standard notation in mathematics. Nonetheless, I would like to write a paper explaining a normalization of a computing model for expert systems....
Izar Urdin's user avatar
13 votes
2 answers
629 views

A reformulation of Erdős conjecture on arithmetic progressions

Erdős conjecture on arithmetic progressions states that if $S$ is a set of positive integers such that $c(S):=\sum_{n \in S} \frac{1}{n} = \infty$ (large set), then $ \forall \ell \ge 3$ the set $S$ ...
Sebastien Palcoux's user avatar
0 votes
1 answer
53 views

Writing a set of all possible (symmetric) products condensely? [closed]

I have a set of elements $\{a_1, a_2, a_3...\}$ and $\{b_1, b_2, b_3...\}$ and I want to condensely formally write the set of all possible products of these elements, where the ordering does not ...
Jake B.'s user avatar
  • 1,423
1 vote
1 answer
429 views

Quotient graph of a tree

We know that every graph is isomorphic to a subgraph of a complete graph. Similarly, can we say that every graph is isomorphic to a quotient graph of a tree?
cl4y70n____'s user avatar
2 votes
1 answer
106 views

Probability distributions with irregular behaviour

Might there be a probability distribution $\mathcal{D}$ such that if we sample $a_i \sim \mathcal{D}([-N,N])$ where $[-N,N] \subset \mathbb{Z}$ then if we define the asymptotic estimate $f$: \begin{...
Aidan Rocke's user avatar
  • 3,827
3 votes
1 answer
106 views

Asymptotic estimate of the cardinality of $H_{2n}=\{\vec{a} \in [-N,N]^{2n}:\sum_{i=1}^{2n} a_i = 0\}$

Let's suppose $a_i \sim \mathcal{U}([-N,N])$ where $[-N,N] \subset \mathbb{Z}$. We may then define: \begin{equation} S_n = \sum_{i=1}^n a_i \tag{1} \end{equation} Now, in order to estimate $\lvert ...
Aidan Rocke's user avatar
  • 3,827
8 votes
1 answer
226 views

Prominent examples of $q$-analogs without known cyclic sieving

The cyclic sieving phenomenon is nicely summarized in the following AMS Notices "What is...?" article: https://www.ams.org/notices/201402/rnoti-p169.pdf. In that article, Reiner, Stanton, and White ...
4 votes
4 answers
279 views

How many residues mod p do you need to take to ensure that you can always find some multiple that contains 3 elements within ϵ of each other

For $\epsilon<p$, let $N(\epsilon,p)$ be the smallest value of $n$ such that for any set $S \subset \mathbb Z_p$ of size $n$, there exists $\lambda\in \mathbb Z_p^{*}$, $\mu \in \mathbb Z_p$ s.t $\...
Ivan Meir's user avatar
  • 4,782
0 votes
1 answer
128 views

Combining three matchings to form a maximal matching

Consider a regular tripartite graph $G$ with maximum degree $\Delta\ge3$ and parts $A,B,C$. Now, the induced subgraphs $A\cup B, B\cup C$ and $A\cup C$ are all bipartite. Now, is there a way to ...
vidyarthi's user avatar
  • 2,007
4 votes
1 answer
166 views

Complementing the red and blue boolean cube?

Given a boolean $0/1$ cube in $n$ dimensions with $2^{n-1}$ red and $2^{n-1}$ blue points can we complement the cube (blue becomes red and vice versa) in $\operatorname{poly}(n)$ transformations? ...
Turbo's user avatar
  • 13.7k
12 votes
2 answers
962 views

Higman's lemma and a manuscript of Erdős and Rado

Motivated by a problem in factorization theory, I've recently proved the following: Theorem. If $X$ is a non-empty finite alphabet and $\mathcal W$ an infinite subset of the free semigroup, $X^\ast$...
Salvo Tringali's user avatar
1 vote
1 answer
124 views

Number formation and bridged graphs, connection or coincidence?

Bridged graphs sequence $g(n) =$ "Number of simple connected bridged graphs on $n+2$ nodes". We have $g(n)=1, 3, 10, 52, 351, 3714,\dots$ from A052446. Number formation sequence We also have $f(n) ...
Vepir's user avatar
  • 591
7 votes
1 answer
217 views

Partitions restricted to only certain summands

Here $n$ is a positive integer and $p(n)$ is the number of unrestricted partitions. Can one always find a subset $s$, of $\{1,2,\ldots,n\}$ such that the number of partitions of $n$ with parts from ...
David S. Newman's user avatar
3 votes
0 answers
261 views

Guises of the refined Eulerian numbers, generated by tangent vectors (OEIS A145271)

The Eulerian numbers (OEIS A008292, not to be confused with the Euler numbers) pop up in numerous scenarios in combinatorics and advanced analysis, one as the components of the h-vectors of the ...
Tom Copeland's user avatar
  • 9,937
6 votes
2 answers
940 views

Remarkable applications of Dickson's lemma

Dickson's lemma states that, for a fixed $k \in \mathbf N^+$, every set of $k$-tuples of natural numbers has finitely many elements that are minimal with respect to the product order induced on $\...
3 votes
0 answers
125 views

$\left< 15\right>^7/15$-womcode construction

In the article Womcodes constructed with projective geometries Frans Merkx constructed several good wom-codes (write-once memory codes, see How to reuse a "write-once" memory by Rivest & Shamir ...
Alexey Ustinov's user avatar
1 vote
1 answer
96 views

Software for Hilbert series of quotients of exterior algebras

Is there some software which computes Hilbert series of quotients of exterior algebras? In commutative case, Maple can compute Hilbert series. Thank you very much.
Jianrong Li's user avatar
  • 6,101
9 votes
2 answers
391 views

Are these two combinatorially-defined sets of integers disjoint?

Fix an integer $n\geq 8$. For each integer $i\leq n/2$, denote by $X_i$ the set $$X_i = \left\{ \frac{n-i+1-k}{n-i+1}\binom nk\binom{k-1}{i-1} ~\middle|~~ i\leq k\leq n-i\right\}.$$ The ...
John McVey's user avatar
  • 1,018

1
68 69
70
71 72
211