EC
 Title
 Extremal Combinatorics
 Funding
 EC  FP7  SP2  ERC
 Call
 ERC2012StG_20111012
 Contract (GA) number
 306493
 Start Date
 2012/10/01
 End Date
 2018/07/31
 Open Access mandate
 no
 Special Clause 39
 no
 Organizations
 WARWICK
 More information
 Detailed project information (CORDIS)

Implicit representation conjecture for semialgebraic graphs
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
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 3graphs with independent neighborhoods
FalgasRavry, Victor; Marchant, Edward; Pikhurko, Oleg; Vaughan, Emil R. (2015)
Projects: EC  EC (306493)Given a family of 3graphs F, we define its codegree threshold coex(n, F) to be the largest number d = d(n) such that there exists an nvertex 3graph in which every pair of vertices is contained in at least d 3edges but which contains no member of F as a subgraph. Let F3,F2 be the 3graph on {a, b, c, d, e} with 3edges abc, abd, abe, and cde. In this paper, we give two proofs that coex(n, {F3,F2}) =  (1/3 + o(1))n, the first by a direct combinatorial argument and the second via a flag...The Erd\H{o}sRothschild problem on edgecolourings with forbidden monochromatic cliques
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
We give a sketch of proof that any two (Lebesgue) measurable subsets of the unit sphere in $R^n$, for $n\ge 3$, with nonempty interiors and of the same measure are equidecomposable using pieces that are measurable.KruskalKatona type Problem
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}^{(r1)}$ such that for every $A\in\mathcal{A}$, every subset of $A$ of size $r1$ 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
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?
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 $0Rational exponents for hypergraph Turan problems
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 $k1$, there exists some finite family $\mathcal{F}$ of $k$hypergraphs for which $ex(n,\mathcal{F})=\Theta(n^{kr})$.Strong Forms of Stability from Flag Algebra Calculations
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 blowup 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.PUBLICATIONS BY ACCESS MODE
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.