Skip to main content
Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Saves in:saves
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options not deleted user 61536

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

25 votes
2 answers
1k views

The number of polynomials on a finite group

A function $f:X\to X$ on a group $X$ is called a polynomial if there exist $n\in\mathbb N=\{1,2,3,\dots\}$ and elements $a_0,a_1,\dots,a_n\in X$ such that $f(x)=a_0xa_1x\cdots xa_n$ for all $x\in X$. …
Taras Banakh's user avatar
  • 41.8k
18 votes

Dividing a cake between $n-1$, $n$, or $n+1$ guests

Writing down the details of the argument of Ilya Bogdanov, we can obtain the following upper bound: Theorem. $f(n)\le\frac83n-1$ for every $n\ge 2$. Proof. If $n=3k+1$ or $n=3k+2$, then following th …
Taras Banakh's user avatar
  • 41.8k
15 votes
1 answer
416 views

What is the smallest cardinality of a self-linked set in a finite cyclic group?

A subset $A$ of a group $G$ is defined to be self-linked if $A\cap gA\ne\emptyset$ for all $g\in G$. This happens if and only if $AA^{-1}=G$. For a finite group $G$ denote by $sl(G)$ the smallest car …
Taras Banakh's user avatar
  • 41.8k
11 votes
1 answer
388 views

Does every finite affine plane have the doubling property?

Definition 1. An affine plane is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ called lines which satisfy the following axioms: Any distinct points $x,y\ …
Taras Banakh's user avatar
  • 41.8k
10 votes
1 answer
350 views

Is the group of translations of an affine plane always commutative?

$\DeclareMathOperator\Dil{Dil}\DeclareMathOperator\Trans{Trans}\DeclareMathOperator\Col{Col}$An affine plane is a set of points $X$ endowed with a family $\mathcal L$ of subsets of $X$, called lines, …
Taras Banakh's user avatar
  • 41.8k
9 votes
0 answers
462 views

Measuring the randomness of texts

The question concerns statistic properties of random words in a finite alphabet $A$. By $A^{<\omega}$ we denote the set of all words in the alphabet $A$, i.e. finite sequences of elements of $A$. Let …
Taras Banakh's user avatar
  • 41.8k
9 votes
1 answer
628 views

A reference to infinite version of the Sunflower Lemma

Please help me to find a proper reference to the following infinite version of the Sunflower Lemma. Lemma. Let $n\in\mathbb N$. Every infinite family of $n$-element sets contains an infinite subfa …
Taras Banakh's user avatar
  • 41.8k
8 votes
1 answer
358 views

A combinatorial property of uncountable groups, II

Problem 1. Is it true that each uncountable group $G$ contains two subsets $A,B\subset G$ such that 1) for any $x,y\in G$ the intersection $xA\cap yB$ is finite and 2) for any function $ …
Taras Banakh's user avatar
  • 41.8k
7 votes
1 answer
325 views

Large gaps in Singer's difference sets

This question is related to the question I asked earlier. For a natural number $n$, a set $D$ of integer numbers is called a $n$-cyclic difference set if each integer number $x\notin n\mathbb Z$ can …
Taras Banakh's user avatar
  • 41.8k
6 votes
0 answers
190 views

The highest degree of a polynomial on a finite group

This question is motivated by the comments and the answer to this MO-question. First let us recall some definitions. A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\m …
Taras Banakh's user avatar
  • 41.8k
6 votes
1 answer
538 views

Does Playfair imply Proclus?

I am interested in the interplay between the Playfair and Proclus Axioms in linear spaces. By a linear space I understand a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of s …
Taras Banakh's user avatar
  • 41.8k
6 votes
1 answer
384 views

What is the cardinality of liners of rank 4? Is it always equal 27?

Definition 1. A binary operation $\cdot:X\times X\to X$, $\cdot:(xy)\mapsto xy$, on a set $X$ will be called a line operation if $$xx=x,\quad xy=yx,\quad (xy)x=y$$ for every $x,y\in X$. Remark 1. Ever …
Taras Banakh's user avatar
  • 41.8k
5 votes
1 answer
357 views

The number of polynomials on a finite group, II

This question is follow up of this MO-post. First let us recall the necessary definitions. A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\mathbb N$ and elements $a_0 …
Taras Banakh's user avatar
  • 41.8k
5 votes
Accepted

Minimal covers in hypergraphs with finite edges

Let $V:=\omega\times\omega$ and $E=\{E_{n,m}:n,m\in\omega\}$ where $$E_{n,m}:=(\{0,\dots,n\}\times\{m\})\cup\{(2n,m+1)\}.$$ It seems that the hypergraph $(V,E)$ has no minimal cover. A simplification …
Taras Banakh's user avatar
  • 41.8k
5 votes
5 answers
562 views

Is every uniform hyperbolic linear space infinite?

I start with definitions. Definition 1. A linear space is a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of subsets of $X$ satisfying three axioms: (L1) for any distinct poi …
Taras Banakh's user avatar
  • 41.8k

15 30 50 per page