Journal of combinatorial theory. Series A

Vol. 160, p. 261-287

DOI: 10.1016/j.jcta.2018.06.015

Date of publication: 2018-11-01

Abstract:

Let p denote the characteristic of , the finite field with q elements. We prove that if q is odd then an arc of size in the projective plane over , which is not contained in a conic, is contained in the intersection of two curves, which do not share a common component, and have degree at most , provided a certain technical condition on t is satisfied. This implies that if q is odd then an arc of size at least is contained in a conic if q is square and an arc of size at least is contained in a conic if q is prime. This is of particular interest in the case that q is an odd square, since then there are examples of arcs, not contained in a conic, of size , and it has long been conjectured that if is an odd square then any larger arc is contained in a conic. These bounds improve on previously known bounds when q is an odd square and for primes less than 1783. The previously known bounds, obtained by Segre [26], Hirschfeld and Korchmáros [17][18], and Voloch [32][33], rely on results on the number of points on algebraic curves over finite fields, in particular the Hasse–Weil theorem and the Stöhr–Voloch theorem, and are based on Segre's idea to associate an algebraic curve in the dual plane containing the tangents to an arc. In this paper we do not rely on such theorems, but use a new approach starting from a scaled coordinate-free version of Segre's lemma of tangents. Arcs in the projective plane over of size q and , q odd, were classified by Segre [25] in 1955. In this article, we complete the classification of arcs of size and . The main theorem also verifies the MDS conjecture for a wider range of dimensions in the case that q is an odd square. The MDS conjecture states that if , a k-dimensional linear MDS code has length at most . Here, we verify the conjecture for , in the case that q is an odd square.]]>

Electronic notes in discrete mathematics

Vol. 68, p. 11-16

DOI: 10.1016/j.endm.2018.06.003

Date of publication: 2018-07-01

Abstract:

Segre’s lemma of tangents dates back to the 1950’s when he used it in the proof of his “arc is a conic” theorem. Since then it has been used as a tool to prove results about various objects including internal nuclei, Kakeya sets, sets with few odd secants and further results on arcs. Here, we survey some of these results and report on how re-formulations of Segre’s lemma of tangents are leading to new results.]]>

Jahresbericht der Deutschen Mathematiker-Vereinigung

Vol. 120, num. 2, p. 147-150

DOI: 10.1365/s13291-017-0170-9

Date of publication: 2018-05-07

European Journal of Mathematics

Vol. 4, num. 1, p. 8-25

DOI: 10.1007/s40879-017-0193-x

Date of publication: 2018-03-01

Abstract:

An arc is a set of vectors of the k-dimensional vector space over the finite field with q elements Fq , in which every subset of size k is a basis of the space, i.e. every k-subset is a set of linearly independent vectors. Given an arc G in a space of odd characteristic, we prove that there is an upper bound on the largest arc containing G. The bound is not an explicit bound but is obtained by computing properties of a matrix constructed from G. In some cases we can also determine the largest arc containing G, or at least determine the hyperplanes which contain exactly k-2 vectors of the large arc. The theorems contained in this article may provide new tools in the computational classification and construction of large arcs.

This is a post-peer-review, pre-copyedit version of an article published in European Journal of Mathematics. The final authenticated version is available online at: https://doi.org/10.1007/s40879-017-0193-x]]>

Abstract:

The project deals with the study of central problems in combinatorics and discrete mathematics. It covers specially three research axes: geometric combinatorics, algebraic combinatorics and probabilistic combinatorics. More precisely, the main objectives are the following: - Freiman conjecture on doubling and volume, its consequences in additive combinatorics and its interplay with the so-called polynomial Freiman-Ruzsa conjecture. - Generalization of graph invariants (chromatic polynomial and symmetric chromatic polynomial), as well as their interactions with matroid theory. - New enumerative and probabilistic results for graph families with topological obstructions, covering bipartite graph classes and regular graphs, among others. - Study of problems in incidence geometry, more particularly in relation to the MDS conjecture and to the Silvester problem for dimension higher than 4. - Study of new logic laws for random discrete structures, including rooted graphs, perfect graphs and permutations. - Analysis of the distance chromatic number of cartesian products of graphs and extensions of the sandwich theorem for non-monotone parameters. The study of these problems involves the development of new geometric, algebraic and probabilistic techniques, as well as the interaction of these areas and the use of new ones, including analytic, topological an number theoretical tools. Building a solid ground for this set of techniques is one of the side objectives of the proposal.]]>

Discrete and computational geometry

Vol. 60, num. 1, p. 1-34

DOI: 10.1007/s00454-017-9935-2

Date of publication: 2017-09-19

Abstract:

Let S be a set of n points in real three-dimensional space, no three collinear and not all co-planar. We prove that if the number of planes incident with exactly three points of S is less than (Formula presented.) for some (Formula presented.) then, for n sufficiently large, all but at most O(K) points of S are contained in the intersection of two quadrics. Furthermore, we prove that there is a constant c such that if the number of planes incident with exactly three points of S is less than (Formula presented.) then, for n sufficiently large, S is either a regular prism, a regular anti-prism, a regular prism with a point removed or a regular anti-prism with a point removed. As a corollary to the main result, we deduce the following theorem. Let S be a set of n points in the real plane. If the number of circles incident with exactly three points of S is less than (Formula presented.) for some (Formula presented.) then, for n sufficiently large, all but at most O(K) points of S are contained in a curve of degree at most four.]]>

Journal of geometry

Vol. 108, num. 2, p. 529-543

DOI: 10.1007/s00022-016-0357-8

Date of publication: 2017-07-01

Abstract:

In this article we consider $S$ to be a set of points in $d$-space with the property that any $d$ points of $S$ span a hyperplane and not all the points of $S$ are contained in a hyperplane. The aim of this article is to introduce the function $e_d(n)$, which denotes the minimal number of hyperplanes meeting $S$ in precisely $d$ points, minimising over all such sets of points $S$ with $|S|=n$.]]>

IEEE transactions on information theory

Vol. 63, num. 6, p. 3658-3662

DOI: 10.1109/TIT.2017.2671344

Date of publication: 2017-06-01

Abstract:

A normal rational curve of the (k-1) -dimensional projective space over Fq is an arc of size q+1 , since any k points of the curve span the whole space. In this paper, we will prove that if q is odd, then a subset of size 3k-6 of a normal rational curve cannot be extended to an arc of size q+2 . In fact, we prove something slightly stronger. Suppose that q is odd and E is a (2k-3) -subset of an arc G of size 3k-6 . If G projects to a subset of a conic from every (k-3) -subset of E , then G cannot be extended to an arc of size q+2 . Stated in terms of error-correcting codes we prove that a k -dimensional linear maximum distance separable code of length 3k-6 over a field Fq of odd characteristic, which can be extended to a Reed–Solomon code of length q+1 , cannot be extended to a linear maximum distance separable code of length q+2 .]]>

The australasian journal of combinatorics

Vol. 65, num. 3, p. 251-260

Date of publication: 2016-06-02

Abstract:

Let $L$ be a set of lines of an affine space over a field and let $S$ be a set of points with the property that every line of $L$ is incident with at least $N$ points of $S$. Let $D$ be the set of directions of the lines of $L$ considered as points of the projective space at infinity. We give a geometric construction of a set of lines $L$, where $D$ contains an $N^{n-1}$ grid and where $S$ has size $2(\frac{1}{2}N)^n$ plus smaller order terms, given a starting configuration in the plane. We provide examples of such starting configurations for the reals and for finite fields. Following Dvir's proof of the finite field Kakeya conjecture and the idea of using multiplicities of Dvir, Kopparty, Saraf and Sudan, we prove a lower bound on the size of $S$ dependent on the ideal generated by the homogeneous polynomials vanishing on $D$. This bound is maximised as $(\frac{1}{2}N)^n$ plus smaller order terms, for $n\geqslant 4$, when $D$ contains the points of a $N^{n-1}$ grid.

Let L be a set of lines of an affine space over a field and let S be a set of points with the property that every line of L is incident with at least N points of S. Let D be the set of directions of the lines of L considered as points of the projective space at infinity. We give a geometric construction of a set of lines L, where D contains an Nn−1 grid and where S has size 2( 1 2N) n plus smaller order terms, given a starting configuration in the plane. We provide examples of such starting configurations for the reals and for finite fields. Following Dvir’s proof of the finite field Kakeya conjecture and the idea of using multiplicities of Dvir, Kopparty, Saraf and Sudan, we prove a lower bound on the size of S dependent on the ideal generated by the homogeneous polynomials vanishing on D. This bound is maximised as ( 1 2N) n plus smaller order terms, for n > 4, when D contains the points of a Nn−1 grid.]]>

Discrete mathematics

Vol. 339, num. 4, p. 1206-1211

DOI: 10.1016/j.disc.2015.11.010

Date of publication: 2016-04-06

Abstract:

We show that the norm graph with n vertices about View the MathML source edges, which contains no copy of the complete bipartite graph Kt,(t-1)!+1, does not contain a copy of Kt+1,(t-1)!-1.]]>

Abstract:

The project addresses a set of problems which are at the forefront of contemporary combinatorics. The main objectives include the following: an extension of Szemerédi type theorems for solutions of linear systems to the sparse setting, which is the arithmetic side of recent developments leading to random versions of Ramsey and density results in combinatorics; the extension to minor closed classes of graphs of the celebrated results on enumeration and parameter analysis of planar graphs, which involve the asymptotic probability distribution of significant parameters and may lead, among other results, to the first known subquadratic algorithm for 4-coloring random planar graphs; the study of a random model for tranversal matroids, which would be a novel contribution to random models for complex combinatorial structures; a longstanding conjecture of Stanley on the feasibility of h-vectors in matroids in terms of pure simplicial complexes, for which only few simple cases have been verified; the use of polynomial methods in the study of the so-called MDS conjecture, proved by one of the members of the team in the prime case, and the improvement of constants involved in Kakeya sets and of Bourgain sets in finite geometries, as well as their extensions to higher dimensions; the extension to the geometric setting of classical results in additive combinatorics, which is connected to the existence of a class of MDS codes in the space of bilinear symmetric forms with respect to a particular metric; the asymptotic analysis of pattern densities in permutations, a novel project strongly connected to extremal graph theory and the theory of graph limits. The treatment of these problems involves a development and interleaving of algebraic, geometric and probabilistic methods in combinatorics. Building a solid ground for this set of techniques is one of the side objectives of the proposal.]]>

Date of publication: 2015

38th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing

Presentation's date: 2014-12

Designs codes and cryptography

Vol. 72, num. 1, p. 177-183

DOI: 10.1007/s10623-013-9863-y

Date of publication: 2014-07-01

Abstract:

A condition on the weight of a codeword of a linear code is obtained using polynomials over the -adic numbers. This condition is obtained by proving a bound on the size of a -fold blocking set of hyperplanes in a finite affine space.]]>

Finding Algebraic Structures in Extremal Combinatorial Configurations

Presentation's date: 2014-05

Finite Geometries

Presentation's date: 2014

SIAM journal on discrete mathematics

Vol. 27, num. 3, p. 1482-1491

DOI: 10.1137/120886960

Date of publication: 2013-08-22

Abstract:

Every biuniform matroid is representable over all sufficiently large fields. But it is not known exactly over which finite fields they are representable, and the existence of efficient methods to find a representation for every given biuniform matroid has not been proved. The interest of these problems is due to their implications to secret sharing. The existence of efficient methods to find representations for all biuniform matroids is proved here for the first time. The previously known efficient constructions apply only to a particular class of biuniform matroids, while the known general constructions were not proved to be efficient. In addition, our constructions provide in many cases representations over smaller finite fields. © 2013, Society for Industrial and Applied Mathematics]]>

SIAM journal on discrete mathematics

Vol. 27, num. 1, p. 575-583

DOI: 10.1137/120880100

Date of publication: 2013-03-21

Abstract:

It is shown that the parameters of a linear code over Fq of length n, dimension k, minimum weight d, and maximum weight m satisfy a certain congruence relation. In the case that q = p is a prime, this leads to the bound m &le (n-d)p-e(p-1), where e {0, 1,.., k-2} is maximal with the property that (n-de) 0 (mod pk-1-e). Thus, if C contains a codeword of weight n, then n-d/(p-1)+d+e. The results obtained for linear codes are translated into corresponding results for (n, t)-arcs and t-fold blocking sets of AG(k-1, q). The bounds obtained in these spaces are better than the known bounds for these geometrical objects for many parameters]]>

Journal of combinatorial designs

Vol. 21, num. 4, p. 163-179

DOI: 10.1002/jcd.21325

Date of publication: 2013-02-01

Congreso de la Real Sociedad Matematica Española

p. 312

Presentation's date: 2013-01-24

Abstract:

A linear code C is a k-dimensional subspace of Fnq , with respect to a fixed basis. Let d 2 N be minimal sich that every non-zero vector of C has at least d non-zero coordinates. With such a code, up to b(d - 1)/2c errors in any codeword can be corrected when sending codewords down a noisy channel. There are many results on error-correcting codes obtained by combinatorial arguments (and these generally apply to non-linear codes as well) such as the sphere packing bound, the Gilbert-Varshamov bound, the Plotkin bound, etc. In this talk I will concentrate on results obtained using linear algebra, for example the MacWilliam’s identities, the MDS conjecture, the maximum weight of a codeword. It is also possible to obtain results for non-linear codes using linear algebra and I will also mention one of these, the Alderson-Gács extension theorem.]]>

Congreso de la Real Sociedad Matematica Española

p. 16

Presentation's date: 2013-01-23

Abstract:

A linear code C is a k-dimensional subspace of Fnq, with respect to a fixed basis. Let d 2 N be minimal sich that every non-zero vector of C has at least d non-zero coordinates. With such a code, up to b(d ¿ 1)=2c errors in any codeword can be corrected when sending codewords down a noisy channel. There are many results on error-correcting codes obtained by combinatorial arguments (and these generally apply to non-linear codes as well) such as the sphere packing bound, the Gilbert-Varshamov bound, the Plotkin bound, etc. In this talk I will concentrate on results obtained using linear algebra, for example the MacWilliam’s identities, the MDS conjecture, the maximum weight of a codeword. It is also possible to obtain results for non-linear codes using linear algebra and I will also mention one of these, the Alderson-Gács extension theorem.]]>

Congreso Bienal de la Real Sociedad Matemática Española

Presentation's date: 2013-01

Date of publication: 2013-01

Designs codes and cryptography

Vol. 65, num. 1, p. 5-14

DOI: 10.1007/s10623-012-9658-6

Date of publication: 2012-10

Abstract:

This article contains a proof of the MDS conjecture for k = 2p - 2. That is, that if S is a set of vectors of F k q in which every subset of S of size k is a basis, where q = p h, p is prime and q is not and k = 2p - 2, then |S| = q + 1. It also contains a short proof of the same fact for k = p, for all q.

The final publication is available at Springer via http://dx.doi.org/10.1007/s10623-012-9658-6]]>

International Combinatorics Conference

Presentation's date: 2012-09

Combinatorics probability and computing

Vol. 21, num. 3, p. 323-329

DOI: 10.1017/S0963548311000423

Date of publication: 2012-05

Journal of the European Mathematical Society

Vol. 14, num. 3, p. 733-748

DOI: 10.4171/JEMS/316

Date of publication: 2012

Date of publication: 2012

Abstract:

The polynomial method refers to the application of polynomials to combinatorial problems. The method is particularly effective for Galois geometries and a number of problems and conjectures have been solved using the polynomial method. In many cases the polynomial approach is the only method which we know of that works. In this article, the various polynomial techniques that have been applied to Galois geometries are detailed and, to demonstrate how to apply these techniques, some of the problems referred to above are resolved.]]>

Graphs and Algebraic Combinatorics

Presentation's date: 2011-08

Workshop on Combinatorial Designs

Presentation's date: 2011-05

Workshop on Combinatorial Designs

Presentation's date: 2011-05

Algebraic Graph Theory

Presentation's date: 2011-03

Designs codes and cryptography

Vol. 56, num. 2-3, p. 87-88

DOI: 10.1007/s10623-010-9409-5

Date of publication: 2010-08

Designs codes and cryptography

Vol. 53, num. 2, p. 119-136

DOI: 10.1007/s10623-009-9298-7

Date of publication: 2009-11

European journal of combinatorics

Vol. 30, num. 7, p. 1575-1584

DOI: 10.1016/j.ejc.2009.03.009

Date of publication: 2009-10

Combinatorica

Vol. 29, p. 511-522

DOI: 10.1007/s00493-009-2509-z

Date of publication: 2009

Abstract:

In this article we present a punctured version of Alon's Nullstellensatz which states that if $f$ vanishes at nearly all, but not all, of the common zeros of some polynomials $g_1(X_1),\ldots,g_n(X_n)$ then every $I$-residue of $f$, where the ideal $I=\langle g_1,\ldots,g_n\rangle$, has a large degree. Furthermore, we extend Alon's Nullstellensatz to functions which have multiple zeros at the common zeros of $g_1,g_2,\ldots,g_n$ and prove a punctured version of this generalised version. Some applications of these punctured Nullstellens\"atze to projective and affine geometries over an arbitrary field are considered which, in the case that the field is finite, will lead to some bounds related to linear codes containing the all one vector.]]>

Jornadas de Matemática Discreta y Algorítmica

p. 117-123

Presentation's date: 2008-07-21

Designs codes and cryptography

Vol. 47, num. 1-3, p. 159-164

DOI: 10.1007/s10623-007-9108-z

Date of publication: 2008-06

Journal of combinatorial theory. Series A

Vol. 115, num. 3, p. 505-516

DOI: 10.1016/j.jcta.2007.08.001

Date of publication: 2008-04

Algebraic Geometry, Coding and Computing

Presentation's date: 2007-10-08

EUROCOMB 2007

Presentation's date: 2007-09-11

Designs codes and cryptography

Vol. 44, num. 1-3, p. 63-67

DOI: 10.1007/s10623-007-9061-x

Date of publication: 2007-09

Electronic notes in discrete mathematics

Vol. 29, num. 1, p. 185-188

DOI: 10.1016/j.endm.2007.07.032

Date of publication: 2007-08

British Combinatorial Conference

Presentation's date: 2007-07-09

Discrete mathematics

Vol. 307, num. 13, p. 1600-1608

DOI: 10.1016/j.disc.2006.09.011

Date of publication: 2007-06

Advances in mathematics

Vol. 211, num. 1, p. 94-104

DOI: 10.1016/j.aim.2006.07.011

Date of publication: 2007-05