All Questions
Tagged with big-list co.combinatorics
64 questions
9
votes
3
answers
1k
views
Examples of combinatorial problems where the only known solutions, or most "natural" solutions, use representation theory?
In Solution of two difficult combinatorial problems with linear algebra, Robert Proctor presents two simply stated combinatorial problems, and gives solutions to them using a linear algebraic approach ...
7
votes
0
answers
166
views
Examples of finitary problems/theorems of high logical complexity? [duplicate]
Generally, number theoretic conjectures which are well-known and easy to explain are either obviously $\Pi^0_1$ or $\Pi^0_2$, which is to say, their truth can be decided by a single membership query ...
- 1,452
20
votes
3
answers
2k
views
Where do root systems arise in mathematics?
One often hears that root systems are ubiquitous in mathematics and physics. The most obvious occurrence of root systems is in the classification of complex simple Lie algebras. Where else do they ...
23
votes
4
answers
3k
views
Brute force open problems in graph theory
Usually, a graph theoretic problem asks whether some class of graphs $C$ possesses a quality $P$. For example, $C$ is the class of all graphs and $P$ is the reconstructability property in Kelly-Ulam ...
36
votes
8
answers
3k
views
Examples of errors in computational combinatorics results
I would like to collect examples of errors in published numerical results in computational combinatorics: where a result (typically a counting of some objects, or an extremal quantity within some ...
1
vote
1
answer
228
views
Named sets of permutations
I am looking into interesting subsets of permutations,
and there are several classes of permutations which are named.
For example, there are
Derangements,
Alternating,
Grassmann permutations (at most ...
12
votes
11
answers
1k
views
Lattices on classical combinatorial families
I am asking for examples of lattices defined on classical combinatorial families, such as Permutations, Catalan objects, set partitions or integer partitions, graphs.
I am mosty interested in lattices ...
- 5,822
15
votes
5
answers
2k
views
Striking existence theorems with mild conditions, and simple to state: more recent examples?
I would like to write an article about powerful existence theorems that assert, under mild and simple conditions, that some basic pattern or regularity exist. See some examples below. By mild ...
5
votes
3
answers
810
views
Update on "Hopf algebras: their status and pervasiveness" by Hazewinkel
Hazewinkel wrote this article in 2005. Perhaps it's time for an update.
For example, updating item
34: Ordinary differential equations much work has been done on the underlying Hopf algebra (HA) of ...
9
votes
7
answers
765
views
Important combinatorial and algebraic interpretations of the coefficients in the polynomial $[n]!_q = (1+q)(1+q+q^2) \ldots (1+q+\cdots + q^{n-1})$
What are some important combinatorial and algebraic interpretations of the coefficients in the polynomial
$$[n]!_q = (1+q)(1+q+q^2) \ldots (1+q+\cdots + q^{n-1})?$$
As motivation, I will give ...
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 "...
16
votes
2
answers
539
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
1
answer
229
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 ...
14
votes
1
answer
565
views
Legendary extra parameters to simplify a counting problem
I am reading Proofs and Confirmations, the history behind the alternating sign matrix conjecture, regarding counting $n \times n$ alternating sign matrices. In the introduction, it is written that ...
16
votes
2
answers
1k
views
Examples of problems where considering "discrete analogues" has provided insight or led to a solution of the original problem
The Kakeya conjecture posits that any Kakeya set in $\mathbb{R}^n$ has dimension $n$.
A discrete (finitized?) version of this problem is the Finite Field Kakeya conjecture, which was proved by Dvir ...
3
votes
2
answers
423
views
Finite groups with small God's numbers
Let $G$ be a finite group and $S$ be generating set it. Now given all words with alphabet $S$, then there exists a minimum word length $N(S,G)$ such that all group elements are represented by a word ...
- 43
33
votes
7
answers
3k
views
Examples of integer sequences coincidences
For the time being, the OEIS website contains almost $300000$ sequences. Each of these sequences is the mark of a specific mathematical concept. Sometimes two (or more) distinct concepts have the ...
5
votes
0
answers
230
views
On a Robin Forman's remark on combinatorial simplicial complexes
In a very captivating introduction to discrete Morse theory, Robin Forman makes the following remark:
...However, that does not explain why so many simplicial complexes that arise in combinatorics ...
- 5,590
18
votes
8
answers
2k
views
Concepts in topology successfully transferred to graph theory and combinatorics with non-trivial applications?
What are some of the difficult concepts in topology that have been transferred to graph theory and combinatorics where a certain new application has been found.
A good example is Lovász's proof of ...
9
votes
4
answers
560
views
When is it easier to work projectively?
There are many instances in which theory over $\mathbb{C}$ is cleaner than theory over $\mathbb{R}$. For example, continuously differentiable functions over $\mathbb{R}$ are not necessarily twice ...
25
votes
3
answers
2k
views
Interpretations and models of permanent
The standard interpretation of permanent of a $0/1$ matrix if considered as a biadjacency matrix of a bipartite graph is number of perfect matchings of the graph or if considered as a adjacency matrix ...
- 13.9k
3
votes
1
answer
288
views
Graph properties that imply a bounded number of edges
Many combinatorial problems can be reduced to bounding the number of edges in a given graph with $n$ vertices. Each time I encounter such a problem, I check whether the corresponding graph has a ...
- 1,072
5
votes
0
answers
199
views
Examples of combinatorial bijections found by considering functors
Let us assume that I have two sets of combinatorial objects, $A$ and $B$,
and I am looking for a bijection (in particular a map) $\psi:A \to B$ between these sets, usually required to preserve some ...
- 15.8k
19
votes
5
answers
1k
views
List of counting proofs instead of linear algebra method in combinatorics
I've just come across this proof of the Graham-Pollak Theorem by Sundar Vishwanathan (thanks to Konrad Swanepoel's sporadic comments about it on this site), that must be called beautiful after its ...
- 19k
21
votes
14
answers
3k
views
Applications of Representation Theory in Combinatorics
What are the examples of interesting combinatorial identities (e.g. bijection between two sets of combinatorial objects) that can be proved using representation theory, or has some representation ...
147
votes
66
answers
40k
views
Important formulas in combinatorics
Motivation:
The poster for the conference celebrating Noga Alon's 60th birthday, fifteen formulas describing some of Alon's work are presented. (See this post, for the poster, and cash prizes offered ...
13
votes
7
answers
2k
views
Finite-space dynamical systems
This question is quite open-ended, but I will formulate several sub-questions that I'll try to make precise. It is about finite-state dynamical system: start with a finite set $X$, with say $n$ ...
- 14.4k
3
votes
3
answers
445
views
When few simple conditions yield a unique intricate structure
If people were asked to do a brainstorming related to the title, everyone would probably come up with dozens of examples. Those could include things as different as
the Mandelbrot set, Julia sets ...
63
votes
19
answers
12k
views
Generalizations of the four-color theorem
The four color theorem asserts that every planar graph can be properly colored by four colors.
The purpose of this question is to collect generalizations, variations, and strengthenings of the four ...
31
votes
11
answers
2k
views
Combinatorial databases
At one point, I remember being excited by seeing the website Encyclopedia of Combinatorial Structures as an extension of Sloane's Online Integer Sequence Database site. Unfortunately, the site (ECS) ...
2
votes
0
answers
114
views
Non-negative, monotone polynomial sequences without combinatorial interpretation
I am wondering what sequences of integers there are, that are known to grow polynomially, are non-negative, monotone but lacks a combinatorial interpretation.
By combinatorial interpretation, they ...
- 15.8k
1
vote
1
answer
208
views
Sequences that represent different drawing of chords?
In combinatorics, there are special kinds of sequences, in which their terms represent the number of different ways that we can draw chords with some properties.
Actually, my question is motivated by ...
50
votes
37
answers
6k
views
Structures that turn out to exhibit a symmetry even though their definition doesn't
Sometimes (often?) a structure depending on several parameters turns out to be symmetric w.r.t. interchanging two of the parameters, even though the definition gives a priori no clue of that symmetry. ...
28
votes
6
answers
2k
views
Multiplying by irrational numbers in combinatorial problems
This is getting no attention on stackexchange.
Everybody knows that the number of derangements of a set of size $n$ is the nearest integer to $n!/e$.
It had escaped my attention until last week, ...
0
votes
6
answers
436
views
Equivalence relations not associated with a group
This is a vague question; so vague that I wonder if anyone will get it. Many, perhaps most, equivalence relations that are regularly used in mathematics correspond to the orbits of some group action ...
20
votes
4
answers
13k
views
Two questions about combinatorics journals
Hello,
I have two questions regarding combinatorics journals. I hope that this is the right place for such questions.
Which combinatorics/DM journals would you consider as the "top tier"?
I tried to ...
5
votes
1
answer
440
views
Repertory of the different sorts of operads
Many different types of operads have emerged in recent years (symmetric, shuffle, cyclic, anticyclic, coloured, etc.).
I would like, for any of these, list the following data:
Description of the ...
6
votes
4
answers
1k
views
fourier analytic proofs
While searching through Mathoverflow, I found out a fourier analytic proof of the Isoperimetric Inequality.Also, by google search I found a fourier analytic proof of Quadratic Reciprocity theorem.I ...
12
votes
3
answers
849
views
Applications of idempotent ultrafilters
Recently Justin Moore has posted a solution to the amenability of Thompson's group F. A key(?) step exploits the existence of idempotent ultrafilters on $\mathbb N$ to construct an idempotent measure ...
12
votes
12
answers
1k
views
Continuous notions with compelling discrete analogues
Following up on the previous MO question "Are there any important mathematical concepts without discrete analogue?", I'd like to ask the opposite: what are examples of notions in math that were not ...
6
votes
7
answers
6k
views
Discrete Mathematics textbooks for undergraduates
For the first time, I will be teaching a course on Discrete Mathematics for electrical and computer undergraduates students.
I intend to focus on practical applications.
I would be grateful if ...
3
votes
11
answers
753
views
A list of symmetric statistics
I would like to have a list of pairs (or tuples) of combinatorial statistics that are (known or conjectured) to have symmetric distribution. Ideally, something like this has already been compiled, ...
5
votes
3
answers
2k
views
Hales Jewett Theorem
In the book Ramsey Theory by Graham, Rothschild and Spencer the authors state:
The Hales Jewett Theorem strips van der Waerden's theorem of its unessential elements and reveals the heart of Ramsey ...
25
votes
5
answers
3k
views
Sperner Lemma Applications
I was always fascinated with this result. Sperner's lemma is a combinatorial result which can prove some pretty strong facts, as Brouwer fixed point theorem. I know at least another application of ...
2
votes
2
answers
418
views
Lovasz theta function - uses
Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
23
votes
4
answers
4k
views
What information is contained in the Kazhdan-Lusztig polynomials?
The Kazhdan-Lusztig polynomials contain all kinds of representation theoretic (and other kinds of) informations.
For example the character of a simple module over a Lie algebra with Weyl group $W$ ...
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 ...
23
votes
3
answers
3k
views
Proofs of parity results via the Handshaking lemma
I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency).
Let me ...
8
votes
3
answers
1k
views
Undecidable problems in geometry
Are there any (many) algorithmically undecidable problems in computational (combinatorial/discrete) geometry?
Update: the Wang tiles answer the question with "any". (I have somewhat overlooked to ...
34
votes
18
answers
20k
views
Interesting and accessible topics in graph theory
This summer, I will be teaching an introductory course in graph theory to talented high school seniors. The intent of the course is not to establish proficiency in graph theory, per se. Rather, I hope ...