LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1

EC

Title
Extremal Combinatorics
Funding
EC | FP7 | SP2 | ERC
Call
ERC-2012-StG_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)

 

  • 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 ...

    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...

    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.

    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...

    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...

    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 Erd\H{o}s-R\'enyi 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

    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.

    The codegree threshold for 3-graphs with independent neighbourhoods

    Falgas-Ravry, Victor; Marchant, Edward; Pikhurko, Oleg; Vaughan, Emil (2013)
    Projects: EC | EC (306493)
    Given a family of 3-graphs $F$, we define its codegree threshold $\mathrm{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,2}$ be the 3-graph on $\{a,b,c,d,e\}$ with 3-edges $\{abc,abd,abe,cde\}$. In this paper, we give two proofs that $\mathrm{coex}(n, F_{3,2})= n/3 +o(n)$, the first by a direct combinatorial argument and...

    Independent sets in hypergraphs and Ramsey properties of graphs and the integers

    Hancock, Robert; Staden, Katherine; Treglown, Andrew (2017)
    Projects: EC | EC (306493)
    Many important problems in combinatorics and other related areas can be phrased in the language of independent sets in hypergraphs. Recently Balogh, Morris and Samotij, and independently Saxton and Thomason developed very general container theorems for independent sets in hypergraphs; both of which have seen numerous applications to a wide range of problems. In this paper we use the container method to prove results that correspond to problems concerning tuples of disjoint independent sets in...

    The maximal length of a gap between r-graph Tur\'an densities

    Pikhurko, Oleg (2015)
    Projects: EC | EC (306493)
    The Tur\'an density $\pi(\cal F)$ of a family $\cal F$ of $r$-graphs is the limit as $n\to\infty$ of the maximum edge density of an $\cal F$-free $r$-graph on $n$ vertices. Erdos [Israel J. Math 2 (1964) 183--190] proved that no Tur\'an density can lie in the open interval $(0,r!/r^r)$. Here we show that any other open subinterval of $[0,1]$ avoiding Tur\'an densities has strictly smaller length. In particular, this implies a conjecture of Grosu [E-print arXiv:1403.4653v1, 2014].
  • 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.

Share - Bookmark

App Box