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

Extremal problems in hypergraph matchings

Title
Extremal problems in hypergraph matchings
Funding
ARC | Discovery Projects
Contract (GA) number
DP120100197
Start Date
2012/01/01
End Date
2014/12/31
Open Access mandate
no
Organizations
-
More information
http://purl.org/au-research/grants/arc/DP120100197

 

  • Empty pentagons in point sets with collinearities

    Barát, János; Dujmović, Vida; Joret, Gwenaël; Payne, Michael S.; Scharf, Ludmila; Schymura, Daria; Valtr, Pavel; Wood, David R. (2012)
    Projects: ARC | Extremal problems in hypergraph matchings (DP120100197)
    An empty pentagon in a point set P in the plane is a set of five points in P in strictly convex position with no other point of P in their convex hull. We prove that every finite set of at least 328k^2 points in the plane contains an empty pentagon or k collinear points. This is optimal up to a constant factor since the (k-1)x(k-1) grid contains no empty pentagon and no k collinear points. The previous best known bound was doubly exponential.

    Multipartite hypergraphs achieving equality in Ryser's conjecture

    Aharoni, Ron; Barát, János; Wanless, Ian M. (2014)
    Projects: ARC | Extremal problems in hypergraph matchings (DP120100197)
    A famous conjecture of Ryser is that in an $r$-partite hypergraph the covering number is at most $r-1$ times the matching number. If true, this is known to be sharp for $r$ for which there exists a projective plane of order $r-1$. We show that the conjecture, if true, is also sharp for the smallest previously open value, namely $r=7$. For $r\in\{6,7\}$, we find the minimal number $f(r)$ of edges in an intersecting $r$-partite hypergraph that has covering number at least $r-1$. We find that $f...

    On a Generalization of the Ryser-Brualdi-Stein Conjecture

    Aharoni, Ron; Charbit, Pierre; Howard, David (2013)
    Projects: ARC | Extremal problems in hypergraph matchings (DP120100197)
    A rainbow matching for (not necessarily distinct) sets F_1,...,F_k of hypergraph edges is a matching consisting of k edges, one from each F_i. The aim of the paper is twofold - to put order in the multitude of conjectures that relate to this concept (some of them first presented here), and to present some partial results on one of these conjectures, that seems central among them.

    On Ryser's Conjecture for Linear Intersecting Multipartite Hypergraphs

    Francetić, Nevena; Herke, Sarada; McKay, Brendan D.; Wanless, Ian M. (2015)
    Projects: ARC | Extremal problems in hypergraph matchings (DP120100197)
    Ryser conjectured that $\tau\le(r-1)\nu$ for $r$-partite hypergraphs, where $\tau$ is the covering number and $\nu$ is the matching number. We prove this conjecture for $r\le9$ in the special case of linear intersecting hypergraphs, in other words where every pair of lines meets in exactly one vertex. Aharoni formulated a stronger version of Ryser's conjecture which specified that each $r$-partite hypergraph should have a cover of size $(r-1)\nu$ of a particular form. We provide a counterexam...

    On the chromatic number of a random hypergraph

    We consider the problem of $k$-colouring a random $r$-uniform hypergraph with $n$ vertices and $cn$ edges, where $k$, $r$, $c$ remain constant as $n$ tends to infinity. Achlioptas and Naor showed that the chromatic number of a random graph in this setting, the case $r=2$, must have one of two easily computable values as $n$ tends to infinity. We give a complete generalisation of this result to random uniform hypergraphs.

    On the Existence of Retransmission Permutation Arrays

    We investigate retransmission permutation arrays (RPAs) that are motivated by applications in overlapping channel transmissions. An RPA is an $n\times n$ array in which each row is a permutation of ${1, ..., n}$, and for $1\leq i\leq n$, all $n$ symbols occur in each $i\times\lceil\frac{n}{i}\rceil$ rectangle in specified corners of the array. The array has types 1, 2, 3 and 4 if the stated property holds in the top left, top right, bottom left and bottom right corners, respectively. It is ca...
  • 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