OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]

fbtwitterlinkedinvimeoflicker grey 14rssslideshare1


Extremal Combinatorics
EC | FP7 | SP2 | ERC
Contract (GA) number
Start Date
End Date
Open Access mandate
Special Clause 39
More information
Detailed project information (CORDIS)


  • Implicit representation conjecture for semi-algebraic graphs

    Fitch, Matthew (2018)
    Projects: EC | EC (306493)
    The implicit representation conjecture concerns hereditary families of graphs. Given a graph in such a family, we want to assign some string of bits to each vertex in such a way that we can recover the information about whether 2 vertices are connected or not using only the 2 strings of bits associated with those two vertices. We then want to minimise the length of this string. The conjecture states that if the family is hereditary and small enough (it only has $2^{O(n\ln(n))}$ graphs of size...

    Generalized solution for the Herman Protocol Conjecture

    Csóka, Endre; Mészáros, Szabolcs (2015)
    Projects: EC | EC (306493)
    We have a cycle of $N$ nodes and there is a token on an odd number of nodes. At each step, each token independently moves to its clockwise neighbor or stays at its position with probability $\frac{1}{2}$. If two tokens arrive to the same node, then we remove both of them. The process ends when only one token remains. The question is that for a fixed $N$, which is the initial configuration that maximizes the expected number of steps $E(T)$. The Herman Protocol Conjecture says that the $3$-toke...

    The codegree threshold for 3-graphs with independent neighborhoods

    Falgas-Ravry, Victor; Marchant, Edward; Pikhurko, Oleg; Vaughan, Emil R. (2015)
    Projects: EC | EC (306493)
    Given a family of 3-graphs F, we define its codegree threshold coex(n, F) to be the largest number d = d(n) such that there exists an n-vertex 3-graph in which every pair of vertices is contained in at least d 3-edges but which contains no member of F as a subgraph. Let F-3,F-2 be the 3-graph on {a, b, c, d, e} with 3-edges abc, abd, abe, and cde. In this paper, we give two proofs that coex(n, {F-3,F-2}) = - (1/3 + o(1))n, the first by a direct combinatorial argument and the second via a flag...

    The Erd\H{o}s-Rothschild problem on edge-colourings with forbidden monochromatic cliques

    Pikhurko, Oleg; Staden, Katherine; Yilma, Zelealem B. (2016)
    Projects: EC | EC (306493)
    Let $\mathbf{k} := (k_1,\dots,k_s)$ be a sequence of natural numbers. For a graph $G$, let $F(G;\mathbf{k})$ denote the number of colourings of the edges of $G$ with colours $1,\dots,s$ such that, for every $c \in \{1,\dots,s\}$, the edges of colour $c$ contain no clique of order $k_c$. Write $F(n;\mathbf{k})$ to denote the maximum of $F(G;\mathbf{k})$ over all graphs $G$ on $n$ vertices. This problem was first considered by Erd\H{o}s and Rothschild in 1974, but it has been solved only for a ...

    Measurable equidecompositions via combinatorics and group theory

    Grabowski, Łukasz; Máthé, András; Pikhurko, Oleg (2014)
    Projects: EC | EC (306493)
    We give a sketch of proof that any two (Lebesgue) measurable subsets of the unit sphere in $R^n$, for $n\ge 3$, with non-empty interiors and of the same measure are equidecomposable using pieces that are measurable.

    Kruskal-Katona type Problem

    Fitch, Matthew (2018)
    Projects: EC | EC (306493)
    The Kruskal Katona theorem was proved in the 1960s. In the theorem, we are given an integer $r$ and families of sets $\mathcal{A}\subset \mathbb{N}^{(r)}$ and $\mathcal{B}\subset\mathbb{N}^{(r-1)}$ such that for every $A\in\mathcal{A}$, every subset of $A$ of size $r-1$ is in $\mathcal{B}$. We are interested in finding the mimimum size of $b=|\mathcal{B}|$ given fixed values of $r$ and $a=|\mathcal{A}|$. The Kruskal Katona theorem states that this mimimum occurs when both $\mathcal{A}$ and $\...

    Asymptotic structure of graphs with the minimum number of triangles\ud

    Pikhurko, Oleg; Razborov, Alexander (2016)
    Projects: EC | EC (306493)
    We consider the problem of minimizing the number of triangles in a graph of given order and size, and describe the asymptotic structure of extremal graphs. This is achieved by characterizing the set of flag algebra homomorphisms that minimize the triangle density.

    How unproportional must a graph be?

    Naves, Humberto; Pikhurko, Oleg; Scott, Alex (2014)
    Projects: EC | EC (306493)
    Let $u_k(G,p)$ be the maximum over all $k$-vertex graphs $F$ of by how much the number of induced copies of $F$ in $G$ differs from its expectation in the binomial random graph with the same number of vertices as $G$ and with edge probability $p$. This may be viewed as a measure of how close $G$ is to being $p$-quasirandom. For a positive integer $n$ and $0

    Rational exponents for hypergraph Turan problems

    Fitch, Matthew (2016)
    Projects: EC | EC (306493)
    Given a family of $k$-hypergraphs $\mathcal{F}$, $ex(n,\mathcal{F})$ is the maximum number of edges a $k$-hypergraph can have, knowing that said hypergraph has $n$ vertices but contains no copy of any hypergraph from $\mathcal{F}$ as a subgraph. We prove that for every rational $r$ between $0$ and $k-1$, there exists some finite family $\mathcal{F}$ of $k$-hypergraphs for which $ex(n,\mathcal{F})=\Theta(n^{k-r})$.

    Strong Forms of Stability from Flag Algebra Calculations

    Pikhurko, Oleg; Sliacan, Jakub; Tyros, Konstantinos (2017)
    Projects: EC | EC (306493)
    Given a hereditary family $\mathcal{G}$ of admissible graphs and a function $\lambda(G)$ that linearly depends on the statistics of order-$\kappa$ subgraphs in a graph $G$, we consider the extremal problem of determining $\lambda(n,\mathcal{G})$, the maximum of $\lambda(G)$ over all admissible graphs $G$ of order $n$. We call the problem perfectly $B$-stable for a graph $B$ if there is a constant $C$ such that every admissible graph $G$ of order $n\ge C$ can be made into a blow-up of $B$ by c...
  • No project research data found
  • Scientific Results

    Chart is loading... It may take a bit of time. Please be patient and don't reload the page.


    Chart is loading... It may take a bit of time. Please be patient and don't reload the page.

    Publications in Repositories

    Chart is loading... It may take a bit of time. Please be patient and don't reload the page.

Share - Bookmark

App Box

Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok